我创建了一个小程序来检查作者是否存在于作者数据库中。我无法找到解决此问题的任何特定模块,因此我使用模块从头开始编写它以进行近似字符串匹配。
该数据库包含大约 6000 位作者,并且格式非常糟糕(许多拼写错误、变体、标题如“博士”等)。查询作者列表通常在 500-1000 之间(我有很多这样的列表),因此速度非常重要。
我的一般策略是尽可能多地修剪和过滤数据库并寻找精确匹配。如果未找到匹配项,我将继续进行近似字符串匹配。
我目前正在使用内置的 difflib.get_close_matches
,它完全符合我的要求 - 但是,它非常慢(几分钟)。因此,我正在寻找其他选择:
- 什么是最快的模块,可以返回最好的,比方说,在数据库中给出查询字符串超过某个阈值的 3 个匹配项?
- 比较两个字符串最快的模块是什么?
我发现的唯一一个是 fuzzy wuzzy,它比 difflib 还要慢。
最佳答案
尝试 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()
关于python - 作者姓名的近似字符串匹配 - 模块和策略,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13980656/