Файл: Основы проектирования программ. Этапы создания программного обеспечения..pdf

ВВЕДЕНИЕ

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

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

ГЛАВА 1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1.1 Задачи обработки текста на естественном языке

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

В их число входит:

1. Машинный перевод — автоматический перевод текстового документа с одного языка на другой.
2. Ранжирование поисковых запросов — это процесс выстраивания найденных по запросу пользователя страниц в порядке наибольшего соответствия искомому запросу.
3. Реферирование тестов — получение краткого изложение текстового документа.
4. Классификация текстовых документов — отнесение каждого документа к определенному классу с заранее известными параметрами.
5. Кластеризация текстовых документов — выделение подмножества тематически похожих документов.
6. Выделение мнения из текста и его эмоционального содержания.
7. Генерация речи из текста.

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

1.2 Подходы решения задач обработки текста на естественном языке

Существует два подхода для решения задач обработки текста на естественном языке:

1. Первый подход – создание экспертной системы. На основе определенных взаимоотношений между словами и словосочетаниями, которые устанавливает эксперт (лингвист) строится необходимая модель для конкретной задачи.
2. Второй подход — статистические модели или машинное обучение. В данном случае используют не правила заранее заложенные в систему, а различные статистические метрики между словами.

Оба подхода имеют свои достоинства и недостатки.

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

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

Необходимо учесть то, что для исправления некоторых опечаток нужно знать контекст, в котором употреблено слово. Таким образом корректор может работать с учетом или без учета контекста. Однако для восстановления контекста необходима большая база документов. Для восстановления контекста используют N-граммы или сверточные нейронные сети. С принципом работы вышеуказанных подходов можно ознакомиться в статье N-GRAM LANGUAGE MODELING USING RECURRENT NEURAL NETWORK ESTIMATION, Google Tech Report, Ciprian Chelba, Mohammad Norouzi, Samy Bengio.

В данной работе будет рассматриваться корректор без учета контекста.

Метрики сходства слов

Прежде чем составлять модель, которая будет исправлять опечатки в слове, рассмотрим некоторые метрики сходства двух строк: расстояние Хэмминга, сходство Джаро — Винклера, расстояние Левенштейна, расстояние Дамерау — Левенштейна.

Расстояние Хэмминга

Расстояние Хэмминга — число позиций, в которых соответствующие символы двух слов одинаковой длины различны. Применяется для подсчета разницы между строками. Первоначально метрика была сформулирована Ричардом Хэммингом для определения меры различия между кодовыми комбинациями (двоичными векторами) в векторном пространстве кодовых последовательностей, в этом случае расстоянием Хэмминга d(x,y) между двумя двоичными последовательностями (векторами) x и y длины n называется число позиций, в которых они различны. Реализация Расстояния Хэмминга очень простая. Расстояние Хэмминга является частным случаем метрики Минковского (при соответствующем определении вычитания) [4]:

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

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

Сходство Джаро — Винклера

В области информатики и статистики сходство Джаро — Винклера представляет собой меру схожести строк для измерения расстояния между двумя последовательностями символов.

Расстояние Джаро между двумя заданными строками это [3]:

, где

|s1|, |s2| – длина строк s1 и s2.

m — количество совпадающих символов.

t — количество транспонированных символов.

Символы строк s₁ и s₂ являются совпадающими, если они одинаковы и находятся на расстоянии не более чем .

Каждый символ строки s₁ сравнивается со всеми соответствующими ему символами в строке s₂. Количество совпадающих символов (но отличающихся порядковыми номерами символов) которое делится на 2, называют количеством транспонированных символов.

Расстояние Джаро — Винклера использует коэффициент масштабирования, что дает более благоприятные рейтинги строкам, которые совпадают друг с другом от начала до определенной длины, которая называется префиксом. Даны две строки s₁ и s₂. Их расстояние Джаро — Винклера рассчитывается по формуле [3]:

, где

d_j — расстояние Джаро между двумя строками.

l – длина префикса (максимум 4).

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

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

Расстояние Левенштейна

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

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

В общем случае:

w (a, b) — цена замены символа a на символ b.

w (ε, b) — цена вставки символа b.

w (a, ε) — цена удаления символа

Данное расстояние можно подсчитать по следующей рекуррентной формуле [2]:

, где

Это формула в частном виде, где цена замены вставки и удаления равна 1.

Расстояние Дамерау — Левенштейна

Расстояние Дамерау — Левенштейна – это мера разницы двух строк символов, определяемая как минимальное количество операций вставки, удаления, замены и транспозиции (перестановки двух соседних символов), необходимых для перевода одной строки в другую. Является модификацией расстояния Левенштейна: к операциям вставки, удаления и замены символов, определённых в расстоянии Левенштейна добавлена операция транспозиции (перестановки) символов.

Расстояние Дамерау — Левенштейна между двумя строками a и b определяется функцией как [2]:

где – индикаторная функция, равная нулю при a_i=b_j и 1 в противном случае.

Каждый рекурсивный вызов соответствует одному из случаев:

соответствует удалению символа (из a в b),

соответствует вставке (из a в b),

соответствие или несоответствие, в зависимости от совпадения символов,

в случае перестановки двух последовательных символов.

ГЛАВА 2. ПРАКТИЧЕСКАЯ ЧАСТЬ

2.1 Математическая модель работы корректора слова

В данной работе будет реализован автокорректор на основе модели Питера Норвига.

Рассмотрим математическую модель корректора. Пусть p(С|W) — вероятность того, что C является предполагаемой поправкой, учитывая исходное слово W. Логично выбрать такое С из набора кандидатов на исправление (назовем его множество Q), чтобы p(C|W) была максимальной. Согласно теореме Байеса

Так как p(W) одинаково для любого C, то при выборе кандидата этой вероятностью можно пренебречь. Тогда формулу можно записать в следующем виде:

, где

p(C) — вероятность встречи кандидата С,

p(W|C) — вероятность того, что слово W соответствует кандидату С.

Чтобы определить вероятность p(C), возьмем несколько документов и вычислим в них частоту появления слов по формуле:

, где

num(C) — количество появления слова С в документах,

N -общее число слов в документах.

Вероятность p(W|C) будет зависеть от правила выбора кандидата. В случае модели Питера Норвига вступает следующие предположение, что p(W|C) зависит от расстояния Дамерау — Левенштейна. Чем больше это расстояние, тем меньше p(W|C).

2.2 Принцип работы корректора Питера Норвига

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

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