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

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

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

计算 bigram 中有多少是集合的成员。pairs1pairs2

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

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

是一个生成器表达式。它会遍历这些项目，并为每个 geoname 字符串创建一个元组。然后，我们将该生成器表达式提供给函数，该函数返回得分最高的元组。geodict(score, str2)max

这是实现 juvian 在评论中提出的建议的一个版本。这样可以节省一点时间。此版本还避免了在任一二元框为空时进行测试。new_first_match

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

一个更简单的变化是不打扰计算，只是与 进行比较。hiscoreboundthresh

我使用 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()