Свежий номер №32 (409) / Teoma и Vivisimo
 
Дата публикации: 27.08.2001

Александр Крупник, krupnik@appl.sci-nnov.ru

Сегодняшний день - есть день величайшего торжества!
 В Испании есть король. Он отыскался. Этот король я.
Н. В. Гоголь. «Записки сумасшедшего»

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

Секрет успеха Google - в удачном алгоритме отбора документов, отвечающих поисковому запросу. Предшественники Google пытались определить «ценность» документа только на основе анализа его текста: как часто и как близко к началу документа встречаются там слова из запроса, есть ли они в заголовке и т. д. Создатели Google решили оценивать соответствие документа запросу с помощью специального числа, похожего по смыслу на индекс цитирования: чем больше ссылок на данный документ, тем это число, называемое PageRank (по имени Лоуренса Пейджа [Lawrence Page] - одного из создателей Google), больше. PageRank той или иной страницы равен взвешенной сумме рангов всех страниц, ссылающихся на нее; вычислять его нужно один раз, и в промежутках между переиндексациями всей базы данных он остается неизменным 1.

Обрабатывая поисковый запрос, Google ищет указанные слова и фразы не только в документах, но и в ссылках на них. Затем вычисляется показатель, величина которого зависит от частоты встречаемости этих слов и фраз, их расположения, величины шрифта (заголовки оцениваются выше) и т. п. Полученное число комбинируется с «индексом цитирования» PageRank, и в результате получается мера «важности» документа, в соответствии с которой Google и показывает его в результатах поиска.

А результаты оказались столь хороши, что очень скоро Google стал «народной» поисковой системой, способной понять ищущего если не с полуслова, то, по крайней мере, с одного-двух. И когда Google стал использоваться тематическим каталогом Yahoo (в случае, если запрашиваемой комбинации слов не удавалось найти в самом каталоге), все увидели, кто теперь король 2.

Казалось бы, все ясно. Google значительно популярнее всех остальных индексов. Его методы определения «важности» документов замечательны, база данных гораздо больше, чем у конкурентов, и чуть ли не каждый месяц добавляются новые возможности: то выясняется, что Google проиндексировал все документы в формате pdf 3, то оказывается, что Google купил базу данных сообщений Usenet, которая раньше располагалась по адресу www.deja.com, а теперь ее адрес groups.google.com, то приходит известие, что Google теперь позволяет искать картинки в Интернете. Дошло, наконец, до того, что в период упадка всей индустрии, когда сайты один за другим закрываются или сокращают штаты, Google стал приносить прибыль и расширяется. Но за расцветом неизбежно следует упадок. И того, кто «взобрался на вершину веревочной лестницы», начинают беспокоить те, кто пока «повис внизу, на шатких ступенях». О двух многообещающих системах, способных со временем занять место Google, мы и поговорим.

Но прежде стоит сказать о недостатках Google, ведь только благодаря им и появляются новые поисковые системы. Самый, наверное, большой недостаток - отсутствие диалога с пользователем. Чтобы найти подходящий материал, библиотекарь общается с посетителем и выясняет, что ему нужно. Но с Google разговора не получается: в ответ на запрос ищущий получает набор кратких описаний документов и должен сам решить, какой документ хорош, а какой нет. Google не может дать нужный вам ответ на слово «Charles», потому что не ясно, о ком идет речь - о Диккенсе, Дарвине или принце Чарльзе.

Чтобы диалог стал возможен, конкуренты Google стараются классифицировать найденные документы, и в результате между человеком и поисковой системой завязывается разговор. Попробуем, например, задать слово «Charles» поисковой системе Teoma. Результаты показаны на рис. 1. Как видим, они разбиты на три части. Вверху, под заголовком «Web Pages Grouped by Topic» показаны результаты автоматической классификации найденных документов. Названия групп («Charles Dickens», «Charles Darwin», «Charles Ives») говорят сами за себя. В нижней левой колонке, озаглавленной «Web Pages», показаны страницы, лучше всего отвечающие запросу. В правой колонке, со странным названием «Experts Links», показаны документы, в которых много ссылок на страницы, стоящие слева. Это могут быть разделы тематических каталогов, где упоминается слово «Charles», или какие-то другие наборы ссылок.

Как видим, Teoma предпочитает Диккенса всем другим Чарльзам. Чтобы переключиться на Дарвина, выберем ссылку «Charles Darwin» в верхней части результатов поиска, и возникнет новое триединство: вверху классификация документов, попавших в раздел «Charles Darwin», слева - самые подходящие документы, а справа - лучшие коллекции ссылок на них.

Правда, в раздел «Charles Darwin» затесались и сайты, посвященные Диккенсу, что говорит о несовершенстве алгоритма кластеризации (то есть автоматического разделения документов на группы), используемого системой Teoma. Но все равно такая сортировка очень полезна. Ведь, приступая к поиску, я могу и не знать, как пишется по-английски «Дарвин», а Teoma подсказывает мне, как точнее сформулировать запрос.

Классификация результатов - вещь замечательная, и ее очень недостает Google. Но Teoma славна не ею, а скорее тем, что пытается обыграть Google в его собственной игре. Определяя соответствие документа запросу, Teoma использует примерно тот же метод, что и Google. Разница в том, что PageRank, используемый Google, определяется всеми проиндексированными документами, он постоянен и не зависит от запроса. А похожая характеристика, используемая в системе Teoma, вычисляется на основе анализа структуры ссылок в уже найденных документах. То есть Teoma, определяя «важность» документа, учитывает только ссылки со страниц, имеющих отношение к запросу. И многие считают, что такой способ лучше. Анализируя структуру ссылок, Teoma не только определяет наиболее соответствующие запросу документы, но и разделяет их на две части: на те документы, на которые чаще всего ссылаются, и те, которые чаще всего ссылаются. Первые располагаются в колонке слева, вторые - в колонке справа. Как видим, и здесь Teoma идет дальше, чем Google.

Второй претендент на престол - метапоисковая система Vivisimo, разработанная в университете Карнеги Меллона (CarnegieMellon University). Ее аскетический интерфейс (как, впрочем, и интерфейс Teoma) до боли напоминает Google. Похожа и история создания этих систем. Как и Google в прошлом, Vivisimo - экспериментальный некоммерческий проект. Только, в отличие от Google, создателей Vivisimo интересовали прежде всего алгоритмы кластеризации. Vivisimo использует иерархическую кластеризацию, представляя документы, найденные поисковыми системами, такими как Altavista и Fast, в виде дерева. Так, на запрос «Queen» Vivisimo создает, помимо прочих, папку «Official», а внутри нее - папки «British Monarchy», «Fan», «Queen Mother», «Other Topics». На рис. 2 показана реакция Vivisimo на запрос «John».

Как видим, на этот идиотский запрос (попробуйте поискать слово «John» в Google) Vivisimo отвечает парой осмысленных результатов. Она как бы говорит нам: «Хм. Странный вопрос. Быть может, вас интересует Джон Кеннеди или Джон Леннон?» Если интересен Леннон, можно выбрать мышью плюсик слева от имени «John Lennon», и тогда в левом окне будут показаны подразделы раздела «John Lennon». Если же выбрать синий треугольник, в правом окне появятся ссылки на документы, попавшие в раздел «John Lennon».

И уж совсем замечательными будут результаты кластеризации, если искать оба слова «John» и «Lennon». Тогда среди папок, показанных Vivisimo, будут такие: «Beatles», «Discography», «Murder», «Fbi, Files», «Guitar», «John Lennon Lyrics» и т. д. То есть, Vivisimo проявляет признаки интеллекта, ведь слов «Guitar», «Murder» и пр. не было в первоначальном запросе. Любопытно, что в папках, сгенерированных по запросу «+John +Lennon» (плюсики задают обязательное присутствие слова), нет раздела «Paul McCartney», который появляется, если потребовать, чтобы в документах не было слова «Yoko»: «+John +Lennon -Yoko».

В сущности, Vivisimo даже не метапоисковая система, а приставка, способная кластеризовать любые данные. Это могут быть патенты, рецепты, стихи - все, что угодно. Алгоритм кластеризации Vivisimo присоединяется к любой поисковой системе. В окошке правее окна запросов можно вместо «Search the Web» выбрать, например, «Альтависту». И тогда Vivisimo перехватит ссылки, выданные «Альтавистой», отсортирует их и украсит ими ветки дерева в своем левом окне.

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

[i40936]


1 (обратно к тексту) - Подробнее см. Sergey Brin and Lawrence Page, «The Anatomy of a Large-Scale Hypertextual Web Search Engine».
2 (обратно к тексту) - Ранее на этом месте побывали Altavista и Inktomi.
3 (обратно к тексту) - Чтобы, например, найти слово «John» только в pdf-файлах, запрос должен быть таким: John filetype:pdf.


Александр Крупник
krupnik@appl.sci-nnov.ru
 


<< Пособие для начинающего диктатора
Все материалы номера
Труба энтропии зовет лечь на дно >>