python - 加速 "closest"字符串匹配算法

Question

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

为此，我下载了 the geoname dataset其中包含很多条目。它给出了可能的名称和纬度/经度坐标。为了尝试加快这个过程，我通过删除对我的数据集没有意义的条目，设法将巨大的 csv 文件(1.6 GB)减少到 0.450 GB。但是它仍然包含 400 万个条目。

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

1. 上周从我在挪威 Jotunheimen 的露营地看到的 Slettmark 山脉
2. 在英国苏格兰斯凯岛 Fairy Glen 探险
3. 加利福尼亚移民荒野的早晨

知道字符串与这么长的字符串匹配，我使用了 Standford's NER通过 NLTK 获得更好的字符串来限定我的位置。现在我有这样的字符串:

1. Slettmarkmountains Jotunheimen 挪威
2. Fairy Glen Skye 苏格兰 英国
3. 加州荒野移民
4. 优胜美地国家公园
5. 半圆顶优胜美地国家公园

geoname 数据集包含如下内容:

1. Jotunheimen Norway Lat Long
2. Slettmarkmountains Jotunheimen Norway Lat Long
3. 布莱斯峡谷纬度
4. 半圆顶纬度
5. ...

我正在应用这个 algorithm在我的条目和包含 4M 条目的 geoname csv 之间获得良好的可能匹配。我首先读取 geoname_cleaned.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:

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

Answer 1

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

在我的改进版本中，我们为每个 str1 生成一次二元组，而不是为每个 str2 重新生成 str1 的二元组我们将其与之进行比较。我们预先计算所有的 geoname 双字母组，将它们存储在由字符串索引的字典中，这样我们就不必为每个 str 重新生成它们。此外，我们将 geoname 双字母组存储为集合。这使得 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()

输出

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 集合的成员。

因此，对于每个 geoname 字符串，我们计算相似性分数并在它 >= 阈值(默认值为 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 项并为每个 geoname 字符串创建一个 (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 和 thresh。