takya.ru страница 1
скачать файл
Сегалович Илья

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


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

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


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

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


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

Прямой поиск


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

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

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

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


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


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

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

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

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

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

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


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


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

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



Смотрите также:
"Как работают поисковые системы?". Цитаты
49.89kb.
1. Классификационные информационно-поисковые языки
153.1kb.
Коммерческий: Да
24.95kb.
Обмен валюты производится в банках. Банки работают с 08. 30 до 12. 30 ежедневно, кроме субботы и воскресенья. После обеда банки работают по понедельникам
29.46kb.
Принято на методическом объединении классных руководителей директор моу можарская сош№15
76.5kb.
Сценарий как механизмы социализации
179.56kb.
Стиг Ларссон: «Девушка с татуировкой дракона»
7263.21kb.
В. М. Курейчик Генетические алгоритмы (ГА) есть поисковые алгоритмы, основанные на механизмах натуральной селекции
76.19kb.
В нту «хпи» работают дистанционные подготовительные курсы
14.83kb.
С. Л. Сотник Тех директор Iveonik Systems, Днепродзержинск в процессе деятельности компании Iveonik Systems, возникла задача
29.71kb.
I. Шумовое загрязнение Шум как одна из важнейших проблем
173.47kb.
Сообщения гис киевгаз и как разработчики системы остановимся на программно-технических и технологических аспектах самой системы и на том, что сопровождает разработку, т е. на контексте системы
128.83kb.