Главная > Документ


Сегалович Илья

";Как работают поисковые системы?";. Цитаты.

В мире написаны сотни поисковых систем, а если считать функции поиска, реализованные в самых различных программах, то счет надо вести на тысячи. Но на какой бы математической модели он не основывался, идеи и программы, реализующие поиск, достаточно просты. Хотя эта простота относится, по-видимому, к той категории, про которую говорят: ";просто, но работает";. Так или иначе, но именно поисковые системы стали одним из двух новых чудес света, предоставив Homo Sapiens неограниченный и мгновенный доступ к информации. Первым чудом, очевидно, можно считать Интернет как таковой, с его возможностями всеобщей коммуникации.

Поисковые системы в исторической перспективе.

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

Алгоритм + структура данных = поисковая система.

Как и любая программа, поисковая система оперирует структурами данных и исполняет алгоритм. Разнообразие алгоритмов не очень велико, но оно есть. Есть четыре класса поисковых алгоритмов. Три алгоритма из четырех требуют «индексирования», предварительной обработки документов, при котором создается вспомогательный файл, сиречь «индекс», призванный упростить и ускорить сам поиск. Это алгоритмы инвертированных файлов, суффиксных деревьев и сигнатур. В вырожденном случае предварительный этап индексирования отсутствует, а поиск происходит при помощи последовательного просмотра документов. Такой поиск называется прямым.

Прямой поиск

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

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

Хотя прямой просмотр всех текстов, довольно медленное занятие, не следует думать, что алгоритмы прямого поиска не появляются в Интернете. Примером такой системы является Норвежская поисковая система Fast (). Кроме того, есть масса программ, комбинирующих индексный поиск для нахождения блока текста с дальнейшим прямым поиском внутри блока. Например, весьма популярный, в том числе и в Рунете, glimpse.

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

Инвертированный файл.

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

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

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

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

Второй (никак не связанный с первым) способ сжатия: упорядочить позиции для каждого слова по возрастанию адресов и для каждой позиции хранить не полный ее адрес, а разницу от предыдущего. Дополнительно на разностный способ хранения адресов накладывают какой-нибудь простенький способ упаковки: зачем отводить небольшому целому числу фиксированное «огромное» количество байт, ведь можно отвести ему столько байт, сколько оно заслуживает. В литературе встречается и более тяжелая артиллерия упаковочных алгоритмов самого широкого спектра: арифметический, Хаффмена (David A. Huffmen), LZW и т.д. Прогресс в этой области идет непрерывно. На практике в поисковых системах они используются редко: выигрыш невелик, а мощности процессора расходуются неэффективно.

В результате всех описанных ухищрений размер инвертированного файла должен составить от 7% до 30% от размера исходного текста (в зависимости от подробности адресации).

Занесены в «Красную книгу».

Неоднократно предлагались и другие, отличные от инвертированного и прямого поиска структуры данных и алгоритмы. Это, прежде всего, суффиксные деревья, а также сигнатуры. Первый из них функционировал и в Интернете, будучи запатентованным алгоритмом поисковой системы OpenText (). Иногда можно встретить суффиксные индексы в отечественных поисковых системах. Второй алгоритм – метод сигнатур – представляет собой преобразование документа к поблочным таблицам хеш-значений его слов – «сигнатуре» – и последовательному просмотру «сигнатур» во время поиска.

Широкого распространения ни тот, ни другой методы не получили.



Скачать документ

Похожие документы:

  1. КУРСОВАЯ РАБОТА НА ТЕМУ «Поисковые системы» ПО ДИСЦИПЛИНЕ "

    Курсовая работа
    ... принципы работыпоисковых систем Как же все-таки работаютпоисковыесистемы? Как ни странно, но логика работы у всех поисковых ... комбинации, как $10 или С++). Поиск цитаты или точного названия Как быть с поиском цитат или ...
  2. " зачем нам чужая земля "

    Список учебников
    ... без просыпу водил по болотам поисковую команду, все они, кроме ... ... "И в ямку бух" - закончил цитату Игорь. -"В ямку бух"еще рано, дорогой ... Теперь пришлось работать в системе лейтенанта Забрудного, а она ни в какое сравнение с системой капитана Скопцова ...
  3. " зачем нам чужая земля " (3)

    Список учебников
    ... без просыпу водил по болотам поисковую команду, все они, кроме ... ... "И в ямку бух" - закончил цитату Игорь. -"В ямку бух"еще рано, дорогой ... Теперь пришлось работать в системе лейтенанта Забрудного, а она ни в какое сравнение с системой капитана Скопцова ...
  4. Хосты 1 СИСТЕМЫ И ТЕХНОЛОГИИ КОЛЛЕКТИВНОГО ДОСТУПА К ИНФОРМАЦИОННЫМ РЕСУРСАМ

    Документ
    ... какому-либо термину. Обычно жирный наклонный шрифт или просто жирный, CITE - цитата ... -поисковойсистеме) без каких-либо переделок последнего (какая разница, с каким терминалом работать ... снять. Команда quit завершает сеанс работы с сервером. Протокол ...
  5. КАК ПИСАТЬ И ОФОРМЛЯТЬ богословские работы на русском украинском и английском языках Руководство Евро-Азиатской Аккредитационной Ассоциации Предисловие

    Руководство
    ... оглавление; познакомьтесь с «поисковыми машинами» в конце книги ... сборе цитат. Как настроить буфер для такой работы? ... – 302 с. Межгосударственный стандарт. Система стандартов по информации библиотечному и ... and Lk. q. v. quod vide (Lat.), which ...

Другие похожие документы..