Skip to content

模糊字符串匹配

数据分析的一个非常重要的技术就是字符串匹配，有很多重复数据尽管是一样的但是他们并不能完全相等，这就需要一种方式来实现模糊匹配。

所谓的模糊匹配通常指概率匹配，即寻找与模式近似而不是完全相等的字符串。

Levenshtein Distance(莱文斯坦距离)

他是针对于两个字符串的差异程度的量化测量分析。测量方式是看至少需要多少次的处理才能够将一个字符串变成另一个字符串。

例如，kitten 和 sitting 的 Levenshtein Distance 是 3，因为将 kitten 变成 sitting 的最小处理方式如下:

  1. kitten -> sitten: 将 k 改为 s
  2. sitten -> sittin: 将 e 改为 i
  3. sittin -> sitting: 添加 g

Tips

也可以删除，例如 ininformed 和 uniformed 的 Levenshtein Distance 是 1(删除 n 一步就行了)

TF-IDF

Levenshtein Distance 是非常好用和精准的模糊匹配字符串方式，但是它最大大问题就是太慢了，每次 process 操作都会匹配 choices 数组中的每一个字符串，对于大量字符串的匹配将是指数级的操作。这对于大数据处理来说是非常难以忍受的因此就需要一种更快的方式来实现。这就是 TF-IDF 。

Tips

TF-IDF 本身并不能进行匹配，他是他能够将字符串转换为向量，而对向量的计算就要快的多，因此他是很多文本语言处理的基石

TF-IDF(词频-逆文档频率)是一种自然语言处理技术，用于测量文档集合中一个单词对文档的重要性。

Text Only
TF-IDF = TF * IDF

- TF(Term Frequency 词频): 该词在文档中出现的次数/文档的总词数
- IDF(Inverse Document Frequency 逆文档频率): log(语料库(所有文档)总数/1(防止分母为0)+包含该词的文档数)

根据上面的公式，TF 决定了一个词对于一个文档的重要性，之所以还需要加一个 IDF 是因为有些词像 and、a 这样的几乎在每个文档中都存在但是它并不重要需要用 IDF 来消除影响。

考虑一个包含 100 个单词的文档，其中单词 cat 出现了 3 次。 cat 的词频(tf)为 (3/100)=0.03。现在，假设我们有 1000 万个文档，其中 1000 个文档中出现了单词 cat，逆文档频率(idf)计算为 log(10,000,000/1,000)=4。因此 TF-IDF 权重是这些量的乘积: 0.03*4=0.12。

N-gram

N-Gram是基于一个假设：第n个词出现与前n-1个词相关，而与其他任何词不相关。整个句子出现的概率就等于各个词出现的概率乘积。各个词的概率可以通过语料中统计计算得到。通常N-Gram取自文本或语料库。

N=1时称为unigram，N=2称为bigram，N=3称为trigram，假设下一个词的出现依赖它前面的一个词，即 bigram，假设下一个词的出现依赖它前面的两个词，即 trigram，以此类推。例如 你今天休假了吗，他的 bigram 依次为: (你今,今天,天休,休假,假了,了吗)。

Tips

理论上 n 越大也好，但经验上 trigram 用的最多。

通常情况下 N-gram 对应的是词(中文语境下需要结巴分词来进行分词)。但这并不是必须的，就像上面的你今天休假了吗这个例子，理论上他的 bigram 应该是(你今天,今天休假,休假了,了吗)这样的分词方式。

有时候我们在处理比较短的英文时，为了避免拼写错误也会直接针对于单个字符进行 n-gram，例如:

Python
import re

def ngrams(string, n=3):
    # 预处理，例如删除特殊字符
    string = re.sub(r'[,-./]',r'', string)
    ngrams = zip(*[string[i:] for i in range(n)])
    return [''.join(ngram) for ngram in ngrams]

print('All 3-grams in "McDonalds":')
ngrams('McDonalds')

All 3-grams in "McDonalds":

['McD', 'cDo', 'Don', 'ona', 'nal', 'ald', 'lds']

Tips

他通常配合 TF-IDF 来实现 feature(特征值) 的提取

KNN: Cosine Similarity(余弦相似度)

通常计算两个 TF-IDF 向量之间的相似度通常使用 Cosine Similarity。他可以看作是归一化点积。因此这个模糊匹配就变成了，对需要搜索的文档执行 TF-IDF 来与语料库中所有的文档的 TF-IDF 执行 Cosine Similarity 计算然后获取最接近的结果，这也就是我们最终匹配的结果。这通常可以通过NearestNeighbors算法实现。

第三方库

  • thefuzz: 简单的基于 Levenshtein Distance 的模糊匹配库
  • Elasticsearch: 分布式的 RESTful 风格的搜索和数据分析引擎，主要用于复杂的长文档关键字搜索
  • annoy: Approximate Nearest Neighbors(近似相邻)主要用于高维向量的相似性搜索，也就是将图片、文本、视频等通过某些算法转换为高维向量，然后只其中进行近似匹配

参考