Аннотация 2
Введение 5
1.1 Метод Дамерау-Левенштейна 8
1.2 Метод Джаро-Винклера 11
Глава 2 Анализ алгоритмов нечеткого сравнения строк 15
2.1 Алгоритм Вагнера-Фишера 15
2.2 Алгоритм Дамерау-Левенштейна 18
2.3 Алгоритм Джаро-Винклера 20
2.4 Сравнительный анализ алгоритмов нечеткого сравнения строк 23
Глава 3 Применение алгоритмов нечеткого сравнения строк в прикладных задачах 25
3.1 Программа сверки справочников между базами 1С v8.1 25
3.2 Региональный мастер-индекс пациентов на платформе InterSystems HealthShare 28
3.3 Информационная система «Фольклор» 30
3.4 Разработка программы поиска клиента в перечне Росфинмониторинга 31
Заключение 41
Список используемой литературы и используемых источников 43
В компьютерных науках нечеткое сравнение строк - это поиск строк в тексте, которые приблизительно соответствуют заданному шаблону.
Другими словами, нечеткое сравнение строк - это тип текстового поиска, который находит совпадения, даже если пользователи неправильно вводят слова или вводят только частичные слова для поиска.
Это задача, известная также, как приблизительное совпадение строк, широко применяется в поисковых системах, базах данных, системах проверки орфографии и на плагиат, а также в других прикладных областях [20].
Так, при разработке многоступенчатых фильтров в системах управления базами данных на одной из стадий необходимо выполнить приблизительное сравнение строк [6]. Как показывает практика, эффективность данной стадии зависит от грамотно подобранных критериев идентичности строк и алгоритмов их сравнения.
Для решения таких задач используются методы нечеткого сравнения строк.
Исследование применения методов нечеткого сравнения строк при решении различных прикладных задач представляет актуальность и научно-практический интерес.
Объектом исследования бакалаврской работы являются методы нечеткого сравнения строк.
Предметом исследования бакалаврской работы является применение методов нечеткого сравнения строк для решения прикладных задач.
Цель выпускной квалификационной работы - анализ алгоритмов нечеткого сравнения строк и исследование возможности их применения при разработке программного обеспечения для решения различных прикладных задач.
Для достижения данной цели необходимо выполнить следующие задачи:
• провести анализ методов нечеткого сравнения строк;
• провести анализ известных алгоритмов нечеткого сравнения строк;
• исследовать применение алгоритмов нечеткого сравнения строк в различных прикладных задачах;
• разработать программу реализации алгоритма нечеткого сравнения строк и оценить ее эффективность.
Методы исследования - методы и алгоритмы нечеткого сравнения строк, объектно-ориентированный подход к проектированию программного обеспечения, теория баз данных.
Практическая значимость бакалаврской работы заключается в разработке программы, реализующей алгоритм нечеткого сравнения строк.
Данная работа состоит из введения, трех глав, заключения, списка используемой литературы и приложений.
Первая глава посвящена описанию методов нечеткого сравнения строк. Рассмотрены методы Дамерау-Левенштена и Джаро-Винклера.
Во второй главе дан обзор известных алгоритмов нечеткого сравнения строк. Описаны свойства алгоритмов Вагнера-Фишера, Дамерау-Левенштена и Джаро-Винклера. Представлен сравнительный анализ указанных алгоритмов.
В третьей главе рассмотрены примеры применения алгоритмов нечеткого сравнения строк для решения различных прикладных задач. Разработана программа, использующая алгоритм Джаро-Винклера для нечеткого сравнения строк в процессе поиска клиентов в Перечне Росфинмонитринга.
В заключении описываются результаты выполнения выпускной квалификационной работы.
Структура бакалаврской работы: 43 страницы, 14 рисунков, 2 таблицы, 25 источников.
Бакалаврская работа посвящена актуальной проблеме анализа методов и алгоритмов нечеткого сравнения строк и исследования их применения при разработке программного обеспечения для решения различных прикладных задач.
В ходе выполнения бакалаврской работы достигнуты следующие результаты:
1. Проанализированы методы нечеткого сравнения строк.
Как показал анализ, наиболее популярными считаются методы нечеткого сравнения строк, основанные на символьном подходе. К ним относятся методы Дамерау-Левенштейна и Джаро-Винклера. С помощью Левенштейна можно подсчитать количество операций, которые необходимы для того, чтобы преобразовать одну строку в другую. Метод Дамерау- Левенштейна также включает транспонирование в ряд отдельных операций. С помощью расстояния Джаро измеряется сходство между двумя строками. Метод Джаро-Винклера позволяет дать более благоприятные оценки для строк, которые соответствуют заданной длине префикса в начале строки.
2. Проанализированы популярные алгоритмы нечеткого сравнения строк.
Как показал анализ, все алгоритмы нечеткого сравнения строк обладают определенными достоинствами и недостатками. Выбор того или иного алгоритма зависит от конкретной прикладной задачи и требований по ее программной реализации.
3. Исследованы области применения алгоритмов нечеткого сравнения строк для решения различных задач.
Как показывает практика, алгоритмы нечеткого сравнения строк применяются для таких прикладных задач, как сравнение наименований элементов справочников двух баз данных 1С8, однозначная идентификация пациентов медучреждений, в том числе по неточным или неполным демографическим данным, морфологический анализ текстов на естественных языках и др.
4. Разработана программа поиска клиентов в Перечне Росфинмониторинга.
Применение алгоритма Джаро-Винклера для нечеткого сравнения и механизмов оптимизации линейного алгоритма в программе поиска клиентов в Перечне Росфинмониторинга позволило повысить функциональные возможности данной программы и увеличить быстродействие поиска почти в 20 раз.
Результаты бакалаврской работы представляют практический интерес и могут быть рекомендованы для разработчиков программного обеспечения, основанного на применении методов нечеткого сравнения строк.
