| 基于逐层剪枝的中文高频重复模式快速提取算法 |
| |
| 引用本文： | 张海军,刘战东,木妮娜.基于逐层剪枝的中文高频重复模式快速提取算法[J].计算机科学,2014,41(5):270-274. |
| |
| 作者姓名： | 张海军 刘战东 木妮娜 |
| |
| 作者单位： | 新疆师范大学初等教育学院 乌鲁木齐830054;新疆师范大学计算机科学技术学院 乌鲁木齐830054;新疆师范大学计算机科学技术学院 乌鲁木齐830054 |
| |
| 基金项目： | 本文受国家自然科学基金项目(61163045,4),新疆维吾尔自治区高校科研基金(XJEDU2012S29),新疆师范大学重点学科招标课题(12XSXZ0601)资助 |
| |
| 摘 要： | 为了从大规模语料中快速提取高频重复模式,以递增n-gram模型为基础,使用散列数据结构提取重复串,并提出了一种基于低频字符和层次剪枝的逐层剪枝算法,用于过滤低频垃圾字串,减少I/O读写次数。在此基础上,应用改进的字串排序算法,使字符串排序可在O(n)时间内完成,从而有效提高重复模式的提取效率。实验表明,该算法是一种有效的重复模式提取算法,其I/O读写次数同语料规模呈线性关系,远小于使用首字符进行语料划分的方法,能快速有效地从规模远大于内存容量的文本语料中提取重复模式,特别适合于大规模语料的高频重复模式提取,对以重复模式为基础的新词识别、术语抽取等具有重要的支撑作用。
|
| 关 键 词： | 重复串 散列表 低频字串 逐层剪枝 新词识别 |
| 收稿时间： | 2013/7/18 0:00:00 |
| 修稿时间： | 2013/10/27 0:00:00 |
Rapid Algorithm of Chinese High-frequency Repeat Extraction Based on Hierarchical Pruning |
| |
| ZHANG Hai-jun,LIU Zhan-dong and Munina.Rapid Algorithm of Chinese High-frequency Repeat Extraction Based on Hierarchical Pruning[J].Computer Science,2014,41(5):270-274. |
| |
| Authors: | ZHANG Hai-jun LIU Zhan-dong and Munina |
| |
| Affiliation: | School of Elementary Education,Xinjiang Normal University,Urumqi 830054,China;School of Computer Science and Technology,Xinjiang Normal University,Urumqi 830054,China;School of Computer Science and Technology,Xinjiang Normal University,Urumqi 830054,China |
| |
| Abstract: | |
| |
| Keywords: | Repeat Hash table Low-frequency strings Hierarchical pruning New words identification |
| 本文献已被 CNKI 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
|
