Редактирование: Задача о редакционном расстоянии

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
#перенаправление [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
+
{{Определение
 +
|definition=
 +
'''Расстояние Левенштейна''' (также '''редакционное расстояние''' или '''дистанция редактирования''') между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.}}
 +
 
 +
== Свойства ==
 +
 
 +
Для расстояния Левенштейна справедливы следующие утверждения:
 +
* <tex>\rm{d}(S_1,S_2) \ge | |S_1| - |S_2| |</tex>
 +
* <tex>\rm{d}(S_1,S_2) \le 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>, а |S| - длина строки S.
 +
 
 +
== Редакционное предписание ==
 +
 
 +
''Редакционным предписанием'' называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: '''D''' (англ. delete) — удалить, '''I''' (англ. insert) — вставить, '''R''' (англ. replace) — заменить, '''M''' (англ. match) — совпадение.
 +
 
 +
Например, для 2-х строк «hell123» и «hello214» можно построить следующую таблицу преобразований:
 +
{| class="wikitable" border = "1"
 +
!'''M''' ||'''M''' ||'''M''' ||'''M''' ||'''R''' ||'''M''' ||'''R''' ||'''I'''
 +
|-
 +
|'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''1''' ||'''2''' ||'''3''' ||
 +
|-
 +
|'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''o''' ||'''2''' ||'''1''' ||'''4'''
 +
|}
 +
 
 +
== Код получения редакторского предписания ==
 +
В строке '''S''' содержится последовательность действий, необходимых для получения из первой строки второй кратчайшим образом.
 +
  readln(s1);
 +
  readln(s2);
 +
  n := length(s1);
 +
  m := length(s2);
 +
  for i := 1 to n do d[0, i] := i;
 +
  for i := 1 to m do d[i, 0] := i;
 +
  for i := 1 to n do for j := 1 to m do
 +
    if s1[i] = s2[j] then
 +
    begin
 +
      d[i, j] := d[i - 1, j - 1];
 +
      p[i, j].x := i - 1;
 +
      p[i, j].y := j - 1;
 +
    end else
 +
    begin
 +
      if (d[i - 1, j] <= d[i, j - 1])and(d[i - 1, j] <= d[i - 1, j - 1]) then
 +
      begin
 +
        d[i, j] := d[i - 1, j] +1;
 +
        p[i, j].x := i - 1;
 +
        p[i, j].y := j;
 +
      end;
 +
      if (d[i, j - 1] <= d[i - 1, j])and(d[i, j - 1] <= d[i - 1, j - 1]) then
 +
      begin
 +
        d[i, j] := d[i, j - 1] +1;
 +
        p[i, j].x := i;
 +
        p[i, j].y := j - 1;
 +
      end;
 +
      if (d[i - 1, j - 1] <= d[i, j - 1])and(d[i - 1, j - 1] <= d[i - 1, j]) then
 +
      begin
 +
        d[i, j] := d[i - 1, j - 1] + 1;
 +
        p[i, j].x := i - 1;
 +
        p[i, j].y := j - 1;
 +
      end;
 +
    end;
 +
  x := n;
 +
  y := m;
 +
  while (x > 0) and (y > 0) do
 +
  begin
 +
  if p[x, y].x - x = 0 then s := 'D' + s else
 +
  if p[x, y].y - y = 0 then s := 'I' + s else
 +
  if s1[x] = s2[y] then s := 'M' + s else s := 'R' + s;
 +
  x := p[x, y].x;
 +
  y := p[x, y].y;
 +
  end;
 +
  writeln(s);
 +
 
 +
 
 +
=== Разные цены операций ===
 +
 
 +
Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность разных ошибок при вводе текста, и т. п. В общем случае:
 +
* w(a, b) — цена замены символа a на символ b
 +
* w(ε, b) — цена вставки символа b
 +
* w(a, ε) — цена удаления символа a
 +
 
 +
Для решения задачи о редакционном расстоянии, необходимо найти последовательность замен, минимизирующую суммарную цену. Расстояние Левенштейна является частным случаем этой задачи при
 +
* w(a, а) = 0
 +
* w(a, b) = 1 при a≠b
 +
* w(ε, b) = 1
 +
* w(a, ε) = 1
 +
 
 +
Как частный случай, так и задачу для произвольных w, решает алгоритм Вагнера — Фишера, приведённый ниже. Здесь и ниже мы считаем, что все w неотрицательны, и действует правило треугольника: если две последовательные операции можно заменить одной, это не ухудшает общую цену (например, заменить символ x на y, а потом с y на z не лучше, чем сразу x на z).
 +
 
 +
== Формула ==
 +
 
 +
Будем считать, что элементы строк нумеруются с первого, как принято в математике, а не нулевого.
 +
 
 +
Пусть <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>\rm{D}(i, j) = \left\{\begin{array}{llcl}
 +
0&&;&i = 0,\ j = 0\\
 +
i&&;&j = 0,\ i > 0\\
 +
j&&;&i = 0,\ j > 0\\
 +
\rm{min}(\\
 +
&\rm{D}(i, j - 1) + 1\\
 +
&\rm{D}(i - 1, j) + 1&;&j > 0,\ i > 0\\
 +
&\rm{D}(i - 1, j - 1) + \rm{m}(S_1[i], S_2[j])\\
 +
)
 +
\end{array}\right.
 +
</tex>,
 +
 
 +
где <tex>\rm{m}(a,b)</tex> равна нулю, если <tex>a = b</tex> и единице в противном случае; <tex>\min(a, b, c)</tex> возвращает наименьший из аргументов.
 +
 
 +
=== Доказательство ===
 +
 
 +
Рассмотрим формулу более подробно. Здесь <tex>D(i, j)</tex> — расстояние между префиксами строк: первыми i символами строки <tex>S_1</tex> и первыми j символами строки <tex>S_2</tex>. Очевидно, что редакционное расстояние между двумя пустыми строками равно нулю. Так же очевидно то, что чтобы получить пустую строку из строки длиной <tex>i</tex>, нужно совершить <tex>i</tex> операций удаления, а чтобы получить строку длиной <tex>j</tex> из пустой, нужно произвести <tex>j</tex> операций вставки. Осталось рассмотреть нетривиальный случай, когда обе строки непусты.
 +
 
 +
Для начала заметим, что в оптимальной последовательности операций, их можно произвольно менять местами. В самом деле, рассмотрим две последовательные операции:
 +
* Две замены одного и того же символа — неоптимально (если мы заменили x на y, потом y на z, выгоднее было сразу заменить x на z).
 +
* Две замены разных символов можно менять местами
 +
* Два стирания или две вставки можно менять местами
 +
* Вставка символа с его последующим стиранием — неоптимально (можно их обе отменить)
 +
* Стирание и вставку разных символов можно менять местами
 +
* Вставка символа с его последующей заменой — неоптимально (излишняя замена)
 +
* Вставка символа и замена другого символа меняются местами
 +
* Замена символа с его последующим стиранием — неоптимально (излишняя замена)
 +
* Стирание символа и замена другого символа меняются местами
 +
 
 +
Пускай <tex>S_1</tex> кончается на символ «a», <tex>S_2</tex> кончается на символ «b». Есть три варианта:
 +
# Символ «а», на который кончается <tex>S_1</tex>, в какой-то момент был стёрт. Сделаем это стирание первой операцией. Тогда мы стёрли символ «a», после чего превратили первые <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> операций
 +
# Символ «b», на который кончается <tex>S_2</tex>, в какой-то момент был добавлен. Сделаем это добавление последней операцией. Мы превратили <tex>S_1</tex> в первые <tex>j-1</tex> символов <tex>S_2</tex>, после чего добавили «b». Аналогично предыдущему случаю, потребовалось <tex>D(i,\ j-1)+1</tex> операций.
 +
# Оба предыдущих утверждения неверны. Если мы добавляли символы справа от финального «a», то чтобы сделать последним символом «b», мы должны были или в какой-то момент добавить его (но тогда утверждение 2 было бы верно), либо заменить на него один из этих добавленных символов (что тоже невозможно, потому что добавление символа с его последующей заменой неоптимально). Значит, символов справа от финального «a» мы не добавляли. Самого финального «a» мы не стирали, поскольку утверждение 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> операций.
 +
 
 +
== Алгоритм Вагнера — Фишера ==
 +
 
 +
Для нахождения кратчайшего расстояния необходимо вычислить матрицу D, используя [[#Формула|вышеприведённую формулу]]. Её можно вычислять как по строкам, так и по столбцам.
 +
Псевдокод алгоритма, написанный при произвольных ценах замен, вставок и удалений (важно помнить, что элементы нумеруются с 1):
 +
<code>
 +
D(0,0) = 0
 +
для всех j от 1 до N
 +
  D(0,j) = D(0,j-1) + цена вставки символа S2[j]
 +
для всех i от 1 до M
 +
  D(i,0) = D(i-1,0) + цена удаления символа S1[i]
 +
  для всех j от 1 до N
 +
    D(i,j) = min(
 +
        D(i-1, j) + цена удаления символа S1[i],
 +
        D(i, j-1) + цена вставки символа S2[j],
 +
        D(i-1, j-1) + цена замены символа S1[i] на символ S2[j]
 +
    )
 +
вернуть D(M,N)
 +
</code>
 +
 
 +
=== Память ===
 +
 
 +
Алгоритм в виде, описанном выше, требует <tex>\Theta(M \cdot N)</tex> операций и такую же память, однако, если требуется только расстояние, легко уменьшить требуемую память до <tex>\Theta(\min(M,N))</tex>. Для этого надо учесть, что после вычисления любой строки предыдущая строка больше не нужна. Более того, после вычисления D(i, j) не нужны также D(i-1,0) … D(i-1,j-1). Поэтому алгоритм можно переписать как
 +
<code>
 +
для всех i от 0 до M
 +
  для всех j от 0 до N
 +
    вычислить D(i, j)
 +
    если i>0 и j>0
 +
      стереть D(i-1, j-1)
 +
вернуть D(M, N)
 +
</code>
 +
 
 +
== Литература ==
 +
*http://en.wikipedia.org
 +
*Романовский И.В. "Дискретный анализ"

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)