python - 作者姓名的近似字符串匹配 - 模块和策略

Question

我创建了一个小程序来检查作者是否存在于作者数据库中。我无法找到解决此问题的任何特定模块，因此我使用模块从头开始编写它以进行近似字符串匹配。

该数据库包含大约 6000 位作者，并且格式非常糟糕(许多拼写错误、变体、标题如“博士”等)。查询作者列表通常在 500-1000 之间(我有很多这样的列表)，因此速度非常重要。

我的一般策略是尽可能多地修剪和过滤数据库并寻找精确匹配。如果未找到匹配项，我将继续进行近似字符串匹配。

我目前正在使用内置的 difflib.get_close_matches，它完全符合我的要求 - 但是，它非常慢(几分钟)。因此，我正在寻找其他选择:

• 什么是最快的模块，可以返回最好的，比方说，在数据库中给出查询字符串超过某个阈值的 3 个匹配项？
• 比较两个字符串最快的模块是什么？

我发现的唯一一个是 fuzzy wuzzy，它比 difflib 还要慢。

Answer 1

尝试 fuzzywuzzy使用 native C python-levenshtein已安装库。

我在我的 PC 上运行了一个基准测试，以在有和没有 C-native levenshtein backend 的 ~19k 单词列表中找到 8 个单词的最佳候选者。安装(使用 pip install python_Levenshtein-0.12.0-cp34-none-win_amd64.whl)我得到了这些时间:

• 无 C 后端:
  在 48.591717004776 秒(0.00032039058052521366 秒/搜索)内比较了 151664 个单词。
• 已安装 C 后端:
  在 13.034106969833374 秒(8.594067787895198e-05 秒/搜索)内比较了 151664 个单词。

那是 ~x4 快(但没有我预期的那么快)。

结果如下:

0 of 8: Compared 'Lemaire' --> `[('L.', 90), ('Le', 90), ('A', 90), ('Re', 90), ('Em', 90)]`
1 of 8: Compared 'Peil' --> `[('L.', 90), ('E.', 90), ('Pfeil', 89), ('Gampel', 76), ('Jo-pei', 76)]`
2 of 8: Compared 'Singleton' --> `[('Eto', 90), ('Ng', 90), ('Le', 90), ('to', 90), ('On', 90)]`
3 of 8: Compared 'Tagoe' --> `[('Go', 90), ('A', 90), ('T', 90), ('E.', 90), ('Sagoe', 80)]`
4 of 8: Compared 'Jgoun' --> `[('Go', 90), ('Gon', 75), ('Journo', 73), ('Jaguin', 73), ('Gounaris', 72)]`
5 of 8: Compared 'Ben' --> `[('Benfer', 90), ('Bence', 90), ('Ben-Amotz', 90), ('Beniaminov', 90), ('Benczak', 90)]`
6 of 8: Compared 'Porte' --> `[('Porter', 91), ('Portet', 91), ('Porten', 91), ('Po', 90), ('Gould-Porter', 90)]`
7 of 8: Compared 'Nyla' --> `[('L.', 90), ('A', 90), ('Sirichanya', 76), ('Neyland', 73), ('Greenleaf', 67)]`

这是基准测试的 python 代码:

import os
import zipfile
from urllib import request as urlrequest
from fuzzywuzzy import process as fzproc
import time
import random

download_url = 'http://www.outpost9.com/files/wordlists/actor-surname.zip'
zip_name = os.path.basename(download_url)
fname, _ = os.path.splitext(zip_name)

def fuzzy_match(dictionary, search):
    nsearch = len(search)
    for i, s in enumerate(search):
        best = fzproc.extractBests(s, dictionary)
        print("%i of %i: Compared '%s' --> `%s`" % (i, nsearch, s, best))

def benchmark_fuzzy_match(wordslist, dict_split_ratio=0.9996):
    """ Shuffle and split words-list into `dictionary` and `search-words`. """
    rnd = random.Random(0)
    rnd.shuffle(wordslist)
    nwords = len(wordslist)
    ndictionary = int(dict_split_ratio * nwords)

    dictionary = wordslist[:ndictionary]
    search = wordslist[ndictionary:]
    fuzzy_match(dictionary, search)

    return ndictionary, (nwords - ndictionary)

def run_benchmark():
    if not os.path.exists(zip_name):
        urlrequest.urlretrieve(download_url, filename=zip_name)

    with zipfile.ZipFile(zip_name, 'r') as zfile:
        with zfile.open(fname) as words_file:
            blines = words_file.readlines()
            wordslist = [line.decode('ascii').strip() for line in blines]
            wordslist = wordslist[4:]  # Skip header.

            t_start = time.time()
            ndict, nsearch = benchmark_fuzzy_match(wordslist)
            t_finish = time.time()

            t_elapsed = t_finish - t_start
            ncomparisons = ndict * nsearch
            sec_per_search = t_elapsed / ncomparisons
            msg = "Compared %s words in %s sec (%s sec/search)."
            print(msg % (ncomparisons, t_elapsed, sec_per_search))

if __name__ == '__main__':
    run_benchmark()