Оглавление
ВВЕДЕНИЕ 2
1. Аналитический обзор методов нечеткого поиска 3
1.1 Классические методы нечеткого поиска по словарю 3
1.2 Исследование механизмов поиска с помощью регулярных выражений. 6
2. Анализ программных решений лингвистической обработки текстов 11
3. Разработка функциональной модели системы поиска по грамматическому словарю древнерусского языка 21
4. Разработка алгоритма поиска по словарю с использованием регулярных выражений 24
5. Проектные решения по системе 26
5.1 Выбор и обоснование выбора программного обеспечения 26
5.2 Выбор инструментальных средств 34
5.3 Разработка системы вводных и выводных данных 42
5.4 Разработка интерфейса и логики работы пользователя в программе 46
6. Тестирование системы 54
ЗАКЛЮЧЕНИЕ 58
СПИСОК ЛИТЕРАТУРНЫХ ИСТОЧНИКОВ 60
ПРИЛОЖЕНИЯ 61
ВВЕДЕНИЕ
Алгоритмы нечеткого поиска (также известного как поиск по сходству или fuzzy string search) являются основой систем проверки орфографии и полноценных поисковых систем вроде Google или Yandex. Например, такие алгоритмы используются для функций наподобие «Возможно вы имели в виду …» в тех же поисковых системах.
Нечеткий поиск является крайне полезной функцией любой поисковой системы. Вместе с тем, его эффективная реализация намного сложнее, чем реализация простого поиска по точному совпадению.
Задачу нечеткого поиска можно сформулировать так:
«По заданному слову найти в тексте или словаре размера n все слова, совпадающие с этим словом (или начинающиеся с этого слова) с учетом k возможных различий».
Например, при запросе «Машина» с учетом двух возможных ошибок, найти слова «Машинка», «Махина», «Малина», «Калина» и так далее.
Алгоритмы нечеткого поиска характеризуются метрикой — функцией расстояния между двумя словами, позволяющей оценить степень их сходства в данном контексте.
Цель исследования: Разработка системы поиска по грамматическому словарю древнерусского языка.
Задачи исследования:
1. Провести аналитический обзор методов нечеткого поиска.
2. Исследовать механизмы поиска с помощью регулярных выражений.
3. Разработать функциональной модели системы поиска по грамматическому словарю древнерусского языка.
4. Разработать алгоритма поиска по словарю с использованием регулярных выражений.
ЗАКЛЮЧЕНИЕ
В настоящее время все большее распространение получают информационные системы и базы данных, содержащие в себе огромное количество текстовой информации. Крупные образовательные центры организуют в Интернете для студентов и сотрудников базы научных статей, авторефератов, многие организации предоставляют доступ к ресурсам электронных библиотек, оргкомитеты конференций публикуют тысячи полных текстов докладов и т. п. Количество электронной информации возросло настолько, что человеку просто не по силам проанализировать её самостоятельно, хотя необходимость проведения такого анализа вполне очевидна, ведь в этих данных заключены знания, которые могут быть использованы при принятии решений. Для автоматической обработки таких данных широко используются методы компьютерной лингвистики.
Компьютерная лингвистика (КЛ) – одно из направлений прикладной лингвистики, которое ориентировано на использование различных компьютерных инструментов (программы, компьютерные технологии обработки данных и их организации) для моделирования функций языка в тех или иных условиях, ситуациях, сферах и т. д., а также вся сфера применения компьютерных моделей языка в лингвистике и смежных дисциплинах. На практике же к термину компьютерная лингвистика относят всё, что связано с использованием компьютеров в языкознание. Компьютерную лингвистику так же часто называю автоматической обработкой текста или машинной лингвистикой [1].
В нашей работы ы разработали Информационную систему поиска по грамматическому словарю древнерусского языка.
Для оценки качества работы системы была проанализирована коллекция из 20 текстов. Основными показателями качества являются:
процент корректно выделенных предложений;
процент корректно выделенных слов древнерусского языка.
Процент корректно выделенных в текстах предложений составил более 97%. При рассмотрении нескольких десятков случаев некорректного выделения предложений и исключения из них опечаток, процент правильно выделенных предложений приблизился к 98%.
Процент корректно найденных сокращений и аббревиатур составил 95%. Ошибочно найденные слова делятся на две группы:
сокращения, состоящие из одного символа (например, «А» – араба);
сокращения, совпадающие с короткими словами, стоящими в конце
предложения (например, «раз.» – разъезд, «мак.» – макар).
СПИСОК ЛИТЕРАТУРНЫХ ИСТОЧНИКОВ
Исходные коды к статье на Java. http://code.google.com/p/fuzzy-search-tools
Расстояние Левенштейна. http://ru.wikipedia.org/wiki/Расстояние_Левенштейна
Расстояние Дамерау-Левенштейна. http://en.wikipedia.org/wiki/Damerau–Levenshtein_distance
Хорошее описание Shift-Or c модификациями Wu-Manber, правда, на немецком. http://de.wikipedia.org/wiki/Baeza-Yates-Gonnet-Algorithmus
Метод N-грамм. http://www.cs.helsinki.fi/u/ukkonen/TCS92.pdf
Хеширование по сигнатуре. http://itman.narod.ru/articles/rtf/confart.zip
Сайт Леонида Моисеевича Бойцова, целиком посвященный нечеткому поиску. http://itman.narod.ru/
Реализация Shift-Or и некоторых других алгоритмов. http://johannburkard.de/software/stringsearch/
Fast Text Searching with Agrep (Wu & Manber). http://www.at.php.net/utils/admin-tools/agrep/agrep.ps.1
Damn Cool Algorithms — автомат Левенштейна, BK-деревья, и еще кое-какие алгоритмы.http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees
BK-деревья на Java. http://code.google.com/p/java-bk-tree/
Алгоритм Маасса-Новака. http://yury.name/internet/09ia-seminar.ppt
Библиотека метрик SimMetrics. http://staffwww.dcs.shef.ac.uk/people/S.Chapman/simmetrics.html
Библиотека метрик SecondString. http://sourceforge.net/projects/secondstring/
ПРИЛОЖЕНИЯ
Приложение 1 – Menaion Medieval описание шрифта
Приложение 2. Индексная страница