Изменения
Нет описания правки
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
|+
|-align="center"
|'''НЕТ ВОЙНЕ'''
|-style="font-size: 16px;"
|
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
''Антивоенный комитет России''
|-style="font-size: 16px;"
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
|-style="font-size: 16px;"
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
|}
{{Определение
|id=levenstain_dist
|definition=
'''Расстояние Левенштейна''' (англ. ''Levenshtein distance'') (также '''редакционное расстояние''' или '''дистанция редактирования''') между двумя строками в теории информации и компьютерной лингвистике — лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.}}
== Свойства ==
* <tex>\rm{d}(S_1,S_2) \leqslant max( |S_1| , |S_2| )</tex>
* <tex>\rm{d}(S_1,S_2) = 0 \Leftrightarrow S_1 = S_2</tex>
где <tex>\rm{d}(S_1,S_2)</tex> — — расстояние Левенштейна между строками <tex>S_1</tex> и <tex>S_2</tex>, а <tex>|S|</tex> — длина строки <tex>S</tex>.
Расстояние Левенштейна является [[Метрическое пространство|метрикой]].
== Разные цены операций ==
Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность разных ошибок при вводе текста, и ти т. пп. В общем случае:* <tex>w(a, b)</tex> — — цена замены символа <tex>a</tex> на символ <tex>b</tex>* <tex>w(\varepsilon, b)</tex> — — цена вставки символа <tex>b</tex>* <tex>w(a, \varepsilon)</tex> — — цена удаления символа <tex>a</tex>
Для решения задачи о редакционном расстоянии необходимо найти последовательность замен, минимизирующую суммарную цену. Расстояние Левенштейна является частным случаем этой задачи при
Будем считать, что элементы строк нумеруются с первого, как принято в математике, а не нулевого.
Пусть <tex>S_1</tex> и <tex>S_2</tex> — — две строки (длиной <tex>M</tex> и <tex>N</tex> соответственно) над некоторым алфавитом, тогда редакционное расстояние <tex>\rm{d}(S_1, S_2)</tex> можно подсчитать по следующей рекуррентной формуле:
<tex>\ \rm{d}(S_1, S_2) = \rm{D}(M,N)</tex> , где
=== Доказательство ===
Рассмотрим формулу более подробно. Здесь <tex>D(i, j)</tex> — — расстояние между префиксами строк: первыми <tex>i</tex> символами строки <tex>S_1</tex> и первыми <tex>j</tex> символами строки <tex>S_2</tex>. Для нашей динамики должен выполняться [[Динамическое программирование|принцип оптимальности на префиксе]]. Очевидно, что редакционное расстояние между двумя пустыми строками равно нулю. Так же очевидно то, что чтобы получить пустую строку из строки длиной <tex>i</tex>, нужно совершить <tex>i</tex> операций удаления, а чтобы получить строку длиной <tex>j</tex> из пустой, нужно произвести <tex>j</tex> операций вставки. Осталось рассмотреть нетривиальный случай, когда обе строки непусты.
Для начала заметим, что в оптимальной последовательности операций, их можно произвольно менять местами. В самом деле, рассмотрим две последовательные операции:
* Две замены одного и того же символа — символа — неоптимально (если мы заменили <tex>x</tex> на <tex>y</tex>, потом <tex>y</tex> на <tex>z</tex>, выгоднее было сразу заменить <tex>x</tex> на <tex>z</tex>).
* Две замены разных символов можно менять местами
* Два стирания или две вставки можно менять местами
* Вставка символа с его последующим стиранием — стиранием — неоптимально (можно их обе отменить)
* Стирание и вставку разных символов можно менять местами
* Вставка символа с его последующей заменой — заменой — неоптимально (излишняя замена)
* Вставка символа и замена другого символа меняются местами
* Замена символа с его последующим стиранием — стиранием — неоптимально (излишняя замена)
* Стирание символа и замена другого символа меняются местами
# Символ «а», на который кончается <tex>S_1</tex>, в какой-то момент был стёрт. Сделаем это стирание первой операцией. Тогда мы стёрли символ <tex>a</tex>, после чего превратили первые <tex>i-1</tex> символов <tex>S_1</tex> в <tex>S_2</tex> (на что потребовалось <tex>D(i-1,\ j)</tex> операций), значит, всего потребовалось <tex>D(i-1,\ j)+1</tex> операций
# Символ <tex>b</tex>, на который кончается <tex>S_2</tex>, в какой-то момент был добавлен. Сделаем это добавление последней операцией. Мы превратили <tex>S_1</tex> в первые <tex>j-1</tex> символов <tex>S_2</tex>, после чего добавили <tex>b</tex>. Аналогично предыдущему случаю, потребовалось <tex>D(i,\ j-1)+1</tex> операций.
# Оба предыдущих утверждения неверны. Если мы добавляли символы справа от финального <tex>a</tex>, то чтобы сделать последним символом <tex>b</tex>, мы должны были или в какой-то момент добавить его (но тогда утверждение 2 было бы верно), либо заменить на него один из этих добавленных символов (что тоже невозможно, потому что добавление символа с его последующей заменой неоптимально). Значит, символов справа от финального <tex>a</tex> мы не добавляли. Самого финального <tex>a</tex> мы не стирали, поскольку утверждение 1 неверно. Значит, единственный способ изменения последнего символа — символа — его замена. Заменять его 2 или больше раз неоптимально. Значит,
## Если <tex>a=b</tex>, мы последний символ не меняли. Поскольку мы его также не стирали и не приписывали ничего справа от него, он не влиял на наши действия, и, значит, мы выполнили <tex>D(i-1,\ j-1)</tex> операций.
## Если <tex>a\ne b</tex>, мы последний символ меняли один раз. Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить <tex>D(i-1,\ j-1)</tex> операций, значит, всего потребуется <tex>D(i-1,\ j-1)+1</tex> операций.
== Алгоритм Вагнера — Вагнера — Фишера ==
Для нахождения кратчайшего расстояния необходимо вычислить матрицу <tex>D</tex>, используя [[#Формула|вышеприведённую формулу]]. Её можно вычислять как по строкам, так и по столбцам.
Для того, чтобы обеспечить время <tex>\Theta(M \cdot N)</tex> при памяти <tex>\Theta(\min(M,N))</tex>, определим матрицу <tex> E </tex> минимальных расстояний между ''суффиксами'' строк, то есть <tex> E(i, j) </tex> {{---}} расстояние между последними <tex> i </tex> символами <tex>S_1</tex> и последними <tex> j </tex> символами <tex>S_2</tex>. Очевидно, матрицу <tex> E </tex> можно вычислить аналогично матрице <tex> D </tex>, и так же быстро.
Теперь опишем алгоритм, считая, что <tex>S_2</tex> — — кратчайшая из двух строк.
* Если длина одной из строк (или обеих) не больше <tex> 1 </tex>, задача тривиальна. Если нет, выполним следующие шаги.
* Разделим строку <tex>S_1</tex> на две подстроки длиной <tex>M/2</tex>. (Если <tex>M</tex> нечётно, то длины подстрок будут <tex>(M-1)/2</tex> и <tex>(M+1)/2</tex>.) Обозначим подстроки <tex>S_1^-</tex> и <tex>S_1^+</tex>.
* Для вычислим последнюю строку матрицы <tex> D </tex> для строк <tex>S_1^-</tex> и <tex>S_2</tex>, последнюю строку матрицы <tex> E </tex> для строк <tex>S_1^+</tex> и <tex>S_2</tex>.
* Найдём <tex> i </tex> такое, что <tex>D(|S_1^-|, i) + E(|S_1^+|, N-i)</tex> минимально. Здесь <tex> D </tex> и <tex> E </tex> {{---}} матрицы из предыдущего шага, но мы используем только их последние строки. Таким образом, мы нашли разбиение <tex>S_2</tex> на две подстроки, минимизирующее сумму расстояния левой половины <tex>S_1</tex> до левой части <tex>S_2</tex> и расстояния правой половины <tex>S_1</tex> до правой части <tex>S_2</tex>. Следовательно, левая подстрока <tex>S_2</tex> соответствует левой половине <tex>S_1</tex>, а правая правая {{---}} правой.
* Рекурсивно ищем редакционное предписание, превращающее <tex>S_1^-</tex> в левую часть <tex>S_2</tex> (то есть в подстроку <tex>S_2[1...i]</tex>)
* Рекурсивно ищем редакционное предписание, превращающее <tex>S_1^+</tex> в правую часть <tex>S_2</tex> (то есть в подстроку <tex>S_2[i+1...N]</tex>).
== Редакционное предписание ==
'''Редакционное предписание''' (англ. ''Editorial prescription'') — последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: '''D''' (англ. delete) — удалить, '''I''' (англ. insert) — — вставить, '''R''' (англ. replace) — — заменить, '''M''' (англ. match) — — совпадение.
Например, для 2-х строк «hell123» и «hello214» можно построить следующую таблицу преобразований:
