Привет хабр.
Пару месяцев назад мне поступил заказ на разработку сайта. Сайт представлял собой сборник статей добавляемых пользователем. Одним из пунктов технического задания было создание поиска. Т.к. я большой любитель изобретать велосипеды, было решено не использовать поиск от Яндекса или гугла.
Обычный поиск
Самым тривиальным решением было разбивать статьи на слова, разбивать запрос на слова и искать совпадения.
Плюсы:
- Высокая скорость. Можно было для этого использовать сразу mysql таблицу со словами
- Простота. Скрипт для такого алгоритма занимал бы всего несколько десятков строк.
минусы:
- низкая точность, отсутствие возможности исправления ошибок
Нечёткий поиск
Итак, было решено сделать все как у «взрослых». Т.е. авто исправление ошибок и поиск не только по точному соответствию слов но и по формам слова. Т.к. хотелось большей производительности, поиск писался не на php, а на Яве постоянно висящей в памяти и хранящей индекс статей.
Стеммер
Для начала надо было определиться, как обобщать разные формы одного слова. Будем считать, что одинаковые слова это слова с одинаковым корнем. Но вот извлечение корня это не лёгкая задача. Решая эту проблему, я быстро нагуглил так называемый «стеммер Поттера» (Сайт автора ). Стеммер Поттера выделяет корень слова, который, однако, не всегда совпадает с лексическим. К тому же он написан для разных языков, в том числе и для русского. Однако пример русского написан на пхп и, переписав его один в один на яву, я получил очень слабую производительность. Проблема решилась использованием регулярных выражений. Из-за нелюбви к регулярным выражениям я взял готовый пример www.algorithmist.ru/2010/12/porter-stemmer-russian.html (Спасибо автору).
В результате производительность получилась на уровне 1 млн. слов в секунду.
Исправление опечаток
Часто бывает так, что пользователь ошибается при вводе запроса. Поэтому нам необходим алгоритм определения похожести слов. Для этого существует много методов, но самым быстрым из них является метод 3-грамм. Суть его такова: Разбиваем слово на тройки последовательно идущих букв. Со вторым поступаем аналогично. Пример:
Конституция => КОН ОНС НСТ СТИ ТИТ ИТУ ТУЦ УЦИ ЦИЯ
Консттуция=> КОН ОНС НСТ СТТ ТТУ ТУЦ УЦИ ЦИЯ
Потом сравниваем эти тройки и чем больше одинаковых троек мы получили, тем выше похожесть слов.
Итого у нас совпадает 6 троек из 8 или 75%.
Этот метод хорош, когда в запросе пропущена или добавлена лишняя буква. Но вот когда человек заменяет одну букву на другую, у нас сразу попадает 3 тройки. Однако обычно лишняя или пропущенная буква это опечатка. А вот заменённая — это орфографическая ошибка. Какие же это ошибки:
- Замена а – о и о-а: мАлоко, пАбеда, рОдон
- Е-и, и-е. бИда, пЕрог
- неправильно употребление мягкого и твёрдого знака.
Поэтому приведём все к одному виду:
Private String replace(String word)
{
word=word.replace('а','о');
word=word.replace('е','и');
word=word.replace('б','п');
word=word.replace('д','т');
word=word.replace('г','к');
word=word.replace('щ','ш');
word=word.replace('ъ','ь');
word=word.replace('ж','ш');
return word;
}
Таким образом, нам надо перебрать все имеющиеся слова и найти самое похожее. При 1 млн. слов это около 1 с, что не приемлемо. Оптимизируем. Для начала, положим, что нас интересуют слова, отличающиеся в длине максимум на 2 буквы. Потом заметим, что из трёх букв существует всего 30 000 вариаций.(33*33*33).Поэтому прохешируем ещё на этапе индексации итого алгоритм будет такой:
String gramms[]=get3gram(word);
int i=0;
for (String gram:gramms)
{
if (this.tgram_abc[len][i][hashabc(gram)]==null)
this.tgram_abc[len][i][hashabc(gram)]=new ArrayList();
this.tgram_abc[len][i][hashabc(gram)].add(id);
i++;
}
Далее сделаем аналогичное для слова с «приведёнными» буквами, потом заменим нн на н и добавим в третий массив, и напоследок удалим все мягкие знаки.
Теперь можно искать похожие слова. Разбиваем слова на граммы, находим хеш кажой тройки и получаем списко слов в которых одни есть на похожих позициях.
HashMap<Integer,Double> GramBalls=new HashMap();
int StartG=(i-2>=0)?i-2:0;
int EndG=(i+2);
for (int l=len-2;l<=len+2;l++)
for (int j=StartG;j<=EndG;j++)
if (this.tgram_abc[l][j][hashabc(gram)]!=null)
for (int id:this.tgram_abc[l][j][hashabc(gram)])
if (!GramBalls.containsKey(id))
GramBalls.put(id, (1-(double)Math.abs(len-l)/3) /(word.length()-2));
В последней строке выведенная методом «тыка» формула, которая означает, что триграмм в конце будет приносить слову 0.7 очков/кол-во триграмма. А первая будет приносить 1 очко/кол-во грамм.
Дальше аналогично ищем для «приведённого» слова из запроса и для слова с заменёнными нн и мягкими знаками. Правда там вместо 1 будет 0.7 и 0.3 соответственно.
После сортируем слова по очкам и выбираем слово с наибольшим кол-вом очков. Однако если у «чемпиона» меньше 0.1 очка то возвращаем null. Это нужно чтобы не учитывать совсем непохожие слова. Т.к. приведённый выше алгоритм определяет что «космонавт» «астма» имеют похожесть 0.05.
Механизм индексации
У «взрослых» индексацией занимаются специальные программы пауки, которые периодически обходят сайты, индексируют содержимое, ищут ссылки на странице и идут по ним дальше. У нас же все просто. При добавлении страницы php скрипт посылает запрос нашем поисковику индексировать страницу. Далее страница очищается от тегов. После разбивается на слова. После этого определяется язык слова. Мы проходим по слову и для каждой буквы добавляем балл языкам, которые поддерживают это символ. Для русского это а-я и дефис «-».Для английского это a-z, дефис и апостроф(‘). Все символы и цифры вынесены в отдельный «символьный язык».
Для хранения и быстрого поиска у нас существует массив списка слов.
ArrayList<IndexPosition> WordIndex[язык текста][служебный индекс текста][язык слова][id слова]
Этот список хранит позицию слова в статье и id статьи.
Аналогично заводим массив для хранения корней слова.
Далее берем заголовок и индексируем его как ещё один текст.
Механизм поиска и ранжирования
Это самый главный механизм любой поисковой системы. Именно от того насколько правильно он создаёт выдачу зависит мнение пользователей.
Когда пользователь нажимает на кнопку поиск php скрипт пересылает запрос поисковику. Тот его разбивает на слова. Только тут есть одно отличие от индексации. Если при добавленной статьи при встрече незнакомого слова мы добавляем его в список слов, то при встрече в запросе незнакомого слова мы ищем наиболее похожее используя метод 3 грамм.
После разбиения для каждого слова мы получаем список из пар id текста – вхождение слова.
Определим, насколько статья подходит запросу:
- Посчитаем, сколько всего слов из запросов есть в статье.(a)
- Посчитаем, сколько всего корней из запросов есть в статье.(b)
- Посчитаем сколько существует словосочетаний слов аналогичных словосочетаниям в запросе( c)
- Посчитаем, сколько существует словосочетаний корней аналогичных словосочетаниям в запросе(d)
- Определим сколько слов из запроса встречаются в статье(e)
- Определим сколько корней из запроса(f )
После чего каждой статье добавим баллы по след формуле:
Math.log(2*a+1)+ Math.log(2+1)+2+Math.log(c*5+1))+ Math.log(d*3+1)))*(f+2*e));
Формула создана по след принципам:
- Слова приоритетнее корней
- Словосочетания приоритетнее обычных слов
- Чем более полно статья описывает поисковый запрос, тем выше её рейтинг. Причём полнота является ключевым
Далее пройдёмся по заголовкам, только там будем умножать баллы на 10, т.к. заголовок отражает суть статьи.
Сортируем и выводим.
Приведённый алгоритм обрабатывает 100 запросов в секунду при индексе в 1000 статей на с процессором 1Ггц.
P.S. Эта статья лишь служит лишь для ознакомления с некоторыми алгоритмами и идеями нечёткого поиска.
Автор: numitus
