Кто ищет, тот всегда найдет

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

Менее чем за десятилетие методы сбора и обработки информации в корне изменились. Сегодня не надо бежать в библиотеку, чтобы что-то найти. Несколько щелчков по клавиатуре — и нужный документ в вашем распоряжении. Теперь, когда английское слово «googling» стало синонимом слова «искать», пришло время усовершенствовать поисковые машины.

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

В статье «Хранение и поиск информации» (Information Storage and Retrieval), опубликованной в Scientific American в сентябре 1966 г., Бен Ами Липетс (Ben Ami Lipetz) описал, как информационные системы того времени справлялись с рутинными конторскими задачами. Автор статьи отметил, что по-настоящему значимые достижения в области информационного поиска появятся только тогда, когда ученые глубже изучат процесс обработки информации человеком, а затем создадут машины с аналогичными способностями. Конечно, компьютеры еще не достигли такого уровня интеллекта, но они уже учитывают личные склонности, привычки и потребности пользователя при выполнении запросов.

Предварительный поиск страниц

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

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

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

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

Лучшие из лучших

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

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

Был разработан целый класс программ, получивших название упаковщиков (wrappers). Принцип их работы основан на том, что он-лайн информация обычно представляется с помощью стандартных «грамматических» структур. В некоторых программах, чтобы получить доступ к скрытому содержанию веб-страниц, используется привычный синтаксис поисковых запросов и стандартный формат он-лайн ресурсов. В других системах реализуются преимущества программируемого интерфейса, который позволяет использовать стандартный набор команд и операций. Примером программы, обеспечивающей доступ к скрытым ресурсам Интернета, может служить Deep Query Manager компании BrightPlanet. Этот менеджер запросов позволяет создавать настраиваемые поисковые порталы и интерфейсы для более чем 70 тыс. скрытых веб-ресурсов.

Если механизм ранжирования опирается только на гиперссылки и слова без учета ограничений, накладываемых на тип сравниваемых веб-страниц, то возникает возможность повлиять на результаты поиска так, чтобы вывести ссылку на какой-либо ресурс в первые строки ответа на поисковый запрос. Например, если в любую из трех главных поисковых машин (Google, Yahoo, MSN) ввести запрос «miserable failure», то в самом верху списка найденных ресурсов почему-то появляется ссылка на правительственный сайт www.whitehouse.gov.

Вместо того чтобы предоставлять пользователю ранжированный список гиперссылок (который сравнительно легко сфабриковать), некоторые поисковые машины пытаются идентифицировать образцы веб-страниц, которые наиболее точно соответствуют запросу, и группируют результаты в более короткие списки. Образцы могут включать в себя распространенные слова, синонимы, словосочетания и даже абстрактные наборы слов. Например, такие системы, как Northern Light и Clusty, связывают каждый набор ссылок с релевантным термином. Пользователь может детализировать дальнейший поиск, выбрав определенную группу результатов.

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

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

В настоящее время, чтобы найти файл на винчестере, требуется отдельное программное обеспечение. Для упрощения процесса можно использовать анализ информации на жестком диске по алгоритмам, использующимся в Интернете. Например, Google недавно объявил о создании программы Desktop Search, которая позволяет производить поиск как на жестком диске, так и в Интернете. В следующей версии операционной системы от компании Microsoft, условно названной Longhorn, тоже будет реализована подобная функция. С применением технологии, разработанной в другом проекте Microsoft, названном Stuff I've Seen («Что я видел»), операционная система Longhorn сможет предложить функцию неявного поиска, при котором значимая информация будет извлекаться без особого запроса. Программа неявного поиска выбирает ключевые слова из текстовой информации, с которой работает пользователь, и индексирует файлы на жестких дисках. Microsoft планирует распространить функцию поиска на содержимое веб-сайтов, чтобы облегчить процесс превращения содержания любого текстового документа в запросы для поисковой системы.

Найди меня

Недавно порталы Amazon, Ask Jeeves и Google объявили о внедрении механизма улучшения результатов поиска, основанного на пользовательской персонализации. Поисковые машины www.A9.com (проект Amazon) и www.MyJeeves.ask.com (проект Ask Jeeves) не только отслеживают запросы и найденные веб-страницы, но также позволяют сохранять их в виде закладок. Пользователь MyJeeves может многократно просматривать накопленные результаты, которые представляют собой как бы персонально организованную область Всемирной Сети. Подобные функции поддерживает и портал www.A9.com, на котором помимо всего прочего предлагается дополнительный набор страниц, сформированный при анализе личной поисковой истории. Это напоминает стандартную для Amazon схему целевой рекламы книг, для которой применяется объединение пользователей в группы по интересам, называемое коллективной фильтрацией (collaborative filtering).

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

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

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

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

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

Другой фактор — конфиденциальность. Зная историю посещения веб-сайтов и поисковых запросов, а также общую картину взаимодействия с приложениями, можно раскрыть немало конфиденциальной информации вплоть до точной идентификации пользователя. Существует программное обеспечение, позволяющее получать содержание веб-сайтов анонимно. Для этого используются промежуточные прокси-серверы. Сайт, принимающий данные либо обслуживающий запрос, «видит» только прокси-сервер и не может отследить пользователя. Подобная технология реализована в системе www.anonymizer.com, которая позволяет просматривать содержание веб-сайтов инкогнито. Другим примером служит программный продукт Freedom WebSecure, в работе которого задействованы многочисленные прокси-серверы и многоуровневое шифрование данных. В принципе, обеспечить разумную степень безопасности несложно. Но пока еще не изобретена поисковая машина, сочетающая пользовательскую персонализацию с высоким уровнем конфиденциальности.

Вместе весело шагать

Системы контекстного поиска могут учитывать местоположение пользователя. Если у человека есть КПК, снабженный GPS-приемником, то поисковая машина может использовать поступающую от него информацию. В Мэрилендском университете разрабатывается система Rover, которая обеспечивает доступ к текстовым, аудио- и видеоресурсам Интернета на обширной территории. Rover выводит на экран карту окружающей местности, отмечая интересные объекты.

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

К сожалению, ошибка определения местоположения GPS-устройств, составляющая 3-4 м, все еще довольно велика. Точность системы может быть увеличена за счет использования наземных радиомаяков, но если потребуется охватить обширную территорию, их установка обойдется слишком дорого. К тому же передача изображений, звуковых и видеофайлов требует более широкой полосы пропускания, чем у современных беспроводных сетей для мобильных устройств. В системах поиска с учетом местоположения успешно прошел проверку беспроводной протокол IEEE 802.11b, обеспечивающий скорость передачи данных до 11 Мбит/с, но широкого распространения он пока не получил.

Что на что похоже

Контекстом могут быть не только личные интересы или местоположение пользователя. Сегодня поисковые машины пошли дальше текстовых запросов и уже работают с графическим материалом. Например, из Интернета можно скачать множество трехмерных изображений, но художникам, дизайнерам и инженерам неудобно искать графику и 3D-модели по ключевым словам. Система поиска трехмерных объектов Принстонской группы исследования образов и методики их поиска предлагает пользователю три способа подачи графических запросов. Первый заключается в применении виртуального холста Teddy. Пользователь рисует на нем двумерный набросок, который программа расценивает как образующую объемного тела. Второй подход позволяет нарисовать несколько двумерных форм, которые затем сравниваются с тринадцатью различными проекциями трехмерных объектов, имеющихся в базе данных. Третий метод заключается в поиске изображения, похожего на 3D-модель, описанную в файле, предоставленном пользователем.

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

Угадай мелодию

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

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

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

Шаг в будущее

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

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

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

Автор: Джейвд Мустафа (Javed Mostafa) (адъюнкт-профессор информатики Университета штата Индиана, ответственный редактор журнала «Транзакции в информационных системах» (Transactions on Information Systems) Ассоциации по вычислительной технике (ACM). Руководит Лабораторией прикладной математики штата Индиана.)

Источник: «В мире науки» № 5, май 2005