Сегментатор предложений

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

Если в качестве разделителей используется точка, то она обрабатывается особым образом, в отличие от знаков «?» и «!». Дело в том, что некоторые слова могут содержать точку, и это не должно вызывать обрыва предложения. Типичный пример - сокращения типа "т.е." или аббревиатуры типа "Р.С.Ф.С.Р.". Аналогично особо обрабатываются числа с десятичной точкой "3.141".

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

Токенизация

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

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

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

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

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

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

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

Границы слов

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

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

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

Граф токенизации

Результат работы лексера - направленный граф, не имеющий циклических путей. В простейшем случае это цепочка токенов без ветвлений:

Рис. 1.1 – Пример простого графа токенов

В более сложных случаях появляются альтернативные пути токенизации:

Рис. 1.2– Пример токенизации

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

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

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

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

В качестве иллюстрации алгоритма построения графа токенизации рассмотрим следующий пример. Изменим режим обработки текста на русском языке таким образом, чтобы лексер не использовал пробелы в качестве естественных маркеров границ слов. Исходная цепочка символов будет такой ЯМЫАРФУ. Нетрудно проверить, что без учета синтаксических правил эта цепочка допускает множество вариантов разбивки на слова.

Рис. 1.3 – Граф синтаксических правил.

Некоторые пути прерываются из-за невозможности найти в словаре подходящее слово. На этом примере хорошо видно, что простой жадный алгоритм, работающий по правилу “брать из входного буфера максимально длинное слово, найденное в лексиконе”, не работает. На первом шаге он извлек бы “ЯМУ” и далее не смог бы продолжить работу. Если добавить в такой жадный алгоритм механизм отката назад при невозможности продолжить токенизации, то он выдал бы в выходной буфер цепочку Я МЫЛА РФ У, которая хотя и содержит только словарные лексемы, но все-таки является ошибочным разбиением.