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

Question

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

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

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

1. 上周我在挪威尤通黑门山的露营地看到了Slettmarkmountains山脉
2. 冒险在神仙的幽谷,斯凯岛,苏格兰,英国
3. 早上在移民荒野,加利福尼亚州

知道字符串匹配这么长的字符串,我通过NLTK 使用Standford的NER来获得更好的字符串来限定我的位置.现在我有类似的字符串:

1. Slettmarkmountains Jotunheimen挪威
2. 童话幽谷斯凯岛苏格兰英国
3. 移民荒野加州
4. 优胜美地国家公园
5. 半圆顶约塞米蒂国家公园

geoname数据集包含以下内容:

1. Jotunheimen挪威Lat Long
2. Slettmarkmountains Jotunheimen挪威Lat Long
3. 布莱斯峡谷拉特龙
4. Half Dome Lat Long
5. ...

我正在应用这个算法来获得我的条目和包含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秒).由于我有超过一百万个条目要处理,这将需要10000小时或更长时间.我想知道你们是否对如何提高速度有任何想法.我想到了并行处理,但我没有任何HPC解决方案.也许简单的想法可以帮助我加快速度.

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

提前致谢 :).

编辑:

我尝试过使用fuzzywuzzy,fuzz.token_set_ratio(s1, s2)它会产生最差的性能(运行时间更糟,结果也不是很好).匹配不如以前使用我的自定义技术那么好,并且单个条目的运行时间增加了15秒.

编辑2:

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

Answer 1

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

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

# 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。

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

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比较thresh。