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

Содержание:

ВВЕДЕНИЕ

Задачи обработки текстов возникли практически сразу вслед за появлением вычислительной техники. Но несмотря на полувековую историю исследований в области искусственного интеллекта, накопленный опыт вычислительной лингвистики, огромный скачок в развитии информационных технологий и смежных дисциплин, удовлетворительного решения большинства практических задач обработки текста пока не найдено. Однако ИТ-индустрия потребовала удовлетворительного решения некоторых задач обработки текстов. Так, развитие хранилищ данных делает актуальными задачи извлечения информации и формирования корректно построенных текстовых документов. Бурное развитие 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 и формируется множество знакомых слов. Корректор возвращает слово из данного множества с максимальной априорной вероятностью. Если множество знакомых слов не удалось сформировать снова, то корректор возвращает слово, которое было введено на вход.

2.3 Проверка качества работы корректора Питера Норвига.

Листинг корректора, реализованный на языке программирования Pithon представлен в Приложении 1.

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

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

Ncorrect/N, где

Ncorrect — кол-во правильных исправлений,

N- общее число слов для проверки.

Листинги программ для для генерации ошибок в слове и проверки качества корректора, реализованные на языке программирования Pithon, представлены в приложениях 2 и 3 соответственно.

2.4 Результаты проверки качества работы корректора.

Для проверки качества работы корректора в качестве словаря был выбран рассказ, состоящий из 11 174 слов. Количество уникальных слов в тексте – 3 009. Для слов с одной ошибкой частота правильных исправлений ~ 95%. Для слов с двумя ошибками частота правильных исправлений ~ 76%. Скорость работы для слов с одной ошибкой ~ 3823 слова в секунду. Скорость работы для слов с двумя ошибками ~ 9 слов в секунду.

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

Рассмотрим достоинства и недостатки данного корректора:

Достоинства:

1. Относительно простая реализация.
2. Неплохое качество модели.

Недостатки:

1. В подавляющем большинстве случаев работает очень медленно (несколько секунд для одного слова). Это может сказаться на качестве в онлайн использовании, где необходимо исправить ошибку за миллисекунды.
2. Данный корректор исправляет лишь одно слово за раз, то есть он не учитывает контекст между словами в строке.
3. Для качественной работы, требуется объемный словарь.

ЗАКЛЮЧЕНИЕ

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

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

БИБЛИОГРАФИЯ

1. Большакова, Е.И. Автоматическая обработка текстов на естественном языке и анализ данных: учеб. пособие/ Е.И. Большакова [и др.] — М.: Изд-во НИУ ВШЭ, 2017. — 269 с.
2. Черненький В.М. Методика идентификации пассажира по установочным данным/ В.М. Черненький, Ю. Е. Гапанюк// Инженерный журнал: наука и инновации .— 2012 .— №3
3. Сходство Джаро — Винклера // Википедия. [2018—2018]. Дата обновления: 25.04.2018. URL: https://ru.wikipedia.org/?oldid=92306663 (дата обращения: 25.04.2018).
4. Расстояние Хэмминга // Википедия. [2018—2018]. Дата обновления: 12.04.2018. URL: https://ru.wikipedia.org/?oldid=92055373 (дата обращения: 12.04.2018)

Приложение 1

Листинг программы «корректор Питера Норвига»

import re

from collections import Counter

#заполнение словаря

def words(text): return re.findall(r'\w+', text.lower())

WORDS = Counter(words(open('slovar.txt').read()))

#вероятность появления слова

def P(word, N=sum(WORDS.values())):

return WORDS[word] / N

#функция корекции слова

def correction(word):

return max(candidates(word), key=P)

#просмотр кандидатов

def candidates(word):

return (known([word]) or known(edits1(word)) or known(edits2(word)) or [word])

#функция определения множества знакомых слов

def known(words):

return set(w for w in words if w in WORDS)

#функция создающая все возможные преобразования слова с глубиной 1

def edits1(word):

letters = 'йцукенгшщзхъфывапролджэячсмитьбю'

splits = [(word[:i], word[i:]) for i in range(len(word) + 1)]

deletes = [L + R[1:] for L, R in splits if R]

transposes = [L + R[1] + R[0] + R[2:] for L, R in splits if len(R)>1]

replaces = [L + c + R[1:] for L, R in splits if R for c in letters]

inserts = [L + c + R for L, R in splits for c in letters]

return set(deletes + transposes + replaces + inserts)

#функция создающая все возможные преобразования слова с глубиной 1

def edits2(word):

return (e2 for e1 in edits1(word) for e2 in edits1(e1))

Приложение 2

Листинг программы «генератор ошибок в слове»

import random

def gen_error(s1):

letters = 'йцукенгшщзхъфывапролджэячсмитьбю' #буквы в русском алфавите

rnd = random.randint(1,4) #равно вероятно выбирается одна из 4 операций(удаление,замена,вставка,транспозиция)

#транспозиция

if(rnd == 1):

rnd1 = random.randint(0,len(s1)-2)

return s1[:rnd1]+s1[rnd1+1]+s1[rnd1]+s1[rnd1+2:]

#удаление

if(rnd == 2):

rnd1 = random.randint(0,len(s1)-1)

return s1[:rnd1]+s1[rnd1+1:]

#замена

if(rnd == 3):

rnd1 = random.randint(0,len(s1)-1)

b = letters[random.randint(0,len(letters)-1)]

return s1[:rnd1]+b+s1[rnd1+1:]

if(rnd == 4):

rnd1 = random.randint(0,len(s1)-1)

b = letters[random.randint(0,len(letters)-1)]

return s1[:rnd1]+b+s1[rnd1:]

Приложение 3

Листинг программы «проверка качества работы корректора Питера Норвига»

import time

error_list1 = {i:gen_error(i) for i in WORDS if(len(i)>3)}

error_list2 = {i:gen_error(gen_error(i)) for i in WORDS if(len(i)>3)}

tm = time.clock()

cnt1 = 0

for i in error_list1:

if(i == correction(error_list1[i])):

cnt1+=1

dt1 = time.clock()-tm

tm = time.clock()

for i in error_list2:

if(i == correction(error_list2[i])):

cnt2+=1

dt2 = time.clock()-tm

print(«correction rate with 1 error : {:.0%}»).format(cnt1/len(error_list1))

print(«time working with 1 error : {:.0%}»).format(len(error_list1)/dt1)

print(«correction rate with 2 error : {:.0%}»).format(cnt2/len(error_list2))

print(«time working with 2 error : {:.0%}»).format(len(error_list2)/dt2)