Python. Нечеткий поиск. Расстояние Левенштейна.
Для нечеткого поиска есть различные алгоритмы. Один из них - это расстояние Левенштейна.
Алгоритм вычисления расстояния Левенштейна вычисляет расстояние между двумя последовательностями символов. Другими словами, он возвращает количество шагов, которые нужно сделать, чтобы привести первую последовательность символов ко второй.
Например, "Нагинск" и "Ногинск". Чтобы первое стало равно второму, нужно заменить один символ, следовательно расстояние Левенштейна для этих двух последовательностей равно 1. Для строки "Нагинс" нужно сделать два шага, чтобы привести к виду "Ногинск" - заменить символ 'а' на 'о' и добавить в конец символ 'к'. Следовательно в данном случае расстояние будет равно 2.
Для поиска с использованием алгоритма вычисления расстояния Левенштейна есть уже готовые библиотеки - fuzzywuzzy и rapidfuzz, например.
from fuzzywuzzy import process
import time
dataset = [
"Ногинск, Богородский городской округ, Московская область, "
"Центральный федеральный округ, Россия",
"Рузино, Ногинск, Богородский городской округ, Московская область, "
"Центральный федеральный округ, Россия",
"Цернское, Пушкинский городской округ, Московская область, "
"Центральный федеральный округ, Россия",
"Раменское, Раменский городской округ, Московская область, "
"Центральный федеральный округ, Россия",
"санатория \"Раменское\", Раменский городской округ, Московская область, "
"Центральный федеральный округ, Россия",
"Урюпинск, городской округ Урюпинск, Волгоградская область, "
"Южный федеральный округ, Россия",
"Кашин, Кашинский городской округ, Тверская область, "
"Центральный федеральный округ, Россия",
"Новое, Большесельский район, Ярославская область, "
"Центральный федеральный округ, Россия",
"Братск, городской округ Братск, Иркутская область, "
"Сибирский федеральный округ, 665729, Россия",
"Якутск, городской округ Якутск, Республика Саха (Якутия), "
"Дальневосточный федеральный округ, 677011, Россия"
]
search_str = "ногинск московская область"
start_time = time.clock()
a = process.extractOne(search_str, dataset)
print(time.clock() - start_time, "seconds")
print()
-------
>0.060080547999999956 seconds
>('Ногинск, Богородский городской округ, Московская область, Центральный федеральный округ, Россия', 86)
Как видим, из десяти строк датасета алгоритм нашел нужную. И затратил на это примерно 0.06 секунды. Это очень много, если что. На данных, насчитывающих сотни тысяч строк это складывается в неприемлемое значение. В датасете с 500000 строк он будет искать нужную строку 50 минут. Конечно, никакой пользователь не будет ждать ответа от поискового движка целый час. Правда, fuzzywuzzy выдает предупреждение, что нужно установить python-Levenshtein, чтобы убыстрить процесс. Но для установки этого модуля на windows требуется такая древняя Microsoft Visual C++ 14.0, что установить python-Levenshtein мне не удалось.
Есть еще библиотека - rapidfuzz. Как видно из названия, она позиционирует себя как быстрый нечеткий поиск. Чтобы протестировать ее, добавим в пример кода выше следующие строки, выделенные цветом:
from fuzzywuzzy import process, fuzz
from rapidfuzz import process as process_r
import time
dataset = [
"Ногинск, Богородский городской округ, Московская область, "
"Центральный федеральный округ, Россия",
"Рузино, Ногинск, Богородский городской округ, Московская область, "
"Центральный федеральный округ, Россия",
"Цернское, Пушкинский городской округ, Московская область, "
"Центральный федеральный округ, Россия",
"Раменское, Раменский городской округ, Московская область, "
"Центральный федеральный округ, Россия",
"санатория \"Раменское\", Раменский городской округ, Московская область, "
"Центральный федеральный округ, Россия",
"Урюпинск, городской округ Урюпинск, Волгоградская область, "
"Южный федеральный округ, Россия",
"Кашин, Кашинский городской округ, Тверская область, "
"Центральный федеральный округ, Россия",
"Новое, Большесельский район, Ярославская область, "
"Центральный федеральный округ, Россия",
"Братск, городской округ Братск, Иркутская область, "
"Сибирский федеральный округ, 665729, Россия",
"Якутск, городской округ Якутск, Республика Саха (Якутия), "
"Дальневосточный федеральный округ, 677011, Россия"
]
search_str = "ногинск московская область"
start_time = time.clock()
a = process.extractOne(search_str, dataset)
print(time.clock() - start_time, "seconds")
print(a)
print()
start_time = time.clock()
a = process_r.extractOne(search_str, dataset)
print(time.clock() - start_time, "seconds")
print(a)
------
>0.060080547999999956 seconds
>('Ногинск, Богородский городской округ, Московская область, Центральный федеральный округ, Россия', 86)
>0.00028495699999986357 seconds
>('Ногинск, Богородский городской округ, Московская область, Центральный федеральный округ, Россия', 85.5, 0)
Библиотека rapidfuzz так же хорошо нашла нужную строку, но затратила на выполнение того же кода в 172 раза меньше времени. Как заявляют авторы, она использует C, поэтому такая быстрая. В датасете, насчитывающем 500000 строк, она будет искать 17 секунд. Гораздо лучше, чем 50 минут, конечно, но для практической работы с пользователями тоже не пригодно.
Можно написать и свою реализацию алгоритма или найти в интернете. Вот одна из них:
def distance(self, a, b):
n, m = len(a), len(b)
if n > m:
# убедимся что n <= m, чтобы использовать минимум памяти O(min(n, m))
a, b = b, a
n, m = m, n
current_row = range(n + 1) # 0 ряд - просто восходящая последовательность
#(одни вставки)for i in range(1, m + 1):
previous_row, current_row = current_row, [i] + [0] * n
for j in range(1, n + 1):
add, delete, change = previous_row[j] + 1, current_row[j - 1] + 1,
previous_row[j - 1]
if a[j - 1] != b[i - 1]:
change += 1
current_row[j] = min(add, delete, change)
return current_row[n]
Эта функция тоже выполняется медленно, поэтому для больших датасетов не пригодна.
***
Комментарии: