Реферат. Отчет 10 с., 1 ч., 1 рис., 0 таблиц, 4 источника

Пояснительная записка

к курсовому проекту

по дисциплине «Информатика»

Реализация нечёткого поиска

 

Проверил:

ассистент____________________________________________________Е. Р. Васильев

подпись

Выполнил:

студент гр. ИВТ-340_________________________________________А. Н. Гулицкий

подпись

 

 

Омск 2012

Отчет 10 с., 1 ч., 1 рис., 0 таблиц, 4 источника

НЕЧЁТКИЙ ПОИСК, РАССТОЯНИЕ ДАМЕРАУ-ЛЕВЕНШТЕЙНА, АЛГОРИТМ ВАГНЕРА-ФИШЕРА, РЕДАКЦИОННОЕ РАССТОЯНИЕ, ПЕРЕСТАНОВКИ, БАЗА УЧЕБНЫХ ЗАВЕДЕНИЙ

Цель курсовой работы – разработка приложения реализующего алгоритм нечёткого поиска.

Объектом исследования является алгоритм нечёткого поиска.

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

В результате работы было создано приложение, реализующее алгоритм нечёткого поиска.

Содержание

 

Введение. 4

1 Постановка задачи. 6

2 Теоретический анализ. 7

3 Описание разработанного приложения. 8

Заключение. 9

Список использованных источников. 10

 

Введение

Современные системы поддерживают ограниченный набор средств для поиска по тексту. Обычно это только поиск полного вхождения искомой подстроки в строке из базы или индекса. Но для реализации полноценного и удобного поиска этого недостаточно. Именно для этих целей применяют алгоритмы нечёткого поиска.

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

 

Постановка задачи

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

 

Теоретический анализ

Из трёх метрик (расстояния Хэмминга, Левенштейна, Дамерау-Левенштейна) в приложении используется расстояние Дамерау-Левенштейна как наиболее эффективное в случае поиска по названиям учебных заведений. Стоимости операций отличаются от стандартного алгоритма: операции удаления и вставки – 2, обмена и замены символа – 1. Экспериментальным путём было выявлено минимальное расстояние для каждого слова запроса, которое не находит сильно отличающиеся названия. Это расстояние 2. [1]

В приложения не используются фонетические алгоритмы [2], такие, как Soundex, по причине нецелесообразности применения их для поиска по названиям учебных заведений.

Более подробно алгоритмы рассмотрены в статье [3].