Решение
практически любой задачи автоматической обработки текста включает в
себя проведение анализа текста на следующих уровнях представления:
Графематический анализ.
Выделение из массива данных предложений и слов (токенов).
Фонетический анализ
Морфологический анализ.
Выделение грамматической основы слова, определение частей
речи, приведение слова к словарной форме.
Синтаксический анализ.
Выявление синтаксических связей между словами в предложении,
построение синтаксической структуры предложения.
Семантический анализ.
Выявление семантических связей между словами и
синтаксическими группами, извлечение семантических отношений.
Каждый такой
анализ — самостоятельная задача, не имеющая собственного (непосредственного)
практического применения, но активно используемая для решения других
задач (прикладных и теоретических).
Подавляющее
большинство исследовательских систем предназначено для решения
именно вспомогательных аналитических задач.
Такие системы
применяются
для апробации
методов
проведения
вычислительных экспериментов,
в качестве
составных частей (библиотек, фреймворков) для систем, решающих
прикладные задачи.
Примером таких
систем могут служить средство NLTK для графематического анализа и
токенизации, морфологический анализатор mystem и синтаксический
парсер ЭТАП3.
Проект АОТ (https://nlpub.ru/АОТ)
— общее название инструментов обработки текста на естественном
языке, разработанных при создании системы автоматического перевода
ДИАЛИНГ. Пакет состоит из компонентов — лингвистических процессоров,
которые друг за другом обрабатывают входной текст. Вход одного
процессора является выходом другого. Авторы выделяют такие
компоненты, как графематический, морфологический, синтаксический и
семантический анализатор.
Графематический анализ
Графематический
анализ - начальный анализ естественного текста, представленного в
виде цепочки ASCII символов, вырабатывающая информацию, необходимую
для дальнейшей обработки Морфологическим и Синтаксическим
процессорами.
В задачу
графематического анализа входят:
Разделение входного текста на слова, разделители и т.д.
Сборка
слов, написанных в разрядку;
Выделение устойчивых оборотов, не имеющих словоизменительных
вариантов;
Выделение ФИО (фамилия, имя, отчество), когда имя и отчество
написаны инициалами;
Выделение электронных адресов и имен файлов;
Выделение предложений из входного текста;
Выделение абзацев, заголовков, примечаний.
Графематический анализ широко используется в OCR.
При распознавании OCR анализирует графический образ символа и выдвигает ряд гипотез, в соответствии с которыми этому образу присваивается текстовый эквивалент (коды изображений заменяются машинными кодами букв).
Основные
алгоритмические технологии распознавания символов:
шаблонная (во входном изображении выделяются растровые изображения отдельных символов, сравниваются со всеми шаблонами, имеющимися в базе, выбирается шаблон с наименьшим количеством точек, отличных от входного изображения. Шаблонные системы проще в реализации, устойчивы к дефектам изображения, имеют высокую скорость обработки входных данных, но надежно распознают только те шрифты, шаблоны которых им известны),
структурная (объект описывается как граф, узлами которого являются элементы входного объекта, а дугами - пространственные отношения между ними. Структурные системы высоко чувствительны к графическим дефектам изображения, нарушающим составляющие элементы. Для этих систем, в отличие от шаблонных и признаковых, до сих пор не созданы эффективные автоматизированные процедуры обучения),
фонтанное преобразование (совмещает в себе достоинства шаблонной и структурной систем. Любой воспринимаемый объект рассматривается как целое, состоящее из частей, связанных между собой определенными отношениями).распознавание
на основе обучаемых нейронных сетей
В основе фонтанного преобразования лежит использование структурно-пятенного эталона с заданием:
обязательных, запрещенных и необязательных структурных элементов;
отношений между структурными элементами;
отношений структурных элементов с описывающим прямоугольником символа;
атрибутов выделения структурных элементов;
атрибутов проверки отношений между элементами;
атрибутовоценки качества элементов и отношений;
позиции начала выделение элемента.
Структурные элементы, выделяемые для класса изображений, могут быть исходными (пятна) и составными (отрезок, дуга, кольцо, точка и т.д.).
Использование составных структурных элементов позволяет строить иерархические описания классов распознаваемых объектов.
В качестве отношений используются связи между структурными элементами (<длина больше>, <правее>, <соприкасается>).
При задании структурных элементов и отношений используются конкретизирующие параметры: диапазон допустимой ориентации отрезка, допустимое расстояние между характерными точками структурных элементов в отношении <соприкасается> и т.д..
Эталон накладывается на изображение, и отношения между выделенными на изображении пятнами сравниваются с отношениями пятен в эталоне. Если выделенные на изображении пятна и отношения между ними удовлетворяют эталону некоторого символа, то символ добавляется в список гипотез о результате распознавания входного изображения.
Благодаря этому система распознает тексты не только «хорошей» печати (книги, журналы), но и «плохой» печати (факсы, матричные принтеры и т.п.), работает не только с текстом, но и с формами, таблицами, распознает рукописный текст.
Всё большее
распространение получает
распознавание с помощью обучаемых нейронных сетей
(не являющееся алгоритмической технологией).
Фонетический анализ
Фонетические
алгоритмы сопоставляют двум словам со схожим произношением
одинаковые коды, что позволяет осуществлять сравнение и индексацию
множества таких слов на основе их фонетического сходства.
Фонетические
алгоритмы
используют при поиске в базах по спискам людей, в программах
проверки орфографии. Зачастую они используются совместно с
алгоритмами нечеткого поиска (которые, несомненно, заслуживают
отдельной статьи), предоставляя пользователям удобный поиск по
именам и фамилиям в различных базах данных, списках сотрудников и
так далее.
Наиболее
известные фонетические
алгоритмы:
Soundex,
Daitch-Mokotoff Soundex,
NYSIIS,
Metaphone,
Double
Metaphone,
русский
Metaphone,
Caverphone.
В 2002 году в 8-ом выпуске журнала «Программист» была
опубликована статья Петра Каньковски, рассказывающая о его адаптации
английской версии алгоритма Metaphone к суровым сибирским морозам,
медведям и балалайкам. Этот алгоритм преобразует исходные слова в
соответствии с правилами и нормами русского языка, учитывая
фонетическое звучание безударных гласных и возможные «слияния»
согласных при произношении. Он показывает очень хорошие результаты
на практике, несмотря на то, что основывается на довольно простых
правилах. Все буквы разбиты на группы по звучанию — гласные и
согласные (vowels и consonants соответственно в английской
терминологии), глухие и звонкие. Звонкие согласные преобразуются в
соответствующие им парные глухие, объединяются «сливающиеся» при
произношении последовательности букв, и проводятся некоторые другие
манипуляции. Ниже я приведу немного доработанный вариант, который, в
отличие от оригинала Петра Каньковски, привносит правила, связанные
с фонетической эквивалентностью Ц и ТСили ДС, и не сжимает окончания
— байты экономить — это не наша задача.
Алгоритм вычисления кода русского Metaphone:
Для всех гласных букв проделать следующие операции.
ЙО, ИО, ЙЕ, ИЕ → И
О, Ы, Я → А
Е, Ё, Э → И
Ю → У
Для всех согласных букв, за которыми следует любая
согласная, кроме Л, М, Н или Р, либо же для согласных на конце
слова, провести оглушение:
Б → П
З → С
Д → Т
В → Ф
Г → К
Склеиваем ТС и ДС в Ц:
ТС → Ц
В итоге, алгоритм очень хорошо справляется со своей задачей —
в результирующем наборе содержатся действительно фонетически схожие
слова. И при этом остается довольно мало лишних слов, в основном
благодаря тому, что гласные не игнорируются, а преобразуются и
используются в итоговом коде. Однако же, есть некоторые слова,
которые, не смотря на свою фонетическую схожесть, не попадают в
результирующий набор из-за слишком «строгих» правил алгоритма.
В задачи морфологии входит
определение слова как особого языкового объекта и описание его
внутренней структуры.
Морфология описывает не только
формальные свойства слов и образующих их морфем (звуковой
состав, порядок следования, и т. п.), но и те грамматические
значения, которые выражаются внутри слова (или «морфологические
значения»). В соответствии с этими двумя крупными задачами,
морфологию часто делят на две области:
«формальную» морфологию, или
морфемику,
грамматическую семантику,
изучающую свойства грамматических морфологических значений и
категорий (морфологически выражаемое словообразование и
словоизменение языков мира).
Примеры сервисов и
библиотек морфологического анализа:
Морфологический анализ является основой для нормализации текста.
Нормализация -
удаление из исходного текста грамматической информации
(падежи, числа, глагольные виды и времена, залоги причастий, род и
так далее).
Два других алгоритма - стемминг и лемматизация -
пытаются достичь такого же эффекта, но глубина преобразования
текста в них меньше.
Основная проблема, возникающая при использовании стеммера - это
обработка слов, которые при образовании разных грамматических форм
меняют не только окончание, но и основу слова.
Нормализация текста не использует стемминг, поэтому она лишена
недостатков потери релевантности из-за особенностей русского
словоизменения.
Лемматизатор по своим результатам стоит намного ближе к
нормализатору. Однако он применяет упрощенный анализ слов, не
учитывая контекст. Это приводит к неоднозначностям при
определении части речи.
Нормализация требует обязательногоя морфологического анализа,
распознающего части речи с учетом контекста и многочисленных правил
согласования (без него нормализация будет давать значительное
количество ошибочных результатов).
Стемминг—
процесс нахождения основы слова для заданного исходного слова
(является частью процесса нормализации текста).
Основа слова
необязательно совпадает с морфологическим корнем слова.
В области
компьютерных наук первая публикация по стеммингу датируется 1968
годом.
Стемминг
применяется в поисковых системах для расширения поискового запроса
пользователя.
Конкретный
способ решения задачи поиска основы слов называется алгоритм
стемминга, а конкретная реализация — стеммер.
Стемминг важен:
при
небольшом наборе текстов
для
русского языка (как флективного).
Русский язык
относится к группе флективных синтетических языков, то есть языков,
в которых преобладает словообразование с использованием аффиксов,
сочетающих сразу несколько грамматических значений, поэтому данный
язык допускает использование алгоритмов стемминга. Русский язык
имеет сложную морфологическую изменяемость слов, которая является
источником ошибок при использовании стемминга. В качестве решения
данной проблемы можно использовать наряду с классическими
алгоритмами стемминга алгоритмы лемматизации, которые приводят слова
к начальной базовой форме.
Если тексты на
английском языке, то этот шаг тоже можно проигнорировать, в силу
того, что количество вариаций той или иной словоформы в английском
языке существенно меньше чем в русском.
Основная идея стеммера
Портера заключается
в том, что существует ограниченное количество
словообразующих суффиксов, и стемминг слова происходит
без использования каких-либо баз основ: только множество
существующих суффиксов и вручную заданные правила.
Алгоритм состоит из пяти шагов. На каждом шаге
отсекается словообразующий суффикс и оставшаяся часть
проверяется на соответствие правилам (например, для
русских слов основа должна содержать не менее одной
гласной). Если полученное слово удовлетворяет правилам,
происходит переход на следующий шаг. Если нет — алгоритм
выбирает другой суффикс для отсечения. На первом шаге
отсекается максимальный формообразующий суффикс, на
втором — буква «и», на третьем — словообразующий
суффикс, на четвертом — суффиксы превосходных форм, «ь»
и одна из двух «н».
на странице познакомиться
с материалами по стеммингу и осуществить стемминг фразы в точном
соответствии с образцом (Должны
быть Ваши ФИО!)
на странице познакомиться
с лемматизацией и осуществить лемматизацию фразы в точном
соответствии с образцом (Должны
быть Ваши ФИО!)
Компьютерная лингвистика:
морфологический анализ
Светлана
Тимошенко из Лаборатории компьютерной лингвистики ИППИ РАН.
Синтаксический анализ
Парсинг
(parsing,
синтаксический анализ)
— процесс сопоставления линейной последовательности лексем (слов,
токенов) языка (естественного или формального)
с его
формальной грамматикой.
Результатом
парсинга является (обычно)
дерево разбора
(синтаксическое дерево).
Синтаксическое дерево
- структура данных, которая
отражает синтаксическую структуру входной последовательности и
является материалом для дальнейшей обработки.
Синтаксическое дерево может быть представлено в виде:
дерева зависимостей,
дерева составляющих,
сочетания первого и второго способов представления.
Всё что угодно,
имеющее «синтаксис», поддается автоматическому анализу:
языки программирования — разбор исходного кода языков
программирования, в процессе трансляции (компиляции или
интерпретации);
структурированные данные — данные, языки их описания, оформления
(XML, HTML, CSS,
конфигурационные файлы и т. п.);
SQL-запросы (DSL-язык);
математические выражения;
регулярные выражения (которые, в свою очередь, могут использоваться
для автоматизации лексического анализа);
формальные грамматики;
тексты на естественных языках...
Компьютерная лингвистика:
синтаксический анализ
Леонид
Иомдин из Лаборатории компьютерной лингвистики ИППИ РАН им. Харкевича
Семантический анализ
Дистрибутивная семантика
— вычисление степени семантической близости между лингвистическими
единицами на основании их распределения (дистрибуции) в больших
массивах лингвистических данных (текстовых корпусах).
Каждому слову присваивается свой контекстный вектор.
Множество векторов формирует словесное векторное пространство.
Семантическое расстояние между понятиями, выраженными словами
естественного языка, обычно вычисляется как
косинусное сходство между векторами словесного пространства.
Косинусное сходство — мера сходства
между двумя векторами предгильбертового пространства, которая
используется для измерения косинуса угла между ними.
Косинусное сходство эффективно в качестве оценочной меры, особенно для
разреженных векторов, так как необходимо учитывать только
ненулевые измерения.
Косинусное
сходство двух текстов изменяется в
диапазоне от 0 до 1, поскольку частота терма (веса tf-idf) не
может быть отрицательной. Угол между двумя векторами частоты
терма не может быть больше, чем 90°.
«Мягкая» косинусная мера — мера
сходства между двумя векторами, учитывающая
сходства между парами признаков. Традиционное косинусное
сходство рассматривает признаки векторной модели как независимые
или полностью обособленные, тогда как «мягкая» косинусная мера
учитывает сходства признаков в векторной модели.
В области
обработки естественного языка сходство между объектами весьма
интуитивно. Такие признаки как слова или
N-граммы могут быть довольно схожи, хотя формально они считаются
различными признаками в векторной модели. Например, слова «играть»
и «игра» различны и, таким образом, отображаются в различных
измерениях в векторной модели, хотя, очевидно, что они связаны
семантически. В случае N-грамм или синтаксических N-грамм может
быть применено расстояние Левенштейна (кроме того, расстояние
Левенштейна может быть также применено и к словам).
Для расчета «мягкой» косинусной меры
вводится матрица s сходства между признаками. Она может
рассчитываться, используя расстояние Левенштейна.
В качестве входных данных он
получает текстовый файл в utf-8.
Результаты работы сохраняются в XML формате.
Компьютерная лингвистика:
семантический анализ
Светлана Тимошенко из Лаборатории компьютерной лингвистики ИППИ РАН
Атрибуция текста
Атрибуция (лат.
attributio) в филологии — определение подлинности или подложности
текста и установление его автора.
Проблема
установления авторства в литературе связана с существованием
анонимных и псевдонимных текстов и представляет собой одну из
древнейших филологических задач, входящих в область текстологии.
В последние
десятилетия в задачах атрибуции применяются математические
и компьютерные методы автоматизации
экспериментов по определению авторства.
Реализация автоматической атрибуции текста на основе использования
скрытых марковских цепей осуществлена в сервисе
Лингвоанализатор
3-эпсилон.
Метод, применяемый для определения авторства текста, основывается на
формальной математической модели встречаемости последовательности
элементов текста как реализации цепи Маркова.
В качестве элементов текста используются последовательности букв и
последовательности грамматических классов слов.
Оказывается, частоты употребления пар букв и пар грамматических
классов в тексте на русском языке являются достаточно устойчивой
характеристикой автора и, видимо, их можно использовать, чтобы
решать проблемы спорного авторства текста.
Проводится сопоставление результатов, полученных при использовании
различных вариантов методики в указанных единицах.
Эксперимент проводится на 385 текстах 82 писателей.