FuzzyWuzzy代码和原理解读 2016-03-26 # FuzzyWuzzy代码和原理解读 [TOC] 今天遇到一个需要对大文本去重的需求,就请教同事之前做的一个相同的问题.同事告知,是使用了 [FuzzyWuzzy](https://pypi.python.org/pypi/fuzzywuzzy) 这个包.由于在下知道文本相似性的计算很多,就想知道到底是什么算法实现的,是否符合我的需求.让我惊讶的是他也不知道,不弄清楚的原因竟然是代码太长.好,今晚我通宵也要整点眉目出来.或许这是当今大多数程序员的通病,不愿去深挖其中的细节,能用就拿来用,不能用接着继续Google .包括我在内,经常这样,为了治好这个病,从此刻开始..... ### 第一步核心原理 先找到FuzzyWuzzy 主页,和文档之类的看看介绍.由于项目开源,这些东西都很容易找到,[源码](https://github.com/seatgeek/fuzzywuzzy) .就在Github 上,down 下来,打开一看核心代码5个py文件,代码总量加上注释共694行代码.这就是所谓的复杂(往往我们都是被自己吓住的). 好了,再仔细看看Github上的文档.发现文档上说是采用[Levenshtein Distance](https://en.wikipedia.org/wiki/Levenshtein_distance)来计算字符串之间的相似度.看起来好高大上的感觉,又被吓了一次.看不明白英文可以找找中文.仔细读发现没那么难.由于这是被一个叫Levenshtein 的俄国人发明的所以才有了这个奇怪的名字,所谓Levenshtein Distance 又叫编辑距离,就是字符串S1转化成S2所需要的替换,插入,删除三种操作最小总次数.这是什么意思呢?网上能找到各种资源来解答举个例子: abcd 转成acdb可以有很多种方式: > abcd->accd->acdd->acdb > abcd->acd->acdb 最小总次数当然是第二种了.即为2 至于这个问题用代码如何实现,确实是个问题, 一时也没什么好办法,这种经典问题肯定是前人已经做了很多的,我们要站在前任的肩上去看这个问题,所谓站在前人肩上,是要从思想的肩膀上.所以不必自己苦苦折腾一个新的求解方法,先理解下别人的方法,如果你有潜力当然可以有你的解法.Wiki 说明中就有部分语言的源码,仔细阅读之后实现一个Python 版完全不是问题,这里面会有些动态规划(很久没接触到快忘了)的思想:下面就有一个网上找来的版本,看看也不复杂, 完全可以做些优化. <pre><code> def levenshtein(self,first,second): if len(first) > len(second): first,second = second,first if len(first) == 0: return len(second) if len(second) == 0: return len(first) first_length = len(first) + 1 second_length = len(second) + 1 distance_matrix = [range(second_length) for x in range(first_length)] #print distance_matrix for i in range(1,first_length): for j in range(1,second_length): deletion = distance_matrix[i-1][j] + 1 insertion = distance_matrix[i][j-1] + 1 substitution = distance_matrix[i-1][j-1] if first[i-1] != second[j-1]: substitution += 1 distance_matrix[i][j] = min(insertion,deletion,substitution) print distance_matrix return distance_matrix[first_length-1][second_length-1] </code></pre> ### 第二步读代码 看文档使用的方法,有下面一些例子: <pre><code> from fuzzywuzzy import fuzz fuzz.ratio("this is a test", "this is a test!") </code></pre> 好吧那就先搞清楚调用这个方法的时候都发生了什么事情. 下面这段代码就是我们调用的. <pre><code> @utils.check_for_none @utils.check_empty_string def ratio(s1, s2): s1, s2 = utils.make_type_consistent(s1, s2) m = SequenceMatcher(None, s1, s2) return utils.intr(100 * m.ratio()) </code></pre> 首先来看两个装饰器是干什么的: check_for_name <pre><code> def check_for_none(func): @functools.wraps(func) def decorator(*args, **kwargs): if args[0] is None or args[1] is None: return 0 return func(*args, **kwargs) return decorator </code></pre> 检查ratio 这个方法的参数是否为None的 <pre><code> def check_empty_string(func): @functools.wraps(func) def decorator(*args, **kwargs): if len(args[0]) == 0 or len(args[1]) == 0: return 0 return func(*args, **kwargs) return decorator </code></pre> 太明显不过,这是检查参数的字符串是否为空字符串的. <pre><code> s1, s2 = utils.make_type_consistent(s1, s2) </code></pre> 为了看懂这句我点进去看make_type_consistent 方法,当然有时候好的代码从名字就大概知道干什么的 <pre><code> def make_type_consistent(s1, s2): """If both objects aren't either both string or unicode instances force them to unicode""" if isinstance(s1, str) and isinstance(s2, str): return s1, s2 elif isinstance(s1, unicode) and isinstance(s2, unicode): return s1, s2 else: return unicode(s1), unicode(s2) </code></pre> 代码中有很好的注释,读代码也没那么难吧.这是在检查参数是否为字符串,如果不是就尝试转成字符串. 好了下面的两句才是重点,因为这里才是怎么计算距离的核心,其实你仔细读文档,你会发现这个包,并没有自己实现上面Levenshtein Distance 的算法而是用了[python-Levenshtein](https://pypi.python.org/pypi/python-Levenshtein/0.10.2#id3) 它是使用了C来实现距离的计算,[源码](https://github.com/miohtama/python-Levenshtein) 也在GitHub上有 <pre><code> m = SequenceMatcher(None, s1, s2) return utils.intr(100 * m.ratio()) </code></pre> 既然也没算距离那到底干了什么,我们再继续往下:看到m 是一个SequenceMatcher 对象,然后调用了m的ratio 方法.这就不细说SequenceMatcher 对象,我们直接看ratio 方法,很奇怪的是这个方法居然代码少的出奇: <pre><code> matches = reduce(lambda sum, triple: sum + triple[-1], self.get_matching_blocks(), 0) return _calculate_ratio(matches, len(self.a) + len(self.b)) </code></pre> 三行就三行,仔细看调用了几个方法.首先用reduce 方法对self.get_matching_blocks()产生的结果调用一个lambda 定义的函数,这个lambda 表达式是在做一个累加求和的运算初始值为0 如果不清楚reduce 方法去查文档吧. 读源码有个很难平衡的事情就是,你是要把所有细节都搞清楚还是从大的思想去把握,太注意细节,项目很大的化你基本就很难出来,导致一些兴趣的丧失,如果完全不注意细节又感觉太空,没学到东西,所以这个问题还需自己把握好. 下面看get_matching_blocks() 这个方法实在寻找想等的子串.返回一个类似[(0, 0, 2),(3,2,2)]的值,意思是,a和b 前连个元素相同,a的3到5个字符和的2到4个字符相同.matches 的意思是所有相等子串的总长度. 再看_calculate_ratio 方法,这就是在计算距离了,前一个是刚刚看到的mathes 后面两个是我们要比较的字符串的总长度: 再一看源码我都呆了: <pre><code> def _calculate_ratio(matches, length): if length: return 2.0 * matches / length return 1.0 </code></pre> 这个方法并没有用到什么高大上的距离 他的计算公式就是,两字符串所有相等子串的总长度/两个字符串的总长度 复杂吗?其实也不简单,有时间可以再仔细看看是怎么找两个字符串所有相等子串的. 到这里都没有用上前面的准备工作,今晚到这里,下次肯定用得到.我只是想治一下胆小的病. ### 错误更正 上面代码是在没有安装[python-Levenshtein](https://pypi.python.org/pypi/python-Levenshtein/0.10.2#id3) 的情况下开始的,所以所有计算的距离的方法都是Python difflib 这个包实现的内容,FuzzyWuzzy 在没有python-Levenshtein 包的情况下默认使用difflib.