как продавать трафик | полезные скрипты | технические вопросы

вопросы хостинга | продвижение сайтов | поисковые системы

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

Автор: И. В. Сегалович
Источник: Яндекс

грузоперевозки 5 тонн, заказ. | Рыбалка на Кольском полуострове. Рыболовный Гид

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

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

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

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

Традиционное представление словарей в программах для IBM PC использует блочно-слотовую организацию, хранящую непосредственный текст основы и закодированное описанием морфологии рядом с ним. Размер такого словаря (на 100–120 тыс слов) обычно составляет 600–800 KB, а процедура идентификации основы включает (под MS-DOS непременно, под MS-WINDOWS чаще всего) чтение одного или нескольких блоков с диска, а затем многократное сопоставление гипотетической основы с основами внутри блока.

Предельно компактное и эффективное решение задачи проверки правописания английских слов было предложено McIllroy 1978, 1982. Решение включало процедуру анализа аффиксов (то есть набор правил для отбрасывания префиксов и суффиксов и список исключений из этих правил) и специальное представление текстов основы. Это представление заменяет текст основы на сответствующий ему бит из хэш-таблицы большого размера. Объем памяти, требуемый для представления одной основы, таким образом, сводится до 14 бит. В то же время порождается ошибка, при которой неправильное слово может быть ошибочно принято за правильное. Вероятность возникновения такой ошибки, впрочем, существенно мала, и может быть понижена за счёт большего разрежения таблицы.

Идея использовать такое представление в русском грамматическом словаре показалась автору в начале 1993 года весьма заманчивой. Для этого необходимо было решить несколько проблем:

Результатом специальной трансляции грамматического словаря, полученного автором в ИППИ РАН и представленного в соответствующем формате, явился словарь на 108 тысяч основ со следующими параметрами:

Занимаемый объем:

Скорость разбора русского текста показывает следующая таблица:

ПроцессорСлов в секунду
286300–500
386SX700–900
386DX900–1300 (до 2000 в 32-битном режиме)
4862500–4000 (до 6000 в 32-битном режиме)

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

Оптимизировалась также технология хранения грамматической информации:

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

Вокруг хэш-словаря сложилась технология построения информационно-поисковых систем (реализуемая в проекте Яndex), которая основывается на следующих идеях:

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

 

как продавать трафик | полезные скрипты | технические вопросы

вопросы хостинга | продвижение сайтов | поисковые системы