Підвищення ефективності алгоритмів нечіткого пошуку з використанням таблиці подібності символів
| dc.contributor.advisor | Петренко, Анатолій Іванович | |
| dc.contributor.author | Клещ, Кирило Олегович | |
| dc.date.accessioned | 2024-07-01T12:04:22Z | |
| dc.date.available | 2024-07-01T12:04:22Z | |
| dc.date.issued | 2024 | |
| dc.description.abstract | Клещ К.О. Підвищення ефективності алгоритмів нечіткого пошуку з використанням таблиці подібності символів. – Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 122 «Комп’ютерні науки». – Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», 2024. Дисертаційне дослідження присвячене підвищенню швидкодії алгоритмів і розробці методу нечіткого пошуку з використанням таблиці подібності символів, для пошуку найбільш релевантних документів до пошукової фрази. В роботі створено метод нечіткого пошуку, який складається з 9 послідовних кроків та потрібен для швидкого пошуку співпадінь на великому наборі текстових даних. За допомогою цього методу була створена система нечіткого пошуку, яка дозволила вирішити задачу пошуку найрелевантніших документів до пошукової фрази з набору таких документів. Розроблений метод нечіткого пошуку комбінує переваги алгоритмів на основі детермінованих скінченних автоматів та алгоритмів на основі динамічного програмування для підрахунку відстані Дамерау-Левенштейна. Така комбінація дозволила впровадити таблицю подібності символів оптимальним чином. В рамках роботи запропоновано підхід та спосіб створення таблиці подібності символів та розроблено приклад такої таблиці для символів з англійського алфавіту, що дозволило знаходити міру подібності поміж двома символами з константною асимптотикою та перетворювати поточний символ в його базовий аналог. Для фільтрування й сортування документів було розроблено метод оцінювання відповідності текстових даних до пошукової фрази на основі метрики, яка одночасно враховує кількість знайдених і незнайдених символів та кількість знайдених і незнайдених слів. Алгоритм Дамерау-Левенштейна дозволяє знаходити відстань редагування поміж двома словами, враховуючи помилки наступних типів: заміна, видалення, додавання та транспозиція символів. В рамках роботи була запропонована модифікація цього алгоритму за допомогою використання таблиці подібності для більш точної оцінки відстані редагування між двома словами. На основі розробленого методу була створена система нечіткого пошуку, яка дозволить знаходити шукані результати швидше та підвищить релевантність отриманих результатів шляхом їхнього сортування відповідно до значень розробленої метрики подібності тестових даних. Також у роботі було досліджено, проаналізовано та надано рекомендації, яким чином можна інтегрувати особливості та потужності таблиці подібності символів з алгоритмом нечіткого пошуку Дамерау-Левенштейна. Дослідження алгоритмів нечіткого пошуку в тексті є важливою темою в галузі обробки тексту та інформаційного пошуку. Це обумовлено зростаючим обсягом текстової інформації і ймовірністю помилок через вплив людського фактору при написанні тексту та створенні текстового контенту. Нечіткий пошук використовує алгоритми для пошуку даних в тексті, які приблизно відповідають шаблону. Це досягається шляхом зіставлення та порівняння рядків або ключових слів, які можуть бути схожими між собою, але не ідентичними. У першому розділі дисертаційної роботи були розглянуті та проаналізовані різні алгоритми нечіткого пошуку. Такі як: алгоритм Дамерау-Левенштейна, алгоритм N-грам, алгоритм Джаро-Вінклера, алгоритм Bitap, звичайний алгоритм Левенштейна, алгоритм SoundE та алгоритми на основі скінченних автоматів. У ролі оптимального алгоритму пошуку відстані редагування між двома словами було обрано алгоритм Дамерау-Левенштейна, бо він дозволяє впровадити таблицю подібності оптимальним чином. Також були розглянуті алгоритми на основі скінченних автоматів, а саме: автомат на основі префіксного дерева, автомат на основі таблиці та автомат на основі хешування. Перші два виявились неефективними через певні недоліки, а останній виявився оптимальним та найбільш універсальним з точки зору швидкодії роботи та часу побудови, а також об’єму витраченої пам’яті. У другому розділі дисертаційної роботи було розроблено та покроково описано метод нечіткого пошуку, який дозволяє знаходити найрелевантніші документи до пошукової фрази. Також були розглянуті переваги та недоліки застосування таблиці подібності символів, підходи та способи її побудови. Було створено приклад таблиці подібності для символів з англійської мови за допомогою групування символів у JSON файлі. Використання таблиці подібності покращує отримані результати, особливо при використанні мов зі спеціальними символами. Це дозволяє знаходити набагато більше релевантних результатів, проте швидкодія алгоритму може зменшитись. За допомогою використання такої таблиці підвищується релевантність відповідних документів навіть при наявності орфографічних помилок, скорочень, слів-синонімів або інших форм неточностей у запиті. Підхід із використанням таблиці подібності символів може бути використаний у системах перевірки орфографії та автоматичної корекції, системах автозавершення та автодоповнення, а також у реалізації функцій з виявлення дублікатів даних та плагіату. У третьому розділі дисертаційної роботи проведено аналіз коректності результатів та ефективності алгоритмів нечіткого пошуку з використанням таблиці і без, а також алгоритму пошуку точного збігу. Було проведено перевірку всіх 4 алгоритмів нечіткого пошуку на основі скінченних автоматів на коректність роботи, а також розроблено та проаналізовано тести продуктивності для різних вхідних даних. Для перевірки коректності було розроблено програму, що використовує словник слів та порівнює редагувальну відстань, обчислену поточним рішенням, із редагувальною відстанню, обчисленою за допомогою готового бібліотечного рішення. Для перевірки продуктивності було проведено тестування, що визначає час побудови автомата та час перевірки слова для кожного з рішень. Також була реалізована система нечіткого пошуку на основі запропонованого методу та впроваджена у веб-додаток для пошуку найбільш релевантних документів. Отримані результати можуть бути корисними та використані в різних галузях, де потрібно ефективно та швидко проводити нечіткий пошук у великих обсягах даних, наприклад, при пошуку подібних документів у пошукових системах або при автокорекції помилок. В рамках роботи було: реалізовано метод нечіткого пошуку, який комбінує переваги алгоритмів на основі детермінованих скінченних автоматів та алгоритмів на основі динамічного програмування для підрахунку відстані Дамерау-Левенштейна; запропоновано технологію створення таблиці подібності символів у розроблений метод та створено приклад такої таблиці для символів з англійського алфавіту, що дозволило знаходити міру подібності двох символів із константною асимптотикою та перетворювати поточний символ в його базовий аналог; модифіковано метод оцінювання відстані редагування між двома словами за допомогою використання таблиці подібності в алгоритмі Дамерау-Левенштейна; запропоновано метод оцінювання відповідності текстових даних до пошукової фрази на основі метрики, яка одночасно враховує кількість знайдених/незнайдених слів та символів. Для реалізації декількох кроків розробленого методу було запропоновано технологію до створення таблиці подібності символів, яка дозволить враховувати можливу семантичну подібність символів в словах. Оцінюючи подібність на основі різних критеріїв, таких як: форма, контекст і фонетика, таблиця подібності символів дозволила модифікувати алгоритм нечіткого пошуку, який може ранжувати відповідні результати навіть за наявності великої кількості неспівпадінь unicode значень схожих символів. Це, в свою чергу, збільшило кількість релевантних результатів на 10 %, в залежності від довжини пошукової фрази. Також було впроваджено реалізований метод у систему для пошуку найбільш релевантних електронних листів, документів або текстів у середовищі для резервного копіювання. | |
| dc.description.abstractother | Kyrylo Kleshch. Improving the efficiency of fuzzy search algorithms with the usage of symbols similarity table. – Qualification scientific work as manuscript. Doctor of Philosophy dissertation under 122 «Computer Science» specialty. – National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute,” Kyiv, 2024. The dissertation research is dedicated to improving the speed of the algorithms and developing a fuzzy search method with the usage of symbols similarity table to find the most relevant documents for a search phrase. The work presents a fuzzy search method consisting of 9 sequential steps necessary for quickly finding matches in a large set of text data. Using this method, a fuzzy search system was created and it can solve the problem of finding the most relevant documents for a search phrase from a set of such documents. The developed fuzzy search method combines the advantages of the algorithms based on deterministic finite automata and algorithms based on dynamic programming for calculating the Damerau-Levenshtein distance. This combination allowed to implement the symbols similarity table optimally. The work proposed an approach and method for creating a symbols similarity table, so the example of this table for symbols from the English alphabet was created, allowing for the measurement of similarity between two symbols with the constant asymptotics and transforming the current symbol into its base analog. For filtering and sorting documents, a method for evaluating the correspondence of text data to a search phrase based on a metric was developed, which simultaneously considers the number of found and unfound symbols and the number of found and unfound words. The DamerauLevenshtein algorithm allows to find the editing distance between two words, considering the errors of the following types: substitution, deletion, addition, and transposition of symbols. In the course of the work, a modification of this algorithm was proposed using a similarity table for a more accurate estimation of the editing distance between two words. The developed method allowed to create a fuzzy search system that would help to find the desired results faster and increase the relevance of the obtained results by sorting them according to the values of the developed similarity metric of test data. Additionally, the work investigated, analyzed, and provided recommendations on how to integrate the features and capabilities of the symbols similarity table with the Damerau-Levenshtein fuzzy search algorithm. Research on fuzzy search algorithms in text is an important topic in the field of text processing and information retrieval. The reason is the increasing volume of textual information and the likelihood of errors due to the influence of human factors in writing text and creating textual content. Fuzzy search uses algorithms to search for data in text that approximately match the pattern. This is achieved by comparing and matching strings or keywords that may be similar but not identical. In the first chapter of the dissertation, various fuzzy search algorithms were considered and analyzed, such as the Damerau-Levenshtein algorithm, the N-gram algorithm, the Jaro-Winkler algorithm, the Bitap algorithm, the standard Levenshtein algorithm, the SoundEx algorithm, and algorithms based on finite automata. The DamerauLevenshtein algorithm was chosen as the optimal algorithm for searching the editing distance between two words because it allows for an optimal implementation of the similarity table. Algorithms based on finite automata were also considered, namely: an automaton based on a prefix tree, an automaton based on a table, and an automaton based on hashing. The first two options were found to be inefficient due to certain drawbacks, while the latter proved to be optimal and the most versatile in terms of the operation speed, construction time, and memory consumption. In the second chapter of the dissertation, a fuzzy search method was developed and described step-by-step, allowing for finding the most relevant documents for a search phrase. The advantages and disadvantages of using a symbols similarity table, approaches, and methods of its construction were also discussed. An example of a symbols similarity table for symbols from the English language was created using symbols grouping in a JSON file. The usage of the symbols similarity table improves the obtained results, especially when using languages with special symbols. This allows for finding significantly more relevant results, although the speed of the algorithm may decrease. Using this table enhances the relevance of the corresponding documents even in the presence of spelling mistakes, abbreviations, synonyms, or other inaccuracies in the query. The approach using a symbols similarity table can be used in spelling check and automatic correction systems, autocompletion and auto-suggestion systems, as well as in implementing functions for detecting data duplicates and plagiarism. In the third chapter of the dissertation, an analysis of the correctness of results and the efficiency of fuzzy search algorithms with and without using a table, as well as the exact match search algorithm, was conducted. All four fuzzy search algorithms based on finite automata were tested for correctness, and performance tests were developed and analyzed for various input data. To verify correctness, a program was developed and it used a word dictionary and compared the editing distance calculated by the current solution with the editing distance calculated using a ready-made library solution. To test performance, a testing was conducted to determine the time it takes to construct the automaton and the time it takes to check a word for each of the solutions. Additionally, a fuzzy search system based on the developed method was implemented and integrated into a web application for searching the most relevant documents. The obtained results can be useful and applicable in various fields where the efficient and fast fuzzy search is required in large volumes of data, such as searching for similar documents in search systems or for an error auto-correction. In the course of the work, the following was accomplished: the implementation of a fuzzy search method that combines the advantages of algorithms based on deterministic finite automata and algorithms based on dynamic programming for calculating the DamerauLevenshtein distance; a proposal of a technology for creating a symbols similarity table in the developed method and creation of an example table for symbols from the English alphabet, enabling the measurement of similarity between two symbols with constant asymptotics and transforming the current symbol into its base analog; the modification of the method for estimating the editing distance between two words using the similarity table in the Damerau-Levenshtein algorithm; a proposal of a method for evaluating the correspondence of text data to a search phrase based on a metric that simultaneously considers the number of found/unfound words and symbols. For the implementation of several steps of the developed method, a technology was proposed for creating a symbols similarity table that allows for considering possible semantic similarity of the symbols in words. Assessing similarity based on various criteria such as form, context, and phonetics, the symbols similarity table allowed for modifying the fuzzy search algorithm, which can rank relevant results even in the presence of a large number of mismatches of Unicode values of similar symbols. This, in its turn, increased the number of relevant results by 10%, depending on the length of the search phrase. Additionally, the implemented method was integrated into a system for searching the most relevant emails, documents, or texts in a backup environment. | |
| dc.format.extent | 137 с. | |
| dc.identifier.citation | Клещ, К. О. Підвищення ефективності алгоритмів нечіткого пошуку з використанням таблиці подібності символів : дис. … д-ра філософії : 122 – Комп’ютерні науки / Клещ Кирило Олегович. – Київ, 2024. – 137 с. | |
| dc.identifier.uri | https://ela.kpi.ua/handle/123456789/67661 | |
| dc.language.iso | uk | |
| dc.publisher | КПІ ім. Ігоря Сікорського | |
| dc.publisher.place | Київ | |
| dc.subject | нечіткий пошук | |
| dc.subject | таблиця подібності символів | |
| dc.subject | алгоритм Дамерау-Левенштейна | |
| dc.subject | скінченний автомат | |
| dc.subject | метрика подібності | |
| dc.subject | обробка текстових даних | |
| dc.subject | модель | |
| dc.subject | об’єкт | |
| dc.subject | аналіз | |
| dc.subject | експертна система | |
| dc.subject | нечітка логіка | |
| dc.subject | пошук за зразком | |
| dc.subject | пошук даних | |
| dc.subject | пошук відповідностей | |
| dc.subject | бенчмарки | |
| dc.subject | fuzzy search | |
| dc.subject | symbols similarity table | |
| dc.subject | Damerau-Levenshtein algorithm | |
| dc.subject | finite automaton | |
| dc.subject | similarity metric | |
| dc.subject | text data processing | |
| dc.subject | model | |
| dc.subject | object | |
| dc.subject | analysis | |
| dc.subject | expert system | |
| dc.subject | fuzzy logic | |
| dc.subject | pattern matching | |
| dc.subject | data search | |
| dc.subject | match search | |
| dc.subject | benchmarks | |
| dc.subject.udc | 004.02 | |
| dc.title | Підвищення ефективності алгоритмів нечіткого пошуку з використанням таблиці подібності символів | |
| dc.type | Thesis Doctoral |
Файли
Контейнер файлів
1 - 1 з 1
Ліцензійна угода
1 - 1 з 1
Ескіз недоступний
- Назва:
- license.txt
- Розмір:
- 8.98 KB
- Формат:
- Item-specific license agreed upon to submission
- Опис: