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

最小总次数当然是第二种了．即为２

至于这个问题用代码如何实现，确实是个问题,　一时也没什么好办法，这种经典问题肯定是前人已经做了很多的，我们要站在前任的肩上去看这个问题，所谓站在前人肩上，是要从思想的肩膀上．所以不必自己苦苦折腾一个新的求解方法，先理解下别人的方法，如果你有潜力当然可以有你的解法．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 表达式是在做一个累加求和的运算初始值为０ 如果不清楚reduce 方法去查文档吧．

读源码有个很难平衡的事情就是，你是要把所有细节都搞清楚还是从大的思想去把握，太注意细节，项目很大的化你基本就很难出来，导致一些兴趣的丧失，如果完全不注意细节又感觉太空，没学到东西，所以这个问题还需自己把握好．
下面看get_matching_blocks() 这个方法实在寻找想等的子串．返回一个类似[(0, 0, 2),(3,2,2)]的值，意思是，a和b　前连个元素相同，a的３到５个字符和的２到４个字符相同．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.