Папа, подари мне Яндекс

Понятно, что единственными людьми, у которых есть шанс получить в подарок поисковую систему Яндекс, являются дети Аркадия Воложа – все остальные конкретно в пролете по понятным причинам.

Сегодня мы не будем строить из себя олигархов, которые обладают деньгами, в количествах достаточных, чтобы купить Яндекс целиком и свести к нулю шансы детей Воложа получить Яндекс; сегодня мы будем играться в игру "Ощути себя Ильей Сегаловичем". Говоря простыми словами, будем разбираться, как своими руками сделать поисковую систему с поддержкой русской или другой морфологии (казахская, украинская, белорусская тоже под этот алгоримт подойдут, нужны будут только словари нужного языка). Замечу, что мы будем играть в игру, а не писать полноценный поисковик по Рунету, поэтому своих детей придется лишний раз угостить мороженным, чтобы не плакали, что вы им вместо Яндекса подарили его упрощенную модель, пусть и работающую.

Отказ от ответственности и условия использования материала, представленного в статье

Любезные друзья, статья будет длинной, и с условием, что я (в сравнении с некоторыми) слабо соображаю в том, о чем пишу, хочется сразу же сказать, что я:

не отвечаю за конкретные реализации описанной ниже модели работы поисковой системы и абсолютно не гарантирую, что любая коммерческая реализация поисковой системы, сделанная по ниже описанным принципам будет работать и тем более приносить деньги;

не предоставляю конкретных реализаций библиотек ни на одном языке программирования, ставьте задачу своему программисту или отделу разработки, пусть пишут, они за это деньги получают;

не предоставляю частных консультаций по воплощению в жизнь того, что будет написано ниже;

не предоставляю статистики запросов моих поисковых систем, любой другой статистики;

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

загрузка...

 

 

Я практик, живущий сегодняшним днем. Мои поисковые системы работают, мощностей хватает, результатами я доволен. Мне этого достаточно;

не предоставляю словарей, с которыми работаю, ищите сами, это несложно, возьмите за основу хотя бы ispell;

не рассказываю, как сделать своего бота, который ходит по сайтам и качает странички, читайте доку по CURL;

не рассказываю, как очистить то, что получил индексирующий бот, от мусора, типа, Javascript'a и HTML. В сети есть нужные библиотеки;

даже не представляю себе, как сделать так, чтобы индекс поисковой системы хранился на нескольких физических серверах;

я челочек безграмотный, в тексте статьи могут быть ошибки, которые на смысл в принципе влиять не должны;

если вы хотите разместить эту статью у себя на сайте, сохранение ссылок внутри статьи, сохранение структуры, включая вступительную часть, и ссылка на оригинал обязательна.

I. Немного фактов, которые лежат на поверхности

(Для программистов: читайте внимательно, я начинаю частично описывать действия, которые должны находить свое отображение в программе)

1. Возьмите какой-нибудь абзац текста, например:
Илья Валентинович Сегалович — российский программист и общественный деятель, один из основателей (вместе со своим другом и одноклассником Аркадием Воложем) компании «Яндекс», ныне технический директор компании. Компания «Яндекс» — лидер на рынке поиска в России.

2. Выкидываем (Илья и Аркадий, уж простите) из абзаца имена собственные, например, пользуясь словарем имен собственных, получаем:
российский программист и общественный деятель, один из основателей (вместе со своим другом и одноклассником) компании «Яндекс», ныне технический директор компании. Компания «Яндекс» — лидер на рынке поиска в России.

3. Убираем все стоп-слова (заведите себе словарик стоп-слов), предлоги, союзы и др:
российский программист общественный деятель, один основателей (вместе своим другом одноклассником) компании «Яндекс», ныне технический директор компании. Компания «Яндекс» — лидер рынке поиска России.

4. Запятые, точки, тире, черточки, двоеточия, скобки, елочки, циферки заменяем на пробелы, двойные пробелы удаляем:
российский программист общественный деятель один основателей вместе своим другом одноклассником компании Яндекс ныне технический директор компании Компания Яндекс лидер рынке поиска России

Имеем еще вполне осмысленный набор слов. Пишем слова в столбик, приводим в один регистр и приводим рядом пару-тройку однокоренных слов (для сравнения):

Что бросается в глаза? Неужели ничего? Показываю:

Для того чтобы приближенно получить корни слов, я отрезал часть. Т.к. резал лично я, то и получилось, что резал я более или менее «правильно» (в определенном смысле этого слова), ниже я покажу, как ПОЧТИ наверняка правильно резать при помощи программы.

Если упорно делать так, как делаю я, т.е. напрочь забыть про правила русского языка, то считайте, что несложный морфологический поиск по маленькой базе тестов у вас уже есть. Правда, он реализован методом лобовой атаки, но уже можно гордо смотреть своему сынишке в глаза, т.к. альфа-релиз поиска практически состоялся, поиск будет работать, независимо от того, с каким окончание будут попадать слова в исходный запрос. Всего лишь, что нужно сделать в программе:

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

с поступающим в систему запросом сделать такую же махинацию, потом от каждого слова, которое приехало в поисковом запросе, отрезать чуть-чуть букв спереди и сзади, у очень длинных слов режем 2-3 буквы сначала 3-4 с конца, у просто длинных – 3-4 с конца, у средних – 2 с конца, у коротких – 1 или вообще ни одной. Слова из 3-х букв, включая самое известное, можно вообще из запроса выкидывать, если они не находятся в специальном словаре невыкидываемых слов. После этого вы получите окончательный запрос, например, из «российский программист основатель Яндекса»
вы получите
«российс програм основат Яндек».

А дальше идем в свою базу и делаем запрос к тем данным, которые сохранили несколько раньше. Какой вы там запрос напишите, мне все равно, главное, чтобы в конце было что-то похожее:

where prepared_text LIKE '%российс%' AND prepared_text LIKE '%програм%' AND prepared_text LIKE '%основат%' AND prepared_text LIKE '%Яндек%'

Надеюсь, понятно, что в prepared_text лежит обработанный на предыдущих этапах текст? На самом деле можно вообще делать запрос и по необработанному тексту. Простенько, со вкусом, все достаточно неплохо работает, и мухи не кусают...

Очень слабенькая необходимость что-то усложнять и оптимизировать появится тогда, когда количество записей с текстом, по которому идет поиск, будет превышать 50 000, а в текстах будет по 500-1000 знаков, причем, поиск будет осуществляться 1-2 раза в минуту, правда, у меня выделенный сервер, и когда наступит необходимость что-то оптимизировать на виртуальных хостингах, мне неизвестно.

Все! Поиск написан, теперь все ждут моей следующей статьи про написание собственной системы контекстной рекламы, после чего пишут ее и вешают на поиск, зарабатывают, как Гугл, по 1 млрд. долларов в месяц, попивая малибу, пребывая на одном из тихоокеанских островов. Я уже там, присоединяйтесь.

Надеюсь, все поняли, что в предыдущем абзаце содержалась тонкая шутка. Работа еще не закончена! Пока ваш программист переваривает первую часть задания по написанию поисковой системы, ищем, как ему усложнить жизнь, если он не читал мои старые статьи про регулярные выражения, и как ему упростить жизнь, если читал.

Оказывается, можно попробовать резать слова не по количеству букв, а по шаблону. В шаблон должны входить самые распространенные окончания:
ий, ая, ые, ов, ям, ями
и много других.

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

Я вам клянусь, что после того, как я реализовал свой морфологический поиск до этого шага (поиск через LIKE), он сразу же начал успешно работать на сайте «Есть работа в Киеве!» (тогда еще только в Киеве). Сразу же на базе библиотеки, которая вытворяла финты по манипуляции с данными в БД, была написана подписка на вакансии и резюме, которая выдавала достаточно точные результаты.

У подобного поиска есть два больших минуса:

- при больших объемах он нагружает сервер;
- маленькие слова часто умещаются в большие слова и по поиску через LIKE находятся именно большие слова, которые не имеют отношения к маленьким.

Сразу отвечу на вопрос, а почему я не пользуюсь полнотекстовым поиском MYSQL или PostgreSQL. Да все потому, что алгоритм этого поиска от меня не зависит, т.е. я вряд ли сяду переписывать алгоритм полнотекстового поиска целой СУБД под свои нужды с учетом своих требований. Я в прошлом вебпрограммист, а не программист на C++, а сейчас вообще не программист, поэтому осваивать новый язык, лезть в готовый продукт не намерен, но поиск, заточенный под свои проекты, иметь хочется.

Пусть СУБД управляет и хранит данные, а я уже найду способ обратиться к СУБД так, чтобы она выдавала мне нужные данные. Хотя стоит заметить, что в СУБД полнотекстовый индекс, скорее всего, будет реализован подобным способом, про который я собираюсь писать дальше, но врать не буду, внутрь СУБД не смотрел.

Какие алгоритмы улучшения релевантности поиска могут быть на данном этапе? Т.к. в вашей базе, скорее всего, нет произведений дорвейщиков с гордым названием «сайты для людей», т.е. доры, да и сайтов немного, то однозначно можно и нужно полагаться на внутренние факторы, например, на количество найденных слов из запроса внутри текста. Т.е. в запросе было слово «программист», если в каком-то из текстов это слово найдено большее количество раз, то этот текст двигаем в результатах поиска наверх. Если база текстов, как у меня, специализированная, то у текстов могут быть другие показатели релевантности, например, на Jobcast'e, украинской поисковой системе по вакансиям и резюме, уже работает фактор времени размещения объявления, я собираюсь дополнительно ввести фактор заработной платы, поднимая вверх те вакансии и резюме, у которых проставлен уровень заработной платы.

II. Пытаемся написать взрослый поиск

Думаю, что ваш программист уже очухался от предыдущего задания и его снова можно загрузить. После первого этапа можно приступать ко второму, все знания у вас уже есть, теорию в голову вложили. Хотя еще немного теории не помешает.

Основой (костяком) любого текста являются существительные, местоимения и глаголы, на прилагательные, наречия, предлоги, союзы по большому счету можно не смотреть. Для качественной работы с текстами можно и нужно искать словари, в которых есть флаги, указывающие на часть речи каждого конкретного слова.

Как было видно в первой части, для реализации поиска было сделано две вещи:

- обработка текста;
- обработка запроса.

Смутно догадываюсь, т.к. в этой области я вообще не силен, и мои познания в русском языке ограничиваются школьной программой, что что-то подобное называется «нормализацией», или «лемматизацией», т.е. когда и тексты и запросы приводятся в нормальную (начальную – прим. редакции) форму. Нормальной формой для глаголов будет инфинитив, или неопределённая форма глагола, для существительных — первое лицо, единственное число, про другие части речи поищите сами (для местоимений – в зависимости от типа; для прилагательных и причастий – это первое лицо, единственное число, мужской род; наречия не изменяются вообще – прим. редакции).

То, что я привел выше, конечно, не является полным приведением в начальную форму. Полным приведением текста в начальную форму будет поиск всех соответствий между словами в различных формах и начальную формами этих слов, т.е. в результате всех действий наш список ДОЛЖЕН превратиться в такой:

Как это сделать?

При помощи словаря и словаря типичных окончаний (последних букв) частей речи, которые соответствуют разным частям речи. Для существительных словарь последних букв (суффиксов – прим. редакции) может выглядеть так (неполный список):
ар, ер, ист, ол, арь, яр, ор, ив, ик, ант, ель, лиг, ес, ог, ент, ат, ен, аф;

При помощи словаря и таблицы соответствий слов в словаре. Т.е. в этой таблице будет записано, что слово Х является начальной формой слов Y, Z, K.

Словарь типичных окончаний иметь в любом случае нужно, чтобы вовремя выявлять и заносить в словарь неологизмы, т.е. новые для словаря слова и их различные формы.

Если вы поняли все, что написано выше, и знаете, что можно сделать с текстом и с запросом, то самое время ввести понятие «индексация текста».

Я догадываюсь, что у вас есть целый комплекс, через который данные из вне попадают в базу данных. Для того чтобы нормально работать с этим текстом во время поиска, как это было описано выше, неплохо было бы все слова текста привести в нормальную форму. Пока, не задавая вопросов, делаем это, на выходе получаем список, подобный приведенному выше. Удаляем из него дубликаты, предварительно посчитав, сколько раз в тексте было упомянуто конкретное слово пусть даже в разных формах. Получаем соответствие между конкретным текстом, у которого в базе есть свой идентификатор, ссылка и др., и словами в начальной форме, которые есть в этом конкретном тексте.

Смею заверить, что если вы работаете с базой данных, которая хранится в компьютере, то компьютер работает гораздо лучше с цифрами, чем с буквами, поэтому список начальных слов, полученных для текста, лучше перевести в список цифровых идентификаторов, после чего по всем полям таблицы, в которые внесены эти идентификаторы, сделать index (см. доку к своей СУБД – это не поисковый индекс), чтобы позже было проще делать всякие JOIN'ы, сложные выборки и т.д.

Вы спросите, каким образом присвоить цифровой идентификатор конкретному слову, которое содержит нормальную форму? Отвечаю! Я делаю CRC32 слова. Т.е. в конце всех преобразований я получаю таблицу, в которую скидываю CRC32 начальные формы слова из текста

| идентификатор странички с текстом | количество таких слов в конкретном тексте |

Точно такой же идентификатор содержится в табличке со словарем реальных слов. Теперь мы можем соотносить цифровые индексы в таблице индексов и слова в поисковом запросе.

Можете доставать лобзик с выжигателем по дереву и пилить себе из фанерки медальку «За построение поискового индекса!» Третьей Степени, т.к. только что вы построили индекс начальных форм слов из конкретно взятого текста. Теперь при поступлении поискового запроса в систему его надо тоже быстренько проиндексировать (т.е. получить на выходе набор циферок, содержащих CRC32 начальных форм слов, введенных в поисковый запрос) и искать по базе индексов.

Поверьте, такой финт разгрузит вашу БД, т.к. поиск не будет проходить через LIKE – он будет проходить по заранее подготовленному индексу, в процессе поиска не будут принимать участие буквы, а только цифры, что даст возможность СУБД оптимизировать свои внутренние процедуры и выполнять максимально простые операции, а значит, делать это быстро.

Что можно улучшить? Уважаемые, улучшить — это значит нагрузить БД. Т.е. улучшать нужно только в том случае, если на том количестве данных, которое валяется у вас в базе данных, выборка становится некачественная. Скажу сразу, что на большом количестве данных, скорее всего, вы столкнетесь с проблемой дублей.

Дубли бывают четкие и нечеткие. При четких дублях все начальные формы слов двух разных текстов совпадают, при нечетких – специалисты по поисковой оптимизации старались менять порядок слов в предложениях, заменять слова синонимами, добавлять разговорные обороты, сравнения, насыщать текст прилагательными и т.д., но исходный и конечный тексты остаются похожими.

Пример:
Текст 1. Компании, расположенной в центре Киева, которая занимается разработкой программного обеспечения, необходим опытный Java-программист. Вас ожидает работа в дружном коллективе, два монитора на столе, чай, кофе, бутерброды за счет компании.

Текст 2. Нам нужен опытный программист на Java. Замечательные условия труда:

отличный коллектив;

офис находится в центре Киева;

чай, бутерброды и кофе за счет компании;

два монитора на столе, любой ноутбук на выбор.

С точки зрения человека, это практически дубли, с точки зрения компьютера, нечеткие дубли. Если натравить индексатор на эти два текста, то множества начальных форм слов будут сильно пересекаться. Множество нормальных форм слов, которые входят в оба объявления, выглядит приблизительно так:

Как бороться с четкими дублями?
Бороться с четкими дублями достаточно просто. Если взять сумму индексов слов в объявлении и найти другие объявления, где эта сумма такая же, то получаем множество четких дублей. Индекс слова представляет из себя CRC32 самого слова и выражен числом. Вероятность, что во всей базе будет другое объявление, составленное из тех же слов, но имеющее другой смысл, минимальна. Также минимальна вероятность того, что другие слова из абсолютно непохожего объявления дадут такую же сумму (в результате сложения CRC32 слов, или, по-другому, индексов слов, получаются числа с 7-8 разрядами).

На сегодня у меня есть полностью готовые системы поиска, которые имеют функционал фильтрации четких дублей. Т.е., чтобы вы были уверены, что до этого шага, на котором я только что прервался, я уже дошел, поэтому все еще пишу с некоторым пониманием того, о ЧЕМ пишу, и держу в уме свои практические наработки.

Как бороться с нечеткими дублями?
Для разборок с нечеткими дублями нужен функционал по работе с множествами – там контрольными суммами уже не обойтись. Придется серьезно начинать работать в сторону увеличения количества данных, которые появляются в результате индексации. Т.е. тупого набора нормальных форм слов, превращенных в их контрольные суммы при помощи функции CRC32, уже не достаточно. Скорее всего, необходимо будет выделять костяк объявления, построенный исключительно из существительных, глаголов и наиболее часто встречающихся их синонимов. Т.е. намек должен быть понятен. Придется запастись словариком синонимов, вернее не словариком, а таблицей отношений, в которой CRC32 одного слова будет указывать, что начальная форма слова с такой контрольной суммой является синонимом начальной формы слова с другой контрольной суммой (сами слова можно не хранить). Также, скорее всего, будет необходимо в момент индексации разделять тексты на абзацы и законченные предложения, чтобы анализировать перестановки абзацев и предложений. Собственно, вы придете к тому, что у вас будет еще одна или две таблицы, в которые будут внесены цепочки слов, которые составляют костяк абзацев и предложений, которые в них входят (с привязкой к конкретному тексту и с учетом синонимов).

Какие факторы могут влиять на позиции разных текстов в таком поиске?

дубль или не дубль. Если понятно, что найденный текст является нечетким дублем другого текста, то, возможно, его нужно будет показать в дополнительных результатах к исходному тексту (такой себе home made supplemental results):

расстояние между словами из поискового запроса в тексте и (!) вхождение их в одно предложение или в один абзац (что менее приоритетно). Для этого придется во время индексирования искать позицию каждого слова и заносить ее в таблицы с индексами (либо вообще в отдельную таблицу);

порядок следования слов в запросе. По желанию можно дать разные веса словам из поискового запроса, чтобы потом, опираясь на это, выводить правила ранжирования найденного текста;

учет частоты употребления слов, когда выше поднимаются тексты, где совпадают редкие слова;

время обновления контента;

индекс актуальности контента (текста). Т.е., если вы обладаете такими данными, как заходят ли на страницу с текстом пользователи, откуда заходят, уходят ли и, если уходят, то куда, по каким запросам из внешних поисковых систем заходят люди, заходят ли с форумов и блогов, то можно делать свой индекс актуальности контента;

в специализированных поисковых системах могут быть свои специфические факторы;

можно применить известные алгоритмы ранжирования (вспоминаем всякие PR'ы и вИЦы).

Все! Бегите к гравировщику и заказывайте медальку «За построение поискового индекса!» Второй Степени. Строить индекс другой, т.е. Первой степени не будем, т.к. это слишком сложно и доступно только Илье Сегаловичу, хотя по наблюдениям доступно не всегда.

III. Премудрости и нюансы по эксплуатации собственного поискового движка

Актуализация индекса

Поисковая система на этом этапе УЖЕ представляет из себя практически живой организм, который намерен вырваться из компьютера и захватить весь мир. Чтобы не вызывать Крепкого орешка и Терминатора для борьбы с искусственным интеллектом, вам необходимо поддерживать его комфортную жизнь внутри системы. Первым и, думаю, главным действием по обеспечению жизни системы является актуализация индекса. Она состоит из:

борьбы со спамом (у меня такого добра уже много). Необходимо удалять его из индекса и с сайта (сайтов);

борьбы с дубликатами, которую я достаточно подробно описал выше;

периодические проверки наличия контента и соответствия его индексу, т.е. надо следить, а есть ли еще тот контент на сайтах, который находится у вас в индексе, также нужно переиндексировать контент при его изменении, чтобы обновить индекс.

Про признаки спама и борьбу с ним при помощи подручных средств на своих сайтах я расскажу позже в отдельной статье, когда в очередной раз напьюсь до состояния нестояния и меня пробьет на откровения.

Препроцессор, он же Колдунщик

Понятно, что эту статью читают люди, которые по роду своей деятельности выполняют работу шаманов, поэтому то, что нормальные люди называют препроцессором поисковых запросов, они (шаманы) называли Колдунщик. Если вы пишете специализированный поиск, то, скорее всего, в базе у вас будет бесконечное множество различных дополнительных признаков контнета, которые вы можете привязать к конкретным запросам. Например, в Jobcast'е, моей поисковой системе по вакансиям и резюме в Украине, запрос «резюме программиста в Киеве» проходит обработку, в результате которой слово «резюме» убирается и преобразовывается в фильтр where vacancy = 0, а часть запроса «в Киеве» преобразовывается в фильтр AND city_id = 7. Для оставшегося слова «программиста» находится начальная форма, и происходит поиск по индексу с учетом фильтров.

Кеш
Понятно даже ежику, что на частотных запросах система все равно будет впустую лопатить кучу данных. Произойдет это тогда, когда частота подачи в систему какого-то одного и того же запроса превысит частоту актуализации и обновления данных, которые выдаются по этому запросу.

Изначально при написании поиска в систему должен быть заложен функционал по логгированию поисковых запросов, а также предусмотрены кеши результатов этих запросов. Таким образом, вы получите возможность перестраивать кеш в моменты наименьшей нагрузки на систему, замораживая выдачу в бизнес время. Кеш также поможет отфильтровывать тексты, когда они еще не попали в результаты поиска.

Количество результатов, пользователи и другие нюансы
В общем случае не имеет смысла выдавать больше 50-ти результатов поиска. Это приблизительно то число результатов, которое максимально просматривает нормальный человек (чаще это число еще меньше). Яндекс может себе позволить выдавать больше, а вам я не советую зря напрягать свое железо.

Советую учить своих пользователей, как пользоваться вашим поиском, предоставляя им удачные примеры эффективных именно в вашей системе поисковых запросов. Всегда найдется товарищ, который в поисковую систему по вакансиям и резюме введет известное слово из трех букв и будет кричать, что система не выдает релевантных результатов. Ваша задача не ублажать идиотов, а предоставить удобный инструмент для своих пользователей.

Каждый писатель поисковых систем рано или поздно наступает на грабли XSS. Самый простой пример – фраза «результатов по запросу тут_ идет_запрос нет». Внедрить в запрос валидный html-код, чтобы получить ссылку с ваших сайтов или угнать куки, не составит большого труда. Именно поэтому фильтруйте то, что выводите пользователю в качестве первоначального поискового запроса.

Собаководы-профессионалы, которые тоже изредка пописывают подобные системы, советуют дополнительно фильтровать запросы, поступающие в систему, чтобы по некоторым из них не показывать контекстную рекламу или вообще ничего не показывать (даже сообщения об ошибке). Для этого заводится отдельный словарик стоп-запросов.

Сергей Колесниченко, "Есть работа в Киеве!"

Статья получена: www.SeoNews.ru

загрузка...