Журнал «Компьютерра» №30 от 23 августа 2005 года

ТЕХНОЛОГИИ: Гадания на поисковых образах

В редакции «КТ» стоит огромный шкаф, две полки которого отведены под подшивки журнала за несколько лет. Если распечатать в том же формате содержимое сайта «КТ», то потребуется уже три шкафа. По оценке Nigma.ru, в Интернете хранится больше 1 млрд. русскоязычных документов (оценка очень приблизительная, но других — более точных — извините, нет). Если предположить, что каждый документ содержит в среднем 5 килобайт текста, то для их офлайнового хранения потребовалось бы 17500 шкафов, для размещения которых необходимо помещение, чья суммарная площадь примерно равна площади двух футбольных полей. Причем практически сразу же нам потребовалось бы еще одно футбольное поле — для новых документов, которые ежедневно появляются тысячами.

Разумеется, ориентироваться в миллиардах документов без поисковых сервисов невозможно. Но так ли хороши современные средства поиска в текстовых документах и нельзя ли их радикально улучшить?

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

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

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

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

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

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

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

Работа с текстом всегда требует определенного языкового обеспечения. В частности, при поиске в русском тексте к безусловно необходимым относится словоизменительный словарь, позволяющий учесть различные морфологические формы известных слов и генерировать гипотезы для слов, не вошедших в словарь. Классический труд Андрея Анатолиевича Зализняка[Зализняк А. А. Грамматический словарь русского языка: Словоизменение. Ок. 110 000 тыс. слов. — 4-е изд., испр. и доп. — М.: «Русские словари», 2003] в полной мере удовлетворяет эти потребности. Определенную пользу может принести и фразеологический словарь. Иногда применяются и словари синонимов. Однако этого недостаточно.

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

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

В этом легко убедиться, посмотрев на wordstat.yandex.ru, какие запросы делают Яндексу.

«Естественный» запрос: +как работает фотошоп — 189 показов в месяц.

«Командный» запрос: уроки фотошоп — 3469 показов в месяц; учебник фотошоп — 673 показа в месяц и т. д.

«Естественный» запрос: +как проехать +в шереметьево — 106 показов в месяц.

«Командный» запрос: шереметьево проезд — 546 показов в месяц; шереметьево добраться — 470 показов в месяц; шереметьево доехать — 409 показов в месяц и т. д.

Даже в поисковой системе Ask Jeeves, изначально позиционировавшей себя как искалка, которая понимает запросы на естественном языке, доля коротких запросов на «командном» языке недавно превысила долю запросов на естественном языке. Вторая причина — ориентация «интеллектуального» поиска на грамотный русский язык. Веб — социальное, а не лингвистическое явление, и для общения в Сети вместо естественного русского языка часто используется жаргон, короткие предложения, ссылки вместо цитат и т. д., что не может учесть ни один словарь, даже во 2-м исправленном издании.

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

Александр Садовский,

руководитель отдела веб-поиска компании «Яндекс»

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

Пример из этой серии — автоматическое включение в запрос синонимов некоторых поисковых слов. Вроде бы — шаг к ИП. На практике же при поиске по слову «господа», которое имеет высокую частоту в значении обращения (вместо прежнего «товарищи») и является помехой для другого своего значения (в смысле баре — собирательного от барина, барыни, барчат и т. п.), автоматически предусмотрена замена «господ» на синонимическое «баре». Но «баре» в родительном имеют омоформу, совпадающую с «баром» (где наливают). Вот так по запросу «господа» появлялся ворох ссылок на многочисленные бары. По крайней мере, на Яндексе еще в начале августа было именно так.

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

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

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

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

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

Конструирование алгоритмов и поддержка такого поиска требует несравненно более основательного языкового обеспечения. Основная проблема здесь — в понимании смысла языкового сообщения. Понимание или интерпретация языкового знака (а значит, и всего текста) эквивалентны тому, что его значение возможно установить. Это реально, если есть критерии опознания в предложении компонент, несущих элементарный смысл. Но необходимы описания этих смысловых компонент, их связей, соответствующие словари и т. п. Как оказалось, ситуация здесь достаточно благоприятная. Функциональное описание перечня всех (!) конструктивно-смысловых единиц и типов связи русского предложения приведено в Синтаксическом словаре[Золотова Г.А. Синтаксический словарь: Репертуар элементарных единиц русского синтаксиса. Изд. 2-е, испр. — 440 с] Галины Александровны Золотовой. Правда, необходимы еще и электронные словари с соответствующим лексическим материалом, а это хоть и понятная, но очень ресурсоемкая работа.

Для наглядности приведем примеры некоторых элементарных структурно-смысловых компонент (синтаксем). Компонента со смыслом местонахождения или местопребывания, называемая в Словаре локативом, имеет форму предлога и имени места в соответствующем падеже (форму предлог + падеж имеют все именные синтаксемы): для родительного это предлоги между (скал, двух сосен, ухабов), против (клумбы, памятника, парадного), среди (двора, улицы), у (входа); для творительного — за (поворотом), между (двумя горами), над ( рестораном), перед (домом), под (Москвой); для предложного — в (доме), на (берегу), при (дороге). Как видно, компонента местонахождения имеет известную и «закрепленную» за нею конструкцию, общую для разных лексических примеров, и, таким образом, вполне может быть опознана в тексте.

Компонента со смыслом орудия действия (инструментив) имеет форму: имен., из + род., с +род., в + вин., на + вин., твор., на + пред. Вот несколько лексических примеров для этой компоненты: мяч, который разбил окно; напильником, которым обрабатывают; на скрипке и т. п. Таких элементарных конструктивно-смысловых компонент для русского предложения насчитывается несколько сотен, и у каждой из них своя морфологическая форма. В результате любую грамматическую конструкцию, которую можно представить в виде комбинации связанных между собой синтаксем, в дальнейшем можно факторизовать (разделить) на данные (слова) и сущности (названия компонент), а также указать схему связей между сущностями (подобие полного синтаксического дерева предложения). По сути, это означает, что любой связный текст может быть представлен в виде иерархической БД. Возможность факторизации текста на естественном языке имеет далеко идущие последствия и для развития других технологий, работающих с текстом как с данными, — в частности, для машинного перевода , text mining, контекстного анализа и пр.

Иерархические модели данных хорошо известны и изучены. Самый известный пример — реестр ОС MS Windows. Использование иерархической модели позволяет строить более сложные индексы, нежели в реляционных БД. Исторически эти модели были первой структурой БД и получили широкое распространение в эпоху мэйнфреймов. Для подобных баз были созданы мощные языки запросов, а по быстродействию они до сих пор вне конкуренции. Реляционные БД со временем оттеснили иерархические, но не факт, что не произойдет частичный реверс.

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

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

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

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

Крупнейшие поисковые сервисы — Google, Yahoo! и MSN — к попыткам научить поисковые движки понимать запросы пользователей и документы видимого интереса не испытывают (вполне возможно, что причины их равнодушия к этим разработкам схожи с соображениями Александра Садовского, изложенными в предыдущей врезке). Интернет-пользователи привыкли к особенностям поисковых машин, знают их сильные и слабые стороны и по большей части удовлетворены имеющимися возможностями. Если в ближайшие несколько лет в поисковых технологиях и появятся революционные качественные изменения, то инициатором их появления станут, скорее всего, не известные лидеры рынка, а компании, которые обыватель с поиском вообще не связывает. В частности, очень активно сейчас развиваются корпоративные поисковые сервисы, которым зачастую ставится задача не только найти похожий по смыслу документ, но и проанализировать его, найти документы с ним связанные, и т. д. И здесь привычным поиском по ключевым словам не обойдешься.

Над технологией, способной обойти привычные ограничения, уже несколько лет работает исследовательский центр IBM. В августе этого года корпорация даже пообещала выложить в Сеть для свободной загрузки исходные коды своей платформы UIMA (Unstructured Information Management Architecture, www.alphaworks.ibm.com/tech/uima).

Информационные агентства поспешили заявить о том, что на смену поиску по ключевым словам приходит поиск по понятиям (key facts вместо key words), однако UIMA поиск по ключевым словам вовсе не отменяет (скорее, дополняет);

является не готовым приложением, а основой для построения специализированных программ анализа данных;

сейчас — после четырех лет разработки — все еще находится в начальной стадии развития, хотя пилотные проекты на базе UIMA существуют.

Подробнее об UIMA, которая оказалась в центре внимания прессы только пару недель назад, можно прочитать в прошлогоднем номере IBM Systems Journal (www.research.ibm.com/journal/sj43-3.html). Там же описаны несколько возможных приложений UIMA (например, www.research.ibm.com/journal/sj/433/mack.html и www.research.ibm.com/journal/sj/433/uramoto.html).

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

У IBM в этом свой интерес — если действительно удастся сделать UIMA стандартом, то вложения в эту технологию окупятся стократ. А там, глядишь, потенциал, заложенный в UIMA, будет раскрыт сторонними разработчиками, да так, что поисковый сервис, скажем, 2015 года на скромный пользовательский запрос о бесплатных mp3 вместо нужных ссылок будет выдавать составленный машиной оригинальный двадцатистраничный реферат о проблемах пиратства в Сети. — В.Г.