Лексер

Назначение и использование лексера

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

Письменная речь может быть представлена печатным текстом (цепочки символов) или графически (отсканированный текст).

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

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

Лексер может использоваться прикладным пользовательским кодом либо явно с помощью вызова функции sol_Tokenize в процедурном API или неявно, при вызове полнотекстового анализа, например sol_MorphologyAnalysis. Обратите внимание, что при вызове лексера через функцию sol_Tokenize результаты отдаются в упрощенном виде, как одна из цепочек токенов в графе, обычно самая короткая.

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

Программирование, настройка и оптимизация лексера и токенизатора

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

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

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

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

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

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

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

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

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

Еще один флаг в описании языка, оказывающий влияние на работу сегментатора - SentenceBrokerFlags. Среди элементов этого флага есть значения:

UseLexicon - использовать лексикон для определения полных словоформ. Точка после полной словоформы считается безусловным разделителем предлодений.

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

MinFormLen=n - минимальная длина полной словоформы.

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

В API движка есть несколько вызовов для использования сегментатора предложений - см. sol_CreateSentenceBroker, sol_CreateSentenceBrokerMem[W,A,8], sol_FetchSentence, sol_GetFetchedSentence[W,A,8], sol_DeleteSentenceBroker. Примеры токенизации для множества особых случаев можно посмотреть в программе-примере TestLexicon.

Они позволяют выполнить разбор текста, заданного строкой в памяти, или содержащегося в дисковом файле. Функции sol_CreateSentenceBroker и sol_CreateSentenceBrokerMem[W,A,8] возвращают объект-перечислитель (итератор), который позволяет продвигаться по тексту с шагом в одно предложение и получать текст каждого извлеченного предложения.

Токенизация

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

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

Энергичный и ленивый режимы лексера

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

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

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

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

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

Границы слов

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

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

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

Тип токенизации определен параметром Segmentation в описании языка. Его значение whitespace означает использование пробелов в качестве естественных границ слов. Значение dictionary_lookup означает, что для разбивки на слова используется просмотр по лексикону по принципу "пытаться найти слова, начиная с текущей позиции, затем - следующее слова после них".

В последнем случае вместо встроенного в движок алгоритма можно использовать внешний токенизатор, оформленный как динамически загружаемая библиотека. Имя файла библиотеки без расширения .DLL или .SO задается параметром SegmentationEngine в описании языка. Например, для японского языка в файле sg_languages.sol можно увидеть такие строки:

language Japanese as JAPANESE_LANGUAGE
{
  ...
  Segmentation = dictionary_lookup
  SegmentationEngine = cabocha_segmenter // используем внешний сегментатор в виде cabocha_segmenter.dll
  ...
}

Функции, которые внешний токенизатор должен экспортировать, описаны в следующем разделе.

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

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

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

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

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

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

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

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

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

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

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

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

Ветвления и неоднозначная токенизация

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

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

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

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

Жадные правила и недетерминированность алгоритмов

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

Во всех таких случаях следует понимать ключевую особенность управляемого такими правилами алгоритма - его недетерминированность. Иначе говоря, в случае успешного применения правила алгоритм делает ветвление на 2 альтернативных варианта дальнейшего анализа. В одном варианте правила применено и рабочая среда пришла в новое состояние. Во втором варианте правило не применено и рабочая среда осталась нетронутой. Если после этого поток исполнения будет применять другое правило, то получим новый альтернативный вариант изменения исходной среды. Все это относится к нежадным правилам. Алгоритм в этом случае ведет себя в целом недетерминированно. Если же применяемое правило объявлено жадным, то состояние среды до правила не сохраняется.

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

Многословные лексемы

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

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

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

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

I listened in breathless silence.

I listened in to your presentation.

В первом случае имеем форму прошедшего времени глагола to listen, и обстоятельство с предлогом in. Можно еще заметить, что in в английском языке может выступать также в роли наречия, но в данном случае это не играет роли.

Во втором случае имеем форму прошедшего времени фразового глагола to listen in. Вторая часть in тут является послелогом. Но в описании английской морфологии такая часть речи не определена, вместо этого лексикон содержит словарную статью для глагола to listen in:

английский глагол to listen фразовый глагол to listen in

В пользу именно такого решения служит то, что значения глаголов to listen in и to listen отличаются. В русском языке аналогичная ситуация регулярно наблюдается для глаголов несовершенного вида и их дериватов совершенного вида, образуемых с помощью различных приставок:

слушать - подслушать

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

I listen in to your presentation

и создает 2 варианта токенизации, соответствующие разным интерпретациям слов listen и in, и только применив правила английской грамматики, выберет из них вариант с фразовым глаголом to listen in. Ключевое правило в данном случае - эвристика, которая запрещает соседствовать словам in и to.

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

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

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

Поэтому лексер, не умея учитывать синтаксические правила, вынужден выполнить ветвление:

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

В противном случае останется только вариант с многословным токеном, как видно на примере с предлогом на потребу:

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

Правила, управляющие токенизацией

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

Рассмотрим сначала письменную печатную речь с пробельной сегментацией.

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

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

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

Имена правил

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

Примеры правил

Вы можете увидеть учебные примеры описываемых правил в исходном тексте tiny_russian_syntax.sol, входящем в SDK Грамматического Словаря.

Символы-разделители

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

language Russian
{
 ...
 WordBrokers = ";:-—<>\".,!?&=+(){}[]\r\n\t« »“”„/"
 ...
}

Обратите внимание, что каждый язык может (и обычно должен) иметь свой набор символов-разделителей. Кроме этого, включать символы в этот список следует аккуратно, рассматривая все морфологические последствия. К примеру, в английском языке символ апострофа может быть разделителем, когда употребляется в ограниченном числе конструкций с так называемыми clitics, к которым относятся 'm, 's, 've, 'd, 'll:

I'am here.

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

man's

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

С помощью SQL запросов можно посмотреть или изменить списки символов-разделителей в словарной базе:

SELECT P.param_value
 FROM  sg_language L, lang_param P
 WHERE L.name='RUSSIAN' AND P.id_language=L.id AND P.param_name='WordBrokers'

Правила unbreakable

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

Пример правила для русского языка, которое выделяет цепочку “т.е.” как одно слово:

unbreakable language=Russian { "т.е." }

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

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

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

{n,m} - цепочка символов с заданием минимальной и максимальной длины. Значения m или n можно опустить: {,n} или {m,} в этом случае пропущенный элемент задает соответственно 0 или бесконечность.

* цепочка символов (символ определен слева) любой длины, включая 0; полностью аналогично {0,}; в регулярных грамматиках этот символ называется "Kleene star".

+ цепочка символов (символ определен слева) любой длины, начиная с 1; полностью аналогично {1,}. В регулярных грамматиках этот символ называется "Kleene plus".

? один символ (задан слева) или пустая подстрока; полностью аналогично {0,1}

Особый случай {m} задает цепочку символов точно определенной длины.

[abc...yz] - любой один символ из заданного набора, регистр не имеет значения

[<abc...yz>] - любой один символ из заданного набора, с точным соблюдением регистра

[:digit:] - цифра

[:space:] - пробельный символ

[:punct:] - пунктуатор

Пример задания паттерна:

unbreakable language=Russian { ~"[:digit:][:digit:]-е" }

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

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

Правила переписывания токенов token_rewriter

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

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

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

l'Italie

c'est

j'ai

qu'est-ce

n'aime pas

t'appelles

s'interessent

d'Europe

И конечно же не обошлось без исключений, когда апостроф нежелательно рассматривать как разделитель:

d'ou

Таким образом, апостроф сам по себе не формирует лексему, но обычно является индикатором сокращенной формы слова-префикса. Вот правило, которое отщепляет односимвольный префикс:

token_rewriter Prefix_splitter greedy language=French
{
 if { ~"([lcjntsd]')(.+)" } then { "?1" "?2" }
}

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

Результативная часть правила перечисляет индексы на группы в сопоставленном регулярном выражении. Знак вопроса служит индикатором того, что терм выдает при выполнении правила подстроку с указанным индексом. Индекс 0 обозначает всю исходную лексему, поэтому в правиле используются индексы 1 и 2.

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

Что получится, если правило будет применено к лексеме l'Italie?

Регулярное выражение будет успешно сопоставлено с лексемой. Группы 1 и 2 будут соответствовать фрагментам l' и Italie. Таким образом, на выходе будет цепочка из двух лексем - сокращенной формы определенного артикля и существительного.

Теперь рассмотрим, как правила переписывания работают при коррекции опечаток.

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

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

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

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

Пример жадного правила, которое делает замену незнаю на не знаю:

token_rewriter не_знаю greedy language=Russian
{
 if { незнаю } then { не знаю }
}

Пример нежадного правила, которое заменяет плач на плачь:

token_rewriter плач_ь nongreedy language=Russian
{
 if { плач } then { плачь }
}

В данном случае мы с одной стороны скорректировали ошибочную запись инфинитива без конечного мягкого знака, а с другой допустили возможность, что тут все-таки написано существительное: не плач, а рев. Какой из вариантов окажется правильным будет решать синтаксический анализатор с использованием своих средств. Что будет делать лексер, получив на входе предложение "Не плач, Мальвина"? Он построит такой граф:

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

В нём будет развилка, с двумя альтернативными вариантами для "плач". Парсер распознает в этом графе императивную конструкцию и построит именно для нее синтаксическое дерево.

Алгоритмы коррекции ошибок

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

1. Слово ошибочно разбито на 2 слова: Оля взяла не большое яблоко.

2. Два слова ошибочно записаны слитно: Оля неможет решить задачу.

3. Пропущено служебное слово: Оля взглянула кошку.

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

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

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

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

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

Рассмотрим на примерах работу алгоритмов коррекции. Для этого удобно использовать утилиту Syntax. Это консольный интерактивный отладчик, который позволяет вводить с клавиатуры предложения, менять режимы работы парсера и видеть результаты анализа. Он входит в состав SDK Грамматического Словаря. Запускаем его с помощью скрипта ...\scripts\syntax\console-syntax.cmd. Вводим директиву #allow_reco, которая включает алгоритмы коррекции ошибок. Затем вводим предложение "Оля взяла не большое яблоко". Результаты синтаксического анализа будут содержать восстановленное прилагательное небольшое:

коррекция разрыва слов в лексере

Проверим, как лексер поступит с двумя словами, ошибочно написанными слитно. Введем предложение "Оля неможет решить задачу". В дополнение к директиве #allow_reco, введем также #traceon, чтобы увидеть, какие попытки делает лексер для исправления ошибок. Получится что-то вроде такой картины:

коррекция слитного написания двух слов в лексере

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

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

коррекция пропуска предлога в лексере

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

В состав SDK Грамматического Словаря входит утилита Reconstructor2, с помощью которой можно сформировать свою базу корректирующих правил. Для этого необходимо отредактировать текстовый файл ...\scripts\reco2\ngrams.csv и запустить ...\scripts\reco2\learn.cmd. В подкаталоге ...\bin-windows появится новый файл reco2.db с правилами. Вы можете поменять имя этого файла, одновременно изменив значение в узле <reco2_db>reco2.db</reco2_db> в конфигурационном файле словаря.

Размещение загружаемых сегментаторов

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

API загружаемых токенизаторов

DLL должна экспортировать несколько функций.

Создание экземпляра сегментатора и его инициализация

void* Constructor( const wchar_t * DataFolder, const wchar_t * Params )

Аргументы:

DataFolder - путь к папке с файлами данных, необходимых сегментатору. Этот путь может указывать на ту же папку, откуда загружена библиотека DLL/SO сегментатора, но в конфигурационном файле словаря в узле segmenter/datapath может быть указан другой путь.

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

Возвращает:

Конструктор должен вернуть указатель на объект, который будет затем передаваться в остальные вызовы API токенизатора как аргумент This. Очень удобно внутри DLL создать в динамической памяти объект со всеми необходимыми ссылками на выделенные ресурсы, чтобы аккуратно освободить их при вызове деструктора Destructor. Кроме того, ничто не запрещает движку создавать одновременно множество токенизаторов с разными настрояками, например для разных вариантов языка. Хранить индивидуальные настройки каждого экземпляра удобно в созданном объекте, указатель на который возвращается конструктором.

Удаление экземпляра сегментатора

void Destructor( void *This )

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

Получение свойств сегментатора

const wchar_t* GetSolarixPluginProperty( void *This, int iProp, int iSub )

Возвращает параметры плагина. Аргумент iProp определяет запрашиваемый параметр, для токенизатора имеют значение только четыре параметра: 0 - должно быть возвращена строка "segmenter", 1 - произвольное название плагина, 2 - любое краткое примечание, 10 - морфологические сегментатора, если вернет строку "classes", то значит он может определять для выделенных слов их грамматические классы. В последнем случае можно вызвать процедуру Segmenation с параметром Params=1, что заставит модуль вернуть разобранный текст в виде XML блока с дополнительными пометками для слов (см. далее).

Изменение параметров работы сегментатора

bool SetSolarixPluginProperty( void *This, int iProp, int iSub, const wchar_t *Value )

В текущей версии не используется.

Получение кода последней ошибки

int GetError( void *This )

Возвращает 0, если ошибок не было, либо ненулевой код ошибки.

Копирование текста ошибки в буфер

int GetErrorText( void *This, wchar_t *Buffer, int BufferLen )

Возвращается длина текста ошибки, измеряемая в единицах широких символов. Если задать аргумент Buffer как NULL, то функция должна вернуть необходимую длину буфера, чтобы выделить под него память и вызвать GetErrorText уже для копирования.

Выполнение сегментации текста

wchar_t* Segmentation( void*This, const wchar_t *OriginalText, wchar_t WordDelimiter, int Params )

Выполняет сегментацию текста в OriginalText. Результат возвращается как указатель на строку, в которой токены разделены символом WordDelimiter. Дополнительные флаги передаются через Params. В текущей версии этот аргумент может быть равен 0 или 1. Для 0 возвращается строка в plain text формате, а для 1 - в формате XML с такой структурой, пример для входного предложения 象は動物です。:

Токенизация японского текста

void SegmenterFreeString( void *This, wchar_t *Ptr )

Освобождает память, выделенную в Segmentation для возвращаемой строки. Так как DLL токенизатора и прикладной код могут использовать разные менеджеры динамической памяти, либо прикладная программа вообще не поддерживает работу с динамической памятью в C-стиле, то вызов Free - единственный надежный способ избежать утечки памяти при множестве вызовов Segmentation.

Отладка лексера

Для отладки лексера следует использовать утилиту Syntax, которая входит в состав SDK словаря. Вызовите ее с опциями командной строки -tokenize -language Russian или введите команду #tokenize после запуска. Введите предложение "мама мыла раму вместе с Машей", которое мы рассматривали при обсуждении ветвлений в графе. Вы увидите следующее:

отладка лексера

В отладчике все пути в созданном графе, заканчивающиеся токеном END, выводятся на консоль. В данном примере получается 2 пути.

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

отладка лексера

Дополнительные материалы

Процедура sol_Tokenize в API

Алгоритмы русской морфологии

Морфологический анализатор

API морфологического анализатора

Синтаксический анализатор

Лексикон

Языки

Словарные статьи

Внутренний язык грамматической машины

Утилита Syntax

  © Elijah Koziev 2010
прикладные проекты на основе грамматического словаря API грамматической машины компоненты для доступа к грамматическому словарю условия получения SDK токенизатор и сегментатор морфологический анализ и синтез лемматизатор база N-грамм синтаксический анализатор словоформы морфология и синтаксис русского языка падеж число род совершенный и несовершенный вид экспорт в SQL формат экспорт в XML формат скрипт SQL словаря структура SQL словаря структура XML словаря компоненты для доступа к грамматическому словарю ORM Persistent Dictionary Library лемматизация стемминг примеры использования грамматического словаря склонение существительных в русском языке склонение русских прилагательных спряжение глаголов в русском языке поиск текста с учетом морфологии OCR подсистема расширенные регулярные выражения генератор текста генератор случайного текста и имитатор рандомизатор синонимизатор перефразировщик Статистика буквенных паттернов

Грамматический словарь русского языка



Грамматический словарь
склонение и спряжение глаголов, существительных, прилагательных

В состав входит русский и английский словарь.

платформа:  Windows 2000 ... Windows 7
требования: 512 Mb свободной памяти, 300 Мб на диске
размер:         34 Мб

  скачать грамматический словарь купить грамматический словарь SDK грамматического словаря
грамматический словарь русского языка



SDK Грамматического словаря



SDK Грамматического Словаря
склонение и спряжение глаголов, существительных, прилагательных

В состав входит русский и английский словарь.

платформа:  Windows 2000 ... Windows 7
размер:         13 Мб

SQL словарь (демо):
sqlite mysql oracle firebird mssql

скачать демо-версию SDK купить SDK API грамматического словаря



Поисковая система



Integra
настольная и сетевая поисковая система 

платформа:  Windows XP ... Windows 7
требования: 512 Mb свободной памяти
размер:         21 Мб

Дополнительные компоненты:
MySQL поисковый сервер 13.5 Мб
Integra.Premium MySQL 3.9 Мб

скачать поисковую систему SDK поисковой системыописание поисковой системы



SDK Поисковой системы



SDK Поискового движка
API для настольной и сетевой поисковая система 

платформа:  Windows XP ... Windows 7
размер:         17 Мб

Дополнительные компоненты:

MySQL поисковый сервер 13.5 Мб
Integra.Premium MySQL 3.9 Мб

скачать SDK SDK поисковой системы



Экранный переводчик



Translator
экранный переводчик

платформа:  Windows XP ... Windows 7
требования: 256 Mb свободной памяти
размер:         4.4 Мб

Дополнительные компоненты:
расширенный англо-русский словарь 6.4 Мб


скачать экранный переводчикописание экранного переводчика



изменено 23-Nov-12