Software & Systems

Любая система, работающая с текстом и использующая морфологический анализатор со словарем основ, сталкивается с проблемой обработки незнакомых слов – лексем, по тем или иным причинам отсутствующих в словаре. Классический труд А.А. Зализняка [1], лежащий в основе большинства современных машинных морфологий русского языка, содержит описания около 100 тысяч слов. Размеры морфологических словарей, используемых в различных прикладных системах, варьируются довольно широко: от 90 тысяч [2] до более 161 тысячи лемм [3]. Однако и при увеличении объема словаря проблема анализа незнакомых слов сохраняется. Одна сторона этого явления связана со словообразовательными возможностями языка, другая – с существованием принципиально открытых категорий лексики (термины, диалектизмы, профессионализмы, разные виды слэнга, разговорная лексика и, наконец, имена собственные).

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

Современные морфологические анализаторы обычно снабжаются специальными механизмами, позволяющими определять морфологию незнакомой словоформы с приемлемым качеством. Эти механизмы основываются либо на некоторой вероятностной модели, либо на правилах [2–4].

В системе интеллектуального анализа текста «Исида-Т», разрабатываемой в ИПС РАН, используется морфологический анализатор «Диалинг» (www.aot.ru). По данным разработчиков [3], предсказание в нем обеспечивает до 87 % правильно распознанных незнакомых словоформ для русского языка, из которых большинство составляют существительные и прилагательные (такой уровень вполне сопоставим с результатами других исследователей, полученными для английского и французского языков). Однако что касается фамилий, то для корректного морфологического предсказания в этой области как минимум требовалось бы, чтобы словарь располагал весьма представительным массивом фамилий всех возможных словоизменительных типов. На практике приходится сталкиваться с тем, что фамилии при распознавании часто подводятся под похожую форму существующего или гипотетического существительного или прилагательного, а при отсутствии таковых воспринимаются как неизменяемые существительные. Так, фамилии на -ов в именительном падеже часто распознаются как форма родительного падежа множественного числа некоторого существительного (для Чемезов выводится каноническая форма Чемез), в то время как с формами косвенных падежей проблем почти не бывает; для фамилий типа Малых, Седых не строится вариант с правильной канонической формой (все они приводятся к прилагательным – малый, седой). Иногда случаются курьезы: финская фамилия Хуовинен распознается как краткая форма прилагательного хуовинный.

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

Описание подхода

Общий алгоритм морфологического анализа фамилий делится на несколько этапов.

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

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

3. Фильтрация результатов путем сравнения данных из одного текста. Этот этап несет основную нагрузку в отсеивании морфологического шума и разрешении регулярных (и часто не разрешимых другими средствами) неоднозначностей. 

4. Построение для анализируемых фамилий новых аннотаций класса Morpho взамен построенных штатной морфологией.

5. Морфологический анализ изолированных фамилий, не охваченных предыдущими этапами.

На вход алгоритму поступают аннотации класса ANE, построенные psl-правилами [5] для встретившихся в тексте цепочек вида: <имя> (воз­можно, <отчество>) <слово с заглавной буквы>.

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

Каждая такая аннотация представляет собой вариант морфологического разбора фамилии. Остановимся подробнее на каждом этапе.

Первичный анализ

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

В качестве данных алгоритм использует таблицу словоизменительных классов фамилий. Таблица редактируема. Строки таблицы соответствуют классам. Столбцы – клеткам стандартной парадигмы существительного. Каждая ячейка, элемент парадигмы, содержит буквы русского алфавита и маркеры (скобки разных видов). Смысл содержимого ячейки – описать альтернативные условия, необходимые для соотнесения словоформы с данной ячейкой. Если правый конец словоформы совпадет с одной из альтернатив, словоформе будут приписаны соответствующая ячейке морфологическая информация (координаты клетки парадигмы) и имя класса, указанное в соответствующей строке. Пример содержимого двух ячеек для класса «м 3* ок/к муж» (обозначения типов основ и склонений отчасти заимствованы из [1]):

{б,в,д,з,л,м,н,п,р,с,т,ш,ж,ч}<ок>[] (ед. ч., м. р., им. п.)

{б,в,д,з,л,м,н,п,р,с,т,ш,ж,ч}<к>[а] (ед. ч., м. р., род. п.)

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

Примеры словоформ, которые сопоставятся с первой ячейкой: Лубок, Божок, Черток, Павшок и т.п. Класс  «м 3* ок/к муж» описывает фамилии, в основе которых происходит чередование «о» с нулем. Очевидно, что не каждая словоформа, успешно сопоставившаяся с первой ячейкой, на самом деле принадлежит упомянутому  классу: она вполне может не иметь беглого «о» в других формах. Причем даже человек не всегда может правильно определить словоизменительное поведение фамилии по одной лишь словоформе (например, Черток – Чертка, Чертку, ... или Чертока, Чертоку, …?). Словоформы Лубок, Божок, Черток, Павшок сопоставятся также и с ячейкой класса без чередований «м 3 муж» с основой на {к, г, х}.

Общее описание алгоритма первичного анализа

На вход поступают текстовые Ф.И.О. с распознанным именем и, возможно, отчеством (точнее, построенные для них аннотации ANE). О фамилии неизвестно ничего, кроме ее буквенного состава. 

На выходе строится текстовый файл, содержащий для каждой цепочки Ф.И.О. набор вариантов морфологического разбора входящей в нее фамилии (набор гипотез).

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

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

Проиллюстрируем работу алгоритма на примере цепочки Евгения Гришковца. Для нее построены три аннотации ANE, соответствующие трем грамматическим наборам омонимичного имени: «ед. ч., м. р., род. п.», «ед. ч., м. р., вин. п.» и «ед. ч., ж. р., им. п.».

1.   Берем грамматический набор из аннотации ANE. Он задает пространство поиска в таблице. В пространстве поиска находим ячейку, цепочка в которой успешно сопоставляется с концом фамилии; маркеры при сопоставлении игнорируются, но при успешном сопоставлении копируются в словоформу; получаем размеченную словоформу.

2.   Имя класса содержится в строке на пересечении со столбцом «Имя класса».

3.   Строим неизменяемую основу для этого варианта разбора – берем цепочку от начала размеченной словоформы до правой фигурной скобки.

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

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

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

Результаты анализа Ф.И.О. Евгения Гришковца, полученные на этом этапе:

{Гришковц}, {ГРИШКОВЦА}, «ж 1-5b жен», (17); (Singular-F-I); (2).

{Гришковц}, {ГРИШКОВЦА}, «ж 5а жен», (17); (Singular-F-I); (2).

{Гришковц}, {ГРИШКОВЦ}, «м 1-5b муж», (17); (Singular-M-R); (2).

{Гришковц}, {ГРИШКОВЦ}, «м 1-5b муж», (17); (Singular-M-V); (2).

{Гришков}, {ГРИШКОВЕЦ}, «м 5*a ец/ц муж», (17); (Singular-M-R); (3).

{Гришков}, {ГРИШКОВЕЦ}, «м 5*a ец/ц муж», (17); (Singular-M-V); (3).

{Гришков}, {ГРИШКОВЕЦ}, «м 5*b ец/ц муж», (17); (Singular-M-R); (3).

{Гришков}, {ГРИШКОВЕЦ}, «м 5*b ец/ц муж», (17); (Singular-M-V); (3).

{Гришковц}, {ГРИШКОВЦ}, «м 5a муж», (17); (Singular-M-R); (2).

{Гришковц}, {ГРИШКОВЦ}, «м 5a муж», (17); (Singular-M-V); (2).

{Гришковц}, {ГРИШКОВЦ}, «м 1-5b муж», (17); (Singular-M-V); (2).

{Гришковц}, {ГРИШКОВЦ}, «м 1-5b муж», (17); (Singular-M-R); (2).

{Гришковц}, {ГРИШКОВЦ}, «м 5a муж», (17); (Singular-M-V); (2).

{Гришковца}, {ГРИШКОВЦА}, «неизм жен», (17); (Singular-F-I); (1).

{Гришковца}, {ГРИШКОВЦА}, «неизм муж», (17); (Singular-M-R); (1).

Исключение некорректных вариантов с помощью правил

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

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

let(i) – i-я буква слова от правого конца;

left(i, j) – цепочка длины i букв в слове слева от let(j);

end(j) – правый конец слова  длиной j букв;

trunc(k) – остаток слова за вычетом k букв справа;

length – число букв в слове.

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

Приведем (содержательно) несколько случаев, в которых алгоритму разрешено исключать с помощью правил варианты с классом «ов-ин муж» (к этому классу относятся фамилии типа Иванов и Калинин):

Если

(1)    каноническая форма фамилии оканчивается на -ин и

(2)    длина ее меньше 4 букв или  она не содержит ни одной гласной, не считая и в -ин,

то вариант с классом «ов-ин муж» удаляется (Бин, Скин – в отличие от Якин).

Если

(1)    каноническая форма фамилии оканчивается на -ов и

(2)    длина ее меньше 4 букв или она оканчивается на -ьов,

то вариант с классом «ов-ин муж» удаляется (Шольов).

Заметим, что критерий отсутствия гласной, используемый в первом случае, к фамилиям на -ов/-ев мы не применяем, так как такое правило удалило бы правильный вариант разбора фамилий Лбов и Мнев.

Типичные дилеммы, с которыми приходится сталкиваться и которые не разрешимы формально (а часто и не только формально):

-ин – по типу Калинин или Толкин?

-ина – по типу Калинина или Скори¢на? Впрочем, даже для Ско¢рина формально нельзя исключить тип Калинина: это вполне допустимо при ударении на первый слог: Ско¢рина, у Ско¢риной, для Ско¢риной.

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

В крайнем случае в отсутствие последних можно отсеять варианты с наименьшим индексом совпадения (в большинстве случаев это не приводит к ошибкам).

Фильтрация результатов путем сравнения данных из одного текста

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

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

Суть алгоритма очень проста: две словоформы побуквенно сравниваются слева направо. Как только находится несовпадение, сравнение прекращается. Пусть M – длина словоформы (наибольшая из двух), N – количество букв, совпавших при сравнении. Тогда две словоформы считаются успешно сопоставленными, если N/M³K, где K – некоторый эвристически подобранный коэффициент (в нашем случае 0,6). Например, рассмотрим фамилии Садовничий и Садовничему. M в данном случае будет равно 11, N – 8. Высчитаем коэффициент: 8 / 11=0,72. Поскольку 0,72 больше, чем 0,6, считаем, что эти фамилии успешно сопоставлены.

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

Приведем фрагмент файла результатов, поступившего на вход третьему этапу.

Файл построен по тексту, в котором упоминаются Валентина Распутина и Валентин Распутин. Следующие текстовые формы были объединены в один кластер методом частичного сопоставления:

Валентина Распутина  {mf}.

m {Распутин}, {Распутин}, «м 1-5b муж», (1); (Singular-M-R); (2).

m {Распутин}, {Распутин}, «м 1-5b муж», (1); (Singular-M-V); (2).

m {Распутина}, {Распутина}, «неизм муж», (1); (Singular-M-R); (1).

m {Распутин}, {Распутин}, «ов/ин муж», (1); (Singular-M-R); (3).

m {Распутин}, {Распутин}, «ов/ин муж», (1); (Singular-M-V); (3).

f {Распутин}, {Распутина}, «ж 1-5b жен»,(1); (Singular-F-I); (2).

f {Распутина}, {Распутина}, «неизм жен»,(1); (Singular-F-I); (1).

f {Распутин}, {Распутина}, «ова/ина жен»,(1); (Singular-F-I); (3).

Валентине Распутиной {f}.

f {Распутин}, {Распутиная}, «ж <п 1> жен», (5); (Singular-F-D); (3).

f {Распутин}, {Распутина}, «ова/ина жен», (5); (Singular-F-D); (4).

Валентином Распутиным {m}.

m {Распутин}, {Распутиный}, «м <п 1a> муж», (13); (Singular-M-T); (3).

m {Распутин}, {Распутиной}, «м <п 1b> муж», (13); (Singular-M-T); (3).

m {Распутин}, {Распутин}, «ов/ин муж», (13); (Singular-M-T); (4).

Элемент кластера, содержащий текстовую цепочку Ф.И.О. и приписанные ей варианты, назовем разделом.

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

Часть строки, включающую основу, каноническую форму и имя класса, назовем «классифицирующей тройкой» (далее – просто тройка).

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

Третий шаг. На этом шаге делается попытка построить пересечение одноименных К-множеств во всем кластере.

Случай А. Если в результате не получено ни одного пустого множества, то каждая строка, содержащая элемент пересечения К-множеств, отмечается знаком «+», как в нашем примере:

Валентина Распутина  {mf}.

m {Распутин}, {Распутин}, «м 1-5b муж», (1); (Singular-M-R); (2).

m {Распутин}, {Распутин}, «м 1-5b муж», (1); (Singular-M-V); (2).

m {Распутина}, {Распутина}, «неизм муж», (1); (Singular-M-R); (1).

+m {Распутин}, {Распутин}, «ов/ин муж», (1); (Singular-M-R); (3).

+m {Распутин}, {Распутин}, «ов/ин муж», (1); (Singular-M-V); (3).

f {Распутин}, {Распутина}, «ж 1-5b жен»,(1); (Singular-F-I); (2).

f {Распутина}, {Распутина}, «неизм жен»,(1); (Singular-F-I); (1).

+f {Распутин}, {Распутина}, «ова/ина жен»,(1); (Singular-F-I); (3).

[…]

Случай Б. Если в результате получено хотя бы одно пустое множество и при этом в кластере встречаются как «однобуквенные», так и смешанные (mf-) разделы, алгоритм усложняется. Дело в том, что наличие «разнополых» вариантов в разделе может быть вызвано просто омонимичной формой имени, следовательно, одно из подмножеств раздела может быть фиктивным. Пример – формально возможные варианты с женским родом для Ф.И.О. Евгения Гришковца:

Евгения Гришковца {mf}.

f {Гришковц}, {Гришковца}, «ж 1-5b жен», (17); (Singular-F-I); (2).

f {Гришковц}, {Гришковца}, «ж 5а жен», (17); (Singular-F-I); (2).

f {Гришковца}, {Гришковца}, «неизм жен», (17); (Singular-F-I); (1).

[…]

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

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

Четвертый шаг. Определение окончательных вариантов для вывода в аннотацию Morpho:

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

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

Приведем в заключение результаты морфологического анализа Ф.И.О. Евгения Гришковца в вымышленном тестовом примере, где содержались также цепочки Евгению Гришковец и Евгений Гришковец (для сравнения – приведенные ранее результаты первого этапа для этого случая содержали 15 вариантов):

Евгения Гришковца.

{Гришков}, {ГРИШКОВЕЦ}, «м 5*a ец/ц муж», (17); (Singular-M-R); (3).

{Гришков}, {ГРИШКОВЕЦ}, «м 5*a ец/ц муж», (17); (Singular-M-V); (3).

{Гришков}, {ГРИШКОВЕЦ}, «м 5*b ец/ц муж», (17); (Singular-M-R); (3).

{Гришков}, {ГРИШКОВЕЦ}, «м 5*b ец/ц муж», (17); (Singular-M-V); (3).

Заметим, что неоднозначность окончательных результатов здесь вполне корректна:

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

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

Описание этапа 4 можно опустить, поскольку он решает чисто техническую задачу построения аннотаций Morpho по результатам предыдущего этапа.

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

Литература

1. Зализняк А.А. Грамматический словарь русского языка: Словоизменение. М.: Русский язык, 1987.

2. Сегалович И., Маслов М. Русский морфологический анализ и синтез с генерацией моделей словоизменения для не- знакомых слов // Диалог’98: тр. Междунар. сем. по компьютерной лингвистике и ее приложениям. Казань: ООО «Хэтер», 1998. Т. 2. С. 547–552.

3. Сокирко А.В. Морфологические модули на сайте www.aot.ru // Диалог’2004: тр. Междунар. конф. М.: Наука, 2004. С. 559–564.

4. Ермаков А.Е., Плешко В.В. Компьютерная морфология в контексте анализа связного текста // Там же. С. 185–190.

5. Куршев Е.П., Кормалев Д.А., Сулейманова Е.А., Трофимов И.В. Исследование методов извлечения информации из текстов с использованием автоматического обучения и реализация исследовательского прототипа системы извлечения информации // Матем. методы распознавания образов: сб. докл. 13-й Всерос. конф. М.: МАКС Пресс, 2007. C. 602–605.