Задача поиска в неструктурированном тексте и лингвистический анализ

Задача поиска в неструктурированном тексте и лингвистический анализ.

, ,

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

Поиск

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

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

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

Рассмотрим две схемы поиска.

Схема 1. Удовлетворящим условию поиска считается слово из списка представимое в виде конкатенации Sl=S*El при том, что слово-образец представимо в виде Sq=S*Eq и El и Eq - совместимые окончания. Словоформе из текста сопоставляются варианты ее разрезания {S*iEi}, образцу - варианты его разрезания {O*jEj}, а поиск по образцу состоит в отыскании исходных словоформ, для которых S*i =O*j при совместимости Ei и Ej. В такой схеме совместимость задается бинарным отношением между длинами хвостовых цепочек букв или собственно окончаниями. Чтобы уменьшить неполноту поиска, последнее описание можно пополнить более тонкой морфологической информацией, например, учесть возможность беглых букв и чередований в корне. Схема 1 не требует предварительной группировки слов из списка и поиск производится в он-лайновом режиме. При обоих способах задания совместимости ("эвристическом" и перечислением пар окончаний), результат поиска будет избыточен и неполон.

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

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

В схеме 2 вместо совместимости окончания El слова из списка и окончания Eq образца используются 1)совместимость окончания El слова из списка и окончания N его возможной "нормальной формы" и 2)совместимость окончания Eq слова из списка и окончания N его "нормальной формы". Нормальная форма - форма, в которой слово стояло бы в словаре, если бы существовало. Окончание нормальной формы далее называется нормальным окончанием. Понятно, практически для любого слова найдется несколько нормальных форм, в том числе несуществующих. Так нормализациями слова "астроном" будут "астроном" и "астрон", а одной из нормализаций слова "длань" будет "дланить".

Построение нормальных форм слова, как и в схеме 1, состоит в выделении всех допустимых окончаний {Ei} слова S=S*1E1= S*2E2=..., после чего, в отличие от схемы 1, для каждого окончания Ei находятся допустимые нормальные окончания {Nij}, т. е. нормальными формами будут считаться конструкции вида SiNij с окончаниями Nij. Построенный по списку исходных слов список нормальных форм включает пары <нормальная форма, нормальное окончание>. Поиск по образцу состоит в построении аналогичного списка для образца и отыскании всех вхождений пар из этого списка в списке, сопоставленном исходным словам.

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

Поиск и словарная нормализация

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

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

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

Словарь и правила

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

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

Грамматическое доуточнение нормализаций

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

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

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

Ошибки в тексте

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

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

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

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

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

Отложенное доопределение

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

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

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

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

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

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

1. Эвристическая связка. Связка по вариантам эвристической нормализации включает неизвестные слова, варианты нормализации которых совпадают. Если нормализации слова (само слово) пересекаются с нормализациями других слов (другими словами), отбрасываем у всех слов из связки нормализации, не попавшие в пересечение. Заметим, что единственным и не более чем правдоподобным основанием для отбрасывания не вошедших в пересечение нормализаций служит то, что реально существующие слова, неизвестные достаточно полному словарю, должны не только подчиняются регулярным правилам, но еще и не порождать омонимии наподобие "три"-> {"тереть", "три"}. На этом же основано допущение, что реально существующее неизвестное слово может войти не более чем в одну связку.

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

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

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

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

Напротив, существующие (но неизвестные) слова, попав в эвристическую связку, почти наверняка окажутся и в словарной. Но что если словарная связка включает еще и другие неизвестные слова. Значит ли это, что она мощнее? Сравним для каждого такого слова расстояние до соответствующей словоформы сопоставленного связке слова из словаря с расстоянием до соответствующей допустимой словоформы слова, сопоставленного эвристической связке. Может оказаться, что расстояние до эвристической связки меньше.

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

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

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

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

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

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

Какая схема лучше

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

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