Лабораторная работа 3 Расстояние между списками 1
Работа добавлена на сайт samzan.net:
Лабораторная работа № 3
Расстояние между списками
1. Краткие теоретические сведения
В некоторых задачах основной характеристикой объекта служит список символов определенного алфавита. Пусть заданы два списка:
Xi = {xi1, xi2, …, xin} и Xj = {xj1, xj2, …, xjn}.
В общем случае n и m могут быть не равны друг другу. Задача заключается в том, чтобы определить такую функцию, которая выражала бы степень сходства этих двух списков.
Очевидно, что любой список из двух может быть преобразован к другому. Например, для преобразования ABCD к ABDE следует сохранить первый и второй символы, заменить третий и добавить четвертый. Введя пустой символ , можно элементарные преобразования записать в виде трех операций:
1) подстановка xi xj – SUB(xi, xj);
2) уничтожение x – DES(x, );
3) создание x – CRE(, x).
Для каждого преобразования можно ввести свою цену c(xi, xj), c(x, ) и c(, x) соответственно.
Для оценки расстояния между двумя списками вводят понятие полной цены последовательности преобразований как наименьшей из всех возможных цен за переход от исходного списка к конечному. Расстояние (Xi, Xj), соответствующее полной цене является минимальным.
Схема преобразований носит название пути. Путь преобразований записывается в виде ряда операций SUB, DES и CRE. Например, путь преобразований от Xi = {xi1, xi2, xi3, xi4, xi5} к Xj = {xj1, xj2, xj3, xj4, xj5, xj6} можно записать так: SUB(xi1, xj1), SUB(xi2, xj2), DES(xi3, ), SUB(xi4, xj3), CRE(, xj4), SUB(xi5, xj5), CRE(, xj6). Здесь предполагалось, что xi1 = xj1, xi2 = xj2, xi4 = xj3, xi5 = xj5.
Положим Xi(l) = {xi1, xi2, …, xil} и Xj(k) = {xj1, xj2, …, xjk}. Положим так же D(l, k) = (Xi(l), Xj(k)). При этом для перехода от D(l – 1, k – 1) к D(l, k) имеются три возможности:
1) путем подстановки, цена которой соответствует цене подстановки SUB(xil, xjk) последних элементов в каждом списке;
2) путем создания последнего элемента в списке Xj с ценой CRE(, xjk);
3) путем уничтожения последнего элемента в списке Xi с ценой DES(xil, ).
Указанную процедуру можно описать следующим образом:
D(l,k) = min{D(l – 1,k – 1) + c(xil, xjk), D(l,k – 1) + c(, xjk), D(l – 1,k) + c(xil, )}.
Для определения расстояния между списками можно воспользоваться методом динамического программирования. Задача состоит в создании матрицы, каждый элемент которой представляет собой оптимальное расстояние D(l, k). Идея здесь следующая: если каждая составляющая пути оптимальна, то и весь путь будет оптимальным. Расстояние между списками вычисляется в соответствии со следующим выражением:
D(l,k) = min{D(l,k – 1) + d(al, bk), D(l – 1,k – 1) + 2d(al, bk), D(l – 1,k) + d(al, bk)},
где d(al, bk) – расстояние между l-й и k-й составляющими опорного списка X и списка-кандидата Y. При этом полагают, что D(1, 1) = 2d(a1, b1). Часто в качестве окончательного результата рассматривают (X, Y) = D(n, m)/(n + m).
2. Задание
Написать программу, реализующую сравнение списков различной длины для определения какой из букв русского алфавита соответствует введенный графический символ.
3. Список источников
1. Гасфилд Дэн. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология/Пер. с англ. И.В.Романовского. – СПб.: Невский Диалект; БХВ-Петербург, 2003.
2. Романовский И.В. Дискретный анализ: Учебное пособие для студентов, специализирующихся по прикладной математике и информатике. – 3-е изд, перераб. и доп. – СПб.: Невский Диалект; БХВ-Петербург, 2003.
3. СБИС для распознавания образов и обработки изображений: Пер. с англ. / Под ред. К.Фу. – М.: Мир, 1988.
4. Фор А. Восприятие и распознавание образов/Пер. с фр. А.В.Серединского; под ред. Г.П.Катыса. – М.: Машиностроение, 1989.
2. Стросса это гранулематознонекротизирующий васкулит поражающий сосуды мелкого и среднего калибра с вовлеч
3. Утверждаю Утверждаю 1й Зам
4. Общая характеристика рыночной экономики
5. Сокровенная тайна рождения
6. по теме Массы и массовое сознание Выполнила- Богачёва Я.
7. эклектичностью Результаты его деятельности на посту руководителя страны неоднозначны
8. Лабораторная работа 3 Определение избыточности сообщений
9. Курсовая работа Государственная регистрация субъектов предпринимательской деятельности
10. научнотеоретическую и практическую компетентность как основу профессионализма
11. Наукоемкие отрасли и производства- оценка эффективности развития и влияние на экономику Республики Беларусь
12. Поняття підприємства
13. командной системы управления экономикой бесперебойное формирование финансовых ресурсов их наиболее эффек
14. Характеристика государства.html
15. тема издержек производства и их эффект на масштабы производства рассматривается с теоретической точки зрени
16. Перекресток г
17. ЛАБОРАТОРНАЯ РАБОТА 1 ИССЛЕДОВАНИЕ ЭТАПОВ ПОСТРОЕНИЯ И РЕАЛИЗАЦИЯ ПРОГРАММ НА ЯЗЫКЕ АССЕМБЛЕР
18. Курсовая работа- Начисление и выплата пенсий по инвалидности
19. п сепсис перитоніт порушення коронарного кровообігу та ін
20. і Та це не зламало дух Франка і він все одно залишається прибічником своїх поглядів це призвело до другого ар