Підвищення ефективності алгоритмів нечіткого пошуку з використанням таблиці подібності символів
Ескіз недоступний
Дата
2024
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Клещ К.О. Підвищення ефективності алгоритмів нечіткого пошуку з використанням таблиці подібності символів. – Кваліфікаційна наукова праця на правах рукопису.
Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 122 «Комп’ютерні науки». – Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», 2024.
Дисертаційне дослідження присвячене підвищенню швидкодії алгоритмів і розробці методу нечіткого пошуку з використанням таблиці подібності символів, для пошуку найбільш релевантних документів до пошукової фрази. В роботі створено метод нечіткого пошуку, який складається з 9 послідовних кроків та потрібен для швидкого пошуку співпадінь на великому наборі текстових даних. За допомогою цього методу була створена система нечіткого пошуку, яка дозволила вирішити задачу пошуку найрелевантніших документів до пошукової фрази з набору таких документів. Розроблений метод нечіткого пошуку комбінує переваги алгоритмів на основі детермінованих скінченних автоматів та алгоритмів на основі динамічного програмування для підрахунку відстані Дамерау-Левенштейна. Така комбінація дозволила впровадити таблицю подібності символів оптимальним чином. В рамках роботи запропоновано підхід та спосіб створення таблиці подібності символів та розроблено приклад такої таблиці для символів з англійського алфавіту, що дозволило знаходити міру подібності поміж двома символами з константною асимптотикою та перетворювати поточний символ в його базовий аналог. Для фільтрування й сортування документів було розроблено метод оцінювання відповідності текстових даних до пошукової фрази на основі метрики, яка одночасно враховує кількість знайдених і незнайдених символів та кількість знайдених і незнайдених слів. Алгоритм Дамерау-Левенштейна дозволяє знаходити відстань редагування поміж двома словами, враховуючи помилки наступних типів: заміна, видалення, додавання та транспозиція символів. В рамках роботи була запропонована модифікація цього алгоритму за допомогою використання таблиці подібності для більш точної оцінки відстані редагування між двома словами. На основі розробленого методу була створена система нечіткого пошуку, яка дозволить знаходити шукані результати швидше та підвищить релевантність отриманих результатів шляхом їхнього сортування відповідно до значень розробленої метрики подібності тестових даних. Також у роботі було досліджено, проаналізовано та надано рекомендації, яким чином можна інтегрувати особливості та потужності таблиці подібності символів з алгоритмом нечіткого пошуку Дамерау-Левенштейна. Дослідження алгоритмів нечіткого пошуку в тексті є важливою темою в галузі обробки тексту та інформаційного пошуку. Це обумовлено зростаючим обсягом текстової інформації і ймовірністю помилок через вплив людського фактору при написанні тексту та створенні текстового контенту. Нечіткий пошук використовує алгоритми для пошуку даних в тексті, які приблизно відповідають шаблону. Це досягається шляхом зіставлення та порівняння рядків або ключових слів, які можуть бути схожими між собою, але не ідентичними. У першому розділі дисертаційної роботи були розглянуті та проаналізовані різні алгоритми нечіткого пошуку. Такі як: алгоритм Дамерау-Левенштейна, алгоритм N-грам, алгоритм Джаро-Вінклера, алгоритм Bitap, звичайний алгоритм Левенштейна, алгоритм SoundE та алгоритми на основі скінченних автоматів. У ролі оптимального алгоритму пошуку відстані редагування між двома словами було обрано алгоритм Дамерау-Левенштейна, бо він дозволяє впровадити таблицю подібності оптимальним чином. Також були розглянуті алгоритми на основі скінченних автоматів, а саме: автомат на основі префіксного дерева, автомат на основі таблиці та автомат на основі хешування. Перші два виявились неефективними через певні недоліки, а останній виявився оптимальним та найбільш універсальним з точки зору швидкодії роботи та часу побудови, а також об’єму витраченої пам’яті. У другому розділі дисертаційної роботи було розроблено та покроково описано метод нечіткого пошуку, який дозволяє знаходити найрелевантніші документи до пошукової фрази. Також були розглянуті переваги та недоліки застосування таблиці подібності символів, підходи та способи її побудови. Було створено приклад таблиці подібності для символів з англійської мови за допомогою групування символів у JSON файлі. Використання таблиці подібності покращує отримані результати, особливо при використанні мов зі спеціальними символами. Це дозволяє знаходити набагато більше релевантних результатів, проте швидкодія алгоритму може зменшитись. За допомогою використання такої таблиці підвищується релевантність відповідних документів навіть при наявності орфографічних помилок, скорочень, слів-синонімів або інших форм неточностей у запиті. Підхід із використанням таблиці подібності символів може бути використаний у системах перевірки орфографії та автоматичної корекції, системах автозавершення та автодоповнення, а також у реалізації функцій з виявлення дублікатів даних та плагіату. У третьому розділі дисертаційної роботи проведено аналіз коректності результатів та ефективності алгоритмів нечіткого пошуку з використанням таблиці і без, а також алгоритму пошуку точного збігу. Було проведено перевірку всіх 4 алгоритмів нечіткого пошуку на основі скінченних автоматів на коректність роботи, а також розроблено та проаналізовано тести продуктивності для різних вхідних даних. Для перевірки коректності було розроблено програму, що використовує словник слів та порівнює редагувальну відстань, обчислену поточним рішенням, із редагувальною відстанню, обчисленою за допомогою готового бібліотечного рішення. Для перевірки продуктивності було проведено тестування, що визначає час побудови автомата та час перевірки слова для кожного з рішень. Також була реалізована система нечіткого пошуку на основі запропонованого методу та впроваджена у веб-додаток для пошуку найбільш релевантних документів. Отримані результати можуть бути корисними та використані в різних галузях, де потрібно ефективно та швидко проводити нечіткий пошук у великих обсягах даних, наприклад, при пошуку подібних документів у пошукових системах або при автокорекції помилок. В рамках роботи було: реалізовано метод нечіткого пошуку, який комбінує переваги алгоритмів на основі детермінованих скінченних автоматів та алгоритмів на основі динамічного програмування для підрахунку відстані Дамерау-Левенштейна; запропоновано технологію створення таблиці подібності символів у розроблений метод та створено приклад такої таблиці для символів з англійського алфавіту, що дозволило знаходити міру подібності двох символів із константною асимптотикою та перетворювати поточний символ в його базовий аналог; модифіковано метод оцінювання відстані редагування між двома словами за допомогою використання таблиці подібності в алгоритмі Дамерау-Левенштейна; запропоновано метод оцінювання відповідності текстових даних до пошукової фрази на основі метрики, яка одночасно враховує кількість знайдених/незнайдених слів та символів. Для реалізації декількох кроків розробленого методу було запропоновано технологію до створення таблиці подібності символів, яка дозволить враховувати можливу семантичну подібність символів в словах. Оцінюючи подібність на основі різних критеріїв, таких як: форма, контекст і фонетика, таблиця подібності символів дозволила модифікувати алгоритм нечіткого пошуку, який може ранжувати відповідні результати навіть за наявності великої кількості неспівпадінь unicode значень схожих символів. Це, в свою чергу, збільшило кількість релевантних результатів на 10 %, в залежності від довжини пошукової фрази. Також було впроваджено реалізований метод у систему для пошуку найбільш релевантних електронних листів, документів або текстів у середовищі для резервного копіювання.
Опис
Ключові слова
нечіткий пошук, таблиця подібності символів, алгоритм Дамерау-Левенштейна, скінченний автомат, метрика подібності, обробка текстових даних, модель, об’єкт, аналіз, експертна система, нечітка логіка, пошук за зразком, пошук даних, пошук відповідностей, бенчмарки, fuzzy search, symbols similarity table, Damerau-Levenshtein algorithm, finite automaton, similarity metric, text data processing, model, object, analysis, expert system, fuzzy logic, pattern matching, data search, match search, benchmarks
Бібліографічний опис
Клещ, К. О. Підвищення ефективності алгоритмів нечіткого пошуку з використанням таблиці подібності символів : дис. … д-ра філософії : 122 – Комп’ютерні науки / Клещ Кирило Олегович. – Київ, 2024. – 137 с.