基于编辑距离的字符串相似度算法研究  

Research on string similar degree algorithm based on Levenshtein distance

作　　者：张胜楠 Zhang Shengnan(Information Engineering College of Hubei Light Industry Technology Institute,Wuhan 430000,China)

机构地区：[1]湖北轻工职业技术学院信息工程学院,武汉430000

出　　处：《现代计算机》2023年第14期23-26,32,共5页Modern Computer

摘　　要：基于编辑距离(LD)求解字符串相似度的算法非常经典,但其在普适性和精确性方面略有不足,基于最长公共子串(LCCS)和最长公共子序列(LCS)对其改进,使计算结果更有区分性、普适性和精确性。另外在计算相似度时,对LD和LCS的求解算法从数据结构的角度进行了优化,在数量级上降低了算法空间复杂度。对实验结果进行了对比分析,证明其可行性和正确性。The algorithm for solving string similarity based on Levenshtein Distance is very classic,but it has some shortcomings in terms of universality and accuracy.It is improved based on Longest Common Substring(LCCS)and Longest Common Subsequence(LCS)to make the calculation results more discriminative,universal,and accurate.In addition,when calculating similarity,the algorithm for solving LD and LCS is optimized from the perspective of data structure,reducing the spatial complexity of the algorithm in an order of magnitude.The experimental results were compared and analyzed to prove their feasibility and correctness.

关 键 词：相似度计算 编辑距离 最长公共子序列 最长公共子串 

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