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

Question

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

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

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

上周从我在挪威 Jotunheimen 的露营地看到的 Slettmark 山脉
在英国苏格兰斯凯岛仙女谷探险
加州移民荒野的早晨

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

Slettmarkmountains Jotunheimen 挪威
Fairy Glen Skye 苏格兰英国
加州荒野移民
Yosemite 国家公园
半穹顶Yosemite国家公园

geoname 数据集包含如下内容：

Jotunheimen 挪威 Lat Long
Slettmarkmountains Jotunheimen Norway Lat Long
布莱斯峡谷纬度
半圆顶纬度
...

我正在应用此 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 字符串 & returns 得分最高的字符串，如果它超过给定的阈值得分，否则它 returns None。 first_match（可能）更快：它只是 return 超过阈值的第一个地理名称字符串，或者 None 如果找不到，那么如果找不到match 那么它仍然必须搜索整个 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 字符串，我们计算相似性分数，如果它 >= 阈值，则 return 它的默认值为 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 函数，该函数 return 是得分最高的元组。

这是 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.

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

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

Speeding up a "closest" string match algorithm

python

language-agnostic

algorithm

performance

string-matching