摘要
用统计方法研究东西方语言的多词单元问题和东方语言的未登录词问题时需要删除同频子串(子串归并).传统的子串归并算法时间复杂度为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.
出处
《复旦学报（自然科学版）》
CAS
CSCD
北大核心
2004年第5期948-951,955,共5页
Journal of Fudan University：Natural Science
基金
国家"八六三"高技术研究发展计划项目资助(2001AA114019
2001AA114210
2002AA117010-08)
国家自然科学基金资助项目(60083006)
国家"九七三"重点基础研究发展规划项目(G19980305011)
