[ главная ]   [ рейтинг статей ]   [ справочник радиолюбителя ]   [ новости мира ИТ ]



Ответов: 0
25-02-12 07:01







   Web - программирование
PHP


ASP






XML



CSS

SSI





   Программирование под ОС











   Web - технологии








   Базы Данных









   Графика






Данные




Web - программирование / PHP /

Яндекс-like поиск своими руками

Редкий веб-программист не сталкивался с задачей написания поиска для своего сайта. Независимо от того – делалось ли это для собственной 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"
;




Комментарии

 Ваш комментарий к данному материалу будет интересен нам и нашим читателям!



Последние статьи: Web - программирование / PHP /

GTK+: перспективы развития
02-03-2010   

Библиотека GTK+ прошла долгий путь развития и сейчас очень популярна. GNOME, одна из ведущих оконных сред, использует GTK+ почти исключительно, GIMP построен на GTK+, множество коммерческих разработчиков ПО, таких как Abobe, NVidia и VMware, решили использовать эту библиотеку в качестве графической основы для своих продуктов... подробнее

Кол. просмотров: общее - 3956 сегодня - 0

Новостной портал
13-11-2009   

Slashdot.org – популярный новостной портал с посещаемостью 50 млн. человек в месяц. Авторы проекта добились такого успеха, предоставляя пользователям свежие и интересные новости из мира IT... подробнее

Кол. просмотров: общее - 3768 сегодня - 0

Параллельное выполнение скриптов может нарушить целостность информации в файлах
13-11-2009   

Здесь рассматривается вопрос, что бывает, если запустить некий скрипт почти одновременно (что происходит, например, при большой нагруженности сервера) несколько раз, т.е. запустить несколько копий одного и того же скрипта. И к чему это может привести... подробнее

Кол. просмотров: общее - 3663 сегодня - 0

No spam.php
10-11-2009   

...и снова о спаме. Кто о нем только не писал, и все писали, что это плохо и ай-яй-яй. Я не буду оригинальничать, и тоже скажу – это плохо. Это ай-яй-яй. Как бороться со спамерами со своей стороны... подробнее

Кол. просмотров: общее - 3725 сегодня - 0

Начинаем работу с рисунками в php для Windows
10-11-2009   

Эта статья даст вам общее представление о том, как создавать, обрабатывать и выводить рисунки в PHP4 для Windows... подробнее

Кол. просмотров: общее - 3717 сегодня - 0



  WWW.COMPROG.RU - 2009-2012 | Designed and Powered by Zaipov Renat | Projects