Хочу поделиться идеей, которую я использовал для реализации релевантного поиска почтовых адресов.
Дано: база адресов Великобритании (это не обязательно, идею можно использовать для чего угодно, но для примера я буду использовать эту базу), примерно 35 000 адресов. Необходимо организовать быстрый, релевантный поиск по этой базе.
Каждый адрес представляет собой набор следующих значений: страна, графство, административный округ, город, почтовый индекс, и координаты. Впрочем для простоты я буду искать только по посткоду и городу. Этого более чем достаточно чтобы уникально идентифицировать любой адрес.
За основу идеи я взял одну небезызвестную статью написанную однажды двумя парнями — Сергеем и Ларри, вы могли слышать о них.
Итак суть идеи. Каждый адрес разбивается на части — на слова. Каждому слову соответствует ссылка на полный адрес и вес этого слова во всей базе данных.
Несмотря на то что почтовый код представляется одним словом, мы все равно разделим его на части, т.к., например, коды «AB», «AB1», «AB11» указывают на одну и ту же область только каждый следующий более точнее детализирует предыдущий. Поэтому код AB11 мы будет разбивать на «AB11», «AB1», «AB».
Например, исходная база:
После построения индекса данные примут примерно следующий вид.
Поиск по такой базе сводится к тому что нам нужно найти все записи соответствующие каждому из слов запроса. Затем просуммировать веса для каждого из адресов, и отсортировать результат по сумме весов.
Например, пользователь вводит в строку поиска: "BT9, Holme". Из строки удаляем знаки препинания, пробелы, разбиваем на слова: «BT9», «BT» и «Holme».
Запрос к базе выглядит примерно так:
В результате получаем:
Что и требовалось найти. Осталось только заменить результат реальными значениями адреса.
Самое сложное — это найти веса для каждого слова.
Для начала определимся какими условиям должен удовлетворять вес слова.
Чтобы немного упростить задачу не будем вводить никаких зависимостей между длинной почтового кода и длинной названия города.
Сумарным весом почтового кода и города будет считать сумарный вес каждого из их компонентов,.т.е.:
«TR10» = «TR10» + «TR1» + «TR» = 4.61 + 3.88 + 2.69 = 11.18
«Сuminestown Industrial Estate» = «Сuminestown» + «Industrial» + «Estate» = 1.69 + 1.88 + 2.91 = 6.48
Предположим что минимальный и максимальный сумарный вес посткода — P_MIN и P_MAX соответственно.
SX, SXX, SXXX, ..., SXN — части посткода.
В соответствии с условием 4, чем больше N тем ближе сумарный вес будет к P_MAX и наоборот — чем N ниже, тем ближе вес будет к P_MIN.
Т.е. посткоды вроде AB, TR,… (N=0) должны иметь минимальный вес — P_MIN.
На графике я показал как меняется сумарный вес посткода в зависимости от N (количество частей на которые можно разбить посткод). Зависимость экспоненциальная.
Здесь хорошо видно что сумма лежит в диапазоне меджду P_MIN и P_MAX.
Мы знаем что:
Возьмем теперь для примера 2 посткода: «AB12» и «AB1».
Они раскладываются соотвественно на P1(AB12 + AB1 + AB) и на P2(AB1 + AB).
Как мы видим у них есть одинаковая часть P1(AB1 + AB) и P2(AB1 + AB), однако если немного подумать то становится понятно что они не должны быть равны и более того, чтобы выполнились условия 4 и 5, которые мы ввели выше должно выполняться следующее условие:
P1(AB1 + AB) < P2(AB1 + AB) < P1(AB12 + AB1 + AB)
Графически это выглядит так:
S + SX + SXX в нашем случае это AB12 + AB1 + AB.
Используя этот график выводим формулы. После безсонной ночи, массы преобразований и подбора коэффициентов у меня получилась следующая формула для нахождения веса посткода:
где,
Length — длинна посткода, N — количество частей на которые его можно разбить.
Принцип нахождения веса города похожий. Я не буду расписывать процесс. Скажу только что минимальный и максимальные веса для города были взяты меньшими.
Формула:
Length — длинна всего адреса, Count — количество слов в адресе.
Вообщем это и весь алгоритм, осталось только создать таблицу с индексом, используя формулы выше.
При размере базы данных примерно в 35 000 адресов, размер индекса составляет примерно 140 000 записей. Поиск происходит довольно быстро. При желании довольно просто можно разнести данные по разным таблицам или даже серверам.
Есть ещё одна хитрость. Можно сделать поиск по неточному соответствию, для этого нужно индексы в базе привести к какой-то основе. Например в простейшем случае можно использовать metaphone-ключ строки. Искать соответственно тоже нужно по этой основе.
Поиск можно посмотреть в действии.
Дано: база адресов Великобритании (это не обязательно, идею можно использовать для чего угодно, но для примера я буду использовать эту базу), примерно 35 000 адресов. Необходимо организовать быстрый, релевантный поиск по этой базе.
Каждый адрес представляет собой набор следующих значений: страна, графство, административный округ, город, почтовый индекс, и координаты. Впрочем для простоты я буду искать только по посткоду и городу. Этого более чем достаточно чтобы уникально идентифицировать любой адрес.
За основу идеи я взял одну небезызвестную статью написанную однажды двумя парнями — Сергеем и Ларри, вы могли слышать о них.
Итак суть идеи. Каждый адрес разбивается на части — на слова. Каждому слову соответствует ссылка на полный адрес и вес этого слова во всей базе данных.
Несмотря на то что почтовый код представляется одним словом, мы все равно разделим его на части, т.к., например, коды «AB», «AB1», «AB11» указывают на одну и ту же область только каждый следующий более точнее детализирует предыдущий. Поэтому код AB11 мы будет разбивать на «AB11», «AB1», «AB».
Например, исходная база:
| ID | Postcode | City |
|---|---|---|
| 1 | AB53 | Cuminestown Industrial Estate |
| 2 | BT94 | Knockroe Archdall |
| 3 | PE36 | Holme |
| 4 | TR10 | Busvannah |
| ... | ... | ... |
После построения индекса данные примут примерно следующий вид.
| Word | Address ID | Rank |
|---|---|---|
| Cuminestown | 1 | 1.691000 |
| Industrial | 1 | 1.884000 |
| Estate | 1 | 2.907000 |
| AB | 1 | 2.691093 |
| AB5 | 1 | 3.884349 |
| AB53 | 1 | 4.608096 |
| Knockroe | 2 | 2.385000 |
| Archdall | 2 | 2.385000 |
| BT | 2 | 2.691093 |
| BT9 | 2 | 3.884349 |
| BT94 | 2 | 4.608096 |
| Holme | 3 | 3.312000 |
| PE | 3 | 2.691093 |
| PE3 | 3 | 3.884349 |
| PE36 | 3 | 4.608096 |
| Busvannah | 4 | 2.194000 |
| TR | 4 | 2.691093 |
| TR1 | 4 | 3.884349 |
| TR10 | 4 | 4.608096 |
| ... | ... | ... |
Поиск по такой базе сводится к тому что нам нужно найти все записи соответствующие каждому из слов запроса. Затем просуммировать веса для каждого из адресов, и отсортировать результат по сумме весов.
Например, пользователь вводит в строку поиска: "BT9, Holme". Из строки удаляем знаки препинания, пробелы, разбиваем на слова: «BT9», «BT» и «Holme».
Запрос к базе выглядит примерно так:
SELECT id, SUM(rank) AS total_rank FROM locations_index WHERE word LIKE 'BT9' OR word LIKE 'BT' OR word LIKE 'Holme%' GROUP BY address_id ORDER BY total_rank DESC;В результате получаем:
| 2 | 6.575442 |
| 3 | 3.312000 |
Что и требовалось найти. Осталось только заменить результат реальными значениями адреса.
Веса слов
Самое сложное — это найти веса для каждого слова.
Для начала определимся какими условиям должен удовлетворять вес слова.
- Вес почтового кода выше веса города.
Почему так? Сделать ошибку при написании 4-х символов (половина из которых цифры) гораздо сложнее чем при написании 7-10 букв.
- Чем меньше количество слов в названии города — тем выше его приоритет.
По той же причине — чем короче адрес, тем меньше вероятность допустить ошибку при наборе.
- Чем короче слова в названии города, тем выше его приоритет.
- Чем точнее почтовый код — тем выше его приоритет.
Почтовый код точнее если указано больше его составляющих. (подробнее о почтовых кодах Великобритании)
Например код «AB21» — указывающий на город «Kirkhill Industrial Estate, Aberdeen City, Scotland» более точный чем «AB» который указывает на область «Aberdeen City, Scotland»
- Чем больше совпадение пользовательского запроса с адресом или посткодом — тем выше его приоритет.
Чтобы немного упростить задачу не будем вводить никаких зависимостей между длинной почтового кода и длинной названия города.
Сумарным весом почтового кода и города будет считать сумарный вес каждого из их компонентов,.т.е.:
«TR10» = «TR10» + «TR1» + «TR» = 4.61 + 3.88 + 2.69 = 11.18
«Сuminestown Industrial Estate» = «Сuminestown» + «Industrial» + «Estate» = 1.69 + 1.88 + 2.91 = 6.48
Вес посткода
Предположим что минимальный и максимальный сумарный вес посткода — P_MIN и P_MAX соответственно.
SX, SXX, SXXX, ..., SXN — части посткода.
В соответствии с условием 4, чем больше N тем ближе сумарный вес будет к P_MAX и наоборот — чем N ниже, тем ближе вес будет к P_MIN.
Т.е. посткоды вроде AB, TR,… (N=0) должны иметь минимальный вес — P_MIN.
На графике я показал как меняется сумарный вес посткода в зависимости от N (количество частей на которые можно разбить посткод). Зависимость экспоненциальная.
Здесь хорошо видно что сумма лежит в диапазоне меджду P_MIN и P_MAX.
Мы знаем что:
Возьмем теперь для примера 2 посткода: «AB12» и «AB1».
Они раскладываются соотвественно на P1(AB12 + AB1 + AB) и на P2(AB1 + AB).
Как мы видим у них есть одинаковая часть P1(AB1 + AB) и P2(AB1 + AB), однако если немного подумать то становится понятно что они не должны быть равны и более того, чтобы выполнились условия 4 и 5, которые мы ввели выше должно выполняться следующее условие:
P1(AB1 + AB) < P2(AB1 + AB) < P1(AB12 + AB1 + AB)
Графически это выглядит так:
S + SX + SXX в нашем случае это AB12 + AB1 + AB.
Используя этот график выводим формулы. После безсонной ночи, массы преобразований и подбора коэффициентов у меня получилась следующая формула для нахождения веса посткода:
где,
Length — длинна посткода, N — количество частей на которые его можно разбить.
Вес города
Принцип нахождения веса города похожий. Я не буду расписывать процесс. Скажу только что минимальный и максимальные веса для города были взяты меньшими.
Формула:
Length — длинна всего адреса, Count — количество слов в адресе.
Вообщем это и весь алгоритм, осталось только создать таблицу с индексом, используя формулы выше.
При размере базы данных примерно в 35 000 адресов, размер индекса составляет примерно 140 000 записей. Поиск происходит довольно быстро. При желании довольно просто можно разнести данные по разным таблицам или даже серверам.
Есть ещё одна хитрость. Можно сделать поиск по неточному соответствию, для этого нужно индексы в базе привести к какой-то основе. Например в простейшем случае можно использовать metaphone-ключ строки. Искать соответственно тоже нужно по этой основе.
Поиск можно посмотреть в действии.