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

【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.更多还原