Редкий веб-программист не сталкивался с задачей написания поиска для своего
сайта. Независимо от того – делалось ли это для собственной CMS или для первого
сайта, сделанного фирме двоюродного дяди топориком на коленке в 10 классе.
Зачастую, задача поиска по сайту решается использованием простого SQL-запроса
вида where `content` like ‘%семенович%’, при котором искомая фраза разбивается
на слова и каждое ищется средствами SQL среди строк в БД. Несмотря на простоту
этого решения, качество результатов такого поиска оставляет желать лучшего.
Ответственные разработчики используют индексацию, учитывают релевантность и даже
морфологию. Однако ещё ни на одном сайте я не видел такого красивого поиска, как
на Яндексе.
Что я сейчас понимаю под красивым поиском:
* Сортировка результатов по релевантности
* Учёт морфологии русского языка
* И самое главное – функцию «возможно вы искали»
Можно ли сделать такой поиск на своем сайте, затратив совсем немного времени и
не используя громоздкие базы словоформ? Можно.
Сразу должен предупредить – это не описание того, как работает поиск на Яндексе.
Это описание того, как сделать поиск, на 80% похожий на поиск в Яндексе:)
Другими словами – будут показаны те методы, которые дают максимальную эффект при
минимальных трудозатратах.
1. Сортировка по релевантности.
«Релевантность - субъективное понятие, выражающее степень соответствия запроса и
найденного, уместность результата» (Wikipedia).
Поскольку понятие субъективное, значит и определять его придется нам самим.
Сделаем релевантность документа функцией двух параметров – числа слов запроса,
которые присутствуют в документе, и количества вхождений всех этих слов в текст.
Например, запрос «компьютерные салоны Сыктывкара».
В тексте «компьютерные» присутствует 5 раз, «салоны» 2 раза, «Сыктывкар» - 0
раз. У нас встретилось 2 слова, и всего 7 их вхождений. На языке математики x=2,
y=7.
Определим функцию релевантность(x,y) = 1000x + y.
При таком ранжировании выше окажутся те страницы, в которых встречается больше
слов из запроса, а между собой они будут отсортированы по частоте вхождения
данных слов.
При правильно построенном индексе сайта, сортировку по релевантности можно легко
включать прямо в SQL запрос, использовав order by (технические подробности
ниже).
2. Учет морфологии русского языка.
Под поиском с морфологией понимают поиск, который не чувствителен к форме слова,
то есть ищет не только «соседей», но и «соседи», «сосед», «соседский» и так
далее.
Добиться этого можно двумя путями – правильным и «почти правильным».
Правильный путь заключается в наличии огромного (порядка 50 мб) словаря
словоформ, грамотно переведенного в формат используемой БД и прикрученный к
«движку» сайта. Найти бесплатный словарь можно тут: Ispell dictionary list,
правда придется разбираться с его структурой.
«Почти правильный» путь – выделять корень слова на основе общих лингвистических
правил языка (отбрасывая стандартные суффиксы и окончания). Делается это при
помощи «стеммера». (Исходный код стеммера для языка PHP).
Минус этого алгоритма в том, что он основан на правилах. А как известно, у
каждого правила есть исключения – данный алгоритм бессилен против пар вроде
«идти»-«шёл», а также непредсказуем в случае с беглыми гласными, довольно часто
встречающимися в русском языке (лев-львов, овца-овец).
При индексации сайта, прежде чем занести очередное слово в базу, мы выделяем его
корень и заносим только его.
При поиске, мы выделяем корни из слов запроса и ищем в базе данных уже лишь их.
В итоге мы сравниваем не сами слова, а корни – поиск с морфологией готов.
3. Функция «возможно вы искали».
Я мог бы долго объяснять почему и для кого нужна эта функция. Но вместо этого
скажу только одно – она есть в Яндексе (для русского) и в Google (для
английского языка). И это при том, что данные поисковые службы очень осторожно и
тщательно подходят к выбору своего функционала.
Как же нам поправить человека, который ввел «малако» вместо «молоко»?
Для английского языка давно существует алгоритм soundex, который устанавливает
одинаковый индекс для строк, имеющих схожее звучание.
В MySQL и PHP функция soundex является встроенной. Работает ли она для русских
слов? Нет, она работает только со словами, записанными латинскими буквами.
Однако ничто не мешает нам записать наши русские слова латинскими буквами!
То есть переводим слово в транслит (не общепринятый транслит, а более подходящий
именно по звучанию) и сразу же можем применять soundex.
К слову, существует попытка реализации русской версии soundex. Правда основана
она на все той же soundex, только предварительно происходит учёт звучания
русских букв.
При индексации слова находим его sound index и записываем в базу данных рядышком
с корнем. При поиске отмечаем те слова из запроса, которые не были найдены ни в
одном документе, и только для них производим поиск близкого по звучанию аналога
(если найдено несколько - отбираем самое часто встречающееся на сайте). Если
такое слово найдено - выводим подсказку.
4. Техническая реализация.
(Реализация на языке PHP для MySQL.)
Структура таблиц в базе данных.
CREATE TABLE `indexing_link` (
`id` int PRIMARY KEY auto_increment,
`url` varchar(255) not null default '',
`title` varchar(255) not null default '',
`short` text not null default ''
);
CREATE TABLE `indexing_word` (
`id` int PRIMARY KEY auto_increment,
`word` varchar(30) not null default '',
`sound` char(4) not null default 'A000'
);
CREATE INDEX idx_word_word ON indexing_word ( word(8) );
CREATE INDEX idx_word_sound ON indexing_word ( sound(4) );
CREATE TABLE `indexing_index` (
`id` int PRIMARY KEY auto_increment,
`link` int not null default 0,
`word` int not null default 0,
`times` int not null default 0
);
CREATE INDEX idx_index_linkword ON indexing_index (link, word);
Таблица link содержит список документов в виде ссылки, заголовка и анонса
(первых 300 символов страницы для вывода в результатах поиска).
Таблица word – содержит слова и включает в себя word – то что осталось после
стеммера (то что мы называли «корнем») и sound – результат функции soundex для
данного слова.
Таблица index связывает две других таблицы. Каждая ее строка – это слово «word»,
встретившеея на странице «link» «times»-раз.
Индексация.
Прежде чем разбивать текст на слова и индексировать их, следует избавится от
тэгов и прочих ненужных символов.
Простейшим решением будет применение регулярных выражении:
$tex = preg_replace('@<script[^>]*?>.*?</script>@si',' ',$tex);
$tex = preg_replace('@<style[^>]*?>.*?</style>@si',' ',$tex);
$tex = preg_replace('@<[/!]*?[^<>]*?>@si',' ',$tex);
Для повышения качества поиска, можно предварительно выделять слова, заключенные
в тэги title, h1-h6, b, strong, em, meta keywords и description, и повышать их
вес в индексе для данной страницы. Например, банально умножив число вхождении
этих слов на 3.
Стеммер.
Код стеммера можно взять тут - Эвристическое извлечение корня из русского слова
Транслитерация:
function rus2lat($string){
$rus = array('ё','ж','ц','ч','ш','щ','ю','я','Ё','Ж','Ц','Ч','Ш','Щ','Ю','Я','Ъ','Ь','ъ','ь');
$lat = array('e','zh','c','ch','sh','sh','ju','ja','E','ZH','C','CH','SH','SH','JU','JA','','','','');
$string = str_replace($rus,$lat,$string);
$string = strtr($string,
"АБВГДЕЗИЙКЛМНОПРСТУФХЫЭабвгдезийклмнопрстуфхыэ",
"ABVGDEZIJKLMNOPRSTUFHIEabvgdezijklmnoprstufhie");
return $string;
}
Поиск по запросу.
Первым делом разбиваем запрос на слова в массив $words, выделив для русских слов
корень стеммером.
Формируем поисковый запрос так.
for($i=0;$i<$num;$i++)
{
$if_clause.="iw.word='".$words[$i]."'";
if($i!=$num-1) $if_clause.=" or ";
}
$query="select il.id,il.url,il.title,il.short, count(distinct iw.id)*1000 + sum(ii.times)
as rel
from indexing_link il, indexing_index ii, indexing_word iw
where (".$if_clause.") and ii.word=iw.id and il.id=ii.link
group by il.id order by rel desc";
Ссылки по теме
Русский стеммер с улучшеными характеристиками, от разработчика поиска на
Рамблере:
http://linguist.nm.ru/stemka/stemka.html
Функция языка PHP для вычисления расстояния между строками:
http://www.php.net/manual/en/function.levenshtein.php
Яндекс.XML — это сервис, позволяющий делать автоматические поисковые запросы к
Яндексу и публиковать его ответы у себя на сайте в собственном дизайне.
http://xml.yandex.ru/
Яndex.Server — приложение для полнотекстового поиска информации на вашем
веб-сервере или в локальной сети с учетом морфологии русского языка.
http://company.yandex.ru/technology/products/yandex-server.xml
Медленный, но интересный корректор правописания:
http://norvig.com/spell-correct.html
http://sphinxsearch.com
Бесплатный поисковый механизм. Требует компиляции и установки на сервер.
Содержит API для интеграции с PHP, Python, Perl, и Ruby.
Из особенностей:
- быстрая работа (10 MB/сек индексация, запрос 0.1 сек на 2 Гб базе)
- масштабируемость, распределенный поиск
- русский и английский стемминг
- ПХП-модуль не требует компиляции для работы
http://www.dataparksearch.org
Поисковый механизм с открытым кодом. Фронт-енд в виде CGI приложения.
Поддерживает:
- словари словоформ ISpell
- синонимы для русского и английского языков
- логический язык запросов (boolean)
- исправление правописания на основе словарей Aspell
P.S. Данная статья писалась с надеждой на то, что в большем числе сайтов будет
организован удобный и полезный поиск. Ведь со временем количество информации в
сети растёт, и одной из приоритетных задач разработчиков я считаю обеспечение
эффективного её поиска.
http://alexblack.habrahabr.ru/
