6

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

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

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

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

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

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

4

2 回答 2

2

在安装了 native-C python-levenshtein库的情况下尝试使用fuzzywuzzy。

我在我的 PC 上运行了一个基准测试，以在安装和未安装C-native levenshtein 后端（使用）的情况下在 ~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()
于 2015-05-04T18:44:59.763 回答
0

Python 的自然语言工具包 (nltk) 可能有一些额外的资源可供您试用 -这个 google groups 线程似乎是一个好的开始。只是一个想法。

于 2013-01-01T14:38:46.857 回答