Дистанция Левенштейна (расстояние Левенштейна, редакционное расстояние, дистанция редактирования)определяется между двумя строками и равна минимальному количеству операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых дляпревращения одной строки в другую.
Впервые такой способ вычисления дистанции (меры различия) между двумя двоичными последовательностями предложил советский ученый-математик В.И. Левенштейн (род. 1935). Впоследствииспособ распространился на последовательностипроизвольного алфавита.
Расстояние Левенштейна активно применяется для исправления ошибок в поисковых системах, в текстовых редакторах, а также в биоинформатике.
Пусть и – две символьные строки, тогда для вычисления дистанции Левенштейна между ними может быть использовано следующеерекуррентное соотношение:
В предыдущем выражении используются символы и Разъясним их смысл:
–количество символов в заданной строке. Например,
–заданная строка без последнего символа. Например,
– последний символ заданной строки. Например,
Поясним принцип применения этого рекуррентного соотношения на следующем примере.
Пусть необходимо вычислить Тогда имеем следующую последовательность шагов:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
Шаги вычисления с 1 по 14 соответствуютрекурсивному погружению, а шаги с 15 по 28 – восходящему вычислению.Нетрудно убедиться, что для превращения слова «сор» в слово «спорт» достаточно удалить (или вставить)две буквы.
На рис. 17 и 18 представлена рекурсивнаяфункцияlevenshtein_r, вычисляющая дистанцию Левенштейна для двух строк, а на рис. 19 и 20 –пример программы, вызывающей эту функцию и результат ее выполнения соответственно.
Рис. 17. Прототип функцииlevenshtein_r,вычисляющей дистанцию Левенштейна между двумя строками
Рис. 19. Пример программы, вызывающейфункцию levenshtein_r
Рис. 20. Результат выполнения программы, представленной на рис. 19
Функция levenshtein_rимеет четыре параметра: lx(длина первой строки), x(массив символов размерностью lx, содержащий символы первой строки), ly(длина второй строки), y(массив символов размерностью ly, содержащий символы второй строки). Фунция возвращает дистанцию Левенштейна между двуми заданными строками.
Реализация функции (рис. 17) практически повторяет рекуррентное соотношение, приведенное выше, поэтому не нуждается в дополнительном пояснении.
В программе, приведенной на рис. 18, вызывается функция levenshtein_rдля вычисления дистанции Левенштейна между строками «сор» и «спорт».
Результат выполнения программы (рис. 17) совпадает с результатом, полученным ранее вручную. Следует лишь обратить внимание, что в отличие от ручного просчета при выполнении функции levenshtein_rнекоторыеподзадачи решаются по несколько раз. Например, дистанция между строками «со» и «спор» вычисляется 3 раза, а это в каждом случае приводит к повторному вычислению дистанций между «с» и «спор», «со» и «спо», «с» и «спо» и т. д.
Следует отметить, что в информатикечастоиспользуетсядистанция Дамерау – Левенштейна, которая является модификацией дистанции Левенштейна и отличается применениемеще одной операции преобразования–перестановки соседних символов.
Лекция №7 Создание и обход бинарного дерева
Пример. Использование бинарного дерева для сортировки данных
Допустим дана последовательность чисел, например:
• 15 10 20 12 8 17 25 5 9
Вывести числа в порядке возрастания:
• 5 8 9 10 12 15 17 20 25
Построим бинарное дерево: первое число будет корнем дерева. Если второе число < 1-го, то оно станет корнем левого поддерева, а если > 1-го, то станет корнем правого поддерева. Каждое следующее число будет добавляться либо в левое поддерево, либо в правое.
Алгоритм:
1. Создание бинарного дерева в виде регулярной сети.
2. Обход дерева слева направо и вывод меток его вершин (чисел).
3. Удаление дерева (освобождение памяти).
Программа
#include <stdio.h>
#include <stdlib.h>
/* Описание бинарного дерева в виде регулярной сети */
// Тип вершины дерева (элемента сети)
struct TREE
{ float number; // число
struct TREE *left, *right; /* указатели на левое и правое поддеревья*/
};
// Прототипы функций
void insert (struct TREE *pt, float x);
void print_tree (struct TREE *pt);
void delete_tree (struct TREE *pt);
/*--------------------------------------*/
/* Главная функция */
/*--------------------------------------*/
void main()
{ struct TREE *pt; // указатель на корень дерева
float x; // очередное число
puts ("\nВведите числовую последовательность");
scanf("%f", &x);
// создание корня дерева
pt = (struct TREE *) malloc (sizeof(struct TREE));
pt->number=x;
pt->left=pt->right=NULL;
// ввод чисел и формирование дерева while (scanf("%f", &x) != EOF)