一种在汉语文本中抽取重复字串的快速算法

摘要

词典未登录词的处理是自然语言处理不可或缺的研究方向.抽取文本中重复出现的字串是抽取未登录词最为直接简便的方法.以往算法运行速度较慢,无法满足海量文本快速处理的要求.遵循"左结合优先"和"最长匹配"原则,本文提出一种快速算法:位置记忆跳跃匹配.该方法最差情况下时间复杂度为o(t2),其中t为重复字串的重复次数.比较实验表明,本方法速度提高明显,数据结构简单,处理过程一次扫描完成.