Основна мета цієї роботи полягає в дослідженні можливості впровадження сучасних методів індексації для нечіткого пошуку. Для поглиблення розуміння області, буде визначено класифікацію, яка враховує всі підходи, як прямі методи, так і послідовні методи на основі фільтрації. Основна увага приділяється словникам, що нечасто поновлюються, які використовуються в основному для пошуку. Тому в роботі вивчаються індекси, які оптимізовані для пошуку, а не для оновлення. Індекси передбачаються асоціативними, тобто, вони здатні зберігати та надавати допоміжну інформацію, наприклад , строкові значення. Всі описані рішення гарантують пошук в рамках певної відстані k і не допускають втрати даних.
НЕЧІТКИЙ ПОШУК, N-ГРАМ, TRIE-ДЕРЕВО, KD-ДЕРЕВО, ВЕБ-СИСТЕМА, ФУНКЦІЯ СХОЖОСТІ РЯДКІВ, АЛГОРИТМ ПОСЛІДОВНОГО ПЕРЕБОРУ, АЛГОРИТМ РОЗШИРЕННЯ ВИБІРКИ, МЕТРИЧНІ ДЕРЕВА, АЛГОРИТМ BITAP.


The primary goal of this work is to survey state-of-the-art indexing methods for fuzzy searching. To improve understanding of the field, introduced a taxonomy that classifies all methods into direct methods and sequence-based filtering methods. Focus of this work on infrequently updated dictionaries, which are used primarily for retrieval. Therefore, indices that are optimized for retrieval rather than for update. The indices are assumed to be associative, that is, capable of storing and retrieving auxiliary information, such as string identifiers. All solutions are lossless and guarantee retrieval of strings within a specified edit distance k.
FUZZY SEARCH, N-GRAM, TRIES, KD-TREES, WEB-BASED SYSTEM, FUNCTION OF DISTANCE BETWEEN TWO WORDS, EXTENSION METHOD, BITAP METHOD, METRIC TREES