加速"最接近"的字符串匹配算法

Question

我目前正在处理一个非常大的位置数据库，并试图将它们与真实世界的坐标进行匹配。

为了实现这一点，我下载了包含大量条目的地名数据集。它给出了可能的名称和纬度/经度坐标。为了尝试加快这个过程，我通过删除对我的数据集没有意义的条目，设法将巨大的csv文件(1.6 GB)减少到0.450 GB。然而，它仍然包含400万个条目。

现在我有很多条目，例如：

1. 上周在我位于挪威约顿海门的营地看到的Slettmarkmountains
2. 在童话谷探险，斯凯岛，苏格兰，英国
3. 加利福尼亚州移民荒野的早晨

知道字符串与这么长的字符串匹配，我通过NLTK使用Standford的NER来获得更好的字符串来确定我的位置。现在我有字符串，比如：

1. Slettmarkmountains Jotunheimen挪威
2. 英国苏格兰仙女格伦斯凯
3. 加利福尼亚州荒野移民
4. 约塞米蒂国家公园
5. 半圆顶约塞米蒂国家公园

地名数据集包含以下内容：

1. Jotunheimen挪威Lat Long
2. Slettmarkmountains Jotunheimen Norway Lat Long
3. Bryce Canyon Lat Long
4. 半球形长闩

我正在应用此算法，以在我的条目和包含4M个条目的geoname csv之间获得尽可能好的匹配。我首先读取了geoname_cleand.csv文件，并将所有数据放入一个列表中。对于我的每个条目，我调用当前条目和geoname_list 的所有条目之间的每个条目string_similarity()

def get_bigrams(string):
"""
Take a string and return a list of bigrams.
"""
s = string.lower()
return [s[i:i+2] for i in list(range(len(s) - 1))]
def string_similarity(str1, str2):
"""
Perform bigram comparison between two strings
and return a percentage match in decimal form.
"""
pairs1 = get_bigrams(str1)
pairs2 = get_bigrams(str2)
union  = len(pairs1) + len(pairs2)
hit_count = 0
for x in pairs1:
for y in pairs2:
if x == y:
hit_count += 1
break
return (2.0 * hit_count) / union

我在原始数据集的一个子集上测试了该算法，它运行良好，但速度明显非常慢(单个位置需要40秒)。由于我有超过一百万个条目要处理，这将需要10000个小时或更长的时间。我想知道你们是否知道如何加快速度。我显然想到了并行处理，但我没有任何HPC解决方案。也许简单的想法可以帮助我加快速度。

我对你们可能有的任何想法都持开放态度，但不知何故，我更喜欢python兼容的解决方案。

提前感谢：)。

编辑：

我尝试过使用fuzz.token_set_ratio(s1, s2)的fuzzywuzzy，但它的性能最差(运行时间更差，结果也不那么好)。比赛不像以前那样好了，我的自定义技术，一次参赛的运行时间增加了15秒。

编辑2:

我也想过在一开始使用某种排序来帮助匹配，但我天真的实现不起作用。但我相信有一些方法可以加快速度，比如删除地名数据集中的一些条目，或者以某种方式对它们进行排序。我已经做了很多清理工作来删除无用的条目，但无法获得低于4M 的数量

Answer 1

我们可以通过以下几种方式加快匹配。我假设在您的代码中，str1是来自数据集的名称，str2是地理名称字符串。为了测试代码，我用你问题中的数据制作了两个小数据集。我写了两个匹配函数best_match和first_match，它们使用您当前的string_similarity函数，所以我们可以看到我的策略给出了相同的结果。CCD_ 8检查所有的地名字符串&如果分数超过给定的阈值分数，则返回分数最高的字符串，否则返回None。first_match(可能)更快：它只返回超过阈值的第一个地名字符串，如果找不到，则返回None，因此如果找不匹配，则仍必须搜索整个地名列表。

在我的改进版本中，我们为每个str1生成一次bigram，而不是为我们比较的每个str2重新生成str1的bigram。我们提前计算所有的地理名称bigram，将它们存储在由字符串索引的dict中，这样我们就不必为每个str重新生成它们。此外，我们将地名二元图存储为集合。这使得计算hit_count要快得多，因为集合成员身份测试比对字符串列表进行线性扫描要快得快。geodict还需要存储每个bigram的长度：一个集合不包含重复项，因此bigram集合的长度可能小于bigram列表，但我们需要列表长度来正确计算分数。

# Some fake data
geonames = [
'Slettmarkmountains Jotunheimen Norway',
'Fairy Glen Skye Scotland UK',
'Emigrant Wilderness California',
'Yosemite National Park',
'Half Dome Yosemite National Park',
]
mynames = [
'Jotunheimen Norway',
'Fairy Glen',
'Slettmarkmountains Jotunheimen Norway',
'Bryce Canyon',
'Half Dome',
]
def get_bigrams(string):
"""
Take a string and return a list of bigrams.
"""
s = string.lower()
return [s[i:i+2] for i in range(len(s) - 1)]
def string_similarity(str1, str2):
"""
Perform bigram comparison between two strings
and return a percentage match in decimal form.
"""
pairs1 = get_bigrams(str1)
pairs2 = get_bigrams(str2)
union  = len(pairs1) + len(pairs2)
hit_count = 0
for x in pairs1:
for y in pairs2:
if x == y:
hit_count += 1
break
return (2.0 * hit_count) / union
# Find the string in geonames which is the best match to str1
def best_match(str1, thresh=0.2):
score, str2 = max((string_similarity(str1, str2), str2) for str2 in geonames)
if score < thresh:
str2 = None
return score, str2
# Find the 1st string in geonames that matches str1 with a score >= thresh
def first_match(str1, thresh=0.2):
for str2 in geonames:
score = string_similarity(str1, str2)
if score >= thresh:
return score, str2
return None
print('Best')
for mystr in mynames:
print(mystr, ':', best_match(mystr))
print()
print('First')
for mystr in mynames:
print(mystr, ':', best_match(mystr))
print()
# Put all the geoname bigrams into a dict
geodict = {}
for s in geonames:
bigrams = get_bigrams(s)
geodict[s] = (set(bigrams), len(bigrams))
def new_best_match(str1, thresh=0.2):
pairs1 = get_bigrams(str1)
pairs1_len = len(pairs1)
score, str2 = max((2.0 * sum(x in pairs2 for x in pairs1) / (pairs1_len + pairs2_len), str2)
for str2, (pairs2, pairs2_len) in geodict.items())
if score < thresh:
str2 = None
return score, str2
def new_first_match(str1, thresh=0.2):
pairs1 = get_bigrams(str1)
pairs1_len = len(pairs1)
for str2, (pairs2, pairs2_len) in geodict.items():
score = 2.0 * sum(x in pairs2 for x in pairs1) / (pairs1_len + pairs2_len)
if score >= thresh:
return score, str2
return None
print('New Best')
for mystr in mynames:
print(mystr, ':', new_best_match(mystr))
print()
print('New First')
for mystr in mynames:
print(mystr, ':', new_first_match(mystr))
print()

输出

Best
Jotunheimen Norway : (0.6415094339622641, 'Slettmarkmountains Jotunheimen Norway')
Fairy Glen : (0.5142857142857142, 'Fairy Glen Skye Scotland UK')
Slettmarkmountains Jotunheimen Norway : (1.0, 'Slettmarkmountains Jotunheimen Norway')
Bryce Canyon : (0.1875, None)
Half Dome : (0.41025641025641024, 'Half Dome Yosemite National Park')
First
Jotunheimen Norway : (0.6415094339622641, 'Slettmarkmountains Jotunheimen Norway')
Fairy Glen : (0.5142857142857142, 'Fairy Glen Skye Scotland UK')
Slettmarkmountains Jotunheimen Norway : (1.0, 'Slettmarkmountains Jotunheimen Norway')
Bryce Canyon : (0.1875, None)
Half Dome : (0.41025641025641024, 'Half Dome Yosemite National Park')
New Best
Jotunheimen Norway : (0.6415094339622641, 'Slettmarkmountains Jotunheimen Norway')
Fairy Glen : (0.5142857142857142, 'Fairy Glen Skye Scotland UK')
Slettmarkmountains Jotunheimen Norway : (1.0, 'Slettmarkmountains Jotunheimen Norway')
Bryce Canyon : (0.1875, None)
Half Dome : (0.41025641025641024, 'Half Dome Yosemite National Park')
New First
Jotunheimen Norway : (0.6415094339622641, 'Slettmarkmountains Jotunheimen Norway')
Fairy Glen : (0.5142857142857142, 'Fairy Glen Skye Scotland UK')
Slettmarkmountains Jotunheimen Norway : (1.0, 'Slettmarkmountains Jotunheimen Norway')
Bryce Canyon : None
Half Dome : (0.41025641025641024, 'Half Dome Yosemite National Park')

new_first_match是相当直接的。线路

for str2, (pairs2, pairs2_len) in geodict.items():

在geodict中的每个项目上循环，提取每个字符串、双值集和真双值长度。

sum(x in pairs2 for x in pairs1)

计数CCD_ 20中的bigram中有多少是CCD_。

因此，对于每个地名字符串，我们计算相似性得分，如果它>=阈值，则返回它，默认值为0.2。您可以给它一个不同的默认thresh，或者在调用它时传递一个thresh

new_best_match稍微复杂一些。)

((2.0 * sum(x in pairs2 for x in pairs1) / (pairs1_len + pairs2_len), str2)
for str2, (pairs2, pairs2_len) in geodict.items())

是生成器表达式。它在geodict项上循环，并为每个地名字符串创建一个(score, str2)元组。然后，我们将生成器表达式提供给max函数，该函数返回得分最高的元组。

---

这是new_first_match的一个版本，它实现了juvian在评论中提出的建议。这可能会节省一点时间。如果两个bigram中的任何一个为空，这个版本也可以避免测试。

def new_first_match(str1, thresh=0.2):
pairs1 = get_bigrams(str1)
pairs1_len = len(pairs1)
if not pairs1_len:
return None
hiscore = 0
for str2, (pairs2, pairs2_len) in geodict.items():
if not pairs2_len:
continue
total_len = pairs1_len + pairs2_len
bound = 2.0 * pairs1_len / total_len
if bound >= hiscore:
score = 2.0 * sum(x in pairs2 for x in pairs1) / total_len
if score >= thresh:
return score, str2
hiscore = max(hiscore, score)
return None

一个更简单的变化是不麻烦计算CCD_ 29&只需将CCD_ 30与CCD_。

Answer 2

我使用SymSpell端口到python进行拼写检查。如果你想尝试processInput，将需要为它添加代码，最好使用2Ring对它进行调整。

from symspellpy.symspellpy import SymSpell, Verbosity  # import the module
import csv

geonames = [
'Slettmarkmountains Jotunheimen Norway',
'Fairy Glen Skye Scotland UK',
'Emigrant Wilderness California',
'Yosemite National Park',
'Half Dome Yosemite National Park',
]
mynames = [
'Jotuheimen Noway',
'Fairy Gen',
'Slettmarkmountains Jotnheimen Norway',
'Bryce Canyon',
'Half Domes',
]
frequency = {}
buckets = {}
def generateFrequencyDictionary():
for geo in geonames:
for word in geo.split(" "):
if word not in frequency:
frequency[word] = 0
frequency[word] += 1

with open("frequency.txt", "w") as f:
w = csv.writer(f, delimiter = ' ',lineterminator='r')
w.writerows(frequency.items())      

def loadSpellChecker():
global sym_spell
initial_capacity = len(frequency)
# maximum edit distance per dictionary precalculation
max_edit_distance_dictionary = 4
prefix_length = 7
sym_spell = SymSpell(initial_capacity, max_edit_distance_dictionary,
prefix_length)
# load dictionary
dictionary_path = "frequency.txt"
term_index = 0  # column of the term in the dictionary text file
count_index = 1  # column of the term frequency in the dictionary text file
if not sym_spell.load_dictionary(dictionary_path, term_index, count_index):
print("Dictionary file not found")
return
def splitGeoNamesIntoBuckets():
for idx, geo in enumerate(geonames):
for word in geo.split(" "):
if word not in buckets:
buckets[word] = set()
buckets[word].add(idx)  

def string_similarity(str1, str2):
pass
def processInput():
for name in mynames:
toProcess = set()
for word in name.split(" "):
if word not in buckets: # fix our word with a spellcheck
max_edit_distance_lookup = 4
suggestion_verbosity = Verbosity.CLOSEST  # TOP, CLOSEST, ALL
suggestions = sym_spell.lookup(word, suggestion_verbosity, max_edit_distance_lookup)
if len(suggestions):
word = suggestions[0].term
if word in buckets:
toProcess.update(buckets[word])
for index in toProcess: # process only sentences from related buckets
string_similarity(name, geonames[index])                    

generateFrequencyDictionary()
loadSpellChecker()
splitGeoNamesIntoBuckets()
processInput()