字符串匹配是计算机科学中研究最经典的问题之一。早期主要是对字符串的精确匹配进行研究,而且大多数研究都是针对DNA片段等小型字符集,或针对英文等中等大小字符集,而对于汉字乃至亚洲语言等大型字符集的研究却不多。然而随着新问题的不断提出,人们发现在实际应用中有时更需要近似字符串匹配。并且字符串近似匹配已经被应用到众多领域之中,比如拼写检查、模式识别、Web搜索、OCR纠错、DNA序列匹配等。本文针对中文字符串的近似匹配算法进行研究,论文的主要成果如下:(1)提出了融合多元信息的编辑距离的计算方法。传统编辑距离算法中只是单纯考虑了增加、删除、替换一个字符的代价,并没有区分各字符的重要程度对字符串相似度的影响,也没有考虑汉字的字形信息。本文在传统编辑距离算法的基础上,融合了汉字的字频信息和字形信息。对于固定库中的字符串,字符出现的频率是一定的。本文将低频字符定义为重要字符,对于重要的字符降低其匹配代价,提高其匹配的概率。汉字字符与英文字符不同,具有在字形上特有的信息,包括五笔、结构、四角、笔画的特征,分别表示了汉字在部件、结构、形状、复杂度上的差别。对于两个字形差异较大的字符,加大其匹配的代价,从而降低其匹配的概率。本文提出的融合多种信息的编辑距离方法,不仅考虑了汉字的字频的信息,而且充分利用了汉字的字形上的差异性。实验结果表明,融合多种信息的编辑距离方法显著提高了字符串近似匹配的精度。(2)提出了融合多元信息的编辑距离与Trie树相结合的方法。对于大量字符串的近似匹配,如果每一条都用编辑距离的方法进行比较,会耗费大量的时间。本文采用融合多元信息的编辑距离与Trie树相结合的方式,结合编辑距离动态规划的思想和Trie树共享前缀的特点,对目标字符串进行剪枝,以减少字符串匹配的次数,从而降低字符串近似匹配的时间。实验结果表明,融合多元信息的编辑距离与Trie树结合的方式在保证准确率不变的情况下,大大减少了字符串近似匹配的时间。