一种基于编辑距离的中文字符串近似匹配算法  

A Chinese String Matching Algorithm Based on Edit Distance

作　　者：王昭 薛晨浩 裴卓雄 Wang Zhao;Xue Chenhao;Pei Zhuoxiong(Shanxi Branch of National Computer Network Emergency Response Technical Team/Coordination Center of China,Taiyuan Shanxi 030012,China)

机构地区：[1]国家计算机网络应急技术处理协调中心山西分中心,山西太原030012

出　　处：《山西电子技术》2024年第4期43-45,共3页Shanxi Electronic Technology

摘　　要：字符串近似匹配是模式匹配领域中的一个重要研究方向。在中文字符串近似匹配中,基于字符操作的编辑距离不能准确衡量由复制、剪贴等操作导致的相似关系。基于此,在传统编辑距离的基础上引入了字符串的平移和复制操作,给出了一种在贪心算法基础上进行动态规划搜索的计算方法,能有效计算改进的编辑距离,在真实数据集上的实验结果和分析显示了对文本检索的有效性。Approximate string matching is an important research direction in the field of pattern matching.In Chinese string approximate matching,the edit distance based on character operation cannot accurately measure the similarity relationship caused by string copy and cut operations.This paper introduces the shift and copy operations of strings on the basis of the traditional edit distance,and presents a calculation method for dynamic programming search based on the greedy algorithm,which can effectively calculate the improved edit distance.Experimental results and analysis show the effectiveness for text retrieval.

关 键 词：字符串匹配 近似匹配 动态规划算法 编辑距离 

分 类 号：TP391.1[自动化与计算机技术—计算机应用技术]