用Python求字符串相似度匹配实战
最近遇到这样一个实际问题，有一份纸质清单A（打印体文字，但是有磨损），同时有一份电子表格B（与A非同一版本），且A和B反映的内容本质上是一致的，只是因为一些因素，(1)导致同一个事物所呈现的文字不一样，比如“电脑”和计算机大概率是指同一个东西。(2)在同一个清单中会有重复出现的值，这就导致用Excel的Vlookup不好使。要求是对二者进行匹配，对他们做一个检验，找出二者能匹配的数量。
为了清楚表达，我模拟还原了一下这个实际情况。
一、实际问题模拟
A是一份电子水果清单，为此我专门搜了水果大全......
同时为了模拟实际情况，我手抄了一份，以此作为磨损的数据。
手抄样式
QQ文字提取：
取出纯汉字（好吧，我有点感叹这个识别准确率！）：
最后问题转化成了两个电子版清单之间的匹配，更进一步说也就是两个数组的匹配，落实到单个水果上，就是两个水果汉字的比较，比如“葡萄”和“葡蔺”这两个字符串的比较和匹配。如下：
二、寻找算法
最近看了些关于数据分析的书，在讲KNN最邻近算法时候，有一个关键的概念--相似度的度量方法，比如有欧式距离（“直线距离”），曼哈顿距离（两点在坐标系上的相对距离之和），余弦相似度（两点夹角余弦值），杰卡德相似系数（“交集”元素数量占“并集”元素数量的比例）。
本次就是“借鉴”杰卡德相似系数来解决问题，这个系数可以举个例子来说明，比如两个人在某宝上购物，甲买了10件，乙买了15件，而他们购买的相同商品有7件，那么他们的购物的相似度用杰卡德相似系数描述就是：甲乙都有购买的数量（交集-共同部分）为7件，甲乙购买的种类不一样的数量之和为（10+15-7=）18件（并集-不重复合计数量），所以他们的相似度为7/18。根据实际情况可知，系数越大，相似度越大。
所以回到这次的问题，在A和B数据里面，完全可以将“葡萄”和“葡蔺”这两个字符串之间的相似度，用杰卡德相似系数来衡量，那么“葡萄”分解为["葡","萄"],扫描文字“葡蔺”分解为["葡","蔺"]。那么他们的共同部分为“葡”，为1个字符，不重复合计数量为3个字符["葡","萄","蔺"]。结果杰卡德相似系数为1/3,也是他们的相似度。
但是我总感觉，纯在此问题中搬这个概念，让两个字符的相似度“偏小”了，因为我总觉得他们“有1/2的相似度”，也就是一字之差。其实我自己的算法，并不是看了这个杰卡德相似系数而来，而是我感觉自己的方法要靠一个什么东西的话，那和这个系数最相近。
我使用的办法基本和上面一样，只是我的分母，取得是字符串较长的字符串长度（也就是字符的数量），因此上面的相似度，我计算的结果是1/2，对于匹配来说指导意义更大。
三、实现“一对多”的模糊匹配
有了上面的算法基础，我想在A中实现某一个水果比如“哈密瓜”匹配到具有一定相似度的B中水果，按实际情况，因为B中有两个“哈密瓜”，因此可以出现以下的匹配结果。
但其实如果说只要有相似度就可以匹配的话，结果远远不止这两个，因为西瓜和甜瓜，或者说只要有个瓜字的，都会匹配进来，因为他们有1/2或者1/3相似度。所以在匹配之前，应该设定一个可接受的相似度，来进行过滤，比如最低要求50%的相似度。那匹配进来的“奇怪结果”就要少很多，或者叫做更加精确。又或者要求100%，那就是精确匹配，容不得一点杂质。
具体实现，算法核心就是相似度这个概念定义，在数据量不大的情况，直接暴力循环，让程序首先在A中选一个水果，然后逐个与B中水果计算相似度，超过指定相似度（比如50%）就可以入选，否则就丢弃，然后选择A中的下一个，重复进行，直到A中水果都匹配完。
四、执行结果
写到这里，没有写python代码的实现过程，这次主要想写这个问题解决的一个思路，其实代码也就是以上思路的一个“翻译”而已，本次直接呈现结果如下，代码以附件的方式放在了最后。
可接受相似度为100%时：（精确匹配，没有模糊的结果出现）
可接受相似度为50%时（此时“葡萄就可以模糊匹配出来”，出现小部分“噪声”-甜瓜匹配结果中包含西瓜）：
可接受相似度为30%时：(“噪声”开始较多的出现)
因此，从上面的结果可以看出，可接受的相似度放太大或者放太小，都不利于结果的最佳呈现，比如此处，50%这个可接受相似度较100,30应该是最佳的。当然不同的问题，不同的数据集，类似的数据分析的参数调整不一样，根据实际检验的结果，做出最佳的调整。
五、总结
写到这里，我看了下字数超过2000了，不晓得有人看到这里不。
其实，本次主要是借这个实际例子，说一些关于自己对数据分析的认识:
1、具体的问题，对应着具体的算法；
2、实际问题的转化，比如两个事物的相似，最终转化成数学上简单的距离，数值，比例来进行衡量，当然一般的模型过程都相对比较杂；
3、根据实际问题，调整相应的参数，让结果最“契合”；
4、此次过程只是数据分析中的一部分，没有做相应的挖掘，只是数据分析、挖掘实现算法的一些实现方式、思路。
最后，这个办法可能不是解决这个问题的最好方式，如果有更好的想法，也诚恳希望介绍指导。
附：Python代码实现
class Match(object):
def __init__(self,stringA,stringB):
if len(stringA) < len(stringB):
self.min = stringA
self.max = stringB
else:
self.max = stringA
self.min = stringB
def approximate_match(self):
re = []
desc = []
for i in range(len(self.min)):
for j in range(len(self.max)):
r = self.min[i].find(self.max[j]) # 核心函数为find
if r != -1:
re.append(r)
desc.append(self.max[j])
match_ratio = len(re)/len(self.max)
match_ratio = str(round(match_ratio*100,2))
return match_ratio
def exact_match(self):
if self.a == self.b:
return str(100)
else:
return str(0)
class Match_list(object):
def __init__(self,item,data_list):
self.item = item
self.data_list = data_list
def approximate_match(self,flag):
item = self.item
data_list = self.data_list
temp = 0
word = []
print(item)
for item2 in data_list:
m = Match(str(item), str(item2))
r = m.approximate_match()
r = float(r)
if r >= float(temp) and r != 0 and r >= flag:
temp = r
word.append(item2)
print(item, word, temp)
