| 基于散列技术的快速子串归并算法 |
| |
| 引用本文： | 吕学强,张乐,黄志丹,胡俊峰.基于散列技术的快速子串归并算法[J].复旦学报(自然科学版),2004,43(5):948-951,955. |
| |
| 作者姓名： | 吕学强 张乐 黄志丹 胡俊峰 |
| |
| 作者单位： | 北京大学,计算语言学研究所,北京,100871;东北大学,计算机软件与理论研究所,沈阳,110004;沈阳师范大学,计算中心,沈阳,110034 |
| |
| 基金项目： | 国家"八六三"高技术研究发展计划项目资助(2001AA114019,2001AA114210,2002AA117010-08),国家自然科学基金资助项目(60083006),国家"九七三"重点基础研究发展规划项目(G19980305011) |
| |
| 摘 要： | 用统计方法研究东西方语言的多词单元问题和东方语言的未登录词问题时需要删除同频子串(子串归并)．传统的子串归并算法时间复杂度为O(n^2),在大规模语料库的处理中效率低下．提出一种基于散列技术的时间复杂度为O(n^2)的子串归并算法,并用数学方法证明其与O(n^2)复杂度的算法等价,即输入相同时输出也相同．不同规模语料上的实验结果表明新算法能够大大缩短子串归并所需时间,适用于大规模语料库的处理．
|
| 关 键 词： | 大规模语料库 文本挖掘 多词单元 未登录词 串频统计 |
| 文章编号： | 0427-7104(2004)05-0948-04 |
Fast Hash Algorithms on Statistical Substring Reduction |
| |
| Abstract: | Statistical processing of multi-word units in occidental or oriental languages and unknown words in oriental languages requires substring reduction. The time complexity of traditional substring reduction algorithms is O(n~2), which is ineffective for large-scale corpora. It proposes a hash algorithm with time complexity O(n), and mathematically proves the equivalence to the O(n~2) one. That is, with the same inputs, the outputs are the same. The experiments on different scale corpora show that the new algorithm can dramatically shorten the processing time than the traditional one. So it is therefore an appropriate choice for large scale corpus processing. |
| |
| Keywords: | large scale corpus text mining multi-word unit unknown word statistical string frequency |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
