Інверсний контекстно-асоціативний метод автоматизованої орфокорекції

Теоретично обґрунтовано та запропоновано інверсний контекстно-асоціативний метод автоматизованого виправлення орфографічних помилок, який забезпечує підвищення швидкості та точності роботи відповідного програмного забезпечення. Дано визначення показника результативності функціонування орфокоректо...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2008
Автори:	Заболотня, Т.М., Михайлюк, А.Ю., Михайлюк, О.С.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут проблем штучного інтелекту МОН України та НАН України 2008
Теми:	Прикладные интеллектуальные системы
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/6820
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Інверсний контекстно-асоціативний метод автоматизованої орфокорекції / Т.М. Заболотня, А.Ю. Михайлюк, О.С. Михайлюк // Штучний інтелект. — 2008. — № 3. — С. 78-88. — Бібліогр.: 11 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-6820
record_format	dspace
spelling	irk-123456789-68202010-03-19T12:00:43Z Інверсний контекстно-асоціативний метод автоматизованої орфокорекції Заболотня, Т.М. Михайлюк, А.Ю. Михайлюк, О.С. Прикладные интеллектуальные системы Теоретично обґрунтовано та запропоновано інверсний контекстно-асоціативний метод автоматизованого виправлення орфографічних помилок, який забезпечує підвищення швидкості та точності роботи відповідного програмного забезпечення. Дано визначення показника результативності функціонування орфокоректора – точності його роботи. Показана ефективність застосування запропонованого методу для виправлення орфографічних помилок у масиві гетерогенних словосполучень за критеріями швидкості та точності корекції. Теоретически обусловлен и предложен инверсионный контекстно-ассоциативный метод автоматического исправления орфографических ошибок, который обеспечивает повышение скорости и точности работы соответствующего программного обеспечения. Дано определение показателя результативности функционирования орфокорректора – точности его работы. Показана эффективность использования предлагаемого метода для исправления орфографических ошибок в массиве гетерогенных словосочетаний по критериям скорости и точности коррекции. 2008 Article Інверсний контекстно-асоціативний метод автоматизованої орфокорекції / Т.М. Заболотня, А.Ю. Михайлюк, О.С. Михайлюк // Штучний інтелект. — 2008. — № 3. — С. 78-88. — Бібліогр.: 11 назв. — укр. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/6820 004.421 uk Інститут проблем штучного інтелекту МОН України та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Прикладные интеллектуальные системы Прикладные интеллектуальные системы
spellingShingle	Прикладные интеллектуальные системы Прикладные интеллектуальные системы Заболотня, Т.М. Михайлюк, А.Ю. Михайлюк, О.С. Інверсний контекстно-асоціативний метод автоматизованої орфокорекції
description	Теоретично обґрунтовано та запропоновано інверсний контекстно-асоціативний метод автоматизованого виправлення орфографічних помилок, який забезпечує підвищення швидкості та точності роботи відповідного програмного забезпечення. Дано визначення показника результативності функціонування орфокоректора – точності його роботи. Показана ефективність застосування запропонованого методу для виправлення орфографічних помилок у масиві гетерогенних словосполучень за критеріями швидкості та точності корекції.
format	Article
author	Заболотня, Т.М. Михайлюк, А.Ю. Михайлюк, О.С.
author_facet	Заболотня, Т.М. Михайлюк, А.Ю. Михайлюк, О.С.
author_sort	Заболотня, Т.М.
title	Інверсний контекстно-асоціативний метод автоматизованої орфокорекції
title_short	Інверсний контекстно-асоціативний метод автоматизованої орфокорекції
title_full	Інверсний контекстно-асоціативний метод автоматизованої орфокорекції
title_fullStr	Інверсний контекстно-асоціативний метод автоматизованої орфокорекції
title_full_unstemmed	Інверсний контекстно-асоціативний метод автоматизованої орфокорекції
title_sort	інверсний контекстно-асоціативний метод автоматизованої орфокорекції
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
publishDate	2008
topic_facet	Прикладные интеллектуальные системы
url	http://dspace.nbuv.gov.ua/handle/123456789/6820
citation_txt	Інверсний контекстно-асоціативний метод автоматизованої орфокорекції / Т.М. Заболотня, А.Ю. Михайлюк, О.С. Михайлюк // Штучний інтелект. — 2008. — № 3. — С. 78-88. — Бібліогр.: 11 назв. — укр.
work_keys_str_mv	AT zabolotnâtm ínversnijkontekstnoasocíativnijmetodavtomatizovanoíorfokorekcíí AT mihajlûkaû ínversnijkontekstnoasocíativnijmetodavtomatizovanoíorfokorekcíí AT mihajlûkos ínversnijkontekstnoasocíativnijmetodavtomatizovanoíorfokorekcíí
first_indexed	2025-07-02T09:41:52Z
last_indexed	2025-07-02T09:41:52Z
_version_	1836527714689875968
fulltext	«Искусственный интеллект» 3’2008 78 2-З УДК 004.421 Т.М. Заболотня, А.Ю. Михайлюк, О.С. Михайлюк Національний технічний університет України «Київський політехнічний інститут», м. Київ, Україна tatiana104@yandex.ru Інверсний контекстно-асоціативний метод автоматизованої орфокорекції Теоретично обґрунтовано та запропоновано інверсний контекстно-асоціативний метод автоматизованого виправлення орфографічних помилок, який забезпечує підвищення швидкості та точності роботи відповідного програмного забезпечення. Дано визначення показника результативності функціонування орфокоректора – точності його роботи. Показана ефективність застосування запропонованого методу для виправлення орфографічних помилок у масиві гетерогенних словосполучень за критеріями швидкості та точності корекції. Вступ На сучасному етапі розвитку суспільства, в умовах зростання потреби у підвищенні рівня інтелектуалізації інформаційних технологій великого значення набула проблема забезпечення ефективної комп’ютеризованої обробки природномовних текстів. Важливою задачею систем автоматичної обробки текстів (АОТ) різного при- значення є перевірка орфографії в текстових даних. На даний момент актуальним є дослідження програмного забезпечення орфокорекції з точки зору виправлення по- милок, адже задача виявлення помилок досліджувалась триваліший час і розв’язана у більшій мірі [1]. Сучасні орфокоректори характеризуються невисоким рівнем автоматизації, орієнтацією на виправлення однократних помилок, відсутністю забезпечення семан- тичної узгодженості варіантів виправлення та контексту спотвореного слова [1], [2]. Ці недоліки зумовлюють низьку ефективність роботи коректорів, основним крите- рієм оцінки якої на сьогоднішній день виступають точність та швидкість обробки текстових даних. Усунення визначених вище вад потребує модифікації існуючих алгоритмів виправлення помилок у напрямку залучення контекстної інформації та лексико-се- мантичних словникових ресурсів для її обробки. Але на даний момент в програмних засобах орфокорекції методика врахування контексту спотвореного слова за допомо- гою семантичного інструментарію є недостатньо розробленою, а отже, дослідження даного питання видається актуальним. 1. Постановка задачі На сьогоднішній день розробка автокоректорів є окремим широко досліджуваним напрямом у галузі створення систем АОТ. Але, незважаючи на це, способи побудови ефективних програмних засобів корекції спотворених слів здебільшого визначаються загальними характеристиками сучасного етапу розвитку систем АОТ та комп’ютерної техніки взагалі. Інверсний контекстно-асоціативний метод автоматизованої орфокорекції «Штучний інтелект» 3’2008 79 2-З 1. З огляду на постійне зростання обсягів пам’яті та швидкодії сучасних комп’ю- терів основними вимогами до систем АОТ сьогодні є точність та швидкість їх роботи. Це сприяє все більшому розповсюдженню використання словників при аналізі даних, яке раніше було неможливим через труднощі, зумовлені підвищеними вимогами до обсягу пам’яті в запам’ятовуючих пристроях. Словниковий підхід забезпечує отримання високоточних результатів обробки текстів [2], [3]. Точність орфокорекції у наукових джерелах визначається як відсоток спотворених слів, для котрих програмою підібрано вірний варіант виправлення [4], або як імовірність входження правильного варіанта до набору гіпотез [5]. 2. На відміну від програмного забезпечення кін. ХХ ст., коли основу машинної обробки тексту складав морфологічний аналіз, теперішні системи широко викори- стовують ресурси та методи синтаксичного та семантичного аналізу (для автома- тичного анотування, реферування, машинного перекладу тощо). 3. Для забезпечення можливості врахування значення слів системами АОТ у більшості випадків розробники віддають перевагу аналізу контексту, а не семантики граматичної структури окремих слів [6]. 4. Загальноприйнятою схемою аналізу тексту залишається так звана послідовна схема (морфологічний, синтаксичний, семантичний рівні аналізу), коли результати кожного попереднього етапу є вихідною інформацією для наступних [6]. Можна сказати, що всі наведені характеристики систем АОТ властиві сучасним автокоректорам у тій чи іншій мірі [5], [7], [8]. Особливу увагу слід приділити схемі аналізу текстових даних, якої дотримуються у своїй роботі системи АОТ. Справа у тому, що етапи аналізу природномовного тексту не є функціонально ізольованими, хоч і виконуються зазвичай послідовно. Згідно з цим, морфологічний аналіз може не лише надавати вихідні дані для синтаксичного та семантичного аналізу, але і використовувати результати останніх [9]. Така тенденція до порушення класичного порядку аналізу текстів сьогодні вже спостерігається у системах АОТ [1], [9]. Але досі обробка контексту спотвореного слова семантичним інструментарієм має місце тільки на кінцевому етапі процесу комп’ютеризованої орфокорекції. Таким чином, виходячи із наведених вище аргументів, метою даної статті стало підвищення швидкості та точності автоматизованого виправлення орфографічних по- милок відповідними програмними засобами за рахунок створення контекстно- асоціативного методу корекції спотворених слів. У відповідності до поставленої мети задачами дослідження є:  вивчення способів реалізації етапів процедури орфокорекції на предмет виявлення можливостей щодо підвищення її ефективності;  розробка контекстно-асоціативного методу орфокорекції для підвищення ефективності роботи відповідного програмного забезпечення за показниками точності та швидкості виправлення помилок;  аналіз результатів експериментального дослідження ефективності запропонованого контекстно-асоціативного методу орфокорекції. 2. Схема автоматизованого виправлення орфографічних помилок Загальноприйнята схема автоматизованої корекції спотвореного слова [1], [10] передбачає реалізацію:  етапу висунення гіпотез (вірогідних варіантів виправлення помилки);  етапу перевірки гіпотез та ухвалення однієї (декількох) з них як виправлення, що пропонується програмою до внесення. Заболотня Т.М., Михайлюк А.Ю., Михайлюк О.С. «Искусственный интеллект» 3’2008 80 2-З На першому етапі послідовно виконуються підбір первинної множини варіантів виправлення із словника та попередня фільтрація її вмісту. Для цього використовуються найпростіші та найшвидші методи пошуку варіантів корекції слова (наприклад, підбір гіпотез за критерієм альфакоду, довжини слова, збігу першої літери слова [10] тощо). На другому етапі виконується перевірка гіпотез на подібність до спотвореного слова за певними критеріями. Тут задіяні більш складні, але, водночас, і більш точні методи аналізу набору гіпотез (наприклад, відстань редагування Левенштейна). Таким чином, умовне віднесення методів визначення варіантів виправлення орфографічних помилок до певного етапу процесу орфокорекції здійснюється на основі їх характеристик (швидкості, точності тощо). З іншого боку, методи висунення та перевірки гіпотез виправлення за своєю суттю передбачають фільтрацію заданої множини слів, адже в результаті застосу- вання кожного з них відбувається звуження поточної множини варіантів корекції спотвореного слова. З огляду на це введемо функцію фільтрації множини слів за певною ознакою filter та визначимо її властивості. Визначення 1. Функція yx WWfilter : називається фільтром множини xW , якщо за її допомогою з елементів xW проводиться формування множини слів yW , які відповідають певному критерію схожості зі спотвореним словом ( xy WW  ). xyyx WWWWfilter  ,: , (1) де yx WW , – множини природномовних слів. Виходячи з фізичного змісту функції filter, її властивостями є: 1) адитивність: )()()( BABA WfilterWfilterWWfilter  ; (2) 2) комутативність композиції фільтрів: при застосуванні композиції функцій xyyxnn WWWWfilterfilterfilterfilterF   ,:... 121  до множини слів xW від перестановки складових ifilter місцями результат yW не змінюється, адже у будь- якому випадку всі слова, які не відповідають хоча б одному критерію відбору, будуть вилучені з множини xW ; 3) якщо BA WW  , то час, необхідний для виконання фільтрації даних множин, характеризується нерівністю )()( B WfilterAWfilter tt  , (3) де )( ,)( B WfilterAWfilter tt – час фільтрації множин BA WW , за допомогою функції filter. Оскільки всі функції, які реалізують методи відбору та перевірки гіпотез виправ- лення, є фільтрами, їм притаманні властивості визначеної вище функції filter. Виходячи з вищенаведеного, пропонується внести уточнення в подання схеми орфокорекції: будемо вважати процес визначення варіантів виправлення таким, що складається із застосування композиції функцій фільтрації до множини слів dictW , яка міститься у словнику. Позначимо послідовність фільтрів як 1 ,:...... 121   mWWfffffFILTERS retrdictimm  , (4) де iii WWf 1: (і = 2, …, m) – фільтр множини слів, отриманої у результаті виконання 1if (для 1f – множини dictW ); retrW – множина слів, визначених коректором як можливі варіанти виправлення за ознаками їх близькості до спотвореного слова. Інверсний контекстно-асоціативний метод автоматизованої орфокорекції «Штучний інтелект» 3’2008 81 2-З Перш ніж приступити до пошуку місця семантичної складової у схемі орфокорекції, реалізація якої забезпечує найбільш ефективну роботу програмного коректора за критеріями точності та швидкості, зупинимось на визначенні точності результату виправлення помилок. Сучасні словникові ресурси характеризуються великим обсягом даних [6], що ускладнює однозначний підбір з них правильного варіанта написання спотвореного слова. Тому виправданим способом оцінювання точності орфокорекції є її обчислення як частки спотворених слів, до множини варіантів виправлення яких входить вірна словоформа [5]. Але для забезпечення високого рівня автоматизації обробки текстових даних потрібно не тільки збільшення імовірності входження правильного варіанта виправлення до набору гіпотез, але й зменшення кількості знайдених нерелевантних гіпотез. Через це необхідним є знаходження способу оцінювання ефективності орфокорекції за критерієм точності, який забезпечив би врахування частки нерелевантних слів у множині варіантів виправлення. У даній статті йдеться про визначення гіпотез шляхом їх пошуку в словнику (а не за допомогою безсловникової генерації), тому при визначенні точності орфокорекції пропонується провести певні паралелі із оцінками результатів роботи програм у теорії інформаційного пошуку [6]. Визначення 2. Під точністю машинної орфографічної корекції спотвореного слова будемо розуміти відношення числа запропонованих орфокоректором вірних варіантів написання слова (це одиниця або нуль) до загальної кількості підібраних слів. \|\| \|\| retr retrcorr W WWPRECISION   , (5) де corrW – множина вірних варіантів корекції спотвореного слова у словнику. Відповідно до формули (5), для того, щоб досягти високого показника точності роботи орфокоректора, необхідно, по-перше, забезпечити постійне входження вірного слова до сформованого масиву варіантів виправлення ( \| \| 1corr retrW W  ), а по-друге, – зменшити загальну кількість слів, які пропонуються програмою як найбільш вірогідні кандидати виправлення помилки ( retrW ). 3. Місце семантичної складової у схемі виправлення орфографічних помилок Згідно з класичною послідовністю обробки текстових даних (морфологічний, синтаксичний та семантичний аналіз), семантичні фільтри набору гіпотез мають стояти наприкінці композиції FILTERS (4). Відповідно ж до сучасних тенденцій щодо зміни загальноприйнятого порядку етапів обробки текстів, можливим є підвищення ефектив- ності програмного орфокоректора у випадку перенесення перевірки гіпотез за семан- тичними критеріями ближче до початку FILTERS. Проведемо дослідження впливу зміни місця семантичної складової у схемі орфокорекції на показники точності та швидкодії програмного коректора. Формування множини гіпотез виправлення за семантичним критерієм із заданого набору слів здійснюватимемо за допомогою функції contf . Визначимо дану функцію як фільтр, який застосовується для відбору із вихідного набору слів тих словоформ, що узгоджені з контекстним оточенням спотвореного слова. Заболотня Т.М., Михайлюк А.Ю., Михайлюк О.С. «Искусственный интеллект» 3’2008 82 2-З Розглянемо 3 варіанти розміщення contf у схемі визначення варіантів виправлення: 1) контекстно-асоціативну фільтрацію гіпотез як останній етап процесу підбору варіантів виправлення: 1 2 1... : , 1cont m m dict retrf f f f f W W m        , (6) 2) проведення відбору гіпотез за ознакою їх відповідності змісту заданого кон- тексту в середині процесу орфокорекції: 1 1 2 1... ... : , 1m m cont i dict retrf f f f f f W W m           , (7) 3) висунення гіпотез за критерієм їх семантичної близькості до контексту спо- твореного слова (перенесення contf на початок схеми корекції): 1 2 1... : , 1m m cont dict retrf f f f f W W m        . (8) Твердження 1. Зміна розташування фільтра contf у схемі орфокорекції не впливає на точність роботи коректора (PRECISION). Доведення. Дане твердження є коректним, виходячи з властивості (2) функцій класу filter: перестановка фільтрів місцями не приводить до зміни результуючої множини слів, а отже, і рівень точності не змінюється, що і потрібно було довести. Тепер визначимо, при якому з трьох наведених варіантів розміщення contf у схемі визначення варіантів виправлення (6) – (8) і за яких умов буде досягатися найвища швидкодія орфокоректора. Розглянемо спочатку застосування семантичного фільтра в кінці процесу підбору варіантів виправлення та у його середині (6), (7) . Нехай 1iW – результат фільтрації множини dictW із використанням композиції функцій 1121 :...   idicti WWfff  (для 1i роль 1iW виконує безпосередньо dictW ). Для обох випадків, що аналізуються, вміст 1iW є однаковим, адже вихідна множина гіпотез і набір функцій, які до неї застосовуються, не відрізняються. Таким чином, для того, щоб швидкодія коректора, який реалізує послідовність фільтрів (7), була не нижчою за швидкість його роботи за схемою (6), має виконуватися нерівність: )() 1 ( )()( 11 mkkkk W m ik Wf m ik Wcontf contf i Wcontf tttt     , (9) де 1iWcont – результат фільтрації слів з 1iW за ознакою близькості за змістом до контекстного оточення спотвореного слова. Проаналізуємо, у якому випадку дана нерівність буде справедливою. contf за визначенням є фільтром, тому справедливим є твердження ,: 11   iicont WcontWf 11   ii WWcont . Отже, маємо: 1_1   ioutconti WWWcont , (10) де outcontW _ – частина множини 1iW , яка була виключена із подальшої обробки через невідповідність семантичному критерію фільтрації слів. Перевірка множин 1iW та 1iWcont за допомогою функцій, які входять до складу композицій (6) та (7) відповідно, проводиться, починаючи з фільтра if : – 1,1   iii f i WWWW i ; – 1,1   iii f i WcontWcontWcontWcont i . Інверсний контекстно-асоціативний метод автоматизованої орфокорекції «Штучний інтелект» 3’2008 83 2-З Виходячи з того, що 11   ii WWcont , можна стверджувати: згідно з (3), нерівність )()( 11   iiii WfWcontf tt є вірною. Відповідно до (2) та (10): 1 1 _ _ ( ) ( ) ( ) ( ) i i i i i cont out i i i cont out i i f W f Wcont f W W Wcont f W Wcont W           , . Застосування фільтра 1if характеризується аналогічним чином: ,1 1   i f i WW i ii WW 1 та iii f i WcontWcontWcontWcont i    1,1 1 . Звідки   )( )()()( _111_111 outcontiiiioutcontiiiiii WffWcontWWffWcontfWf  11   ii WWcont і т.д. У підсумку на основі властивості 3) (3) функції filter отримуємо 1 1( ) ( ).k k k k m m f Wcont f W k i k i t t        Тому для того, щоб перенесення семантичного фільтра ближче до початку послідовності FILTERS сприяло прискоренню роботи орфокоректора, у випадку, який розглядається, необхідно, щоб виконувалась умова 1( ) ( )i mW Wf fcont cont t t    (9) . Якщо аналогічним чином провести аналіз умов підвищення швидкодії програмних засобів орфокорекції для пар композицій функцій (6) – (8), (7) – (8), можна дійти висновку, що при перенесенні семантичного фільтра ближче до початку послідовності FILTERS коректор працюватиме швидше за умови виконання нерівностей )()( mdict WW contfcontf tt  та )()( 1  idict WW contfcontf tt відповідно. Таким чином, для того, щоб обрати варіант розміщення contf у схемі визначення варіантів виправлення, який забезпечує найвищу швидкодію орфокоректора, необхідно порівняти час виконання перевірки гіпотез на відповідність контексту за допомогою функції contf у кожному із згаданих випадків. mW є результатом послідовної фільтрації 1iW , яка в свою чергу отримується шляхом відбору слів з множини dictW ( dictim WWW  1 ). Тому, згідно з визначенням функції filter (3), виконання вищезгаданих нерівностей є неможливим, якщо не існує жодної відмінності у реалізації contf при зміні її місця у схемі орфокорекції. Отже, для визначення існування можливості підвищення швидкодії орфокоректора при переміщенні contf у послідовності фільтрів вмісту словника необхідно дослідити специфіку реалізації даної семантичної функції на різних етапах схеми орфокорекції. Оскільки послідовності фільтрів (6) та (7) є подібними (в першому випадку функції contf передує композиція з m фільтрів, а в другому – з і фільтрів), далі аналізувати будемо тільки два варіанти розміщення функції contf : прямий порядок фільтрації гіпотез (6) та інверсний (8). Будемо вважати, що:  час, потрібний для вибору із словника одного слова за будь-якою ознакою, є однаковим для усіх критеріїв відбору в межах задачі орфокорекції;  час, потрібний для перевірки слова на відповідність будь-якій ознаці, є однаковим для усіх простих формальних фільтрів;  будь-яка вибірка слів, підібраних за певним критерієм, зберігає репрезентативність відносно інших критеріїв фільтрації. Заболотня Т.М., Михайлюк А.Ю., Михайлюк О.С. «Искусственный интеллект» 3’2008 84 2-З Крім цього, мірою семантичної близькості двох слів вважатимемо довжину шляху між відповідними вершинами графа словника, а кількісне оцінювання семантичної близькості альтернативи виправлення до контекстного оточення спотвореного слова виконуватимемо на основі визначення величини, оберненої мінімальній з довжин найкоротших шляхів від заданого слова до контексту за структурою словника [11]. Для забезпечення орфокоректора даними про семантично-асоціативні зв’язки між словами природної мови будемо використовувати онтологічний словниковий ресурс у формі орієнтованого графу, вершинами якого є лексеми природної мови, поєднані лексико- семантичними відношеннями [9], [11]. З огляду на те, що із збільшенням дистанції між вершинами графа словника сила семантичного зв’язку між ними швидко зменшується [9], слова, відстань від яких до контексту перевищує певний поріг maxdist, будемо вважати нескінченно віддаленими від нього і не включатимемо їх до множини гіпотез. Це дасть змогу отримувати набір варіантів виправлення, котрі мають задану міру семантичної близькості до контексту, аналізуючи при цьому обмежену частину словникового ресурсу (оточення контекстних слів у радіусі maxdist). При цьому процедуру визначення слів, близьких за змістом до контексту, можна організувати таким чином, що для її успішного завершення достатньо обробити вершини графа словника у радіусі minR від контексту, де: )min(min RR  , де )}))((()maxdist(\|{   x i r i r i WxxrrR  (11а) або )})(()maxdist(\|{   i r i r iA xxFrrR , (11б) dictx WW  – результат попереднього відбору гіпотез, які потрібно перевірити на семантичну відповідність контексту; FА – абстрактна функція перевірки елементів заданої множини слів на відповідність іншим критеріям схожості із спотвореним словом; ix – слово контекстного оточення; r i r i xx уу , – відображення r-го ступеня вершини ix графа словника (пряме та зворотне). Твердження 2. Застосування семантичної функції contf під час висунення гіпотез виправлення забезпечує більш швидке отримання результату роботи орфокоректора, ніж її використання для остаточної перевірки множини гіпотез. Доведення. Будемо аналізувати вершини графа словника, які лежать у радіусі minR = maxdist від слів контексту (щоб розглянути випадок, коли необхідною є обробка максимально припустимої кількості слів, семантично пов’язаних з контекстом спотвореного слова). Введемо позначення:  \|context\| – кількість слів контексту, які містяться у словнику;  y – максимальна кількість лексико-семантичних зв’язків (дуг графа), які має одне слово dictWw з іншими лексемами словника; y має порядок, близький до порядку величини \|context\|. а) Інверсна послідовність фільтрів (8). Окіл контексту context із радіусом maxdist становить    t j jycontextA maxdis 1 \|\| слів [11]. Під час виконання )( dictcont Wf із словника відбирається А слів і передається для подальшої фільтрації без проведення додаткових перевірок. б) Пряма послідовність фільтрів (6). Для перевірки семантичної узгодженості гіпотез та контексту спотвореного слова функції contf передається dictmm WWW  , слів. Разом з цим для роботи фільтра )( mcont Wf у будь-якому випадку необхідно знати окіл контексту (у даному доведенні – це A слів), а отже, додатково потрібно отримати А слів із словника. Виконання AWm додаткових перевірок закінчує роботу даної послідовності фільтрів. Інверсний контекстно-асоціативний метод автоматизованої орфокорекції «Штучний інтелект» 3’2008 85 2-З Таким чином, інверсний порядок виконання фільтрації спричиняє виконання меншої кількості дій і, значить, забезпечує більш швидку роботу функції contf (тобто )()( mdict WW contfcontf tt  ). Вище показано, що за умови справедливості даної нерівності можна стверджувати, що час виконання композиції фільтрів (8) є меншим, ніж час виконання композиції (6), що і потрібно було довести. (Для випадків, коли minR < maxdist, справедливість зазначених нерівностей зберігається.) 4. Інверсний контекстно-асоціативний метод автоматизованого виправлення орфографічних помилок З огляду на викладені вище результати дослідження загальної схеми орфокорекції та особливостей її реалізації можна визначити інверсний контекстно- асоціативний метод автоматизованої орфокорекції. В основу методу пропонується покласти встановлення зворотного порядку фільтрації вмісту словника, оскільки доведено факт підвищення швидкості пошуку варіантів виправлення при збереженні точності роботи орфокоректора у разі перенесення семантичної складової схеми корекції на її початковий етап. Згідно з даним методом процедура контекстно-асоціативної автоматизованої орфокорекції являє собою послідовне виконання таких дій: 1) встановлення радіуса пошуку r рівним мінімально припустимому значенню; 2) висунення гіпотез виправлення за ознакою семантичної близькості до контекстного оточення спотвореного слова; 3) перевірка гіпотез виправлення на подібність до спотвореного слова за формальними ознаками; 4) збільшення радіуса пошуку гіпотез виправлення та перехід до п. 2 даного методу у випадку, якщо, по-перше, r < maxdist, а по-друге, якщо на заданій відстані r від вершин графа словника, котрі відповідають словам контексту, не знайдено жодного слова, яке задовольнило б усім критеріям схожості зі спотвореним словом; в іншому разі – закінчення пошуку варіантів виправлення. Важливою особливістю методу є його ітераційний характер. Він дозволяє зменшити кількість дій щодо обробки слів під час орфокорекції і тим самим підвищити швидкість її виконання. 5. Дослідження ефективності інверсного контекстно-асоціативного методу орфокорекції Для експериментальної апробації запропонованого методу орфокорекції, а також для перевірки справедливості теоретичних тверджень, які доводяться у статті, використано масив словосполучень, які характеризуються різною потужністю множин слів, які складають контекст спотвореного слова; різною кількістю помилок, припущених у слові (1 та 2 помилки); різною силою семантичного зв’язку контексту із спотвореним словом. Для підтвердження досягнення найкращих показників роботи коректора за умови застосування фільтрів до вмісту лексико-семантичного словника в інверсному порядку проаналізовано результати функціонування відповідного програмного забезпечення у випадках, коли алгоритмом його роботи передбачено: 1) використання семантичної функції contf на початку та наприкінці послідовності фільтрів (прямий та інверсний порядок фільтрації); Заболотня Т.М., Михайлюк А.Ю., Михайлюк О.С. «Искусственный интеллект» 3’2008 86 2-З 2) проведення спроб виправлення одно- та двократних помилок; 3) встановлення радіуса околу контекстного оточення спотвореного слова за структурою графа словника рівним від 1 до 5 переходів (maxdist = 1...5). Крім того, показники роботи орфокоректора порівнюються із аналогічними показниками відповідного модуля, вбудованого до пакета MS Word, функціональність якого сьогодні найчастіше використовується для обробки текстів. 60% 70% 80% 90% 100% 110% 120% 1 2 3 4 5 максимальний радіус околу контексту (maxdist) ві дн ос ни й ча с ро бо ти fc on t ( % ) прямий порядок, 1 помилка інверсний порядок, 1 помилка прямий порядок, 2 помилки інверсний порядок, 2 помилки а 0% 20% 40% 60% 80% 100% 120% 1 2 3 4 5 максимальний радіус околу контексту (maxdist) ві дн ос ни й ча с ро бо ти к ор ек то ра (% ) прямий порядок, 1 помилка інверсний порядок, 1 помилка прямий порядок, 2 помилки інверсний порядок, 2 помилки б Рисунок 1 – Графік залежності відносного часу роботи семантичної функції (а) та орфокоректора взагалі (б) від особливостей реалізації алгоритму орфокорекції Різноманітність даних, які надходять на вхід орфокоректора, робить неможливим отримання узагальненої оцінки часу корекції в секундах (чи інших одиницях виміру часу). Тому результати вимірювань часових значень наводяться відносно відповідних показників роботи коректора, коли він виконує виправлення однократних помилок із застосуванням фільтрів вмісту словника в прямому порядку. Як бачимо на рис. 1а, проведення фільтрації вмісту словникового ресурсу в інверсному порядку приводить до покращення часових характеристик роботи функції contf (порівняно із застосуванням contf в кінці фільтрації) незалежно від радіуса пошуку варіантів виправлення у графі словника. При застосуванні фільтрів у прямому порядку час виконання contf при виправ- ленні двократних помилок є більшим, ніж час її роботи при корекції слів з одинар- ними помилками; при застосуванні фільтрів в інверсному порядку дані часові показники практично збігаються. На рис. 1 не подано характеристики роботи MS Word, оскільки час його роботи можна порівнювати з часом роботи розробленого орфокоректора тільки за умови аналізу околу контексту з радіусом R = maxdist. У разі maxdis t<= 4 швидкість роботи MS Word значно (до 3 разів) поступається швидкодії нового орфокоректора. Отже, умова )()( mdict WW contfcontf tt  (п. 3) виконана, і загальний час проведення орфокорекції повинен бути меншим при застосуванні фільтрів до вмісту слов- никового ресурсу в інверсному порядку, що і підтверджується рис. 1б. Практичні дослідження підтвердили справедливість теоретично прийнятої комутативності композиції функцій filter. Разом з тим, очевидною є перевага розроблених програмних засобів орфокорекції за критерієм точності над модулем Інверсний контекстно-асоціативний метод автоматизованої орфокорекції «Штучний інтелект» 3’2008 87 2-З виправлення помилок MS Word (рис. 2). Найімовірнішою причиною таких результатів є припущення про те, що останній не реалізує перевірки варіантів виправлення на семантичну узгодженість з контекстом спотвореного слова [2]. 25% 35% 45% 55% 65% 75% 85% 1 2 3 4 5 максимальний радіус околу контексту (maxdist) то чн іс ть о рф ок ор ек ці ї ( % ) Виправлення 1 помилки Виправлення 2 помилок MS Word Рисунок 2 – Графік залежності точності роботи програмних засобів від реалізації алгоритму орфокорекції Факт, що розроблене ПЗ, яке реалізує запропонований метод автоматизованої орфокорекції, не характеризується 100 % точністю роботи, пояснюється тим, що, з одного боку, при виправленні однократних помилок слова, які мають двократні помилки, залишаються невиправленими, а з іншого боку, спроба виправлення двократних помилок спричиняє додавання до результатів зайвих слів у випадку корекції слів, які мають однократну помилку. Можна відмітити ще одну важливу закономірність: точність виправлення помилок перестає зростати при maxdist > 4. Отже, з точки зору досягнення найвищої точності роботи орфокоректора збільшувати далі радіус пошуку гіпотез недоцільно. Перспективним напрямком подальшого вивчення питання побудови орфо- коректорів на основі контекстно-асоціативних методів визначення варіантів виправлення є введення ранжування семантичних відношень лексико-семантич- ного словникового ресурсу за певними критеріями та врахування ваги відповідних дуг графа під час вибору його наступних вершин для аналізу. Висновки Доведено факт збереження точності, визначено умови покращення часових характеристик роботи коректора при перенесенні семантичного фільтра гіпотез на початок послідовності функцій підбору варіантів виправлення. Показано, що найкращі показники щодо швидкості роботи ПЗ забезпечує перенесення контекстно- асоціативної обробки текстових даних на етап висунення гіпотез. Запропоновано інверсний контекстно-асоціативний метод виправлення орфографічних помилок шляхом ітеративного чергування процедур відбору гіпотез із словника за ознакою семантичної близькості до контексту та наступної їх пере- вірки на відповідність формальним критеріям подібності до спотвореного слова, такий, що забезпечує підвищення швидкості та точності роботи орфокоректора за рахунок зменшення потужності множини слів, які при цьому обробляються. Заболотня Т.М., Михайлюк А.Ю., Михайлюк О.С. «Искусственный интеллект» 3’2008 88 2-З Запропоновано трактування точності корекції як відношення числа вибраних програмою вірних варіантів написання слова до загальної кількості отриманих варіантів, що дозволяє оцінювати точність виправлення помилок у випадку підбору гіпотез з великого за обсягом словника, а також фіксувати зміни у загальній кіль- кості варіантів виправлення, запропонованих програмою. Дослідження на практиці ефективності запропонованого методу орфокорекції підтвердило теоретичні положення, викладені у статті, та дозволило визначити рекомендовані значення параметрів алгоритму виправлення помилок, встановлення яких забезпечує ефективну роботу програмного орфокоректора. Література 1. Kukich K. Techniques for Automatically Correcting Words in Text // ACM Computing Surveys. – 1992. – Vol. 24, № 4. – P. 377-439. 2. Лавошникова Э.К. О компьютерной коррекции «популярных» ошибок в текстах на русском языке // НТИ, сер. 2. – 2003. – № 9. – С. 28-34. 3. Михайлюк А.Ю., Заболотня Т.М. Комбінований метод виправлення орфографічних помилок у текстових даних // Вісник Хмельницького національного університету. – 2007. – № 2, Т. 2. – С. 21-26. 4. Kashyap R.L., Oommen B.J. Spelling correction using probabilistic methods // Pattern Recognit.Lett. – 1984. – Vol. 2, № 3. – P. 147-154. 5. Schaback J., Li F. Multi-Level Feature Extraction for Spelling Correction In Proc.of the IJCAI-2007 // Workshop on Analytics for Noisy Unstructured Text Data. – Hyderabad, India, 8 January 2007. – P. 79-86. 6. Пещак М.М. Нариси з комп’ютерної лінгвістики. – Ужгород: Закарпаття, 1999. – 199 с. 7. Trushkina Yu. Context-based Ranking of Suggestion for Spelling Correction // In Proc. of the RANLP 2005. – Borovetz, Bulgaria, 21 – 23 September 2005. 8. Andrew R. Golding A. Bayesian Hybrid Method for Context-Sensitive Spelling Correction // In Proceedings of the ACL Third Workshop on Very Large Corpora. – June 1995. – P. 39-53. 9. Марченко О.О. Алгоритми семантичного аналізу природномовних текстів: Дис. канд. фіз.-мат. наук: 01.05.01 / КНУ ім. Тараса Шевченка. – К., 2005. 10. Файн В.С., Рубанов Л.И. Машинное понимание текстов с ошибками. – М.: Наука, 1991. – 151 с. 11. Заболотня Т.М. Оптимізація процесу контекстноорієнтованої орфокорекції шляхом спрощення обчис- лення міри семантичної близькості слів // Проблеми інформатизації та управління: Зб. наук. праць. Випуск 3 (21). – К.: НАУ, 2007. – С. 55-59. Т.Н. Заболотняя, А.Ю. Михайлюк, Е.С. Михайлюк Инверсионный контекстно-ассоциативный метод автоматической орфокоррекции Теоретически обусловлен и предложен инверсионный контекстно-ассоциативный метод автоматического исправления орфографических ошибок, который обеспечивает повышение скорости и точности работы соответствующего программного обеспечения. Дано определение показателя результативности функционирования орфокорректора – точности его работы. Показана эффективность использования предлагаемого метода для исправления орфографических ошибок в массиве гетерогенных словосочетаний по критериям скорости и точности коррекции. Стаття надійшла до редакції 09.07.2008

Інверсний контекстно-асоціативний метод автоматизованої орфокорекції

Репозитарії

Схожі ресурси