Повышение эффективности работы опечаточника

Министерство образования РФ Нижегородский государственный университет Факультет вычислительной математики и кибернетики Кафедра математического обеспечения ЭВМ Реферат

«Повышение эффективности работы опечаточника»

Выполнил: студент группы 83−09Комин А. В

Научный руководитель: к.ф.-м.н., Окатьев В. В.

Н. Новгород 2012 г.

• Введение
• Общие сведения об исправлении опечаток
• Где используется исправление опечаток
• Алгоритмы, используемые опечаточниками
• Алгоритм нечеткого поиска
• Расстояние Левенштейна
• Обобщения
• Формула
• Алгоритм Вагнера — Фишера
• Различные модели ошибок опечаточников
• Используемая схема работы
• Используемые данные
• Принцип работы данной схемы
• Постановка задачи
• Общая схема решения поставленной задачи
• Алгоритм исследования одного параметра
• Библиография

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

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

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

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

Успех в решении прикладных задач компьютерной лингвистики зависит, прежде всего, от полноты и точности представления в памяти ЭВМ декларативных средств и от качества процедурных средств. На сегодняшний день необходимый уровень решения этих задач пока еще не достигнут, хотя работы в области компьютерной лингвистики ведутся во всех развитых странах мира. Можно отметить серьезные научные и практические достижения в области компьютерной лингвистики. Так в ряде стран (Россия, США, Япония, и др.) построены экспериментальные и промышленные системы машинного перевода текстов с одних языков на другие, построен ряд экспериментальных систем общения с ЭВМ на естественном языке, ведутся работы по созданию терминологических банков данных, тезаурусов, двуязычных и многоязычных машинных словарей (Россия, США, Германия, Франция и др.), строятся системы автоматического анализа и синтеза устной речи (Россия, США, Япония и др.), ведутся исследования в области построения моделей естественных языков.

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

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

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

текстовый автоматический опечатка исправление

Общие сведения об исправлении опечаток

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

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

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

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

Где используется исправление опечаток

1) Исправление опечаток реализовано в поисковых системах (при введении запросов пользователями)

§ Google

Функция Google Suggest, которая помогает уточнить поисковый запрос, исправляет опечатки, транслитерирует слова и в случае необходимости меняет раскладку клавиатуры

§ Яндекс

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

§ Rambler

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

2) Существуют программы для исправления раскладки клавиатуры

· Punto Switcher — программа для автоматического переключения между различными раскладками клавиатуры в операционных системах семейства Microsoft Windows и Mac OS X. Работая в фоновом режиме, Punto Switcher проводит статистический анализ последовательностей вводимых символов слова, и, если сочетание букв оказывается нетипичным для языка, на котором вводятся символы, Punto Switcher переключает язык ввода, стирает напечатанное, эмулируя нажатия клавиши < Backspace, и повторно вводит текст уже с правильной раскладкой клавиатуры.

· Keyboard Ninja — это компьютерная программа для операционных систем Microsoft Windows, предназначенная для автоматического переключения раскладки клавиатуры при наборе текста и автоматического исправления ошибочно набранного не в той языковой раскладке текста. Например, если набрано ghbdtn, программа автоматически исправляет данный текст на привет.

3) Существуют специальные программы для исправления опечаток в тексте

Microsoft Word (часто — MS Word, WinWord или просто Word) — текстовый процессор, предназначенный для создания, просмотра и редактирования текстовых документов, с локальным применением простейших форм таблично-матричных алгоритмов.

OrfoCheck — программа для проверки текстов на опечатки. В отличие от Word’а и других программ проверки орфографии слова проверяются не по словарю правильных слов, а по словарю опечаток.

Алгоритмы, используемые опечаточниками

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

Алгоритм нечеткого поиска

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

Задачу нечеткого поиска можно сформулировать так:

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

Например, при запросе «Машина» с учетом двух возможных ошибок, найти слова «Машинка», «Махина», «Малина», «Калина» и так далее.

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

В числе наиболее известных метрик — Левенштейна и Дамерау-Левенштейна.

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

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

Применение

Расстояние Левенштейна и его обобщения активно применяется:

· для исправления ошибок в слове (в поисковых системах, базах данных, при вводе текста, при автоматическом распознавании отсканированого текста или речи).

· для сравнения текстовых файлов утилитой diff и ей подобными. Здесь роль «символов» играют строки, а роль «строк» — файлы.

· в биоинформатике для сравнения генов, хромосом и белков.

Редакционным предписанием называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: D (англ. delete) — удалить, I (англ. insert) — вставить, R (replace) — заменить, M (match) — совпадение.

Например, для 2-х строк «CONNECT» и «CONEHEAD» можно построить следующую таблицу преобразований:

MMMRRRRI

CONNECT

CONEHEAD

Найти только расстояние Левенштейна — более простая задача, чем найти ещё и редакционное предписание.

Недостатки

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

1. При перестановке местами слов или частей слов получаются сравнительно большие расстояния;

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

Обобщения

Разные цены операций

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

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

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

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

Формула

Здесь и далее считается, что элементы строк нумеруются с первого, как принято в математике. Пусть S1 и S2 — две строки (длиной M и N соответственно) над некоторым алфавитом, тогда редакционное расстояние d (S1,S2) можно подсчитать по следующей рекуррентной формуле

где m (a, b) равна нулю, если a = b и единице в противном случае; min (a, b, c) возвращает наименьший из аргументов.

Алгоритм Вагнера — Фишера

Как частный случай, так и задачу для произвольных w, решает алгоритм Вагнера — Фишера, приведённый ниже. Здесь и ниже мы считаем, что все w неотрицательны, и действует правило треугольника: если две последовательные операции можно заменить одной, это не ухудшает общую цену (например, заменить символ x на y, а потом с y на z не лучше, чем сразу x на z).

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

для всех i от 0 до M

для всех j от 0 до N

вычислить D (i, j)

вернуть D (M, N)

Или в более развёрнутом виде, и при произвольных ценах замен, вставок и удалений:

D (0,0) = 0

для всех j от 1 до N

D (0,j) = D (0,j-1) + цена вставки символа S2[j]

для всех i от 1 до M

D (i, 0) = D (i-1,0) + цена удаления символа S1[i]

для всех j от 1 до N

D (i, j) = min (

D (i-1, j) + цена удаления символа S1[i],

D (i, j-1) + цена вставки символа S2[j],

D (i-1, j-1) + цена замены символа S1[i] на символ S2[j]

вернуть D (M, N)

Для восстановления редакционного предписания требуется вычислить матрицу D, после чего идти из правого нижнего угла (M, N) в левый верхний, на каждом шаге ища минимальное из трёх значений:

· если минимально (D (i-1, j) + цена удаления символа S1[i]), добавляем удаление символа S1[i] и идём в (i-1, j)

· если минимально (D (i, j-1) + цена вставки символа S2[j]), добавляем вставку символа S1[i] и идём в (i, j-1)

· если минимально (D (i-1, j-1) + цена замены символа S1[i] на символ S2[j]), добавляем замену S1[i] на S2[j] (если они не равны; иначе ничего не добавляем), после чего идём в (i-1, j-1)

Здесь (i, j) — клетка матрицы, в которой мы находимся на данном шаге. Если минимальны два из трёх значений (или равны все три), это означает, что есть 2 или 3 равноценных редакционных предписания.

Различные модели ошибок опечаточников

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

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

Варианты с использованием модели ошибок описаны в работах Цобеля и Дарта[2][3]. В них описывается, что модель ошибок учитывает несколько параметров: статистические данные о реальных опечатках, фонетическую близость слов, а так же близость на клавиатуре. Они также проводили сравнение алгоритмов анализа строк по произношению, и отметили, что этот вариант, плохо подходит для общей задачи коррекции опечаток.

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

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

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

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

Используемая схема работы

При проведении данной работы использовалась следующая схема работы опечаточника:

Используемые данные

Входные данные

Представляют собой тестовую выборку, представленную в текстовом файле.

Входной файл (он же тестовая выборка).

Формат:

word₁ [t correct₁₁, correct₁₂]

word₂ [t correct₂₁, correct₂₂]

Здесь: word — слово с ошибкой или опечаткой. Далее по желанию через табуляцию указываются варианты исправления (варианты исправления между собой разделяются «,»), тогда в автоматической выдаче пометятся те слова, которые совпали с вариантами исправления, указанными вручную.

Пример записи во входном файле:

Безплатно бесплатно

Параметры опечаточника

Текстовый файл, содержащий параметры, влияющие на качество работы опечаточника.

Параметры

Описание параметров с их значениями по умолчанию:

lev=0.165

максимальное (пороговое) значение расстояния Левенштейна, при котором одно слово считается исправлением другого.

len₁=4

len₂=7

coeff₁=0.2

coeff₂=0.3

coeff₃=0.4

Коэффициенты фильтрации. Пусть L — длина исправляемого слова, K — коэффициент, участвующий в фильтрации, тогда при

L < len₁ K = coeff₁;

len₁ < L < len_2K = coeff₂;

L > len_2K = coeff₃.

limit=5

Максимальное количество подсказок в выходном файле для одного исправляемого слова. Неявно влияет на порядок выдачи, то есть и на то, какая подсказка будет стоять на первом месте. Предположим, что limit == 5, это значит, что из списка наилучших подсказок мы возьмем только первые 5 штук, которые затем подвергаются заключительной сортировке. Если вариант, указанный человеком как правильный, будет стоять в этом списке на 6 месте, то мы правильный вариант теряем. Если бы мы указали limit = 6, то в выдаче появился бы правильный вариант.

log_arg=2.0

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

filter=all

Фильтрация выдачи подсказок. Принимает следующие значения:

none — оставляем все варианты;

trigon — фильтрация по правилу треугольника;

lev_dist — откидываются далекие от первой подсказки варианты;

all — включаются обе сортировки сразу.

sort=count_freq

Финальная сортировка. Принимет следующие значения:

count_freq — сортировка по количеству исправлений в слове, в рамках одинакового количества — по частоте;

mistake — сортировка по типу опечасток в слове;

lev_freq — сортировка по по расстоянию Левенштейна, в рамках одинакового расстояния — по частоте.

Словарная база

База слов, которую использует опечаточник.

Выходные данные

Все выходные данные записываются в два выходных файла.

1) Выходной файл с подробным описанием результатов для всех слов Формат выходного файла:

word₁ t time₁ t etalon

lev_dist₁₁ t correct₁₁ t [N₁₁, M₁₁]

lev_dist₁₂ t correct₁₂ t [N₁₂, M₁₂]

Здесь:

word₁ — обрабатываемое слово с ошибкой или опечаткой,

time₁ — время, потраченное на получение исправлений слова word₁,

etalon — вариант исправления, выбранный человеком,

lev_dist₁₁ — расстояние Левенштейна между word₁ и correct₁₁,

correct₁₁ — вариант исправления word₁,

[N₁₁, M₁₁] - проставляется, если вариант исправления совпадает с вариантом, указанным вручную (эталоном). N₁₁ — номер варианта в списке, указанным человеком, M₁₁ — номер варианта в автоматическом списке.

Выходной файл с общим описанием результатов для эксперимента:

Param — параметры опечаточника

Time — время работы опечаточника

Words — количество слов в эксперименте

Stat: all — right — [1,1] — [1,2] — [1,3]

Где

all — общее количество слов предложенных опечаточником

right — количество слов совпавших с выбором пользователей

[1,1] - количество слов, поставленных опечаточником и пользователем на первое место

[1,2] - количество слов, поставленных пользователем на первое место, а опечаточником на второе

[1,3] - количество слов, поставленных пользователем на первое место, а опечаточником на третье

Принцип работы данной схемы

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

Постановка задачи

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

Основными показателями эффективности работы опечаточника являются:

1) Полнота Данная характеристика определяется в первую очередь количеством слов в выборке, которые как пользователем, так и опечаточником были поставлены на первое место при исправлении опечаток.

2) Время работы Данная характеристика определяется временем, затраченным опечаточником на исправление опечаток.

Общая схема решения поставленной задачи

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

Все параметры можно разделить на 3 группы

1) Параметр, исследуемый на данном шагу

2) Уже исследованные параметры

3) Не исследуемые параметры (параметры не входящие в 1 и 2 группы)

Алгоритм исследования одного параметра

1) Произвольным образом выбираем значения не исследуемых параметров из области их задания.

2) Производим разбиение области задания исследуемого параметра В итоге для каждой точки данного разбиения можно задать параметры решателя (точка разбиения и не исследуемые параметры)

3) В каждой точке разбиения исследуемого параметра проводим эксперимент.

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

4) Сортируем полученные характеристические вектора в соответствии с лексикографическим порядком по невозрастанию.

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

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

целое число = N — n ,

где N-количество разбиений параметра, а n порядковый номер вектора в отсортированной последовательности.

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

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

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

Библиография

1. Damerau, F.J. A technique for computer detection and correction of spelling errors

2. Justin Zobel, Philip W. Dart: Phonetic String Matching: Lessons from Information Retrieval // SIGIR '96 Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, 1996

3. Justin Zobel, Philip W. Dart: Finding Approximate Matches in Large Lexicons // Software—Practice & Experience, Volume 25 Issue 3, March 1995

4. Карпенко М. П., Протасов С. В. «Некоторые методы очистки словаря запросов поиска»