Ранжированный поиск
Есть некоторая база данных содержащая некоторые названия и численность населения, пусть будут название городов, я создаю некоторую форму в которой человек предположительно хочет найти информацию о городе, но он не всегда знает корректное его написание, да и называть люди могут по разному (Питер/Санкт петербург, Санкт-Петербург) и я хочу выдавать человеку самый возможный вариант (т.е. в зависимости от похожести названия + учитывая популяцию, если город большой, то с большей вероятностью алгоритм поставит его на первое место в ранжировании результата.
Есть ли какие-то готовые алгоритмы или идеи насчет такого ранжирования в поиске по базе данных?
P.S. База данных - это обычная табличка в pandas.
Ответы (2 шт):
Не совсем понятна проблема. Есть "некоторая" база данных - ну, наверное, в терминах Python - датафрейм, в котором индекс - название города, а "некоторый" столбец содержит население. Отсортировали свой датафрейм по этому столбцу. И работайте с ним как хотите. Хотите - делайте подвыборку по начальным символам индекса и выдавайте ее в порядке вашей отсортированного датафрейма. А не хотите - сортируйте по индексу, а после ввода части названия - делейте выборку из датафрейма и ее сортируйте. Единственно, что непонятно, как вы Питер/Санкт-Петербург/Петроград/Ленинград отождествлять собрались - ну "похожесть названия" тут явно ни к чему. Но это совершенно отдельная задача.
Набросал по приколу вам готовое решение. Формулами и деталями реализации можно поиграться при желании:
# pip install fuzzywuzzy[speedup]
import numpy as np
import pandas as pd
from fuzzywuzzy import fuzz
from fuzzywuzzy import process
# берём сайт с готовой статистикой по крупным городам России, подготавливаем данные
url = 'https://sites.google.com/site/ruregdatav1/spisok-gorodov-rossii'
html = pd.read_html(url)
df = html[5].iloc[3:176,1:3]
df.columns = ['city', 'people']
df['people'] = list(map(int, map(''.join, map(str.split, df.people.values))))
# берём логарифм от размера населения городов
df['people_score'] = np.log1p(df.people.values)
# делаем поиск по конкретной подстроке
city_to_find = 'сара'
# вычисляем процент похожести каждого из городов на искомый
df['fuzzy_score'] = df.city.map(dict(process.extract(city_to_find, df.city.values, limit=df.shape[0])))
# домножаем на логарифм от населения, чтобы получить итоговый рейтинг
df['score'] = df.fuzzy_score * df.people_score
# выдаём 5 наиболее подходящих городов (с ненулевым рейтингом)
df.loc[df.score > 0].sort_values('score', ascending=False).head(5)
Вывод (форматировать мне лениво):
city people people_scorefuzzy_score score
133 г. Саратов 838042 13.638825 90 1227.494222
132 г. Саранск 320612 12.677990 90 1141.019106
130 г. Самара 1156659 13.961047 68 949.351203
14 г. Барнаул 632391 13.357265 68 908.294002
10 г. Астрахань529793 13.180244 68 896.256560