我需要知道使模糊算法在这3种情况下彼此不同的标准:
Levenshtein距离算法
Levenshtein distance是用于度量两个序列之间差异的字符串度量。非正式地说,两个单词之间的Levenshtein距离是将一个单词转换为另一个单词所需的最小单字符编辑次数(即插入、删除或替换)。
Damerau-Levenshtein距离
Damerau-Levenshtein距离是两个字符串(即有限符号序列)之间的距离(字符串度量),通过对将一个字符串转换为另一个字符串所需的最小操作次数进行计数而给出,其中操作被定义为单个字符的插入、删除或替换,或者两个相邻字符的转置。
由Wu和Manber修改的位图算法
位图算法是一种近似字符串匹配算法。该算法告诉给定文本是否包含与给定模式“近似相等”的子串,其中近似相等是根据Levenshtein距离定义的-如果子串和模式彼此在给定距离k内,则算法认为它们相等。
我的文档是一张表,上面有公司的名字,有些公司因为拼写错误而被重复了两次或三次。在这种情况下,如何通过匹配来对公司进行分组?选择哪种算法?为什么?在这个文件中,我有100k行,而且还在增长。
发布于 2019-05-30 22:32:14
如果你使用的是谷歌工作表,试着使用Flookup。您说您的列表有超过100K的行,因此根据Google的(定时)执行限制,这可能会被证明是一个挑战,但我仍然鼓励您尝试一下。您可能会感兴趣的一个函数是:
FLOOKUP(lookupValue, tableArray, lookupCol, indexNum, [threshold], [rank])
完整披露:我为谷歌工作表创建了Flookup
发布于 2019-05-20 04:15:56
如果你想对公司进行分组,你可以使用位置敏感的散列或聚类方法,比如K-medoids聚类,例如,Levenshtein编辑距离作为度量。或者,您可以使用SymSpell。
Levenshtein-和Damerau-Levenshtein距离都是字符串相似性的良好指标,但请确保使用快速实现。在Github上有太多流行且极其缓慢的实现。我所知道的最好的是PolyLeven或editdistance。
https://stackoverflow.com/questions/56164101
复制相似问题