莱文斯坦距离在相似短信管控中的应用与优化  

Application and Optimization of Levenshtein Distance in Similar Control of Short Message

作　　者：黄书涵 HUANG Shuhan(China Telecom Fufu Information Technology Co.,Ltd.,Fuzhou,China,350003)

机构地区：[1]中电福富信息科技有限公司,福州350003

出　　处：《福建电脑》2020年第10期5-8,共4页Journal of Fujian Computer

摘　　要：本文设计了一套实时短信过滤系统中以输入短信与样本短信之间的相似度为依据进行短信过滤的方案。它基于Levenshtein距离动态规划求解的算法计算短信文本的相似度。针对该算法的缺陷,本文还提出了一种预测结果提前退出计算的优化机制。在真实数据测试中优化后的算法相比优化前速度有了大幅度提高,有效地满足了该业务流程性能的要求。This paper designs a scheme of SMS filtering.The scheme is based on the similarity between input SMS and sample SMS in the real-time SMS filtering system.It uses Levenshtein Distance dynamic programming algorithm to calculate the similarity of SMS text.The defect of the algorithm is overcome by using the optimization mechanism that the prediction results exit the calculation ahead of time.Compared with before optimization,the speed of the improved algorithm is greatly improved.

关 键 词：Levenshtein 编辑距离 动态规划 相似度 短信过滤 

分 类 号：TP311.52[自动化与计算机技术—计算机软件与理论]