Обнаружение и исправление ошибок пользователя по словарям допустимых слов и словосочетаний
Рассматривается метод контроля, автоматической (полуавтоматической) идентификации и исправления орфографических и смысловых ошибок пользователя, допущенных на этапе первичного формирования или ввода документа. Предложены модели оценки вероятностных характеристик, определяющих эффективность и область...
Збережено в:
| Дата: | 2006 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем математичних машин і систем НАН України
2006
|
| Назва видання: | Математичні машини і системи |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/83978 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Обнаружение и исправление ошибок пользователя по словарям допустимых слов и словосочетаний / В.А. Литвинов, С.Я. Майстренко, В.И. Ходак // Мат. машини і системи. — 2006. — № 2. — С. 80-86. — Бібліогр.: 5 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-83978 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-839782015-07-02T03:01:45Z Обнаружение и исправление ошибок пользователя по словарям допустимых слов и словосочетаний Литвинов, В.А. Майстренко, С.Я. Ходак, В.И. Моделювання і управління великими системами Рассматривается метод контроля, автоматической (полуавтоматической) идентификации и исправления орфографических и смысловых ошибок пользователя, допущенных на этапе первичного формирования или ввода документа. Предложены модели оценки вероятностных характеристик, определяющих эффективность и область целесообразного применения метода. Розглядається метод контролю, автоматичної (напівавтоматичної) ідентифікації та виправлення орфографічних і смислових помилок користувача, що були зроблені на етапі первинного формування або вводу документа. Запропоновано моделі оцінки імовірнісних характеристик, які визначають ефективність та область доцільного використання методу. The method of the checking, automatic (semiautomatic) to identifications and corrections spelling and semantic user' s errors, which were made in step of primary shaping or entering the document, is considered. Models of the estimation of the probabilistic features, defining efficiency and area of the expedient using the method are offered. 2006 Article Обнаружение и исправление ошибок пользователя по словарям допустимых слов и словосочетаний / В.А. Литвинов, С.Я. Майстренко, В.И. Ходак // Мат. машини і системи. — 2006. — № 2. — С. 80-86. — Бібліогр.: 5 назв. — рос. 1028-9763 http://dspace.nbuv.gov.ua/handle/123456789/83978 681.51:57 ru Математичні машини і системи Інститут проблем математичних машин і систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Моделювання і управління великими системами Моделювання і управління великими системами |
| spellingShingle |
Моделювання і управління великими системами Моделювання і управління великими системами Литвинов, В.А. Майстренко, С.Я. Ходак, В.И. Обнаружение и исправление ошибок пользователя по словарям допустимых слов и словосочетаний Математичні машини і системи |
| description |
Рассматривается метод контроля, автоматической (полуавтоматической) идентификации и исправления орфографических и смысловых ошибок пользователя, допущенных на этапе первичного формирования или ввода документа. Предложены модели оценки вероятностных характеристик, определяющих эффективность и область целесообразного применения метода. |
| format |
Article |
| author |
Литвинов, В.А. Майстренко, С.Я. Ходак, В.И. |
| author_facet |
Литвинов, В.А. Майстренко, С.Я. Ходак, В.И. |
| author_sort |
Литвинов, В.А. |
| title |
Обнаружение и исправление ошибок пользователя по словарям допустимых слов и словосочетаний |
| title_short |
Обнаружение и исправление ошибок пользователя по словарям допустимых слов и словосочетаний |
| title_full |
Обнаружение и исправление ошибок пользователя по словарям допустимых слов и словосочетаний |
| title_fullStr |
Обнаружение и исправление ошибок пользователя по словарям допустимых слов и словосочетаний |
| title_full_unstemmed |
Обнаружение и исправление ошибок пользователя по словарям допустимых слов и словосочетаний |
| title_sort |
обнаружение и исправление ошибок пользователя по словарям допустимых слов и словосочетаний |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| publishDate |
2006 |
| topic_facet |
Моделювання і управління великими системами |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/83978 |
| citation_txt |
Обнаружение и исправление ошибок пользователя по словарям допустимых слов и словосочетаний / В.А. Литвинов, С.Я. Майстренко, В.И. Ходак // Мат. машини і системи. — 2006. — № 2. — С. 80-86. — Бібліогр.: 5 назв. — рос. |
| series |
Математичні машини і системи |
| work_keys_str_mv |
AT litvinovva obnaruženieiispravlenieošibokpolʹzovatelâposlovarâmdopustimyhslovislovosočetanij AT majstrenkosâ obnaruženieiispravlenieošibokpolʹzovatelâposlovarâmdopustimyhslovislovosočetanij AT hodakvi obnaruženieiispravlenieošibokpolʹzovatelâposlovarâmdopustimyhslovislovosočetanij |
| first_indexed |
2025-07-06T10:52:12Z |
| last_indexed |
2025-07-06T10:52:12Z |
| _version_ |
1836894528068386816 |
| fulltext |
ISSN 1028-9763. Математичні машини і системи, 2006, № 2 80
УДК 681.51:57
В.А. ЛИТВИНОВ, С.Я. МАЙСТРЕНКО, В.И. ХОДАК
ОБНАРУЖЕНИЕ И ИСПРАВЛЕНИЕ ОШИБОК ПОЛЬЗОВАТЕЛЯ ПО СЛОВАРЯМ
ДОПУСТИМЫХ СЛОВ И СЛОВОСОЧЕТАНИЙ
Abstract: The method of the checking, automatic or semiautomatic to identifications and corrections spelling and
semantic user’ s errors, which were made in step of primary shaping or entering the document, is considered. Models
of the estimation of the probabilistic features, defining efficiency and area of the expedient using the method are
offered.
Key words: errors’ s automatic identification, spelling and semantic errors, dictionary of the possible words.
Анотація: Розглядається метод контролю, автоматичної або напівавтоматичної ідентифікації та
виправлення орфографічних і смислових помилок користувача, що були зроблені на етапі первинного
формування або вводу документа. Запропоновано моделі оцінки імовірнісних характеристик, які визначають
ефективність та область доцільного використання методу.
Ключові слова: автоматична ідентифікація помилок, орфографічні та смислові помилки, словники
допустимих слів.
Аннотация: Рассматривается метод контроля, автоматической либо полуавтоматической
идентификации и исправления орфографических и смысловых ошибок пользователя, допущенных на этапе
первичного формирования или ввода документа. Предложены модели оценки вероятностных
характеристик, определяющих эффективность и область целесообразного применения метода.
Ключевые слова: автоматическая идентификация ошибок, орфографические и смысловые ошибки,
словари допустимых слов.
1. Введение
Автоматическое обнаружение, идентификация и исправление ошибок пользователя является
важным фактором повышения уровня интеллектуализации интерфейса человек-компьютер. В [1]
исследуются модели и характеристики общих методов и алгоритмов автоматической
идентификации и исправления типовых ошибок пользователя на основе словаря допустимых слов.
В теоретических моделях [1] и практических коммерческих программных продуктах подобного
назначения [2–4] в качестве словарей подразумеваются и используются орфографические словари
соответствующих языков, т.е. словари, определяющие правильное написание (представление)
отдельных слов. Целью настоящей работы является обобщение и распространение методов и
подходов [1] на ошибки, имеющие более сложную грамматическую и смысловую структуру, и
построение моделей оценки вероятностных характеристик, определяющих возможности их
обнаружения, автоматической идентификации и исправления.
2. Основные понятия и определения
Нами рассматривается система ввода, контроля достоверности, идентификации и исправления
обнаруженных ошибок.
Для основных понятий и компонентов системы примем следующие определения и
обозначения:
l
kA – входное l -е слово (атрибут некоего информационного объекта) длиной kn символов
в алфавите kq ;
=
l
K
l
k
ll A...A...AA
1
– входное словосочетание (кортеж из K атрибутов);
ISSN 1028-9763. Математичні машини і системи, 2006, № 2
81
i
kT – словарь допустимых значений k -го слова )N,...,i( k1= ;
jTT – словарь допустимых значений словосочетаний )N,...,j( 1= .
Примечание. Словари могут быть как реальными, так и виртуальными. Во втором случае
виртуальный словарь может быть задан некоторым логико-
арифметическим соотношением, определяющим правило построения
допустимых слов и словосочетаний (например, избыточным кодом
контроля по модулю и т.п.).
Орфографическую ошибку определим как переход l
k
l
k AA → , в результате которого
образуется значение, отсутствующее в словаре i
kT . Такая ошибка обнаруживается в результате
проверки допустимости отдельного взятого слова.
Смысловую ошибку определим как переход l
k
l
k AA → , в результате которого образуется
допустимое значение, разрешенное словарем i
kT . Смысловая ошибка может быть обнаружена
(или нет) только в результате проверки допустимости словосочетания в целом.
Примечание. Смысловая ошибка в приведенной трактовке может иметь двоякое
происхождение:
1) как результат неумышленного искажения отдельных символов слова при формировании
документа (сообщения) или его вводе;
2) как результат неправильного истолкования формируемого словосочетания и замены
одного значения атрибута другим, тоже формально допустимым.
В качестве наглядного иллюстративного примера рассмотрим правильное словосочетание
русского языка "кот бежит". Орфографическая ошибка "кот → крт" может быть обнаружена путем
проверки допустимости значения "крт", отсутствующего в словаре. Смысловая ошибка "кот → кит"
не обнаруживается на уровне орфографического контроля, но ошибка в словосочетании "кит
бежит" – налицо. И, наконец, смысловая ошибка "бежит → лежит" не обнаруживается вообще (без
более широкого контекстного анализа, но этот уровень контроля мы здесь не рассматриваем).
Статическая структура рассматриваемой системы приведена на рис. 1.
Сформулируем исходное правило построения jTT :
Если ji
K
i
k.
i TTA...A..A ∈1 , то
i
k
i
k TA ∈∀ ( )K,...,k;N,...,i k 11 == . (1)
Суть правила заключается в том, что допустимые словосочетания состоят исключительно
из допустимых слов.
Примечание. Правило не носит абсолютного характера, а лишь ограничивает область
рассматриваемых ситуаций случаями, наиболее типичными для представления данных. Для более
сложных случаев, которые теоретически могут быть свойственны в частности, отношениям между
элементами знаний, это правило может и не выполняться. Например, некие лица Z,Y,X вместе
( )XYZ могут быть совместимыми, а попарно ( )YZ,XZ,XY – нет.
ISSN 1028-9763. Математичні машини і системи, 2006, № 2 82
Из (1) вытекают следующие свойства проверяемых словосочетаний l
K
l
k
l A...A...A1 по отношению к
возможным ошибкам.
1. Если ji
K
i TTA...A ∉1 и i
k
l
k TA ∉∃ , то произошла орфографическая ошибка в слове l
kA .
2. Если ji
K
i TTA...A ∉1 и i
k
l
k TA ∈∀ , то произошла смысловая ошибка из-за формально
допустимого искажения неизвестного слова.
3. Если ji
K
i TTA...A ∈1 , то i
k
l
k TA ∈∀ , и ошибка в словосочетании отсутствует (или не
обнаружена).
3. Общая схема контроля-коррекции словосочетания
Возможны два варианта этапности контроля-коррекции словосочетания.
В первом варианте вначале проверяются отдельные слова на наличие орфографических
ошибок. Ошибки (при их наличии) обнаруживаются, идентифицируются и исправляются по
алгоритмам моделей [1]. Затем выполняются контроль совместимости слов словосочетания,
идентификации и коррекция смысловых ошибок.
Во втором варианте вначале производится контроль совместимости, а затем, в
зависимости от результата, контроль отдельных слов и далее – идентификация и исправление
орфографических, а затем смысловых ошибок.
Рис. 1. Структура рассматриваемой системы
iT1
Al
1 … Al
k … Al
K
lA
.
.
.
1N
1
1
n
q
.
.
.
KN
i
KT
kn
Kq
1
1A … 1
kA … 1
KA
… …
… …
. .
. .
. .
jA1 … j
kA … j
KA
. .
. .
. .
∏
=
K
k
kN
1
N
jTT
kN
ISSN 1028-9763. Математичні машини і системи, 2006, № 2
83
Явная предпочтительность второго варианта определяется тем фактором, что ошибок
следует ожидать далеко не в каждом словосочетании. Следовательно, во втором варианте
большая часть контрольных проверок ограничится проверкой «группового» условия
jl
K
l TTA...A ∈1 .
Общая схема алгоритма контроля-коррекции на основе второго варианта включает
следующие этапы:
1. Проверка jl
k
l TTA...A ∈1 . Если результат положительный, то словосочетание считается
безошибочным. Иначе – в словосочетании имеется ошибка; переход к п. 2.
2. Проверка условия i
k
l
k TA ∈∀ . Если результат отрицательный и i
k
k
l TA ∉∃ , то произошла
орфографическая ошибка в слове l
kA . Она обрабатывается схемой АИК [1] с последующим
переходом к п. 1. )l:l( 1+= . Иначе в словосочетании имеется смысловая ошибка. Переход к п. 3.
3. Идентификация смысловой ошибки и ее исправление (с участием или без участия
пользователя). Переход к п.1.
Граф, отображающий структуру частных исходов-событий алгоритма, приведен на рис. 2.
При оценке вероятностей 222121 ππππ ,,, будем исходить из следующего допущения о их
распределении:
а) множества допустимых значений слов
i
kA мощностью kN среди множества их
всевозможных значений мощностью kn
kq ;
б) множества допустимых значений словосочетаний j
K
j
k A...A мощностью N среди
множества их всевозможных значений мощностью kN
K
k 1=
Π .
12π
Рис. 2. Структура событий
3 Идентификация и
исправление
2 Идентификация и
исправление [1]
Ошибка не
обнаружена
22π
Произошла ошибка в k -м слове
l -го словосочетания
Ошибка
орфографическая
Ошибка смысловая
1π 2π
Ошибка не
обнаружена
Ошибка
обнаружена
Ошибка
обнаружена
012 =π 111 =π
ISSN 1028-9763. Математичні машини і системи, 2006, № 2 84
С учетом определения типов ошибок, принятого допущения о распределении вероятностей
и свойств 1–2 получим,
kn
k
k
q
N
−=π 11 ;
kn
k
k
q
N
=π2 ;
k
K
k
N
N
1
21 1
=
Π
π −= ;
k
K
k
N
N
1
22
=
Π
π = . (2)
Из приведенных соотношений видно, что контролирующая способность (относительное
количество обнаруженных ошибок) для орфографического контроля равна:
kn
k
k
орф
q
N
D −== π 11 ,
а для совокупности орфографического и смыслового контролирующая способность будет равна:
k
K
k
kn
k
k
k
K
k
kn
k
k
kn
k
k
см,орф
N
N
q
N
N
N
q
N
q
N
D
11
2121 111
==
Π
Π
πππ ⋅−=−+−=⋅+= .
Примем для всех Kk ,...1= отношение ,const
q
N
r
kn
k
k ==
∏
=
=
K
k
kN
N
R
1
.
Тогда rRD см,орф −= 1 .
При 1<r и 1<R (а эти неравенства практически всегда достаточно глубоки) величина
орфсм,орф DD 〉〉 . Например, для 210−=r и 210−=R только орфографический контроль
теоретически позволяет обнаружить 99% ошибок, а орфографический + смысловой – 99,99%.
4. Идентификация и исправление смысловых ошибок
Идентификация смысловых ошибок и оценка вероятностных характеристик этого процесса
возможны на основе применения и исследования механизма [1] генерации обратных искажений
ошибочного слова по словарям i
kT .
Будем интерпретировать K – кратное словосочетание как K – символьное гиперслово в
смешанном алфавите ,,...,...1 Kk NNN а смысловую ошибку в гиперслове – как однократную
транскрипцию k -го гиперсимвола. Под гипервариацией будем понимать замену текущего значения
слова l
kA на очередное из словаря i
kT . В контексте этих определений процесс автоматической
(полуавтоматической) идентификации заключается в генерации гипервариаций в классе
однократных транскрипций и проверке допустимости образованного гиперслова по словарю jTT .
Полное количество генерируемых гипервариаций KV определяется простым выражением:
KNV
K
k
kK −∑=
=1
. (2)
ISSN 1028-9763. Математичні машини і системи, 2006, № 2
85
В зависимости от используемого алгоритма разрешения возможной неоднозначности
совпавшее гиперслово словаря jTT может предлагаться пользователю для подтверждения
корректировки либо исправляться автоматически. При условии сохранения допущения о случайном
распределении значений словосочетаний в словаре jTT и применении соотношений общей
модели испытаний Бернулли вероятность ( )KV,R,gP в точности g случайных совпадений
определяется выражением
( ) ( ) gKVgg
KVK RRV,R,gP C −
−⋅⋅= 1 .
Вероятность одновременного искажения более одного слова будем считать пренебрежимо
малой. В этом случае в терминах [1] "корректируемой" ошибкой является однократная
транскрипция, и вероятность ее появления (при условии, что в словосочетании обнаружена
смысловая ошибка) равна 1, так что все выражения [1] для вероятностей правильной AKP , ложной
ЛКP и ручной PКP коррекции соответственно упрощаются. Например, для наиболее простого (в
смысле анализа) и перспективного для применения в рассматриваемом приложении алгоритма 3,
требующего подтверждения предлагаемой корректировки пользователем,
( )mPAK π= ,
0≈ЛКP ,
( )mPPК π−= 1 ,
где ( )mπ определяет вероятность того, что среди m предложенных вариантов корректировки
содержится правильный вариант. Как показано в [5],
( ) ( ) ( ) 1
1
11
0
1
1
1
1
−−
−
−
=
−
=
−−
−∑
+
+∑ −=π gKVgg
KV
KV
mg
m
g
gKVgg
KV RRC
g
m
RRCm .
В таблице приведены иллюстративные результаты расчета значений ( )mPАК π= для
следующих данных:
,3=K 2
1 10=N ; 2
2 105⋅=N ; 3
3 10=N ; 234 105,105,105 ⋅⋅⋅=N .
В этом случае, как следует из (1) и (2), ,1597=kV 543 10,10,10 −−−=R .
Таблица. Иллюстративные результаты расчета значений АКP
m R
1 2 3 4 5
310− 0,4994 0,7964 0,9315 0,9857 0,9953
410− 0,9242 0,9960 0,9998 1,0000 1,0000
510− 0,9920 0,9999 1,0000 1,0000 1,0000
Как видно из таблицы, для данных значений NNK k ,, результаты полуавтоматической
идентификации смысловой ошибки, допущенной при вводе, можно считать вполне приемлемыми –
ISSN 1028-9763. Математичні машини і системи, 2006, № 2 86
правильное значение атрибута находится среди 3–5 альтернатив с вероятностью, весьма близкой к
1 (с точностью в пределах 5 знаков). Для ошибки, допущенной при формировании первичного
документа, возможно только автоматическое исправление (алгоритмы 1, 2 [1]) или возврат
документа на проверку и исправление к первоисточнику. Уверенное автоматическое исправление
возможно только в случае таких сочетаний значений NN k , , при которых 1≈m .
Поскольку, как известно, среднее число "удачных" исходов для испытаний Бернулли равно
KRV (в наших обозначениях), то обобщенным ориентировочным критерием оценки применимости
метода автоматической идентификации и исправления смысловых ошибок может служить
неравенство ε<kRV . Выражая левую часть через “первичные” параметры словарей NN k , ,
получим:
ε<
∏
⋅
=
=
∑
K
k
K
k
k
k
N
NN
1
1 ,
где ε – принятое допустимое относительное количество “ручных” (или ложных) исправлений.
Например, значение ε = 0,01 означает, что примерно на 100 случаев идентификации
смысловой ошибки в 1 случае в дополнение к правильной вариации со словарем jTT произойдет
еще одно случайное ложное совпадение. В этом случае алгоритм 1 [1] выполнит правильную
автоматическую коррекцию с вероятностью 0,5, а алгоритмы 2, 4 предложат идентифицировать и
исправить ошибку "вручную".
5. Выводы
Совместный контроль орфографических и смысловых ошибок позволяет существенно повысить
достоверность вводимой информации.
Для автоматической идентификации и исправления смысловых ошибок может быть
использован метод генерации обратных искажений словосочетания и проверки их допустимости.
Полученные в работе [1] соотношения вместе с выражениями (1)–(3) позволяют получить
ориентировочные оценки результативности метода. В перспективе применение описанного
подхода возможно и для более сложных ошибок, – в частности, сочетания кортежей таблицы
(экземпляров входных форм). Это случай нуждается в отдельном исследовании.
СПИСОК ЛИТЕРАТУРЫ
1. Кузьменко Г.Є., Литвинов В.А., Майстренко С.Я., Ходак В.І. Алгоритми і моделі автоматичної ідентифікації та
корекції типових помилок користувача на основі природної надмірності // Математичні машини і системи. –
2004. – № 2. – С. 134–148.
2. AfterScan. http://www/afterscan.com/ru.
3. http://www.abbyy.ru/products/handprint/WP_form_processing_65.pdf.
4. Редактор 1ДФ. http://octant.com.ua.
5. Литвинов В.А., Майстренко С.Я., Ступак Н.Б. Некоторые оценки вероятностных характеристик процесса
автоматической идентификации ошибок пользователя на основе эталонного словаря // УСиМ. – 2001. – № 2. –
C. 21–24.
|