基于散列技术的快速子串归并算法  

Fast Hash Algorithms on Statistical Substring Reduction

作　　者：吕学强[1] 张乐[2] 黄志丹[3] 胡俊峰[1] 

机构地区：[1]北京大学计算语言学研究所,北京100871 [2]东北大学计算机软件与理论研究所,沈阳110004 [3]沈阳师范大学计算中心,沈阳110034

出　　处：《复旦学报（自然科学版）》2004年第5期948-951,955,共5页Journal of Fudan University：Natural Science

基　　金：国家"八六三"高技术研究发展计划项目资助(2001AA114019;2001AA114210;2002AA117010-08);国家自然科学基金资助项目(60083006);国家"九七三"重点基础研究发展规划项目(G19980305011)

摘　　要：用统计方法研究东西方语言的多词单元问题和东方语言的未登录词问题时需要删除同频子串(子串归并).传统的子串归并算法时间复杂度为O(n2),在大规模语料库的处理中效率低下.提出一种基于散列技术的时间复杂度为O(n)的子串归并算法,并用数学方法证明其与O(n2)复杂度的算法等价,即输入相同时输出也相同.不同规模语料上的实验结果表明新算法能够大大缩短子串归并所需时间,适用于大规模语料库的处理.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.

关 键 词：归并 散列 算法 时间复杂度 大规模 删除 语料库 法能 处理 东西方 

分 类 号：N941.1[自然科学总论—系统科学] TP391[自动化与计算机技术—计算机应用技术]