Принципы построения поисковых систем (на примере Google)
Любая автоматизированная информационно-поисковая система (ИПС) состоит из двух основных частей: формирователя собственной базы данных и генератора ответов на запросы пользователей. Главными показателями для первой являются ее объем и продуманность внутренней структуры, а для второй - скорость поиска информации и удобство пользования. На самом деле такое деление очень условно, потому что функциональная гибкость запросов изначально зависит от структуры базы данных: невозможно запросить что-то, что не было заложено в алгоритмы разработчиками.
Скажем, можно создать программу (Интернет-робота), которая будет скачивать все содержимое глобальной сети (если позволяют каналы связи) и сваливать эту информацию в одну кучу. Но, даже обладая всем этим богатством, невозможно потом будет хоть как-нибудь им воспользоваться. Конкретный поиск в неструктурированной базе данных заставит обработчик запросов полностью (!) просмотреть все содержимое кучи. Именно поэтому создатели поисковых систем и баз данных вводят индексацию внутренней структуры. То есть упрощенно под индексом можно понимать нечто, помогающее существенно ускорить поиск (алгоритмы, способы обращения к большим объемам информации, способы упорядочивания и хранения данных и т. д.).
С другой стороны, пусть существует хорошо проработанная база данных. По определенному запросу пользователя программа-обработчик поисковой системы выдаст множество документов, где встречается заданное словосочетание. Задачей номер один для создателей ИПС является такая сортировка результатов поиска, чтобы в самых первых позициях находились именно те документы, которые были затребованы. Этот параметр называется релевантностью ответа. Если задать в поиске только общие слова, например <корм для собак>, тогда как вы ищете информацию про его ингредиенты, вряд ли в первой паре страниц отчета вам выдадут то, что вы искали. Поисковая система просто не в состоянии знать ваши мысли. Поэтому, задавая запрос, максимально конкретизируйте его для получения наиболее точного результата.
Давайте изучим внутреннюю структуру ИПС на примере Google (www.google.com).
Google появился сравнительно недавно, в 1998 г. Его создатели, сотрудники Стенфордского университета (США) Сергей Брин и Лоуренс Пейдж, постарались сделать его механизм более гибким и расширяемым, чем существовавшие на то время у грандов поиска - Аltavista и Inktomi.
Для справки:
На данный момент Google имеет самый большой объем проиндексированных страниц – порядка 15 миллиардов.
Рейтинг основных поисковых системы (по данным Nielsen NetRatings)
http://www.google.com/ - 46.2%
http://www.yahoo.com/ - 22.5%
http://search.msn.com/ - 12.6%
Количество сайтов в интернете
В настоящее время, по данным исследования компании Netcraft, общее число сайтов в Интернете превышает 100 миллионов (из них 1млн. – сайты Рунета), среди которых порядка 50% «живых». Ежемесячно в интернете появляется несколько миллионов новых сайтов – с 2004г количество сайтов в сети удвоилось.
Речь идет не только о собственно html- и xml-документах, но и pdf, doc и даже флэш-анимации. Причем только Google, в отличие от других иностранных ИПС (мы не рассматриваем "Яндекс", "Рамблер> и <Апорт>), хорошо индексирует русскоязычные Web-ресурсы в зоне.ru.
Почти в каждой поисковой системе есть своя внутренняя система оценки <качества> документов. В Google она называется PageRank (PR). Суть ее заключается в том, что при решении о порядке выдачи пользователю списка страниц, попадающих под его запрос, во внимание принимается некий коэффициент, зависящий от количества ссылок с других сайтов на эту страницу и от их популярности. На самом деле в этом есть рациональное зерно. Ведь если рассматриваемая страница действительно такая важная, что ее стоит прочитать, скорее всего, на нее уже ссылаются другие источники. Верно и обратное: если на документ никто не ссылается - кому он тогда нужен?! Причем PageRank - это не просто общая сумма ссылок, это нормализованное отношение количества ссылок, приводящих на данную страницу, к количеству исходящих c нее. Расчетная формула, опубликованная С. Брином и Л. Пейджем, выглядит следующим образом:
где d - эмпирически подобранный коэффициент (d=0.85); Т1...Tn - страницы, ссылающиеся на рассматриваемый документ; С(Tn)... С(Tn) - общее количество ссылок, ведущих вовне со страниц Т1...Tn.
Отсюда видно, что PageRank любого документа зависит от PageRank документов, с которых возможен переход на него. Таким образом, он всегда будет высоким для страниц, имеющих популярность в Интернете.
Важно также отметить, что PageRank имеет смысл вероятности, с которой среднестатистический Интернет-путешественник попадет на определенную страницу, хаотически блуждая по ссылкам. Сумма PageRank всех страниц равна единице
где N - количество проиндексированных страниц).
Вышеприведенная формула достаточно проста, и если задаться целью построить некоторое количество взаимосвязанных страниц, то, по-видимому, PageRank каждой может быть искусственно завышен. Например, можно попытаться сократить число ведущих вне ссылок и создать большое кольцо, в котором документ ссылается только на <друзей>. Тогда каждый из них вследствие итеративности алгоритмов расчета PageRank будет иметь достаточно высокий коэффициент <важности>. Несмотря на это в модели Google, вероятно, предусмотрены какие-то механизмы, позволяющие не начислять слишком высокий PageRank <подозрительным> и <нежелательным> сайтам. И естественно, эти механизмы являются ноу-хау и не подлежат разглашению.
Применение PageRank в поисковиках
Традиционные способы нахождения релевантных страниц, в случае односложных запросов не дают удовлетворительных результатов, т.к. по популярным темам (например “рефераты”, “работа“) всегда найдётся большое число страниц с одинаковой релевантностью. Для того, чтобы как-то упорядочить такие страницы, поисковики пускаются на разные хитрости. Например выдают первыми те страницы, которые имеют большую посещаемость (Rambler) или которые присутствуют в каталоге (Yandex, Aport). В Google для этих целей применяется PageRank, что даёт потрясающие результаты, и за короткое время Google стал занимать лидирующие позиции не только по объёму базы, но и по качеству поиска. Из наших поисковиков первым PageRank стал использовать Aport, за ним Yandex. В Rambler эта технология не применяется, но на данном этапе такая возможность рассматривается, и, не исключено, что PageRank будет использоваться и в этой поисковой системе.
На ряду с упорядочиванием результатов поиска по PageRank, есть и другое применение для этой технологии. Дело в том, что число страниц в Интернете на столько велико, что поисковики уже не могут себе позволить индексировать всё подряд. А поскольку PageRank служит критерием ценности страницы, то логично проводить индексацию страниц в порядке убывания PageRank. В Google пошли даже дальше: теперь простой отправки формы для регистрации не достаточно, - для того, чтобы сайт был проиндексирован необходимо наличие хотя бы одной внешней ссылки.
Введение в PageRank
PageRank - статическая величина, предназначенная для оценки качества страниц не зависимо от каких либо запросов, т.е. с помощью PageRank вычисляется “глобальная ценность” каждой страницы. Авторы PageRank Сергей Брин и Ларри Пейдж, разработавшие технологию дополнительного ранжирования результатов выдачи поисковиков, в последствии стали основателями компании Google.
За основу PageRank был выбран академический подход оценки важности публикации автора по числу её упоминаний в библиографических ссылках других авторов. Для адаптации к применению в Интернет в алгоритм были внесены следующие изменения: вес каждой ссылки учитывается индивидуально и нормируется по числу ссылок на ссылающейся странице. Кроме того, PageRank может быть интерпретирован в терминах случайного блуждания
Вычисление Pagerank
Представьте себе идеального веб-серфера перемещающегося по всемирной паутине. Пусть сёрфер посещает страницу p, случайное блуждание при этом находится в состоянииp. На каждом шаге, веб-сёрфер либо перепрыгивает на другую страницу в сети, выбранную псевдо-случайным образом, либо он следует по ссылке на текущей странице, при этом не возвращаясь и не посещая одну и ту же страницу дважды. Вероятность случайного прыжка обозначим какdтогда вероятность перехода по ссылке будет1–d. Таким образом, вероятность нахождения пользователя на страницеpможно вычислить по следующей формуле:
где R(p)- PageRank страницы,С(p)– число ссылок на странице,к– число ссылающихся наpстраниц,d- коэффициент затухания (damping factor). Обычно0.1<d<0.15. Если масштабировать PageRank таким образом, что
где N - число всех страниц, для которых производится расчёт PageRank, тоR(p)можно рассматривать как распределение вероятности по всем страницам.
Для вычисления PageRank составляется матрица MразмеромNxN, где каждому элементуmijматрицы присваивается значениеR0(p)=1/C(p)в том случае, если сi–й страницы имеется ссылка наj-ую, все оставшиеся элементы матрицы заполняются нулями. Таким образом, вычисление PageRank сводится к отысканию собственного вектора матрицыMчто достигается умножением матрицыMна векторRjна каждом шагу итерации. Введение коэффициента затухания гарантирует, что процесс сходится.
Повышаем значимость сайта
Осознав победное шествие PageRank, нельзя не задуматься об его увеличении для своей странички. Интуитивно понятно, что чем авторитетнее ресурс, на котором размещена ссылка тем больше она увеличивает PageRank страницы, на которую ссылается. И наоборот, чем больше ссылок на странице, тем меньше будет её вклад в повышение PageRank вашей страницы – ещё одно доказательство бесполезности участия в FFA (Free For All – сайты, содержащие набор ссылок со свободным добавлением). Менее очевидна оптимальная топология взаимоссылающихся страниц. Например, страницы организованные в “кольцо” (когда каждая страница ссылается на соседа слева и справа, последняя ссылается на первую, а первая на последнюю) будут иметь один и тот же PageRank не зависимо от числа страниц в кольце (если не проводить масштабирование по сумме, то PageRank у всех будет равен 1). То же справедливо для «звёзд» или случая, когда все ссылаются на всех, и, вероятно, это утверждение справедливо вообще для всех симметричных топологий. Гораздо более перспективны с точки зрения увеличения PageRank асимметричные топологии. Утверждение о бесполезности создания «пустых» (но ссылающихся друг на друга) сайтов у бесплатных хостеров не столь очевидно. Например, можно организовать обмен ссылками на 5 сайтах таким образом, что у одного из них PageRank будет в 15 раз больше, чем минимальный не нулевой PageRank. В этом несложно убедится, написав небольшую программку. О том, как это сделать, читайте в статье Efficient Computation of PageRank
Некоторые распространённые заблуждения связанные с PageRank
Проанализировав сообщения в рунетовских форумах, посвященных позиционированию в поисковых системах, можно выделить целый ряд утверждений о PageRank, как минимум спорных, а зачастую просто неверных. Кратко рассмотрим эти утверждения:
Если на какой-то сайт есть много ссылок с FFA, гостевых книг или на сайтов другой тематики, то PageRank будет занижен.
Не стоит путать понятия «индекс цитирования» и PageRank. При расчёте PageRank анализ содержимого ни сайта ни текста ссылки не производится, учитываются только общее число ссылок и их веса, поэтому никаких штрафных санкций при наличии ссылок с «неправильных» страниц не применяется.
Если добиться высокого PageRank для какой-то страницы, то эта страница будет на первом месте в результатах поиска.
Не верно, по той причине, что PageRank является не основным критерием для ранжирования страниц, а вспомогательным. В противном случае, на первых страницах по очень многим запросам располагались бы только рейтинги и топы. Только при прочих равных условиях страница с более высоким PageRank будет располагаться выше в результатах поиска.
Если зарегистрировать сайт во всех популярных каталогах, то PageRank будет очень высоким
Не стоит обольщаться - PageRank вычисляется не для сайта целиком, а для отдельно взятой страницы. Поэтому ссылка из глубокой поддириктории, скажем в Yahoo, может быть менее ценна чем страница Васи Пупкина. Так что, тут можно взять не качеством ссылок, а их количеством. Надо только обращать внимание на то, чтобы ссылки из каталога шли напрямую на ваш сайт, а не через cgi-скрипт, иначе они просто не будут учитываться. Кроме того, правила многих каталогах требуют размещения корневой страницы, а не того документа, PageRank которого вы собираетесь повышать. Поэтому гораздо эффективнее можно повысить PageRank конкретной страницы ссылкой с корневой страницы своего собственного сайта.
PageRank уменьшается при проставлении внешних ссылок
Весьма спорное утверждение, как говорилось выше PageRank понижается в случае симметричного объединения ссылающихся страниц, вероятность получить которое при проставлении внешней ссылки ничтожно мала. Если такую фобию в себе не перебороть, то можно дать совет завести специальную страницу для обмена ссылками. Кстати, стоит заметить, что при расчёте PageRank никто не обещал разделять ссылки на внешние и внутренние.
Google - продолжение
Еще одна важная черта ИПС Google заключается в том, что в ней хранятся описания ссылок на проиндексированные страницы. Эта особенность позволяет более адекватно проводить поиск в накопленной базе данных. Скажем, автор странички забыл указать ее название между тегами <title></title>. Любая ИПС при выдаче результатов поиска ставит высокий приоритет словам, указанным именно в названии. В этом случае Google будет ориентироваться по текстам ссылок на эту страничку, справедливо основываясь на предположении, что если кто-то ставит ссылку на что-то, то уж, по крайней мере, он эту страничку изучил и постарался наиболее емко отобразить ее содержание в тексте ссылки. Именно поэтому во всех наставлениях по правильному оформлению содержимого документов имеется следующий совет.
Никогда не ставьте ссылку под словами <здесь>, <тут>, <сюда>(например:полную версию постановления смотри <a href=<...>>здесь</a>). Попробуйте написать так:<на сайте есть также и <a href=<...>>полная версия постановления</a>>. Кстати, сказанное верно еще и потому, что почти во всех браузерах текст внутри тега<a>подсвечивается тем или иным образом (выделяется подчеркиванием, цветом). Глаз при беглом просмотре странички более вероятно зацепится за выделенные информативные слова, чем за неконкретное краткое наставление<вам сюда>.Как говорится, покупатель и продавец, будьте взаимно вежливы!
Кроме расчетов PageRank и запоминания текста ссылок, Google хранит шрифтовой размер и смещение каждого слова относительно начала документа. (Примечание: некоторые ИПС ориентируются также и на цветовое выделение слов относительно текста.) В спецификации HTML 3.2 было определено семь уровней заголовков по размеру шрифта (от <h1>- самого крупного, до<h7>- самого мелкого). Поэтому поисковик всегда выдаст по запросу документ, в котором данное слово выделено более крупным шрифтом или находится ближе к его началу. Благодаря тому что система знает конкретное место каждого слова в документе, становится возможен так называемый Proximity search - поиск по наиболее близкому расположению слов друг относительно друга. Например, по запросу<слово1 слово2>ИПС найдет много документов у себя в базе данных, но в отчет в первых строках пойдут только те, в которых<слово1> находится максимально близко слева от<слова2>.
Теперь более подробно рассмотрим схему функционирования информационно-поисковой системы Google. Всю основную работу по просеиванию сквозь себя содержимого Сети выполняют Интернет-роботы (боты, crawlers). Каждый из них берет один адрес (URL, uniform resource locator; каждый URL соответствует определенному идентификатору документа) из базы данных URL-сервера, скачивает и передает содержимое странички на сервер хранения документов (рис. 1). Необходимо отметить, что все содержимое сервера хранится в заархивированном виде для увеличения его вместимости.
Рис. 1. Структура информационно-поисковой системы Google
Другая программа - индексатор - занимается тем, что разлагает текст документа на составляющие его слова (хит в терминологии Google), запоминая при этом местонахождение, шрифтовой вес, а также написано ли слово заглавными или строчными буквами и принадлежит ли оно к категории <особенных> (названия документов, метатеги, URL'ы и тексты ссылок). Вся эта информация складывается в набор контейнеров, именуемых на рисунке прямым индексом. Структура хранимых в нем данных выглядит следующим образом (рис. 2).
Рис. 2. Структура прямого индекса (doc_id - идентификатор документа; word_id - идентификатор слова; null_word - символ окончания документа; n_hits - частота, с которой слово встречается в документе)
Идентификаторы слов берутся из словаря, который постоянно пополняется. Одновременно с этим индексатор просматривает содержимое тегов <a></a> и проверяет корректность всех ссылок в службе разрешения имен DNS (domain name service). Если ему встретился URL, которого нет в базе данных по doc_id, он пополняет не только ее, но и коллекцию ссылок. В дальнейшем этот Интернет-адрес попадает в URL-сервер и круг замыкается. Система поиска новых документов, при условии, что на них хоть кто-нибудь ссылается, становится самодостаточной - она сама себя подпитывает.
Но каким образом ИПС узнает о новых Web-ресурсах, которых еще никто не успел посетить? Для разрешения этой проблемы разработчики предусмотрели ручную форму регистрации ресурсов в поисковой системе. Введенные в нее адреса после проверки на корректность также попадают в URL-сервер.
Заметим, что каждая из программ, обозначенных на рис. 1 эллипсом, работает независимо от других, причем аппаратные конфигурации серверов и рабочих станций, на которых функционирует <движок> Google, выбираются так, чтоб не создавать <пробок> при обработке информации, собранной Интернет-роботами.
Описанная выше структура прямого индекса не очень удобна при поиске документов на основании встречающихся в них слов (пользователь задает слово или словосочетание, а система должна найти подходящий документ). Чтобы решить эту проблему, был введен так называемый инверсный, или обратный, индекс (рис. 3). В нем любому слову из словаря соответствует набор doc_id-документов, в которых это слово встречается. Работой по постоянному формированию инверсного индекса занимаются сортировщики. Так как, во-первых, всегда появляются новые документы и, во-вторых, обновляются старые, индекс приходится постоянно перестраивать.
Рис. 3. Структура инверсного индекса (word_id - идентификатор слова; ndocs - количество документов с этим словом; doc_id - идентификатор документа; n_hits - частота, с которой слово встречается в документе)
Пусть от пользователя поступил запрос найти документы со словом <мухобойка>. Программа, формирующая ответы, посмотрит в словарь, найдет там word_id для <мухобойки>, сформирует запрос в базу данных с использованием инверсного индекса и получит набор документов, в которых это слово встречается. Далее на основании PageRank, количества хитов, их качества и, может быть, других ограничений и приоритетов разработчиков будут распределены порядковые номера страниц в выходном списке. В итоге Интернет-пользователь получит самую оптимальную, по мнению ИПС, информацию о том, где и что писали о правилах и способах мухоубийства.
Качество поисковой системы, как уже было отмечено, зависит не только от количества проиндексированных документов, правил их отбора в итоговый список, но и от того, как часто Интернет-роботы заново проверяют содержимое ранее обработанных сайтов. В таблице на примере thermo.karelia.ru приведены данные об общем объеме запрошенных роботами документов и количестве заходов на сайт (по данным Webalizer - анализатора журналов Web-сервера).
Из таблицы видно, что роботы <Яндекса> и Google ведут себя по-разному. <Яндекс> останавливается на корневом документе Web-сервера (например, index.html) и скачивает содержимое сайта последовательно, документ за документом, в один поток. Google распараллеливает работу между несколькими роботами, причем каждый из них при скачивании может <отвлекаться> на другие дела. То есть эти две поисковые системы характеризуются совершенно различными структурами URL-серверов и способами пополнения информации из Интернета.
Второй важный вывод, который напрашивается по результатам изучения приведенной таблицы, заключается в том, что русскоязычные поисковики <лучше> иностранных, они более часто посещают ресурсы постсоветского пространства. Даже <Апорт>, уступивший на данный момент третье место Google по общему количеству обрабатываемых запросов (данные с www.spylog.ru), как минимум раз в месяц просматривает содержимое каждого сайта.
Последние две строчки в таблице требуют некоторых пояснений. За надписью Sunet.ru скрывается один из московских провайдеров Интернет-услуг (e-Style). Причем поражает завидное постоянство, с которым действует их робот. Какой из поисковых систем они предоставляют информацию и предоставляют ли ее вообще - автору неизвестно.
Dec.com - робот некогда существовавшего гиганта Digital Equipment Corporation (впоследствии он был перекуплен компанией Compaq). Dec поддерживал Altavista, поэтому можно предположить, что получаемая информация идет в закрома самой известной ИПС.
В заключение хотелось бы заметить, что каждый сайт строится уникальным образом, имея линейную, древовидную или смешанную структуру. Одни построены на документах с динамическим контентом, другие вообще статичны и не изменяются. По-видимому, будет существовать разница даже в процессе индексации постоянно изменяющихся сайтов, имеющих динамическое содержимое. Не секрет, что целая категория Web-ресурсов, отнесенных к разделу новостных, просматривается чуть ли не ежеминутно.
Машинный перевод
Системы машинного перевода еще далеки от совершенства. Мои знакомые профессиональные переводчики, не раз вынужденные оценивать своих электронных конкурентов, в один голос твердят, что машина языка не понимает и не поймет. Один даже категорически заявил: «Учить машину естественному языку - все равно что поставить обезьяну вместо регулировщика: палочку крутить будет, а зачем это нужно делать, так и не уразумеет». Но есть и другое мнение. Например, моя бывшая одноклассница полгода вела электронную переписку с французом, пользуясь системой ПРОМТ для перевода с русского на французский и наоборот. Французского она не знала совсем, но адресат об этом так и не догадался.
И все же, почему серьезные люди начинают плеваться после первого же сеанса работы с любым машинным переводчиком. Мне кажется, неприязнь частично связана с самим термином «машинный перевод» или с еще более громким - «искусственный интеллект». Пафоса в обоих терминах гораздо больше, чем реального наполнения. Они даже построены одинаково. Берется слово («перевод» или «интеллект»), которое применимо только к человеческой деятельности, и к нему добавляется что-то от компьютера. И обычные люди, неспециалисты, ошибочно полагают, что компьютер может здесь подменить человека, а на самом деле подменить человека он может только в редких, оговоренных программистами случаях!
Машинных переводчиков довольно много, и они очень разные. Есть старые заслуженные системы, например, основанная в 1968 году Systran (www.systransoft.com). Ее разработка стала целой научной эпохой в машинном переводе. Есть и новые, среди которых немало халтурных. Одна из них носит название LanguageForce (www.languageforce.com). Несколько лет назад фирма LanguageForce объявила, что сделала переводчик, который включает пятьдесят языков (перевод со всех на все), и стала продавать его задешево. Объем продаж был огромен, но вскоре клиенты, сравнив качество перевода с аналогами, поняли, что их надули. О LanguageForce сейчас ничего не слышно.
Традиционно системы машинного перевода делятся на две категории: основанные на правилах (rule-based) и основанные на примерах (example-based). В первых языковая грамматика проработана глубже, языковых правил больше. Системы второго типа - самообучающиеся, они строятся на динамическом порождении языковых правил для конкретных текстовых примеров. Границы между системами example-based и rule-based не очень четкие, поскольку и те и другие используют словари (статическая информация о языке) и правила работы со словарями. Яркий представитель класса example-based - система Trados (www.trados.com), работающая фактически на одних примерах, без грамматики. Trados предназначена для больших переводческих центров, где накопилось много параллельных текстов (два текста, один из которых является переводом другого). Она позволяет не переводить дважды одно и то же предложение, а просто находит такое же или очень похожее предложение в базе параллельных текстов и выдает уже сделанный кем-то перевод. При больших массивах однотипных текстов такой подход весьма эффективен. Вообще, понятие массива документов очень важно для машинного перевода. Большинство специалистов сходится во мнении, что машинный перевод возможен только для прикладных (технических) текстов, которые могут быть заданы определенными, порой гигантскими массивами. Художественная литература, как антипод технических текстов, никогда не будет переводиться компьютером адекватно.
На российском рынке машинных переводчиков немного, и главный среди них - система ПРОМТ (www.translate.ru). По моему субъективному мнению, ПРОМТ занимает до 95 процентов рынка машинного перевода в России, причем его позиции сильны не только у нас, но и в Европе. О бывшем конкуренте ПРОМТа - системе «Сократ» - почти ничего не слышно, хотя они вышли из одной питерской лаборатории и еще лет пять назад конкурировали. Ходят слухи, что компания «Арсеналъ» (создатель «Сократа») готовит новую версию системы машинного перевода, на порядок превосходящую аналоги. Дождемся ли? Кроме коммерческих машинных переводчиков, есть и академические. Самый авторитетный - это русско-англо-русская система ЭТАП (proling.iitp.ru). Для России ЭТАП - то же, что Systran для остального мира: она дала начало целому научному направлению, ставшему основным в российских академических разработках машинного перевода. В отличие от ПРОМТ, технологии системы ЭТАП описывались в открытых публикациях. ПРОМТ в этом смысле - черный ящик. Кто из них победит на рынке, сказать, конечно, трудно. Но что значит «победит»? Как оценить качество работы машинного переводчика? Одна из технологий построена на подсчете того, сколько раз нужно нажать на клавиши, чтобы исправить допущенные программой ошибки, но мне кажется, что правильнее считать ошибки так, как это делается в школе. Не поставил запятую в диктанте - ошибка, выбрал не ту грамматическую форму слова - ошибка и т. д. Отдельно нужно присвоить каждому предложению коэффициент понятности. Перевод может содержать массу грамматических ошибок, но быть предельно ясным. Как, например, предельно ясен перевод русской фразы «иду я домой» на английский «go I home», хотя порядок слов - неверный. Используя такую систему оценки, можно легко понять, чем ПРОМТ отличается от ЭТАПа. Создатели ПРОМТа готовы пожертвовать грамматической правильностью в пользу понятности перевода. Создатели ЭТАПа, напротив, уделяют пристальное внимание грамматике и стараются выдавать только грамматически верные результаты. Дело в том, что ПРОМТ ориентирован на конечного пользователя, а ЭТАП - академическая разработка, ей ошибаться нельзя. Можно ли синтезировать эти два подхода? Трудно, но попытки уже есть. Один из вариантов представлен на сайтеwww.aot.ru(группа «Диалинг»).
Сразу скажу, что русско-английский машинный переводчик, выложенный на этом сайте, пока не дотягивает ни до ПРОМТа, ни до ЭТАПа. Однако я уверен, что у него большое будущее. В чем конструктивное превосходство аотовского переводчика? Он лучше ПРОМТА тем, что у него открытая задокументированная архитектура с четко прописанными компонентами и интерфейсами между ними. Он лучше ЭТАПа тем, что не «зациклен» на грамматической правильности. Аотовский переводчик скорее выдаст перевод с несколькими ошибками, чем не выдаст ничего. Он лучше ПРОМТа и ЭТАПа вместе взятых, потому что у него есть так называемый поверхностно семантический модуль. А вот здесь начинается что-то непонятное. Что такое семантика? Сам термин «семантический анализ», несмотря на популярность, не является устоявшимся. Теоретические лингвисты и вообще гуманитарии трактуют его гораздо глубже, чем прикладники. Под семантикой обычно понимают выражение смысла слов путем их толкования. Однако многие специалисты приходят к выводу о невозможности эффективной алгоритмической реализации семантического анализа через толкования. Таким образом, толкование теряет прикладное значение. Надо искать что-то другое. Подход, который группа «Диалинг» взяла за основу, называют информационно-ролевым. Это означает, что смысл текста выражается графом, в узлах которого стоят слова или единицы, равные по объему словам. Например, числительные, которые в русском языке выражаются многословной конструкцией, сливаются в один узел. Или, например, связка «быть», которая в русском языке иногда опускается («она пионерка»), должна быть восстановлена в отдельный узел. Отношения графа задаются перечнем и называются семантическими отношениями. Рассмотрим примеры.
«Дом Пашкова стоял на пригорке»:
Кроме слов, семантические узлы могут включать:
знаки препинания. Например, для предложения «Он купил картошку, лук».
устойчивые обороты. Например, для предложения «По правде говоря, я сплю»:
абстрактные узлы связки. Например, для предложения «Он считал этого человека великим ученым»:
устойчивые словосочетания. Например, «Ему не хватило духа сказать об этом»:
жесткие синтаксические группы, например, для словосочетания «двадцать два мальчика»:
Получив для каждого предложения входного текста такую семантическую структуру, мы можем построить вопросно-ответную систему. Например, для построения ответа на вопрос «Где стоит дом Пашкова?» нам нужно сравнить семантическую структуру вопроса со структурой предложения «Дом Пашкова стоял на пригорке» и отождествить слово «пригорок» со словом «где», поскольку все остальное у вопроса и исходного предложения будет совпадать. На сайте www.aot.ruлюбой желающий может ввести свое предложение и попробовать выстроить похожую семантическую структуру. Во многих случаях она не будет полностью связанной - из-за неполноты словарей (сейчас их наполнение составляет 50 процентов) или ошибки во входном предложении.
Как же осуществляется машинный перевод на базе аотовской семантической структуры? По русской семантической структуре строится такая же, но уже английская, в узлах которой стоят английские слова или устойчивые словосочетания. Затем по семантической структуре синтезируется цепочка английских слов. Например:
Руccкое предложение: «Своим неожиданным приездом он застал меня врасплох».
Русская семантическая структура:
Английская семантическая структура:
Английский перевод: «He took me by surprise by his unexpected arriving».
Теперь понятно, что использование аотовской семантической структуры полезно как в вопросно-ответных системах и системах машинного перевода, так и в любых системах автоматической обработки текста. Самый серьезный недостаток нашего подхода в том, что семантика работает довольно медленно (двадцать слов в секунду), но качество того стоит. Как же строится семантическая структура?
Первый этап - построение узлов и словарных интерпретаций каждого узла. В большинстве случаев узел - это одно слово, но могут быть и словосочетания (например, «застать врасплох»). В прикладной лингвистике нет четких границ между понятием устойчивого словосочетания и свободной цепочки слов. Но есть некоторые методологические принципы. Один из них - принцип удаления: cемантическая или синтаксическая структура некоторой фразы P должна быть инструкцией по добавлению или удалению разных частей этой фразы. Причем при любых модификациях структуры действуют два правила:
cтруктура не должна содержать разрывов.
чем ближе друг к другу слова в структуре, тем сильнее их смысловое взаимовлияние. Слова, стоящие в одном узле, должны оказывать друг на друга максимальное влияние, именно об этом думают составители словаря, когда указывают, что те или иные слова образуют устойчивое словосочетание.
Словарная интерпретация узла - это множество словарных статей, в каждой из которых записано, какими другими узлами может управлять данный узел.
На втором этапе первичного семантического анализа строится граф гипотетических связей - в котором отношения между узлами проводятся только на основе грамматических условий. Граф гипотетических связей почти всегда содержит много лишних гипотез, которые придется отбрасывать на последнем этапе.
Например, для фразы: «Одной из главных задач 1999 года Банк России считает восстановление доверия населения и хозяйствующих субъектов к российскому рублю» будет построен такой граф гипотетических связей (рис. 1).
Не пытайтесь понять эту структуру, просто подумайте, о том количестве вариантов, которые машина должна перебрать, чтобы получить дерево.
Третий этап первичного семантического анализа - получение деревьев и выбор лучшего дерева по строгим лингвистическим критериям. Например, предыдущий граф будет превращен в следующий (рис. 2).
