Национальные особенности поисковых систем

Зашла речь о том, кто чем занимается, и, услышав про проверку правописания, водитель сказал: «А, ну ясно – взяли западную программу и приладили к русскому языку. Я знаю, как это делается».

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

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

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

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

Основные понятия

Не будем уточнять, в каком формате и в какой именно системе документооборота хранятся наши документы. Допустим, что нам необходимо найти нужный документ в таком множестве документов, что невыгодно всякий раз просматривать их все подряд; если же документов много, то искать нужный документ следует по его содержанию (тексту), а не по так называемым реквизитам – дате создания, размеру, автору и пр.

Сценарий поиска документа при помощи поисковой программы обычно очень прост – вы вводите запрос на поиск, состоящий из одного или нескольких слов, после чего предъявляется список имен найденных документов. При желании можно открыть любой из найденных документов; если поисковая система позволяет, искомые слова в документе выделяются – «подсвечиваются».

• Что можно вводить в качестве запроса – слова, словосочетания, предложения на естественном языке? Нужно ли задавать запрос в виде логической формы из слов?
• Что является единицей поиска – предложение, документ, абзац?
• Находятся ли все грамматические формы слов, различаются ли прописные и строчные буквы, синонимы, близкие по смыслу документы?
• Упорядочивается ли список найденных документов и как?

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

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

Релевантность

Найденный по запросу документ может иметь отношение к запросу, т. е. содержать нужную (искомую) информацию, а может и не иметь к запросу никакого отношения. В первом случае документ называется релевантным (по-английски relevant – «относящийся к делу»), во втором – нерелевантным, или шумовым.

Полнота и точность поиска

Основными понятиями в мире поисковых средств являются точность и полнота поиска.

• Точность поиска – это параметр, показывающий, какова доля релевантных документов в общем числе найденных.
• Полнота поиска – дополнительный параметр, показывающий, какова доля найденных релевантных документов в общем количестве релевантных документов. Если в области поиска на самом деле имеется 100 документов, содержащих нужную информацию, а по запросу найдено из них всего 30, то полнота поиска равна 30%.

Ясно, что и точность поиска, и его полнота зависят не только от свойств поисковой системы, но и от правильности построения конкретного запроса, а также от субъективного представления пользователя о том, что такое нужная ему информация.

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

Индексация

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

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

Поиск по комбинациям слов

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

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

Единица поиска

Как ни удивительно, одно из основных понятий в мире поисковых систем – единица поиска – находится на заднем плане и редко встречается в рекламе и обзорах поисковых средств.

Единица поиска – это квант текста, в пределах которого в данной поисковой системе мы признаем слова запроса встретившимися совместно.

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

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

Ранжирование результатов поиска

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

Итак, суммируем сказанное: основным показателем качества поисковой системы является соотношение полнота-точность. Система должна уметь индексировать документы заранее, в режиме off-line, а также быстро пополнять индекс в режиме on-line, проводить поиск по комбинациям слов, помнить координаты слов в документах и ранжировать найденные документы по их релевантности.

Необходимый минимум русификации

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

Форматы и кодировки

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

Очевидно, для правильного поиска документов поисковая система должна уметь иденцифицировать разные кодировки русских букв. Эти кодировки различны, например, для текстовых файлов в формате ASCII и для текстовых файлов Windows. В последнее время все активнее применяется новый, 16-разрядный стандарт кодирования символов – Unicode (www.unicode.org).

Сейчас многие сталкиваются с необходимостью производить поиск также среди документов, полученных из сети Интернет или созданных для публикации в сети, т. е. приготовленных в формате HTML. К сожалению, с русским языком и тут возникают дополнительные сложности – на просторах Интернета «гуляют» еще несколько кодировок кириллицы (наиболее известной альтернативой самой популярной кодировке Windows CP1251 является КОИ-8, но есть и другие).

Кроме кодировки поисковая система должна также правильно определять формат документа. Даже если русские буквы в документе находятся в нужной кодировке, неправильное определение его формата приведет к той же «гречке» и не позволит искать заданные слова. Как минимум, поисковая система должна различать форматы ASCII, Windows ASCII, RTF, Microsoft Word, HTML.

Выделение слов

Чтобы отыскать в тексте слово, нужно хотя бы знать, где в нем находятся слова. Хотя, в отличие от древних языков, в настоящее время принято употреблять пробелы между словами, выделение слов – не такая простая задача, как кажется.

Обычно словом считается последовательность букв «от разделителя до разделителя». Разделителями считаются пробелы, знаки препинания и прочие неалфавитные символы. Однако имеются символы, которые, не будучи буквами, не являются и разделителями в полном смысле этого слова. К ним относятся, в частности, апостроф «‘» и дефис «-». Действительно, иногда дефис разделяет части слова (кто-нибудь, сине-зеленый), а иногда – самостоятельные слова (мать-одиночка). Апостроф, особенно в английском языке, может являться самостоятельной частью слова (don’t, Д’Артаньян), а может использоваться просто в качестве кавычек.

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

Ох уж эта буква «ё»...

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

Многие помнят, например, что встроенный редактор в Norton Commander 3.0 не позволял вводить русскую букву «р», и ее приходилось заменять латинской буквой «p». До сих пор встречаются тексты, где слова с буквой «р» набраны неправильно; в частности, такие слова и сейчас часто встречаются даже в известных электронных энциклопедиях отечественного производства, что заставляет при поиске словарной статьи запрашивать эти слова дважды – с русской и с латинской буквой.

Известно также, что версия 2.0 текстового редактора Microsoft Word не позволяла выделить русское слово щелчком мыши – выделение обязательно «разбивалось» буквой «ч». Естественно, и тезаурус, и проверка правописания, и поисковая «машинка» в Word 2.0 работали на русских текстах с перебоями.

А буква «ё» долгое время была падчерицей для текстовых редакторов и экранных и клавиатурных драйверов. До сих пор в некоторых почтовых системах русская буква «ё» зачастую «съедается», превращаясь в неалфавитный символ. Но это не главная проблема со строптивой буквой.

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

Очевидно, правильная система поиска должна признавать все комбинации с буквой «ё» за одно и то же слово. Обычно для простоты это делается так: и при индексации, и при поиске буква «ё» всегда «понижается» до «е».

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

Продвигаемся дальше.

Прописные и строчные буквы, джокеры и прочее

Искомое слово чаще всего представляет собой нечто большее, чем последовательность знаков.

Полнота поиска по строке обеспечивается за счет таких стандартных средств, как отождествление заглавных и малых букв (что тоже требует чувствительности к языку) и джокеры (wildcards) наподобие «*» (что означает любое количество любых символов). К сожалению, при этом резко возрастет количество шума, т. е. понизится точность поиска. Для коротких слов уровень шума при использовании шаблонов будет чрезвычайно высоким.

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

Слова, склонные к перемене

Почти любое русское слово – это на самом деле набор из нескольких словоформ. Для среднего русского существительного таких форм двенадцать – одна основная и 11 косвенных (6 падежей единственного и 6 множественного числа). У русского глагола косвенных форм порядка 25 (а если считать формы причастий, то и все 200). В процессе словоизменения общий смысл слова остается тем же, изменяются только форма и роль слова в предложении.

Как справиться с этим разнообразием? Нужен так называемый морфологический поиск, т. е. поиск, опирающийся на знание морфологии языка (науки о словоизменении).

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

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

Любая серьезная поисковая система, применяемая в России, должна иметь основанный на словаре морфологический анализ слов русского языка. Обычно полноценный словарь для русского языка должен включать не менее 100-120 тысяч основ слов, а таблицы окончаний – не менее нескольких сотен наборов эквивалентных окончаний.

Генрих VIII и бензин АИ–93

Когда размышляешь над проблемами поиска документов, не сразу приходит в голову, что для полнотекстового поиска не менее, чем слова, важны другие текстовые объекты, а именно — даты, числа, сокращения, денежные суммы.

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

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

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

Не нужно лишних слов

Ясно, что некоторые слова в общем-то никогда не попадут в исло искомых. Подобные слова называются шумовыми, или «стоп-словами».

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

В процессе разработки программ проверки правописания мы сделали интересные практические наблюдения. Список из 400 наиболее часто употребляемых слов русского языка (конечно, со всеми их грамматическими формами) экономит обращения к словарю в 30% случаев, т. е. грамматические формы этих четырех сотен слов, всего около 2000 форм, составляют одну треть всех слов в «среднем» тексте. В основном этот список состоял из неизменяемых предлогов, частиц и местоимений, но в него входили и глаголы наподобие «делать». Частотный список на 8000 слов покрывал уже 80% всех словоупотреблений в текстах.

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

Легко ли отличить законченную мысль?

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

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

Кроме всего прочего, граница предложения очень важна при поиске словосочетаний, так как словосочетания всегда существуют только внутри предложения.

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

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

На пути к идеалу

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

Нечеткий ответ лучше четкого

Так называемый булевский поиск заставляет пользователя фактически заниматься программированием на языке, состоящем из операторов «И», «ИЛИ», «НЕ», «РЯДОМ» и других, более изощренных. И это не поверхностная аналогия: построение удачного запроса к булевской поисковой системе может потребовать длительной отладки и исправления ошибок. Именно поэтому в большинстве поисковых систем есть средства ведения истории запросов.

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

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

Такие поисковые системы существуют и успешно работают; этот подход избавляет пользователя от каких-либо хлопот при формулировании запроса.

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

Ручка, ручонка или ручища

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

Однако для классического морфологического анализа пары слов «кожа» и «кожаные», «Турция» и «турецкий» включают совершенно разные слова, а не формы одного слова.

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

«Звездочка» на конце слов не спасает положения.

В качестве примера типов словообразования, широко распространенных в русском языке, можно привести:

1. видовые пары (вставать – встать, садиться – сесть). Этот вид словообразования (а точнее, родства слов) является одним из самых мучительных для иностранцев, изучающих русский язык;

2. отглагольные существительные и прилагательные (проверять – проверка, проверочный);

3. прилагательные, образованные от существительных (нога – ножной, акция – акционерный);

4. уменьшительные и увеличительные степени (рука, ручка, ручонка, ручища);

5. дефисные образования (человек-невидимка, давай-давай, год-полтора, черно-красный, весело-хмельной, художественно-строительный);

6. приставки «пол» и «полу» (полстакана, полукруг, полушайба).

Для учета связей между «родственниками» нужен словообразовательный словарь. Такие словари для русского языка имеются, и высокого качества, например словари Улуханова и Тихонова.

Печь или не печь

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

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

Есть и другой вид омонимии – многозначность слова. Известный пример: слово «ключ», которое в зависимости от контекста может означать «родник», «инструмент для запирания двери» или «разгадку».

В русском тексте омонимия может достигать 20% (каждое пятое слово имеет больше одного значения или объяснения); в английском языке омонимия еще выше, так как почти у всякого английского существительного есть омоним-глагол, и наоборот, однако омонимия по словоформам в английском языке встречается значительно реже.

Ясно, что для снятия даже простой грамматической многозначности (разрешения омонимии) нужно использовать не только само слово, но и его окружение.

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

Для русского языка одним из основных методов является использование окончаний слов для определения их согласованности между собой. А для английского языка данный метод неприменим из-за практического отсутствия окончаний.

Есть также возможности для разрешения смысловой омонимии, заключающиеся в использовании статистических сведений о совместной встречаемости слов.

Облигации или ценные бумаги?

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

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

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

Холодно-горячо

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

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

P. S. Вот обещанная отгадка: слово «простой» является, в частности, формой повелительного наклонения глагола «простоять», предлог «при» совпадает с формой родительного падежа существительного «пря» (устаревший вариант слова «распря»), а «трусь» – это также форма первого лица единственного числа глагола «тереться».

КОРОТКО ОБ АВТОРЕ: