Мы можем ускорить сопоставление несколькими способами. Я предполагаю, что в вашем коде str1 - это имя из вашего набора данных, а str2 - строка геонамов. Чтобы проверить код, я сделал два крошечных набора данных из данных вашего вопроса. И я написал две соответствующие функции best_match и first_match, которые используют вашу текущую функцию string_similarity, чтобы мы могли видеть, что моя стратегия дает те же результаты. best_match проверяет все строки геонаме и возвращает строку с наивысшей оценкой, если она превышает заданную пороговую оценку, в противном случае возвращается None. first_match (потенциально) быстрее: он просто возвращает первую строку геонаме, которая превышает пороговое значение, или None, если он не может его найти, поэтому, если он не находит соответствия, он все равно должен искать весь список географических названий.
В моей улучшенной версии мы генерируем биграммы для каждого str1 один раз, вместо того, чтобы заново генерировать биграммы для str1 для каждого str2, с которым мы их сравниваем. И мы заранее вычисляем все биграммы геонамов, сохраняя их в формате dict, проиндексированном строкой, чтобы нам не приходилось их регенерировать для каждого 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()
выход
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. Вы можете присвоить ему другое значение по умолчанию 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, в которой реализовано предположение, высказанное Джувианом в комментариях. Это может сэкономить немного времени. Эта версия также позволяет избежать тестирования, если один из биграммов пуст.
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.