Как найти расстояние между элементами матрицы

Расстояние Левенштейна для чайников

Когда я взялась решать задачку по динамическому программированию — реализовать алгоритм, который рассчитывает расстояние Левенштейна — мне пришлось послушать пару небольших лекций и прочесть несколько статей (приведу их в конце), чтобы разобраться. Я решила попытаться пересказать алгоритм настолько просто, чтобы по этому объяснению можно было снять ролик для тиктока (когда он снова возобновит свою деятельность в РФ). Дальше — мало формул и много картинок.

Понятие редакционного расстояния

Расстояние Левенштейна, или редакционное расстояние, — метрика cходства между двумя строковыми последовательностями. Чем больше расстояние, тем более различны строки. Для двух одинаковых последовательностей расстояние равно нулю. По сути, это минимальное число односимвольных преобразований (удаления, вставки или замены), необходимых, чтобы превратить одну последовательность в другую.

Например, LEV(’БИБА’, ‘БОБА’) = 1, так как потребуется провести одну замену ‘И’ на ‘О’:

Расстояние между Австрией и Австралией по Левенштейну составит 2 — понадобится два удаления:

А вот между котиком и скотиной — 3 — две вставки и одна замена:

Существует также модификация метрики — расстояние Дамерау — Левенштейна, в котором добавлена операции перестановки символов. В данной статье мы не будем его рассматривать.

Практическое применение

Расстояние Левенштейна активно используется для исправления ошибок в словах, поиска дубликатов текстов, сравнения геномов и прочих полезных операций с символьными последовательностями.

Метрика названа в честь советского математика, выпускника мехмата МГУ Владимира Иосифовича Левенштейна. Он всю жизнь проработал в Институте Прикладной Математики им. М.В.Келдыша, умер в 2017 году.

Алгоритм Вагнера — Фишера

Итак, вычислим расстояние между двумя строками методом Вагнера — Фишера: составим матрицу D и каждый её элемент вычислим по рекуррентной формуле:

Немного пугает? Разберёмся, как использовать формулу для заполнения таблицы.

Ясно, что первые три строчки рекуррентной формулы помогут нам заполнить только первый столбец и первую строку таблицы. Для всех остальных ячеек мы будем пользоваться четвёртой строкой — той, что с минимумом. Здесь— символы, соответствующие ячейкам i и j. Оператор если символы и не равны друг другу, и если равны.

Обратите внимание, что первый символ последовательности будет иметь индекс 1, как принято в математике, а не 0.

Будем заполнять таблицу построчно.

Рассчитаем D(1,1), это символы ‘Г’ и ‘Л’. Они не равны друг другу, значит m(’Г’, ‘Л’) = 1. Тогда D(1,1) — это минимум между значениями D(0,1) + 1, D(1,0) + 1 и D(0, 0) + m(’Г’, ‘Л’) = D(0, 0) + 1. Эти клетки выделены голубым. То есть min(1+1, 1+1, 0+1) = min(2, 2, 1) = 1.

Рассчитаем следующую клетку, D(1, 2). Для этого просто сдвинем голубой уголок на одну клетку вправо:

Так как символы ‘Г’ и ‘А’ не равны, используем ту же формулу:

D(1, 2) = min(D(0,2) + 1; D(1,1) + 1; D(0, 1) + 1) = min(2+1; 1+1; 1+1) = 2.

Передвигая голубой уголок, аналогично заполним первые две строки и начало третьей, пока не доберёмся до совпадающих символов ‘Б’ в D(3,3):

Из-за того, что символы совпадают, замена этим двум символам не нужна, поэтому при подсчёте минимума число в розовой ячейке не увеличивается на единицу, т.е. D(3, 3) = min(D(2,3) + 1; D(3,2) + 1; D(2, 2) + 0) = min(3+1; 3+1; 2+0) = 2.

Заполняем таким образом таблицу до самого конца.

Расстояние Левенштейна в этой мартице — нижняя правая ячейка, D(9,8):

Ура! Нам понадобится 5 шагов, чтобы превратить Гибралтар в лабрадора.

Если вас интересует только понимание алгоритма, а не его реализация в коде, на этом всё.

Реализация в динамическом программировании

Если же реализовать всё-таки нужно, посмотрим, как это сделать на Python.

Так как мы заполняем матрицу, нам понадобится 2 цикла, длины которых равны длинам символьных последовательностей, которые мы хотим сравнить или преобразовать.

В целях минимизации используемой памяти мы располагаем строковые последовательности так, чтобы длины строк были минимальны. Это необязательно, но существенно сэкономит память, если одна из последовательностей длинная, а другая короткая.

def levenshtein(str_1, str_2):
    n, m = len(str_1), len(str_2)
    if n > m:
        str_1, str_2 = str_2, str_1
        n, m = m, n

Ясно, что хранить всю матрицу в памяти не нужно* — достаточно текущей и предыдущей строк. Циклы начинаются с 1 — так же, как индексы в таблице:

*нужно в случае, если задача стоит не посчитать расстояние, а составить редакционное предписание: последовательность односимвольных операций (вставок, удалений и замен), в результате которой одна последовательность превратится в другую. Эта задача сложнее формализуется, поэтому выходит за рамки данной статьи.

  current_row = range(n + 1)
  for i in range(1, m + 1):
		  previous_row, current_row = current_row, [i] + [0] * n

Проще основным случаем считать тот, когда символы равны, и в случае, если нет — прибавлять к ячейке в предыдущей строке по диагонали (розовой) единицу:

for j in range(1, n + 1):
		add, delete, change = previous_row[j] + 1, current_row[j - 1] + 1, previous_row[j - 1]
		if str_1[j - 1] != str_2[i - 1]:
			   change += 1
		current_row[j] = min(add, delete, change)

Весь алгоритм в таком случае будет выглядеть так:

def levenstein(str_1, str_2):
    n, m = len(str_1), len(str_2)
    if n > m:
        str_1, str_2 = str_2, str_1
        n, m = m, n

    current_row = range(n + 1)
    for i in range(1, m + 1):
        previous_row, current_row = current_row, [i] + [0] * n
        for j in range(1, n + 1):
            add, delete, change = previous_row[j] + 1, current_row[j - 1] + 1, previous_row[j - 1]
            if str_1[j - 1] != str_2[i - 1]:
                change += 1
            current_row[j] = min(add, delete, change)

    return current_row[n]

В данной реализации цены замены, удаления и вставки равны друг другу и единице, но, в зависимости от задачи, они могут принимать неравные значения.

Время работы этого алгоритма — m*n, т.е. равно произведению длин символьных последовательностей.

Когда не нужно изобретать велосипед

В коммерческой разработке и/или при обработке больших массивов слов писать метод самостоятельно чаще всего нет смысла. В Python есть библиотека, в оригинале написанная на C, а также библиотека, содержащая разные метрики оценки сходства строк. Также можно посчитать расcтояние в NLTK.

Заключение

На мой взгляд, разбор алгоритма вычисления расстояния Левенштейна — не только хорошая задачка для собеседования, но и просто увлекательное занятие. Заполнение таблицы напомнило мне азиатскую игру Го.

Здорово, когда не просто пользуешься реализацией алгоритма из коробки, но и понимаешь, как именно всё работает. Надеюсь, после этой статьи у вас стало на один такой алгоритм больше.

Литература

• https://medium.com/analytics-vidhya/levenshtein-distance-for-dummies-dd9eb83d3e09

• https://habr.com/ru/post/117063/

• Расстояние Левенштейна на Python

Disclaimer. This is by no means a complete and fully rigorous answer, but should be a pretty good starting point.

First, unless I misunderstand what you’re trying to capture with your definition of neighbour, shouldn’t it be that $(x_1,y_1)neq(x_2,y_2)$ are neighbours if and only if one of the following occurs

1. $Delta x=Delta y=1$;
2. $Delta x=1$ and $Delta y=0$; or
3. $Delta x=0$ and $Delta y=1$.

Otherwise $Delta x+Delta y=2$ could allow $(1,1)$ to be a neighbour of $(1,3)$, which would mean that there are actually $10$ non-neighbour combinations in a $3times 3$ matrix.

If my comment above is actually what you’re interested in, then the number $C_n$ of possible combinations of non-neighbouring matrix entries in an $ntimes n$ matrix is the number of ways to place 2 nonattacking kings on an $ntimes n$ board, which is apparently given by the explicit formula
$$C_n=frac{(n — 1)(n — 2)(n^2 + 3n — 2)}2,qquad ninmathbb N.$$
Note that this means that $C_3=16$ instead of $18$. This formula is confirmed by the following MatLab code (you can play around with the parameter $N$ to change the dimension, and the output $C$ is the number of pairs we’re looking for).

N=3; % Dimension of matrix

X=zeros(2,N^2); % 2 x N^2 array whose columns represent matrix entries

% The loop below generates all matrix entries
ctr=1;
for(i=1:N)
    for(j=1:N)
        X(1,ctr)=i;
        X(2,ctr)=j;
        ctr=ctr+1;
    end
end

% All possible combinations of two entries
C=nchoosek(N^2,2);

% The loop below goes through all combinations.
% If a combination contains neighbouring entries, we remove one from C.
% After going through all combinations, the number C left is precisely
% the number of non-neighbouring combinations.
for(i=1:N^2)
    for(j=i+1:N^2)
        dx=abs(X(1,i)-X(1,j));
        dy=abs(X(2,i)-X(2,j));
        if((dx==1 && dy==0) || (dx==0 && dy==1) || (dx==1 && dy==1))
            C=C-1;
        end
    end
end
C

I suspect that a nice exact formula for the average Euclidean distance of a uniform non-neighbouring pair for arbitrary $n$ may not exist. However, it could still be possible to get a tractable asymptotic answer. In this line of thought, my suspicion is that your random variable can be thought of as a finite-dimensional approximation of the average distance between two random points in a square, which is apparently equal to
$$gamma:=frac{2+sqrt{2}+5log(1+sqrt{2})}{15}.$$

More precisely, we can represent an $ntimes n$ matrix as a square grid inside the unit square (see here for an example with $n=13$), where the sides of the smaller squares in the grid are of size $n^{-1}$, and each smaller square represents a matrix entry.

Given two points $z_1=(x_1,y_1)$ and $z_2:=(x_2,y_2)$ sampled uniformly from the unit square in $mathbb R^2$, we can obtain two randomly selected matrix entries by looking at which of the smaller squares $z_1$ and $z_2$ land into. Of course, this does not take into account your requirement that the matrix entries be non-neighbours, but for very large $n$, the probability that two random points $z_1$ and $z_2$ in $[0,1]^2$ land in neighbouring squares converges to zero, so I expect that this approximation should work out regardless.

If this approximation does indeed work, then we can expect that the average euclidean distance you’re looking for, at least for large $n$, is approximately equal to
$$ncdotgamma= ncdot frac{2+sqrt{2}+5log(1+sqrt{2})}{15}.$$

After doing some MatLab simulations, it appears that this is a pretty good approximation, as shown in the picture below (the purple line is the asymptotic value $ncdot gamma$, and the yellow $+$’s are the actual averages computed using a very similar code to the one I used above to compute the values of $C_n$).

Нравится ресурс? Помоги проекту!

расстояние между элементами матрицы

• Подписаться на тему
• Сообщить другу
• Скачать/распечатать тему

Сообщ. #1 , 23.10.08, 07:13

Нужен простой алгоритм для решения задачи: В булевой матрице A(n,m) найти минимальное и максимальное расстояние между элементами, равными 1. расстояние это (поправьте если это не так): Если элементы располагаются в одной строке (столбце), то расстояние это A(i,j)-A(i,j+k) = k ( A(i+k,j)-A(i,j) = k ), если элементы располагаются в разных строках (и/или столбцах), то расстояние определяется по правилу треугольника Пифагора: k = sqrt((A(i+p,j)-A(i,j))^2+(A(i,j+p)-A(i+p,j))^2)

Akina	Сообщ. #2 , 23.10.08, 07:43
	Заранее составить матрицу расстояний distance(i, j) = sqrt(i*i + j*j) и считать расстояния k = distance(abs(x1-x2), abs(y1-y2))

tomsksmile	Сообщ. #3 , 23.10.08, 08:32
	Akina, спасибо за идею. Еще и булевой матрицы нет. Пока координаты (x,y) генерируются в натуральных величинах (в метрах), между ними-то и нужно вычислять расстояние.

OpenGL	Сообщ. #4 , 23.10.08, 09:59
	Вообще если рассматривать эти координаты как точки на плоскости, то наиболее удаленные точки находятся на выпуклой оболочке. А про поиск наиболее близких точек можно почитать здесь, глава 3-5. Сообщение отредактировано: OpenGL — 23.10.08, 10:32

tomsksmile	Сообщ. #5 , 23.10.08, 10:22
	OpenGL, спасибо. смотрю. Сообщение отредактировано: tomsksmile — 23.10.08, 10:24

amk	Сообщ. #6 , 23.10.08, 13:43
	В C есть такая функция — hypot(x, y) считает длину гипотенузы треугольника с катетами x и y. Проще говоря — sqrt(x^2 + y^2). Не вызывает переполнений.

OpenGL	Сообщ. #7 , 23.10.08, 20:47
	а дельфийская переполнение вызывает?

Pavia	Сообщ. #8 , 24.10.08, 14:02
	OpenGL Hypot из модйля math. Нет не вызывает. И еще она там с повышенной точностью, нежели прямой вариант.

0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)

0 пользователей:

• Предыдущая тема
• Алгоритмы
• Следующая тема

[ Script execution time: 0,0728 ]   [ 15 queries used ]   [ Generated: 28.05.23, 03:07 GMT ]  

Нормой называют
функционал 
,
удовлетворяющий следующим аксиомам:

1. 
   ,

2. 
   ,

3. 
    (аксиома
   треугольника),

4. 
    для
   любого числа 
    (абсолютная
   однородность).

Таким
образом, норма — это полунорма, на которую
наложено дополнительное условие: норма
равна нулю только на нулевом элементе.

Нормированным
пространством называют
линейное пространство с заданной на
нём нормой.

Норму
элемента линейного пространства 
 обозначают 
.

Полное
нормированное пространство
называется банаховым
пространством.

Евклидово
пространство.
Скалярным произведением в
действительном линейном
пространстве 
 называется
функционал от двух переменных 
,
определённый для любых 
 и
удовлетворяющий следующим аксиомам:

1. 
   ,

2. 
   ,

3. 
   ,

4. 
   ,

5. 
   .

Евклидово
пространство —
это линейное пространство с заданным
в нём скалярным произведением.

В
евклидовом пространстве норма естественным
образом определяется через скалярное
произведение:

Ортогонализация —
это процесс построения ортонормированной
системы на основе линейно независимой
системы векторов.

Теорема
1 (Об ортогонализации). Рассмотрим
линейно независимую систему

элементов
евклидова пространства 
.
В пространстве 
 существует
ортогональная система элементов

,
причём каждый элемент 
 есть
линейная комбинация вида

,каждый
элемент 
 представляется
в виде
,при
этом, каждый элемент 
 определяется
с точностью до множителя 
.

Вопрос 9. Матрицы и основные действия над матрицами. Свойства действий над матрицами.

  Матрица
может состоять как из одной строки, так
и из одного столбца. Вообще говоря,
матрица может состоять даже из одного
элемента.

Определение. Если
число столбцов матрицы равно числу
строк (m=n), то матрица называетсяквадратной.

Определение. 
Матрица вида:= E,называется единичной
матрицей.

 Определение. Если a_mn = a_nm ,
то матрица называется симметрической.

Определение. Квадратная
матрица вида  называется диагональной матрицей.

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

Определение. Суммой
(разностью) матриц
является матрица, элементами которой
являются соответственно сумма (разность)
элементов исходных матриц.

c_ij = a_ij  b_ij
С = А + В = В + А.

Операция умножения
(деления) матрицы
любого размера на произвольное число
сводится к  умножению (делению) каждого
элемента матрицы на это число.

 (А+В)
=А  В
А() = А  А 

Операция
умножения матриц

Определение: Произведением матриц
называется матрица, элементы которой
могут быть вычислены по следующим
формулам: AB = C;

Из
приведенного определения видно, что
операция умножения матриц определена
только для матриц, число
столбцов первой из которых равно числу
строк второй.

Свойства
операции умножения матриц. 

1)Умножение
матриц не
коммутативно,
т.е. АВ  ВА
даже если определены оба произведения.
Однако, если для каких – либо матриц
соотношение АВ=ВА выполняется, то такие
матрицы называютсяперестановочными.

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

Перестановочными
могут быть только квадратные матрицы
одного и того же порядка.

АЕ
= ЕА = А

Очевидно,
что для любых матриц выполняются
следующее свойство: AO = O;  OA = O,

где
О – нулевая матрица.

 2)
Операция перемножения матриц ассоциативна, т.е.
если определены произведения АВ и (АВ)С,
то определены ВС и А(ВС), и выполняется
равенство: (АВ)С=А(ВС). 

3)
Операция умножения матриц дистрибутивна по
отношению к сложению, т.е. если имеют
смысл выражения  А(В+С) и (А+В)С, то
соответственно: А(В + С) = АВ + АС

(А
+ В)С = АС + ВС.

4)
Если произведение АВ определено, то для
любого числа  верно
соотношение: (AB)
= (A)B = A(B). 

5)
Если определено произведение АВ , то
определено произведение В^ТА^Т и
выполняется равенство:(АВ)^Т =
В^ТА^Т,
где индексом Т обозначается транспонированная матрица.

 6)
Заметим также, что для любых квадратных
матриц det (AB) = detAdetB.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #