Разработка и реализация процедуры выявления похожих строк (летняя практика)

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
Автор Хорошевский Владимир Федорович
Профиль на сайте ВШЭ
Электронная почта
Организация кафедра ММСА/ФКН/НИУ ВШЭ
Учебный год 2015
По теме задания можно сделать курсовую в следующем году обучения


Задание

Разработка и реализация процедуры выявления похожих строк. Исходные данные: Текстовый файл, каждая строка которого содержит ФИО человека в следующем формате: Фамилия + пробел + Инициал1 + точка + Инициал2 + точка

Примечания: 1) фрагмент Инициал2 + точка может отсутствовать. 2) В исходном файле могут быть одинаковые строки

Результат работы процедуры: Текстовый файл, строки которого те же, что и у входного файла, но все они упорядочены по убыванию степени похожести.

Какие начальные требования?

Рекомендуемый план исследования: 1) Изучение методов нечеткого сравнения строк. 2) Изучение различных метрик для выявления похожих строк, включая (как минимум) - косинусное расстояние, - расстояние Левенштейна, - расстояние Жаккарда. 3) Выбор 2-х метрик, наиболее подходящих для решения поставленной задачи. 4) Реализация процедур нечеткого сравнения строк для 2-х выбранных метрик. 5) Сравнение полученных результатов. 6) Подготовка отчета, где будут представлены - Постановка задачи. - Теоретическая часть (методы и метрики нечеткого сравнения строк). - Практическая часть (спецификация реализованных алгоритмов). - Экспериментальная часть (сравнение результатов). - Заключение (выводы и рекомендации по использованию разработанных процедур).

Какие будут использоваться технологии?

Процедура должна быть реализована на языке Java или C++

Какая дополнительная литература понадобится?