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

Томита-парсер — созданный компанией Яндекс вариант GLR-парсера (от англ. GeneralizedLeft-to-rightRightmostderivationparser — Обобщенный восходящий магазинный анализатор), впервые описанного Масару Томита в 1984 году. В настоящее время открытый код парсера доступен для разработчиков в коммерческих и некоммерческих целях. В составе парсера три основных лингвистических процессора: токенизатор (осуществляет разбиение входного текста на слова и несловарные токены), сегментатор (разделяет текст на предложения) и морфологический анализатор mystem (производит частеречную разметку).

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

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

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

Грамматики для Томита-парсера состоят из правил. У каждого правила есть левая и правая части, разделенных символом —>. В левой части стоит один нетерминал (S в примере, приведенном ниже). В правой части стоит список терминалов или нетерминалов (S1 … Sn), после которого указываются условия (Q), применяемые ко всему правилу в целом.

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

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

Для запуска Томита-парсера созданы файлы: config. proto — конфигурационный файл парсера (сообщает парсеру, где искать все остальные файлы и как их интерпретировать); dic. gzt — корневой словарь, содержит перечень всех используемых в проекте словарей и грамматик; mygram. cxx — грамматика;kwtypes.proto — описания типов ключевых слов.

Фрагмент файла dic. gzt:

encoding «utf8» ;

import «base.proto» ;

import «articles_base.proto» ;

import «kwtypes_my.proto» ;

import «facttypes.proto» ;

TAuxDicArticle «LOC» .

{.

key = { «tomita:loc.cxx» type=CUSTOM }.

}.

city «Нижний_Новгород» .

{.

key = «Нижний Новгород» ;

mainword = 2;

}.

city «Санкт_Петербург» .

{.

key = «Санкт-Петербург» | «Питер» | «Петербург» ;

lemma = «Санкт-Петербург» ;

Фрагмент файла config. proto:

encoding «utf8» ;

TTextMinerConfig {.

Dictionary = «dic.gzt»; // корневой словарь газеттира.

PrettyOutput = «debug.html»; // файл с отладочным выводом.

Input = {.

File = «test.txt»; // файл с анализируемым текстом.

Type = dpl; // режим чтения «document per line» (каждая строка — отдельный документ).

}.

Articles = [.

{ Name = «LOC» } // Запустить статью корневого словаря «Location» .

].

Facts = [.

{ Name = «LocFact» } // Сохранитьфакт «LocFact» .

].

Output = {.

File = «facts.txt»; // Записатьфактывфайл «facts.txt» .

Format = text; // используя при этом простой текстовый формат.

}.

}.

Алгоритм работы парсера:

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

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

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

На последовательности множеств терминалов GLR-парсер строит все возможные варианты разметки. Из всех построенных вариантов также отбираются те, которые как можно шире покрывают предложение.

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

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