汉字／字符串编辑距离和编辑路径的有效求解技术

本文提出了一种有效的编辑距离和编辑路径求解技术，该技术不但适合于单字符字符串而且也适合于双字节汉字串的编辑距离和编辑路径的计算。它首先通过一有效的字符串相似匹配算法计算出串编辑距离，而后通过简单的二进制字位运算正确计算出串（最短）编辑路径。文章也给出了本技术的完整实现算法并分析了算法的复杂性。

AN EFFICIENT APPROACH TO COMPUTING CHAR/CHINESE CHARACTER STRINGS' EDIT DISTANCES AND EDIT PATHS

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.