Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лабораторная работа № 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.