Классификация

По области поиска (условно)

Локальные

Предназначены для поиска информации по какой-либо части всемирной сети, например по одному или нескольким сайтам, либо по локальной сети .

Глобальные

Предназначены для поиска информации по всей сети Интернет либо по значительной её части. Представителями таких поисковых машин являются поисковые системы Google , Яндекс и т. п. Поисковые машины осуществляют поиск информации различного типа, например текстов, видео, изображений, географических объектов, персональных данных и др. При этом файлы, с которыми может работать поисковая машина, могут быть как текстового формата (например.html, .htm, .txt, .doc, .rtf…), так и графического (.gif, .png, .svg…) или мультимедийного (видео и звук). Пока наиболее распространённым является именно поиск по текстовым документам.

Поисковый запрос

Исходной информацией для поиска является поисковый запрос .

Функции

Поисковые машины выполняют несколько функций:

Поиск ссылок

Поиск ссылок на страницы и другие документы сайтов.

Автоматический

Ручной режим

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

Индексация документов сайтов

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

Поиск по базе данных проиндексированных документов

Может состоять из нескольких этапов

Нахождение документов, соответствующих поисковому запросу

Ранжирование документов в соответствии с их релевантностью поисковым запросам

Кластеризация документов

Примечания

См. также

Поисковые машины (список)
Общие
Региональные

Accoona (Китай/США) Alleba (Филиппины) Ansearch (Австралия/США/Великобритания/Новая Зеландия) Апорт (Россия) Daum (Юж. Корея) Guruji.com (Индия) Поиск@Mail.Ru (Россия) Maktoob (Бл. Восток) Meta.ua (Украина) Miner.hu (Венгрия) Najdi.si (Словения) Onkosh (Бл. Восток) Рамблер (Россия) Rediff (Индия) SAPO (Португалия) Search.ch (Швейцария) Sesam (Норвегия/Швеция) Walla! (Израиль)

…лидеры
Тематические
Метапоиск

AskNet.ru Brainboost Clusty Dogpile FarSEER exactus.ru Excite HotBot Info.com Ixquick Krozilo Mamma Metacrawler MetaLib Нигма Myriad Search SideStep Surfwax Turbo10 WebCrawler GlobalFileSearch

Открытые /
свободные
Детские

AGAKIDS (Россия) Ask Kids (Великобритания) Frag Finn (Германия) Kids AOL (США) Kids Yahoo! (США) Quintura Дети (Россия) Семейный Яндекс (Россия) Гогуль (Россия)


Wikimedia Foundation . 2010 .

Смотреть что такое "Поисковая машина" в других словарях:

    Поисковая машина - (searching engine): веб сервер, проводящий индексацию веб страниц на доступных серверах (например, Yandex)... Источник: ИНТЕРНЕТ РЕСУРСЫ. ТРЕБОВАНИЯ ДОСТУПНОСТИ ДЛЯ ИНВАЛИДОВ ПО ЗРЕНИЮ. ГОСТ Р 52872 2007 (утв. Приказом Ростехрегулирования от… … Официальная терминология

    поисковая машина - Веб сервер, проводящий индексацию веб страниц на доступных серверах (например, Yandex). [ГОСТ Р 52872 2007] Тематики информационные технологии в целом EN searching engine … Справочник технического переводчика

    В Интернет специальный веб сайт, на котором пользователь по заданному запросу может получить ссылки на сайты, соответствующие этому запросу. Поисковая система состоит из трех компонент: 1 поискового робота; 2 индекса системы; и 3 программы,… … Финансовый словарь

    В Internet поисковая машина, которая: отсылает запрос на поиск в несколько поисковых систем; и генерирует из полученных ответов сводку (на одной странице). По английски: Meta search engine Синонимы: Мета гусеница Синонимы английские: Metacrawler… … Финансовый словарь

    Эта статья должна быть полностью переписана. На странице обсуждения могут быть пояснения. Поисковая система программно аппаратный комплекс с веб интерфейсом, предоставляющий возможност … Википедия

    Поисковая система - – (англ. search engine, синонимы: искалка, поисковый сервер, поисковая машина) – Инструмент для поиска информации в Интернете. Как правило, работа поисковой машины состоит из двух этапов. Специальная программа (поисковый робот, автомат, агент,… … Энциклопедический словарь СМИ - Поисковая система веб сайт, предоставляющий возможность поиска информации в Интернете. Большинство поисковых систем ищут информацию на сайтах Всемирной паутины, но существуют также системы, способные искать файлы на ftp серверах, товары в… … Википедия

Книги

  • К вопросу об эффективности поиска конкретики в Интернете , И. А. Семёнов. Согласно исследованиям Berkley, объём информации в Интернете по состоянию на 2003 год оценивался в 258, 85 терабайта, и это только общедоступные данные. По данным Internet World Stats, рост… электронная книга

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

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

История создания

Считается, что создателем первого поискового движка выступил Алан Эмтейдж (Alan Emtage). В 1989 году он работал в университете Макгилла в Монреале, куда переехал из родного Барбадоса. Одной из его задач как администратора университетского факультета информационных технологий было нахождение программ для студентов и преподавателей. Чтобы облегчить себе работу и сэкономить время, Алан написал код, который выполнял поиск за него.

«Вместо того чтобы тратить свое время на брожение по FTP-сайтам и пытаться понять, что на них есть, я написал скрипты, которые делали это за меня, - рассказывает Алан, - и делали быстро».

<поле>:<необязательный пробел><значение><необязательный пробел>
Запись <поле> могла принимать два значения: User-agent или Disallow. User-agent конкретизировала имя робота, для которого описывалась политика, а Disallow определял разделы, к которым закрывался доступ.

Например, файл с такой информацией запрещает всем роботам доступ к любым URL с /cyberworld/map/ или /tmp/, или /foo.html:

# robots.txt for http://www.example.com/ User-agent: * Disallow: /cyberworld/map/ # This is an infinite virtual URL space Disallow: /tmp/ # these will soon disappear Disallow: /foo.html
В этом примере закрывается доступ к /cyberworld/map для всех роботов, кроме cybermapper:

# robots.txt for http://www.example.com/ User-agent: * Disallow: /cyberworld/map/ # This is an infinite virtual URL space # Cybermapper knows where to go. User-agent: cybermapper Disallow:
Этот файл «развернет» всех роботов, которые попробуют получить доступ к информации на сайте:

# go away User-agent: * Disallow: /

Бессмертный Archie

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


Несмотря на тот факт, что Archie - это поисковый движок, он все же предлагает несколько функций для настройки поиска. Помимо возможности указать базу данных (анонимные FTP или польский веб-индекс), система предлагает выбрать варианты трактовки введенной строки: как подстроку, как дословный поиск или регулярное выражение. Вам даже доступны функции по выбору регистра и три опции по изменению вариантов отображения результатов: ключевые слова, описание или ссылки.


Также имеются несколько опциональных параметров поиска, которые позволяют более точно определить необходимые файлы. Имеется возможность добавления служебных слов OR и AND, ограничение области поиска файлов определённым путем или доменом (.com, .edu, .org и др.), а также задание максимального числа выдаваемых результатов.

Хотя Archie очень старый поисковый движок, он все же предоставляет довольно мощную функциональность при поиске нужного файла. Однако по сравнению с современными поисковыми системами, он крайне примитивен. «Поисковики» ушли далеко вперед - достаточно лишь начать вводить желаемый запрос, как система уже предлагает варианты поиска. Не говоря уже об используемых алгоритмах машинного обучения.

Сегодня машинное обучение представляет собой одну из главных частей поисковых систем, таких как Google или «Яндекс». Примером использования этой технологии может быть ранжирование поиска: контекстуальное ранжирование, персонализированное ранжирование и др. При этом очень часто применяются системы Learning to Rank (LTR).

Машинное обучение также позволяет «понимать» запросы, вводимые пользователем. Сайт самостоятельно корректирует написание, обрабатывает синонимы, разрешает вопросы многозначности (что хотел найти пользователь, информацию о группе Eagles или же об орлах). Поисковые системы самостоятельно учатся классифицировать сайты по URL - блог, новостной ресурс, форум и т. д., а также самих пользователей для составления персонализированного поиска.

Прапрадедушка поисковых движков

Archie породил такие поисковые системы, как Google, потому в какой-то мере его можно считать прапрадедушкой поисковых движков. Это было почти тридцать лет назад. Сегодня индустрия поисковых систем зарабатывает порядка 780 миллиардов долларов ежегодно.

Что касается Алана Эмтейджа, то когда его спрашивают об упущенной возможности разбогатеть, он отвечает с долей скромности. «Разумеется, я бы хотел разбогатеть, - говорит он. - Однако даже с оформленными патентами я мог бы и не стать миллиардером. Слишком легко допустить неточности в описании. Иногда выигрывает не тот, кто был первым, а тот, кто стал лучшим».

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

Когда нетпиковец сталкивается с задачей, требующей временных затрат (например, создать проект Звезды смерти или построить компактный аппарат холодного ядерного синтеза), он в первую очередь думает, как автоматизировать эту работу. Результаты таких размышлений мы собираем на cпециальной странице нашего сайта. Сегодня мы расскажем о том, как в недрах агентства Netpeak рождается новый полезный сервис.

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

Задача

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

Нашей задачей было сделать так, чтобы все варианты запросов — как правильные, так и с ошибками — вели на одну страницу. Например, для каждого из запросов baseball, basaball, baaeball, baselball были свои страницы, а нужно было сделать так, чтобы все варианты сходились на одну страницу с правильным запросом — baseball. В таком случае страница будет соответствовать правильной форме запроса и мы сможем избавиться от мусора в выдаче.

Примеры групп:

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

Цель

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

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

Как рождался новый метод

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

Что это значит? Мы определяем вероятность встретить слово в языке и для каждого слова находим вероятности допустить в нем разные ошибки. Все бы ничего, и теория тут красивая, но для сбора такой статистики нужно иметь огромный размеченный текстовый корпус для каждого языка (опять же, ближе всего к этому подошли поисковики). Естественно, возникли вопросы, как это делать и кто все это будет воплощать в код. До нас подобным делом никто не занимался (если знаете кейс — киньте ссылку в комментарии), поэтому методику разрабатывали с нуля. Было несколько идей и заранее не было очевидно, какая из них лучше. Поэтому мы ожидали, что разработка будет вестись циклически — подготовка идеи, реализация, тестирования, оценка качества, а затем решение — продолжать дорабатывать идею или нет.

Реализацию технологии можно условно разбить на три этапа. О каждом из них — подробнее.

Этап №1. Формирование проблемы. Первые грабли

Внимание! После этой строки будет много терминов, которые мы постарались объяснить максимально простым языком.

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

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

Расстояние Левенштейна показывает, какое минимальное количество изменений (удаление, вставка и замена) в строке А надо сделать, чтобы получить строку В.

  • Замена символа: sh[e]res — sh[i]res, sh[o]res;
  • Вставка символа: sheres — s[p]heres;
  • Удаление: gol[d][f] — golf, gold.

В каждом из примеров расстояние между словом с ошибкой и правильной формой — 1 исправление.

Коэффициент Жаккарда на би- и триграммах помогает выяснить, сколько общих комбинаций из двух- или трехсимвольных слогов есть у строк А и В.

Пример: пусть мы рассматриваем строки A = snowboard и B = border. Общая формула коэффициента для биграмм имеет вид:

J = (число одинаковых биграмм для А и В) / (общее число биграмм в А и В)

Разобьем строки на биграммы:

биграммы для A = { sn, no, ow, wb, bo+, oa, ar, rd+ } - 8 штук; биграммы для B = { bo+, or, rd+, de, er } - 5 штук; Плюсиками отмечены одинаковые биграммы их 2 штуки - bo и rd.

Для триграмм будет аналогично, только вместо двух букв будут использоваться три. Коэффициент Жаккарда для них будет такой:

Пример более похожих слов:

А = baseball и В = baaeball { ba+, as, se, eb+, ba+, al+, ll+ } { ba+, aa, ae, eb+, ba+, al+, ll+ } J = 5 / (7 + 7 - 5) = 0.56

Хотя коэффициент Жаккарда и работает быстрее, но не учитывает порядок слогов в слове. Поэтому использовался в основном для сравнения с расстоянием Левенштейна. Теоретически, тут все было просто. Методики кластеризации для малых данных решаются достаточно легко, но на практике оказалось, что для завершения разбивки нужны либо огромные вычислительные мощности, либо — годы времени (а в идеале — и то, и другое). За две недели работы был написан скрипт на Python. При запуске он читал фразы из файла и выдавал списки групп в другой файл. При этом, как и любая программа этот скрипт грузил процессор и использовал оперативную память.

Большинство испытанных методов требовали терабайтов памяти и недели процессорного времени. Мы же адаптировали методы так, чтобы программе хватало 2 гигабайта памяти и одного ядра. Впрочем, миллион запросов обрабатывался примерно 4-5 дней. Так что время выполнения задачи все равно оставляло желать лучшего. Результат работы алгоритма на небольшом примере можно представить в виде графика:

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

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

Этап №2. Упрощение. Новая надежда

Мы переделали алгоритм, приблизив его к традиционным механическим корректорам грамматики. Благо, таких достаточно. В качестве базы была выбрана библиотека для Python — Enchant. В этой библиотеке есть словари практически для любого языка мира, в использовании она довольно проста, и есть возможность получить подсказки — что на что нужно исправлять. В ходе предыдущего этапа мы многое узнали о видах запросов и о том, на каких языках могут быть эти запросы.

Из открытого доступа были собраны следующие словари:

  • английский (Великобритания);
  • английский (США);
  • немецкий;
  • французский;
  • итальянский;
  • испанский;
  • русский;
  • украинский.
  1. Если оно правильное (находится в одном из словарей) — оставляем его как есть;
  2. Если оно неправильное — получаем список подсказок и берем первую попавшуюся;
  3. Все слова вновь склеиваем в фразу. Если такой фразы мы раньше не встречали, то создаем для неё группу. Исправленная форма фразы становится её «центром». Если же встречали, то значит для этой фразы уже есть своя группа, и мы добавляем туда новую ошибочную форму.

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

Этап №3. Дополнения и пробуждение Силы

Проблема транслитерации решилась довольно просто и традиционно. Во-первых, сделали словарик соответствия букв кириллицы и латиницы.

В соответствии с ним преобразовали каждую букву в проверяемых словах и отметили, есть ли для полученного слова исправление по словарю. Если вариант с транслитерацией имел наименьшее количество ошибок, то мы выбирали его как правильный. А вот имена собственные — тот еще орешек. Самым простым вариантом пополнить словари оказался сбор слов из дампов Википедии. Однако и в Вики есть свои слабые места. Слов с ошибками там довольно много, а методика их фильтрации еще не идеальна. Мы собрали базу слов, которые начинались бы с большой буквы, и без знаков препинания перед ними. Эти слова и стали нашими кандидатами в имена собственные. Например, после обработки такого текста подчеркнутые слова добавлялись в словарь:

При внедрении алгоритма оказалось, что для поиска подсказок в дополненном словаре Enchant иногда требуется больше 3 секунд на слово. Чтоб ускорить этот процесс, была использована одна из реализаций автомата Левенштейна .

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

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

На изображении представлен автомат для слова food со всевозможными двумя ошибками. Стрелка вверх означает вставку символа в текущую позицию. Стрелка по диагонали со звездочкой — замена, с эпсилон — удаление, а по горизонтали — буква остается без изменений. Пусть у нас есть слово fxood. Ему будет соответствовать путь в автомате 00-10-11-21-31-41 — что равносильно вставке в слово food буквы x после f.

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

Что в итоге?

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

На создание кода и его испытания в общем ушло 40 часов работы математика-аналитика. Вывод: если вам однажды понадобится обработать около двух миллионов запросов — не отчаивайтесь. Такие задачи можно автоматизировать. Понятно, что добиться 100% точности будет очень сложно, но обработать корректно хотя бы 95% процентов информации — реально.

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

    Создание полноценного поискового движка сайта по сложности, стоимости и срокам превосходит создание большого сайта.

    Данное утверждение может показаться неожиданным. На многих сайтах можно встретить формы поиска по сайту . Может создаться впечатление, что, раз форма поиска по сайту - составная часть сайта, то и стоить она должна дешевле сайта.

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

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

    Распространение таких поисковых движков - дань моде. Заказчик хочет иметь поисковый движок. Не зная, как оценить результаты работы поискового движка, он не может понять, насколько эффективна его работа.

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

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

Пример

    Сайт посвящен веб-дизайну. Основное внимание уделяется вопросам создания сайта и редизайну. На сайте много раз встречается фраза "создание сайта", но нет фраз "изготовление сайта" и "разработка сайта".

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

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

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

Пример 2

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

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

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

Пример 3

    Тот же сайт и тот же поисковый движок.

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

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

На заметку:

    Примеров некорректной работы поисковых движков каждый опытный пользователь Интернет может привести множество.

    Не случайно, алгоритм работы поисковой системы и рейтинг, который она выстраивает на основе запроса, учитывает и анализирует многие параметры .

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

    Естественно, что при создании большинства бизнес-сайтов, с бюджетом до $ 40 000 - $ 50 000, ручная доводка поисковых движков - дело невыгодное.

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

Резюме

    Создание полноценного поискового движка сайта по сложности, стоимости и срокам превосходит создание большого сайта.

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

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

Привет хабр.
Пару месяцев назад мне поступил заказ на разработку сайта. Сайт представлял собой сборник статей добавляемых пользователем. Одним из пунктов технического задания было создание поиска. Т.к. я большой любитель изобретать велосипеды, было решено не использовать поиск от Яндекса или гугла.

Обычный поиск

Самым тривиальным решением было разбивать статьи на слова, разбивать запрос на слова и искать совпадения.
Плюсы:

  • Высокая скорость. Можно было для этого использовать сразу 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[i]==null) this.tgram_abc[i]=new ArrayList(); this.tgram_abc[i].add(id); i++; }

Далее сделаем аналогичное для слова с «приведёнными» буквами, потом заменим нн на н и добавим в третий массив, и напоследок удалим все мягкие знаки.
Теперь можно искать похожие слова. Разбиваем слова на граммы, находим хеш кажой тройки и получаем списко слов в которых одни есть на похожих позициях.

HashMap 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]!=null) for (int id:this.tgram_abc[l][j]) 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 WordIndex[язык текста][служебный индекс текста][язык слова]

Этот список хранит позицию слова в статье и id статьи.
Аналогично заводим массив для хранения корней слова.
Далее берем заголовок и индексируем его как ещё один текст.

Механизм поиска и ранжирования

Это самый главный механизм любой поисковой системы. Именно от того насколько правильно он создаёт выдачу зависит мнение пользователей.
Когда пользователь нажимает на кнопку поиск php скрипт пересылает запрос поисковику. Тот его разбивает на слова. Только тут есть одно отличие от индексации. Если при добавленной статьи при встрече незнакомого слова мы добавляем его в список слов, то при встрече в запросе незнакомого слова мы ищем наиболее похожее используя метод 3 грамм.
После разбиения для каждого слова мы получаем список из пар id текста – вхождение слова.
Определим, насколько статья подходит запросу:

  1. Посчитаем, сколько всего слов из запросов есть в статье.(a)
  2. Посчитаем, сколько всего корней из запросов есть в статье.(b)
  3. Посчитаем сколько существует словосочетаний слов аналогичных словосочетаниям в запросе(c)
  4. Посчитаем, сколько существует словосочетаний корней аналогичных словосочетаниям в запросе(d)
  5. Определим сколько слов из запроса встречаются в статье(e)
  6. Определим сколько корней из запроса(f)

После чего каждой статье добавим баллы по след формуле:

Math.log(2*a+1)+ Math.log(2+1)+2+Math.log(c*5+1))+ Math.log(d*3+1)))*(f+2*e));

Формула создана по след принципам:

  1. Слова приоритетнее корней
  2. Словосочетания приоритетнее обычных слов
  3. Чем более полно статья описывает поисковый запрос, тем выше её рейтинг. Причём полнота является ключевым

Далее пройдёмся по заголовкам, только там будем умножать баллы на 10, т.к. заголовок отражает суть статьи.
Сортируем и выводим.
Приведённый алгоритм обрабатывает 100 запросов в секунду при индексе в 1000 статей на VPS с процессором 1Ггц.
P.S. Эта статья лишь служит лишь для ознакомления с некоторыми алгоритмами и идеями нечёткого поиска.