加速“最接近”字符串匹配算法

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

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

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

1. 上周从我位于挪威尤通黑门的露营地看到的斯莱特马克山脉
2. 在英国苏格兰斯凯岛仙女谷探险
3. 加利福尼亚州移民荒野的早晨

知道字符串与这么长的字符串匹配，我使用斯坦福大学的NER https://nlp.stanford.edu/software/tagger.shtml通过 NLTK 获得更好的字符串来限定我的位置。现在我有这样的字符串：

1. 挪威尤通黑门州斯莱特马克山脉
2. 仙女格伦斯凯 苏格兰 英国
3. 加州移民荒野
4. 优胜美地国家公园
5. 半圆顶优胜美地国家公园

geoname 数据集包含以下内容：

1. 尤通黑门挪威经纬度
2. Slettmarkmountains Jotunheimen 挪威 经纬度
3. 布莱斯峡谷经纬度
4. 半圆顶经纬度
5. ...

我正在应用这个算法 http://www.catalysoft.com/articles/StrikeAMatch.html在我的条目和包含 4M 条目的 geoname csv 之间获得良好的可能匹配。我首先读取 geoname_cleaned.csv 文件并将所有数据放入列表中。对于我拥有的每一项条目，我都会调用我的每一项条目string_similarity()当前条目和 geoname_list 的所有条目之间

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 秒）。由于我有超过 100 万个条目需要处理，因此这将花费 10000 小时或更长时间。我想知道你们是否知道如何加快速度。我显然想到了并行处理，但我没有任何可用的 HPC 解决方案。也许简单的想法可以帮助我加快速度。

我对你们可能有的任何想法持开放态度，但在某种程度上更喜欢与 python 兼容的解决方案。

提前致谢 ：）。

Edit:

我尝试过 fuzzywuzzyfuzz.token_set_ratio(s1, s2)并且它的性能最差（运行时间更差，结果也不那么好）。使用我的自定义技术，比赛效果不如以前那么好，单次参赛的运行时间足足增加了 15 秒。

Edit 2:

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

我们可以通过多种方式加快匹配速度。我假设在你的代码中str1是数据集中的名称，并且str2是一个地理名称字符串。为了测试代码，我根据您问题中的数据制作了两个小数据集。我写了两个匹配函数best_match and first_match使用您当前的string_similarity函数，这样我们就可以看到我的策略给出了相同的结果。best_match检查所有地理名称字符串，如果超过给定的阈值分数，则返回分数最高的字符串，否则返回None. first_match（可能）更快：它只返回超过阈值的第一个地理名称字符串，或者None如果它找不到，那么如果它没有找到匹配项，那么它仍然必须搜索整个地理名称列表。

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

# 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()

output

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)

计算有多少个二元组pairs1是成员pairs2 set.

因此，对于每个地理名称字符串，我们计算相似度分数，如果它 >= 阈值（默认值为 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 在评论中提出的建议。它可能会节省一点时间。此版本还避免测试任一二元组是否为空。

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

一个更简单的变化是不打扰计算hiscore并比较bound to thresh.