Інверсний контекстно-асоціативний метод та програмні засоби автоматизованої орфокорекції природномовних текстових об’єктів

Размещено на http://www.allbest.ru/

Національний технічний університет України

«Київський політехнічний інститут»

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

кандидата технічних наук

Інверсний контекстно-асоціативний метод та програмні засоби автоматизованої орфокорекції природномовних текстових об'єктів

Заболотня Тетяна Миколаївна

Київ - 2008

Анотація

Заболотня Т.М. Інверсний контекстно-асоціативний метод та програмні засоби автоматизованої орфокорекції природномовних текстових об'єктів. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 - комп'ютерні системи та компоненти. - Національний технічний університет України «КПІ», Київ, 2008.

Дисертаційна робота присвячена розробці контекстно-асоціативних методів та програмних засобів орфокорекції, реалізація яких забезпечує підвищення швидкості та точності виправлення орфографічних помилок комп'ютерними системами автоматичної обробки текстів (АОТ).

Запропоновано інверсний контекстно-асоціативний метод автоматизованого виправлення орфографічних помилок шляхом ітеративного чергування процедур відбору гіпотез із лексико-семантичного словника за ознакою близькості за змістом до контексту та наступної їх перевірки на відповідність формальним критеріям схожості на спотворене слово. Застосування даного методу дозволяє підвищити ефективність відповідних програмних засобів за рахунок зменшення кількості операцій щодо обробки наборів гіпотез у ході орфокорекції.

Подано спосіб структурно-алгоритмічної організації орфокоректора у формі спеціалізованого реактивного програмного агента, який забезпечує його взаємодію з модулями відкритих систем АОТ.

Експериментально досліджено ефективність запропонованого методу орфокорекції та його програмної реалізації згідно з агентним підходом до побудови ПЗ за умови їх використання в інформаційно-пошуковій системі Єдиного інформаційного середовища НТУУ «КПІ». Отримані результати підтвердили теоретичні положення дисертації та дозволили визначити рекомендовані значення параметрів алгоритмів виправлення помилок, встановлення яких забезпечує ефективну роботу розробленого орфокоректора.

Ключові слова: автоматична обробка текстів, автоматизоване виправлення орфографічних помилок, контекстно-асоціативні методи орфокорекції, лексико-семантичні словникові ресурси, програмні агенти.

Аннотация

Заболотняя Т.Н. Инверсный контекстно-ассоциативный метод и программные средства автоматизированной орфокоррекции естественно-языковых текстовых объектов. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - компьютерные системы и компоненты. - Национальный технический университет Украины «КПИ», Киев, 2008.

Диссертационная работа посвящена разработке контекстно-ассоциативных методов и программных средств орфокоррекции, реализация которых позволяет повысить скорость и точность исправления орфографических ошибок компьютерными системами автоматической обработки текстов (АОТ).

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

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

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

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

Представленный в диссертации способ структурно-алгоритмической организации орфокорректора в форме специализированного реактивного программного агента обеспечивает его интегрируемость в существующие открытые системы АОТ и оперативное взаимодействие с их модулями.

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

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

Экспериментально исследована эффективность предложенного метода орфокоррекции и его программной реализации в соответствии с агентным подходом к построению программного обеспечения при их использовании в информационно-поисковой системе Единого информационного пространства НТУУ «КПИ».

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

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

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

Abstract

Zabolotnia T. The inverse context-associative method and software of automatized spelling correction of natural language objects. - Manuscript.

The thesis for the candidate's degree by the speciality 05.13.05 - computer systems and components. - National technical university of Ukraine “KPI”, Kyiv, 2008.

This thesis work is devoted to the development of context-associative methods and software of spelling correction, implementation of which provides the increase of speed and precision of spelling errors correction by computer systems of automatic texts processing (ATP).

The inversion context-associative method of computer assisted correction of spellings errors is offered by means of iterative interleaving of procedures of hypotheses selection from a lexico-semantic dictionary on grounds of the content closeness to the context and their following check as for the correspondence to the formal criteria of similarity to the distorted word. Application of this method allows to promote efficiency of the corresponding software due to diminution of amount of operations in relation to the processing of the sets of hypotheses while the spelling correction.

The way of structural-algorithmic organization of spelling corrector in the form of specialized reactive software agent is given. It provides corrector's interaction with the program modules of ATP open systems.

The efficiency of the offered method of spelling correction and its software implementation according to the agent approach to the software development were studied experimentally on condition of their use in information retrieval system of Single information space of NTUU “KPI”. The got results confirmed theoretical positions of thesis work and allow to define the recommended option settings of algorithms of the errors correction, establishment of which provides effective work of the developed spelling corrector.

Key words: automatic texts processing, computer assisted correction of spellings errors, context-associative methods of spelling correction, lexico-semantic dictionaries, software agents.

1. Загальна характеристика роботи

Актуальність теми. На сучасному етапі розвитку суспільства, в умовах зростання потреби у підвищенні рівня інтелектуалізації інформаційних технологій великого значення набула проблема забезпечення ефективної комп'ютеризованої обробки природномовних об'єктів. З огляду на постійне збільшення обсягу електронної документації, вирішення вказаної проблеми неможливе без підвищення продуктивності програмних систем автоматичної обробки текстів (далі систем АОТ, або САОТ). Результативність таких систем значною мірою визначається ефективністю роботи та способом взаємодії окремих їх складових.

Слід зазначити, що сьогодні, зважаючи на стрімке нарощування обчислювальних потужностей комп'ютерів, основний критерій оцінки ефективності програмного забезпечення (ПЗ) АОТ змінився з економності щодо залучення апаратних ресурсів на точність та швидкість обробки текстових даних. Тому вирішення задачі побудови програмних засобів АОТ з урахуванням нової критеріальної характеристики оцінки їх ефективності набуло особливої значущості.

Важливою задачею систем АОТ різного призначення є перевірка орфографії (виявлення та виправлення помилок) в текстових даних. У сучасних системах автоматизованої перевірки орфографії задача виявлення помилок, як більш детермінована та досліджувана триваліший час, розв'язана у більшій мірі, ніж задача корекції спотворених слів, котра потребує визначення словоформи, яку автор тексту насправді мав на увазі. Тому актуальним є дослідження програмного забезпечення орфокорекції саме з точки зору виправлення помилок. Далі вважатимемо, що інформація про спотворене слово та його контекст надходить до орфокоректора від інших програмних засобів.

Сучасні програмні орфокоректори характеризуються невисоким рівнем автоматизації, орієнтацією на виправлення однократних помилок, відсутністю забезпечення семантичної узгодженості варіантів виправлення та контексту спотвореного слова. Ці недоліки зумовлюють низьку ефективність роботи коректорів та спричиняють необхідність залучення користувача до процесу визначення вірних варіантів написання слова з помилкою.

Дослідження останніх вітчизняних та зарубіжних робіт у галузі автоматичної обробки природномовних текстів показало, що усунення визначених вище вад потребує модифікації існуючих алгоритмів виправлення помилок у напрямку залучення контекстної інформації та лексико-семантичних словникових ресурсів для її обробки. Проведення аналізу асоціативних зв'язків між словами уможливлює коректне звуження множини гіпотез, які мають бути оброблені під час визначення варіантів виправлення, що позитивно впливатиме на ефективність функціонування систем АОТ в цілому. Але на даний момент в існуючих програмних засобах орфокорекції методика врахування контексту спотвореного слова за допомогою семантичного інструментарію є недостатньо розробленою, а отже, дослідження даного питання видається актуальним.

З точки зору організації взаємодії орфокоректора з іншим програмним забезпеченням у межах систем АОТ перший найчастіше розробляють як жорстко вбудований до таких систем модуль або як автономну програму, до котрої при необхідності звертається сам користувач. Обидва наведені способи організації коректора не передбачають можливості його підключення як окремо розробленої утиліти до відкритих програмних комплексів, а також зумовлюють необхідність побудови великої кількості модифікацій подібних модулів. У такій ситуації актуальним є визначення способу побудови орфокоректорів, який би дозволив підключати їх до вже існуючих систем та гнучко налаштовувати на роботу із різними типами модулів.

Теоретичною основою дослідження був науковий доробок вчених у галузі побудови систем обробки текстів, математичного моделювання природної мови, програмного виправлення помилок у природномовних текстових даних Г.Г. Бєлоногова, М.Ф. Бондаренка, О.Ф. Гельбуха, Н.П. Дарчук, В.І. Левенштейна, Н.М. Леонтьєвої, Е.Ф. Скороходька, В.С. Файна, Ю.П. Шабанова-Кушнаренка, В.А. Широкова, K. Kukich, A. Zamora та ін., а також у галузі створення інтегрованих інформаційних систем та підходів до побудови інтелектуальних систем, зокрема на основі технології програмних агентів, яку досліджували Т.А. Гаврилова, В.І. Городецький, О.Г. Додонов, Д.О. Поспєлов, Ю.В. Рогушина, В.Б. Тарасов, В.Ф. Хорошевський, N.R. Jennings, M. Wooldridge та ін.

Таким чином, дисертаційна робота, спрямована на розв'язання задачі розробки контекстно-асоціативних методів виправлення орфографічних помилок та способів структурно-алгоритмічної організації програмних засобів, які реалізують ці методи, здатні функціонувати у межах систем АОТ та забезпечують підвищення ефективності роботи цих систем в цілому, є актуальною.

Зв'язок роботи з науковими програмами, планами, темами. Дана дисертаційна робота виконувалась відповідно до планів науково-дослідних робіт Міністерства освіти і науки України та Національного технічного університету України «КПІ» в межах держбюджетних тем:

- № 2601 «Структурно-алгоритмічна організація інструментальних комп'ютерних засобів комплексної підтримки системних освітніх технологій» (державний реєстраційний номер 0103U000396);

- № 2604 «Методи та засоби підвищення інформаційної стійкості локальних освітніх комп'ютерних технологій та мереж» (державний реєстраційний номер 0103U000397);

- № 2704 «Інтелектуальні комп'ютерні інструментальні засоби для підтримки оптимізованого управління інформаційними процесами в сучасних комплексних інтенсивних технологіях» (державний реєстраційний номер 0104U000521).

Мета і завдання дослідження. Метою дослідження є підвищення ефективності виправлення орфографічних помилок комп'ютерними системами автоматизованої обробки природномовних текстів за рахунок розробки та реалізації контекстно-асоціативних методів та програмних засобів корекції спотворених слів.

Відповідно до вказаної мети в роботі поставлені і розв'язані такі задачі:

- аналіз існуючих методів та засобів автоматизованого виправлення орфографічних помилок в природномовних текстових даних;

- дослідження способів реалізації етапів процедури орфокорекції на предмет виявлення можливостей щодо підвищення її ефективності;

- розробка контекстно-асоціативних методів орфокорекції для підвищення ефективності роботи відповідного програмного забезпечення за показниками точності та швидкості виправлення помилок;

- розробка способу автоматизованої модифікації словникового ресурсу програмного орфокоректора для підвищення ефективності обробки предметноорієнтованих природномовних текстів;

- розробка способу структурно-алгоритмічної організації програмних орфокоректорів, спрямованого на забезпечення їх інтегрованості до відкритих систем АОТ;

- експериментальне дослідження ефективності запропонованих контекстно-асоціативних методів орфокорекції.

Об'єктом дослідження є процес автоматизованої обробки природномовних текстових даних.

Предметом дослідження є контекстно-асоціативні методи та програмні засоби автоматизованого виправлення орфографічних помилок в природномовних текстових даних.

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

Наукова новизна одержаних результатів. В роботі містяться нові наукові знання про методологію автоматизованого виправлення орфографічних помилок у природномовних текстових інформаційних об'єктах та про організацію відповідного програмного забезпечення, які у своїй сукупності забезпечують розв'язання поставлених задач і досягнення мети роботи. Конкретні наукові результати полягають у наступному:

1. Набув подальшого розвитку контекстноорієнтований підхід до автоматизованого визначення правильного варіанту виправлення. Формування множини гіпотез щодо корекції спотвореного слова виконується на основі врахування їх семантичних зв'язків з контекстом.

2. Вперше запропоновано метод організації процедури автоматизованої орфокорекції, який полягає у формуванні множини гіпотез виправлення за ознакою максимальної семантичної близькості до контексту та подальшій їх перевірці на подібність до спотвореного слова за формальними критеріями. Це дозволяє підвищити швидкість та точність орфокорекції відповідними програмними засобами за рахунок зменшення потужності множини слів, які при цьому обробляються.

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

4. Розроблено новий спосіб кількісного оцінювання семантичної близькості альтернативи виправлення до контекстного оточення спотвореного слова шляхом обчислення величини, оберненої мінімальній з довжин найкоротших шляхів від даної альтернативи до елементів контексту за структурою графу лексико-семантичного словника. Показано, що, на відміну від існуючих, запропонований спосіб дозволяє зменшити кількість слів, що підлягають обробці у ході орфокорекції, і завдяки цьому підвищити її швидкість.

5. Дано визначення точності машинної орфокорекції спотвореного слова через співвідношення кількості правильних варіантів виправлення та загальної кількості альтернатив, запропонованих коректором. Це дозволяє об'єктивізувати оцінку ефективності програмних орфокоректорів за рахунок локалізації осередку помилки в тексті.

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

Визначений у дослідженні характер впливу параметрів системи АОТ на вибір способу структурно-алгоритмічної організації орфокоректора може бути врахований при розробці програмних засобів виправлення орфографічних помилок із застосуванням технології програмних агентів.

Результати роботи, пов'язані із створенням програмного забезпечення обробки природномовних текстових даних, використовуються на кафедрі спеціалізованих комп'ютерних систем НТУУ «КПІ» при викладанні навчальних дисциплін «Організація баз даних», «Комп'ютерні системи штучного інтелекту», «Програмне забезпечення спеціалізованих комп'ютерних систем», а також у ПЗ електронної бібліотеки учбових матеріалів та інформаційно-пошукової системи для єдиного інформаційного середовища НТУУ «КПІ» (КБ інформаційних систем НТУУ «КПІ»).

Особистий внесок здобувача. Всі основні результати дисертаційної роботи отримані автором самостійно. У публікаціях, написаних у співавторстві, здобувачу належать: [1] - алгоритм обчислення арифметичних значень блоком логічного виведення експертної системи; [2] - структурна організація програмних адаптерів для забезпечення інтеграції гетерогенного ПЗ, а також загальні шаблони їх поведінки; [3] - змістовна суть комбінованого методу виправлення орфографічних помилок; [6] - спосіб структурно-алгоритмічної організації орфокоректора з врахуванням характеристик САОТ як його зовнішнього середовища; [7] - рекомендовані характеристики системи управління інформаційними процесами; [8] - пропозиція щодо застосування методу експертних оцінок для оперативного моніторингу показника ефективності роботи системи управління; [9] - алгоритм попереднього аналізу даних, що надходять до підсистеми прогнозування інформаційно-аналітичного комплексу; [10] - алгоритми обробки основного змісту електронних документів; [12] - алгоритм формування вмісту спеціалізованого словника на основі ресурсу WordNet; [13] - постановочна частина роботи, а також структурна організація програмного агента, здатного до утворення цілей.

Апробація результатів дисертації. Основні положення і результати дисертаційної роботи доповідалися та обговорювалися на І міжнародній конференції ACSN «Сучасні комп'ютерні системи та мережі: розробка та використання» (м.Львів, 2003р.), міжнародній науково-практичній конференції “Мікропроцесорні пристрої та системи в автоматизації виробничих процесів” (м.Хмельницький, 2003р.), міжнародній практичній конференції «Сучасні проблеми і досягнення в галузі радіотехніки, телекомунікацій та інформаційних технологій» (м.Запоріжжя, 2006р.), ХІ міжнародному молодіжному форумі "Радиоэлектроника и молодежь в ХХІ веке" (м.Харків, 2007р.), VIII міжнародній науково-практичній конференції «Современные информационные и электронные технологии» (м. Одеса, 2007р.), V міжнародній науково-практичній конференції «Комп'ютерні системи в автоматизації виробничих процесів» (м. Хмельницький, 2007р.), І міжнародній науково-практичній конференції «Методи та засоби кодування, захисту й ущільнення інформації» (м. Вінниця, 2007р.), науково-технічних семінарах кафедри спеціалізованих комп'ютерних систем НТУУ «КПІ»(2003 - 2008 рр.)

Публікації. За матеріалами дисертації опубліковано 13 друкованих робіт, з них 6 у фахових виданнях, які входять до переліку ВАК України, 1 стаття, а також 6 тез доповідей на науково-практичних конференціях.

Структура дисертації. Дисертація складається зі вступу, чотирьох розділів, висновків до кожного розділу, загальних висновків, списку використаних джерел (104 найменування, з них 42 іноземною мовою), 5 додатків. Робота містить 27 рисунків та 1 таблицю. Загальний обсяг дисертації - 169 друкованих сторінок, з них 147 сторінок основного тексту та 9 сторінок списку використаних джерел.

2. Основний зміст

У вступі обґрунтовано актуальність теми дисертації, сформульовано мету та задачі дослідження, розкрито наукову новизну і практичну значимість отриманих результатів, охарактеризовано методи дослідження, наведено відомості про зв'язок дисертації з плановими науково-дослідними роботами, апробацію і впровадження результатів роботи, публікації і особистий внесок автора.

У першому розділі проаналізований стан досліджень проблеми автоматизованого виправлення орфографічних помилок у природномовних текстових даних: визначені загальні тенденції у галузі побудови систем АОТ, а також розглянуті існуючі методи та програмні засоби автоматизованої орфокорекції.

У результаті аналізу встановлено, що хоча розробка програмного забезпечення виправлення орфографічних помилок є окремим широко досліджуваним напрямом у галузі створення систем АОТ, визначення способів організації орфокоректорів здебільшого базується на врахуванні загальних характеристик сучасного етапу розвитку систем АОТ, адже на сьогоднішній день коректори є невід'ємною складовою більшості згаданих систем.

У дослідженні визначено такі тенденції, які переважають зараз у галузі побудови систем АОТ:

1. Сучасні системи АОТ широко використовують ресурси та методи синтаксичного та семантичного аналізу (для автоматичного анотування, реферування, машинного перекладу тощо).

2. Для забезпечення можливості врахування значення слів системами АОТ у більшості випадків розробники віддають перевагу аналізу контексту, а не семантики граматичної структури окремих слів.

3. Загальноприйнятою схемою аналізу тексту залишається так звана послідовна схема (морфологічний, синтаксичний, семантичний рівні аналізу), коли результати кожного попереднього етапу є вихідною інформацією для наступних.

4. З огляду на постійне зростання обсягів пам'яті та швидкодії сучасних комп'ютерів основними вимогами до систем АОТ сьогодні є точність та швидкість їх роботи (а не економність щодо залучення апаратних ресурсів). Це сприяє більш широкому використанню словникового підходу до аналізу даних, який забезпечує отримання високоточних результатів обробки текстів.

Вищенаведені тенденції обумовили вибір шляхів вирішення задач дисертаційного дослідження щодо розробки методів та програмних засобів автоматизованого виправлення орфографічних помилок.

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

- спрямованість коректорів на обробку однократних помилок;

- низький рівень автоматизації процесу орфокорекції;

- нездатність виправляти помилки, які перетворюють вірно написане слово на спотворене, котре міститься у словнику.

Наявність зазначених недоліків викликана використанням контекстнонезалежних методів орфокорекції, які характеризуються відсутністю врахування асоціативних зв'язків спотвореного слова з його контекстним оточенням у процесі визначення варіантів виправлення.

З огляду на це, з метою підвищення ефективності програмних коректорів запропоновано основну увагу в дослідженні приділити розробці та реалізації контекстно-асоціативних методів автоматизованого виправлення помилок. Використання цих методів є єдиним можливим шляхом знаходження варіантів виправлення слів, які помилки перетворили на інші слова, котрі містяться у словнику. Разом з тим, контекстно-асоціативні методи можна використовувати і для обробки словоформ, які помилки перетворили на некоректні для даної мови слова.

У першому розділі також визначено, що на сьогоднішній день у системах АОТ спостерігається певне віддалення від класичного порядку аналізу текстів (морфологічний, синтаксичний, семантичний рівні аналізу), яке зумовлене тим, що етапи аналізу природномовного тексту не є функціонально ізольованими, хоч і виконуються зазвичай послідовно. Згідно з цим, морфологічний аналіз може не лише надавати вихідні дані для синтаксичного та семантичного аналізу, але і використовувати результати останніх. Досі обробка контексту спотвореного слова семантичним інструментарієм мала місце тільки на кінцевому етапі процесу виправлення орфографічних помилок. З врахуванням вищезазначеного у дисертації пропонується дослідити способи реалізації етапів процесу орфокорекції з метою визначення умов підвищення швидкості та точності обробки даних.

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

В межах словникового підходу, обраного для застосування у дисертаційному дослідженні, важливим чинником розв'язання даної задачі є визначення словника, аналіз вмісту якого служить основою для вибору варіантів виправлення спотвореного слова.

Оскільки контекстно-асоціативними методами обробки текстів передбачається звертання до лінгвістичних ресурсів, котрі містять дані про семантичні зв'язки між словами природної мови, у дисертації запропоновано використання у процесі орфокорекції програмного словника, на логічному рівні організованого у формі орієнтованого графу G = (W_dict, E), вершинами якого є лексеми природної мови W_dict, поєднані лексико-семантичними відношеннями з множини Е, як такого, що реалізує найпоширеніший ресурс для обробки змісту природномовних текстових даних - онтологію.

Показано, що під час виправлення орфографічних помилок з урахуванням семантико-асоціативних зв'язків між словами природної мови для кількісного оцінювання близькості за змістом двох слів доцільно використовувати довжину шляху між відповідними вершинами графу G.

Для визначення ж ступеня семантичної близькості альтернативи виправлення до контекстного оточення спотвореного слова запропонований новий спосіб обчислення даної величини, ефективність застосування якого у роботі порівнюється з результативністю способу, котрий використовується у практиці синтактико-семантичного аналізу текстів.

Відповідно до існуючого способу міра семантичної близькості варіанту виправлення до контексту спотвореного слова обчислюється як обернена величина сумарної довжини найкоротших шляхів від даного слова до усіх слів контекстного оточення за структурою лексико-семантичного ресурсу (далі Міра1). Такий спосіб визначення Міри1 використовується в межах підходу до встановлення наявності зв'язку між словом та контекстом шляхом перевірки близькості заданого слова та кожного елементу обраної множини контекстних слів. Характерною рисою даного способу є необхідність обробки всіх вершин графу G, відстань від яких до вершин, пов'язаних із словами контексту, не перевищує значення певного припустимого порогу maxdist.

Новим способом, запропонованим у дисертації, передбачено обчислення міри близькості альтернативи до контексту як величини, оберненої до мінімальної з довжин найкоротших шляхів від гіпотези до елементів контексту (далі Міра2). Спосіб розроблено на основі іншого підходу до визначення зв'язку слова та контексту, який полягає в такому: вважається, що слово відповідає змісту свого оточення тоді, коли воно має семантичний зв'язок принаймні з одним значущим елементом контексту (не власним іменем, не словом зі «стоп-списку» тощо). Отже, процес перевірки відповідності заданої гіпотези та певного набору слів, які складають контекст спотвореного слова, може бути закінчений після знаходження першої пари семантично пов'язаних слів. Таким чином, використання запропонованого способу дозволяє перевіряти під час орфокорекції тільки вершини, які лежать в радіусі R_min від вершин слів контексту, де ,

або

де - результат попереднього відбору гіпотез, які потрібно перевірити на семантичну відповідність контексту;

F_А - абстрактна функція перевірки елементів заданої множини слів на відповідність формальним критеріям схожості із спотвореним словом;

x_i - слово контекстного оточення;

- відображення r-го ступеня вершини графу (пряме та зворотне).

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

У межах вирішення задачі визначення способів реалізації етапів процедури орфокорекції, що забезпечують підвищення ефективності останньої, у дисертаційній роботі запропоновано внести уточнення в подання схеми орфокорекції: вважати процес визначення варіантів виправлення таким, що складається із застосування композиції функцій фільтрації FILTERS до множини слів, які містяться у словнику.

,

де f_i: W_i-1 > W_i (і =2,…, m) - фільтр множини слів, отриманої у результаті виконання f_i-1 (для f₁ - множини W_dict). f_i може служити як для відбору з певної множини слів гіпотез за формальними ознаками схожості на спотворене слово, так і для вибору альтернатив виправлення, узгоджених за змістом з контекстним оточенням спотвореного слова. В останньому випадку f_i позначено як f_cont.

Визначення 1. Функція filter називається фільтром множини W_x, якщо за її допомогою з елементів W_x проводиться формування множини слів W_y, які відповідають певному критерію схожості зі спотвореним словом (W_x, W_y - множини природномовних слів).

,

Виходячи з фізичного змісту функції filter, її властивостями є:

1) аддитивність: ;

2) комутативність композиції фільтрів: при застосуванні композиції функцій до множини слів W_x від перестановки складових filter_i місцями результат W_y не змінюється;

3) якщо , то час, необхідний для виконання фільтрації цих множин, характеризується нерівністю , де - час фільтрації множин W_A та W_B.

На основі результатів проведеного аналізу впливу позиції семантичного фільтру f_cont у схемі орфокорекції на ефективність виправлення помилок:

- доведено факт збереження точності роботи коректора при зміні місця f_cont у композиції функцій FILTERS;

- виявлено, що для підвищення швидкості роботи коректора при перенесенні f_cont на етап висунення гіпотез, необхідним є виконання нерівності ;

- встановлено, що при використанні Міри1 та Міри2 семантичної близькості альтернатив виправлення до контексту в процесі орфокорекції вищезгадана нерівність є справедливою, а отже, найкращі показники щодо швидкості роботи орфокоректора забезпечує проведення контекстно-асоціативної обробки текстових даних на етапі висунення гіпотез;

- показано доцільність покладення в основу функції f_cont обчислення Міри2 семантичної відповідності альтернативи виправлення до контексту слова з помилкою.

Виходячи з вищенаведених положень, запропоновано інверсний контекстно-асоціативний метод виправлення орфографічних помилок, згідно якого процедура автоматизованої орфокорекції передбачає послідовне виконання таких дій:

1) встановлення радіусу пошуку r рівним мінімально припустимому значенню (наприклад, r=1);

2) висунення гіпотез виправлення за ознакою семантичної близькості до контекстного оточення спотвореного слова (тобто за ознакою їх приналежності околу контексту радіуса r);

3) перевірка гіпотез виправлення на подібність до спотвореного слова за формальними ознаками;

4) збільшення радіусу пошуку гіпотез виправлення та перехід до п.2 даного методу у випадку, якщо, по-перше, r<maxdist, а по-друге, якщо на заданій відстані r від вершин графу G, котрі відповідають словам контексту, не знайдено жодного слова, яке задовольнило б усім критеріям схожості зі спотвореним словом; в іншому разі - закінчення пошуку варіантів виправлення.

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

Оскільки результативність методів орфокорекції залежить від вмісту словникових ресурсів, які при цьому використовуються, для підтримки ефективної роботи коректора із вузькотематичними текстовими даними розроблено спосіб комп'ютеризованого формування предметноорієнтованого словникового ресурсу шляхом автоматизованої модифікації існуючого універсального лексико-семантичного словника з врахуванням вимог до терміносистеми конкретної предметної галузі.

Перетворення словникового ресурсу пропонується проводити у два етапи:

- фільтрації лексики (умовного виключення слів, які не зустрічаються в документах даної предметної галузі);

- систематизації лексем (забезпечення зв'язності графу словника шляхом відновлення зв'язків між відібраними на попередньому етапі вершинами).

Третій розділ дисертаційної роботи присвячений вирішенню задачі розробки способу структурно-алгоритмічної організації програмного орфокоректора, спрямованого на забезпечення його інтегрованості до відкритих систем АОТ.

В основу розв'язання даної задачі запропоновано покласти агентоорієнтований підхід до створення програмного забезпечення. У дослідженні під агентом розуміється самостійна програмна система, яка здатна отримувати дані від зовнішнього середовища, інтерпретувати їх та визначати свою реакцію на них. Зовнішнім середовищем агента є простір, у якому існує сам агент, об'єкти середовища та інші агенти.

Стан зовнішнього середовища пропонується визначати за набором значень квазістатичних параметрів САОТ та за оперативними даними, які надходять до агента-коректора у вигляді повідомлень від інших компонентів системи або від користувача.

Квазістатичними є такі параметри системи, значення яких під час її роботи змінюються дуже рідко (якщо змінюються взагалі), до числа котрих, перш за все, належать: структурна організація САОТ, функціональні характеристики САОТ (ступінь інтелектуальності алгоритмів аналізу текстових даних системою; характер текстових даних, з якими працює система; пріоритетність критеріїв визначення ефективності роботи системи), програмно-апаратне забезпечення роботи САОТ.

Оперативні дані, які надходять до агента-коректора в реальному часі, можна розділити на службові повідомлення та запити на виправлення спотвореного слова із набором вказівок щодо особливостей проведення процесу корекції.

До множини І пропонується включити дані про поточний стан складових агента-коректора, а також дані про можливість ініціювання роботи орфокоректора іншим модулем САОТ.

Оскільки орфокоректор є сервісним доповненням САОТ, до його обов'язків не повинно входити ініціювання взаємодії з іншими модулями системи. Крім того, не слід занадто ускладнювати організацію агента-коректора (особливо при локальному розміщенні САОТ), тому що це може спричинити втрату оперативності його функціонування, що для програмного забезпечення допоміжного характеру є вкрай небажаним. Таким чином, по відношенню до САОТ агент-коректор має проявляти реактивний тип поведінки.

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

У четвертому розділі дисертації зазначено, що запропонований контекстно-асоціативний метод виправлення орфографічних помилок та його програмну реалізацію згідно з агентним підходом до побудови ПЗ доцільно використовувати в інформаційно-пошукових системах (ІПС). Для теоретичного обґрунтування та експериментальної перевірки даного твердження обрано інформаційно-пошукову систему Єдиного інформаційного середовища (ЄІС) НТУУ «КПІ», розроблену на кафедрі спеціалізованих комп'ютерних систем НТУУ «КПІ».

Проаналізовано функціональні профілі згаданої ІПС та визначено, що виправлення орфографічних помилок може бути необхідним у процесі повнотекстового пошуку документів, їх кластеризації та генерації інвертованого індексу документів. Для того, щоб відповідні модулі пошукової системи могли ініціювати роботу орфокоректора, його запропоновано ввести до складу модуля лінгвістичної підтримки на серверному боці ІПС.

Також у розділі подано опис розроблених програмних засобів, які реалізують запропонований метод виправлення орфографічних помилок та використовуються у програмному забезпеченні проекту ЄІС НТУУ «КПІ». Активною складовою коректора, побудованого у формі програмного агента, є набір таймерів, які відповідають за ініціацію перевірки вмісту відповідних буферів. Тому алгоритм його роботи зводиться до алгоритму обробки подій таких таймерів.

Створено програмний інструментарій модифікації вмісту універсального лексико-семантичного ресурсу формату WordNet 3.0 з метою використання останнього при роботі із текстовими даними певної тематики.

Для експериментальної апробації запропонованого методу орфокорекції, а також для перевірки справедливості теоретичних тверджень, які доводяться у другому розділі роботи, та коректності розробленого способу модифікації вмісту лексико-семантичного словника використано масив запитів користувача до ІПС ЄІС НТУУ «КПІ», котрі характеризуються різною потужністю множин слів контексту; різною кількістю помилок, припущених у слові (1 та 2 помилки); різною силою семантичного зв'язку контексту із спотвореним словом.

Проаналізовано результати функціонування коректора у випадках, коли алгоритмом його роботи передбачено:

1) використання Міри1 та Міри2 сили семантичного зв'язку контексту спотвореного слова та варіантів виправлення;

2) виконання функції f_cont на початку та наприкінці послідовності фільтрів (прямий та інверсний порядок фільтрації);

3) використання універсального та тематичноорієнтованого лексико-семантичних словників для визначення варіантів виправлення;

4) проведення спроб виправлення одно- та двократних помилок;

5) встановлення радіуса околу контекстного оточення спотвореного слова за структурою графа словника рівним від 1 до 5 переходів (maxdist = 1..5).

Показники ефективності роботи створеного орфокоректора порівняно із аналогічними показниками модуля, вбудованого до пакету MS Word, функціональність якого найчастіше використовується для обробки текстів. Робота коректора базується на використанні WordNet 3.0 для англійської мови, оскільки кінцевого варіанту локалізації словника даного формату для української мови поки що не існує.

Різноманітність вхідних текстових даних створює незручності при оцінюванні часових показників роботи коректора в секундах (чи інших абсолютних одиницях виміру часу). Тому результати вимірювань часу орфокорекції наведено у вигляді відношення часу роботи коректора при заданих вихідних умовах (t) до відповідного показника роботи коректора, коли він виконує виправлення однократних помилок із застосуванням фільтрів вмісту універсального словника в прямому порядку (t_баз).

Показником ефективності роботи програмних засобів орфокорекції, на основі значень якого можна робити висновки щодо швидкості виправлення помилок, є час виконання семантичної функції f_cont. На рис.4 показано, що умова виконана (для Міри1 - при maxdist<=3), тому загальний час орфокорекції має бути меншим при застосуванні фільтрів до вмісту словникового ресурсу в інверсному порядку.

Відповідно до отриманих даних визначено, що для забезпечення підвищення швидкості при збереженні рівня точності роботи ІПС, до якої включено розроблений орфокоректор, в алгоритмі функціонування останнього необхідно передбачити:

- виконання фільтрації вмісту словника в інверсному порядку;

- залучення для реалізації семантичного фільтра Міри2 семантичної близькості варіантів виправлення та контексту спотвореного слова;

- використання для роботи орфокоректора спеціалізованого словника;

- неперевищення радіусом околу контексту, в якому здійснюється пошук варіантів виправлення, значення maxdist=4.

Висновки

В дисертаційній роботі запропоноване нове вирішення задачі створення програмних засобів автоматизованого виправлення орфографічних помилок, яке знайшло відображення в розробці та експериментальному дослідженні інверсного контекстно-асоціативного методу орфокорекції, спрямованого на підвищення швидкодії та точності роботи відповідного ПЗ, а також у розробці способу структурно-алгоритмічної організації орфокоректора, яка забезпечує його інтегрованість до відкритих систем АОТ.

1. На основі дослідження існуючих методів та засобів автоматизованого виправлення орфографічних помилок у природномовних текстових об'єктах аргументовано доцільність використання алгоритмів семантичного аналізу текстових даних у ході орфокорекції, показано необхідність визначення місця процедури семантичноорієнтованого аналізу контексту в загальній схемі орфокорекції, обґрунтовано актуальність розробки способів структурно-алгоритмічної організації програмного орфокоректора, здатного гнучко налаштовуватись на взаємодію з модулями довільних сучасних систем АОТ.

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

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

4. Запропоновано спосіб оцінювання ступеня семантичної близькості альтернативи виправлення до оточення спотвореного слова за мінімальною з довжин найкоротших шляхів від неї до елементів контексту у графі словника. Застосування даного способу дозволяє зменшити кількість операцій щодо перевірки наборів гіпотез на відповідність спотвореному слову у ході орфокорекції.

5. Розроблено спосіб формування предметноорієнтованого словникового ресурсу шляхом автоматизованої модифікації існуючого універсального лексико-семантичного словника з урахуванням вимог до терміносистеми конкретної предметної галузі. Використання спеціалізованого словника відповідними програмними засобами дозволяє оперативно та точно аналізувати текстові дані з певної тематики.

6. Запропоновано спосіб структурно-алгоритмічної організації орфокоректора у формі спеціалізованого реактивного програмного агента, що забезпечує його інтегрованість до існуючих відкритих систем АОТ та оперативну взаємодію з їх модулями.

7. Розроблено програмні засоби, які реалізують запропонований інверсний контекстно-асоціативний метод виправлення орфографічних помилок у природномовних текстових даних та використовуються у межах Єдиного інформаційного середовища НТУУ «КПІ». Створено програмний інструментарій модифікації універсального лексико-семантичного ресурсу формату WordNet 3.0. Отримані результати експериментальних досліджень розробленого орфокоректора підтвердили теоретичні положення даної дисертаційної роботи, що дозволило визначити рекомендовані значення параметрів алгоритмів виправлення помилок, встановлення яких забезпечує ефективну роботу даного програмного продукту.

автоматизований орфографічний помилка програмний

Список опублікованих праць за темою дисертації

1. Петрашенко А.В., Михайлюк А.Ю., Блєдний Д.В., Заболотня Т.М. Підхід до побудови блоку логічного виведення експертної системи // Вісник технологічного університету «Поділля». - 2004. - Т.2, №2. - С.69-72. - Автором розроблений алгоритм обчислення арифметичних значень блоком логічного виведення ЕС.

2. Тарасенко В.П., Михайлюк А.Ю., Заболотня Т.М. Спеціалізовані інтелектуальні агенти як засіб інтеграції гетерогенного програмного забезпечення // Інформаційні технології та комп'ютерна інженерія. - 2006. - № 3(7). - С. 96-101. - Автором запропоновані структурна організація програмних адаптерів для забезпечення інтеграції гетерогенного ПЗ, а також загальні шаблони їх поведінки.

3. Михайлюк А.Ю., Заболотня Т.М. Комбінований метод виправлення орфографічних помилок у текстових даних // Вісник Хмельницького національного університету. - 2007. - Т.2, № 2. - С. 21-26. - Автором запропонована змістовна суть комбінованого методу виправлення орфографічних помилок.

4. Заболотня Т.М. Селективний підхід до автоматизованого формування оперативного спеціалізованого лексико-семантичного словникового ресурсу // Бионика интеллекта. - 2007. - № 2(67). - С. 27-31.

5. Заболотня Т.М. Оптимізація процесу контекстноорієнтованої орфокорекції шляхом спрощення обчислення міри семантичної близькості слів // Проблеми інформатизації та управління. - 2007. - № 3(21). - С.55-59.

6. Заболотня Т.М., А.Ю. Михайлюк, В.П. Тарасенко Структурно-алгоритмічна організація програмного агента-орфокоректора // Наукові вісті НТУУ “КПІ”. - 2008. - № 1. - С.88-96. - Автором розроблено спосіб структурно-алгоритмічної організації орфокоректора з врахуванням характеристик САОТ як його зовнішнього середовища.

7. Михайлюк А.Ю., Заболотня Т.М., Нужний В.В., Осипов М.С., Сапсай Т.Г. Оптимізація управління інформаційними процесами як універсальний засіб підвищення ефективності сучасних технологій // Мікропроцесорні пристрої та системи в автоматизації виробничих процесів: зб.наук.праць за мат-ми міжн. наук.-практ. конф., 15-17 трав. 2003р. / МОНУ, Технологіч. ун-т «Поділля». - Хмельницький: Техн. ун-т «Поділля», 2003. - С. 81-85. - Автором сформульовані рекомендовані характеристики системи управління інформаційними процесами.

8. Mykhailyuk A., Tarassenko V., Nuzhny V., Osipov M., Zabolotnya T. Some Aspects of the Efficiency Evaluation Problem of Heterogeneous Information // ACSN2003: мат. І міжн. конф. «Сучасні комп'ютерні системи та мережі: розробка та використання», (Львів, 24-26 вер. 2003р.) / МОНУ, Нац. ун-т «Львівська політехніка». - Львів: Львівська політехніка, 2003. - С.125-127. - Автором запропоновано застосування методу експертних оцінок для оперативного моніторингу показника ефективності роботи системи управління.

...