Get Bits

Редкий веб-программист не сталкивался с задачей написания поиска для своего сайта. независимо от того – делалось ли это для собственной 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('@]*?>.*?@si',' ',$tex); $tex = preg_replace('@]*?>@si',' ',$tex); $tex = preg_replace('@]*?>@',' ',$tex); Стеммер.

Код стеммера можно взять тут - http://getbits.info/wp-go.php?url=http://tips.xet.ru/archives/stemmer-portera-na-php

Транслитерация:

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

habrahabr.ru

• PHP: Безопасный метод авторизации на PHP
Примечание: мини-статья написана для новичков Давайте посмотрим вокруг: форумы, интернет магазины, гостевые книги и т.д. используют регистрацию и последующую авторизацию пользователей. Можно даже сказать, что это почти необходимая функция каждого сайта (только если это не домашняя страничка Васи Пупкина или не визитная карточка, какой-нибудь небольшой компании). Сегодня я хочу поделиться со всеми новичками информацией, о том, как лучше это все реализовать. 1. Модель (клиент) Регистрация - логин
• PHP: Введение в Zend Framework (продолжение)
Продолжаем рассказ о Zend Framework. В первой части статьи была описана концепция программной архитектуры MVC, рассмотрена структура типового веб-приложения, базирующегося на Zend Framework и выполнена демонстрационная реализация контроллера и вида на его основе. Во второй части будет раскрыта тема модели и приведен пример взаимодействия приложения с базой данных. Для печaти рекомендуется использовaть полную версию стaтьи в формaте PDF: zend-fw-intro.pdfАвтор: Роб Ален, http://akrabat.comОриги
• Web-разработка: Отслеживание исходящих ссылок с помощью Google Analytics
Google Analytics предоставляет широкие возможности по сбору и анализу статистики сайта, но, способ отслеживания исходящих ссылок, предлагаемый в справочном центре… …мягко говоря, не очень удобен. Поскольку сама возможность очень интересная, я решил все-таки использовать ее и при этом обойтись без прикрепления onclick к каждой внешней ссылке. План Можно, конечно, пройти по всем ссылкам на странице с помощью JavaScript и прикрепить к каждой соответствующий обработчик onclick, но это некрасиво, н
• CakePHP: Tips & tricks CakePHP #2
В связи с выходом пре-беты 1.2 второй выпуск tips&tricks. Продолжаем знакомить Вас с идеями и проблемами версии 1.2, особенностями пре-беты, с которыми мы встретились в процессе разработки социальной сети. Кроме того, мы завели себе блог на Хабре - присоединяйтесь, задавайте вопросы. Думаю, нам есть что обсудить.Новый core.php! Самое главное измение пре-беты – это новый формат файла core.php! Замените обязательно при обновлении этот файл и настройте его по усмотрению. В принципе, все описание
• Web-разработка: jQuery для JavaScript-программистов
Примечание: ниже расположен перевод статьи "jQuery for JavaScript programmers", в которой автор высказывает свое мнение об этой библиотеке, ориентируясь, в первую очередь, на продвинутых программистов, и приводит несколько десятков примеров ее использования.Когда jQuery увидела свет в январе 2006, я подумал: «очередная красивая игрушка». Выбор CSS-селекторов в качестве базиса было, конечно, изящной идеей (подробнее о ней в моей заметке getElementsBySelector), но использование цепочек преобразов
• Web-разработка: JavaScript: создание DOM фрагментов
Если приходилось когда-нибудь писать JavaScript и приходилось в JavaScript’е писать что-то вроде: var p = document.createElement( "p" ); p.appendChild( document.createTextNode( "Настоящий рыба фиш." ) ); var div = document.createElement( "div" ); div.setAttribute( 'id', 'new' ); div.appendChild( p ); то это может быть вам полезно. Проблема: когда создаёшь более, чем один элемент, вложенные друг в друга, код становится очень сложным. Предлагаю простой инструмент решения задачи — функцию create(
• PHP: Введение в Zend_Auth
В статье приведен обзор возможностей компоненты Zend_Auth, дающий общее представление о реализации пользовательской авторизации в приложениях на базе Zend Framework. В качестве основы приводимых примеров, использованы материалы статьи «Введение в Zend Framework». Примеры протестированы на Zend Framework версий 0.9, 0.9.1 и 0.9.2, и скорее всего будут работать с более поздними версиями, но не с более ранними. Автop: Рoб Алeн, http://akrabat.comОpигинaл:http://akrabat.com/zend-auth-tutorialПepe
• JavaScript: Объекты в JavaScript
Очередная статья для новичков, наставляющая на верный путь в разработке своих приложений на Javascript. Javascript, помимо стандартных возможностей, предоставляет массу способов использовать объектно-ориентированное программирование. Для этого существуют следующие способы: Оператор newЛитеральная нотацияКонструкторы объектовПрототипыАссоциативные массивыИспользуем оператор new Это, наверное, самый легкий способ создания объекта. Вы просто создаете имя объекта и приравниваете его к новому объект
• PHP: Программируем стартап Веб 2.0 на PHP
Итак, вы воодушевлены идеей стартапа Веб 2.0. Вы полагаете, что придумали что-то оригинальное и свежее. Вам видится эффектная реализация вашей идеи. Вы верите, что ваш проект произведет революцию на рынке. Если именно такие мысли занимают вас, самое время заняться бизнес-планом. Планирование бизнеса – это отдельная дисциплина и об этом можно найти множество литературы. Впрочем, если вы не имеете опыта составления бизнес-планов, лучше прибегнуть к помощи профессионалов. Чем хуже спрогнозирован
• Ruby: Знакомство с Ruby on Rails (часть 2)
В пpoдoлжeнии cтaтьи ”Пepвoe знaкoмcтвo c Ruby on Rails” мы нaучимcя paбoтaть c бaзoй дaнныx, и coздaдим кaтaлoг cтaтeй.Узнaeм кaк нaпиcaть плaгин, пoпpoбуeм иcпoльзoвaть AJAX и paccмoтpим нeкoтopыe пpoблeмы пpи paзвёpтывaнии пpилoжeния нa xocтингe.Нaчнeм c бaзы дaнныx.Я paбoтaю c MySQL, пoэтoму пpимepы уcтaнoвки будут для нeё.Пoльзoвaтeлям Windows нужнo cкaчaть и уcтaнoвить MySQL-5.0.Пoльзoвaтeлям Linux (Ubuntu) eщe пpoщe:$>sudo apt-get install mysql-server-5.0 libmysql-rubyПocлe