摘要
本文提出一种有效的编辑距离和编辑路径求解技术，该技术不但适合于单字节字符串而且也适合于双字节汉字串的编辑距离和编辑路径的计算。它首先通过一有效的字符串相似匹配算法计算出串编辑距离，而后仅通过简单的二进制字位运算正确计算出串（最短）编辑路径。文章也给出了本技术的完整实现算法并分析了算法的复杂性。
This paper proposes an efficient approach to computing edit distances and edit paths for both char (one byte) strings and Chinese character (two bytes) strings, which, at first, computes edit distances by using an efficient string approximate matching algorithm, and then computes correctly (the shortest) edit paths by using only simple binary bit operations. The whole implementation algorithm and the complexity analysis of the algorithm are also provided.
出处
《计算机研究与发展》
EI
CSCD
北大核心
1996年第8期574-580,共7页
Journal of Computer Research and Development
关键词
字符串
汉字串
编辑距离
编辑路径
汉字信息处理
Char string, Chinese character string, edit distance, edit path, approximatematching.
