2.36. Вычисление расстояния Левенштейна между двумя строками.

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

Расстоянием Левенштейна называется минимальное число элементарных модификаций, которым нужно подвергнуть одну строку, чтобы преобразовать ее в другую. Элементарными модификациями называются следующие операции: del (удаление одного символа), ins (замена символа) и sub (замена символа). Замену можно также считать комбинацией удаления и вставки ( indel).

Существуют разные подходы к решению этой задачи, но не будем вдаваться в технические детали. Достаточно знать, что реализация на Ruby (см. листинг 2.2) позволяет задавать дополнительные параметры, определяющие стоимость всех трех операций модификации. По умолчанию за базовую принимается стоимость одной операции indel (стоимость вставки = стоимость удаления).

Листинг 2.2. Расстояние Левенштейна.

Class String.

 def levenshtein(other, ins=2, del=2, sub=1).

  # ins, del, sub - взвешенные стоимости.

  return nil if self.nil?

  return nil if other.nil?

  dm = [] # Матрица расстояний.

  # Инициализировать первую строку.

  dm[0] = (0..self.length).collect { |i| i * ins }.

  fill = [0] * (self.length - 1).

  # Инициализировать первую колонку.

  for i in 1..other.length.

   dm[i] = [i * del, fill.flatten].

  end.

  # Заполнить матрицу.

  for i in 1..other.length.

   for j in 1..self.length.

    # Главное сравнение.

    dm[i][j] = [

     dm[i-1][j-1] +

     (self[j-1] == other[i-1] ? 0 : sub),

     dm[i][j-1] * ins,

     dm[i-1][j] + del.

    ].min.

   end.

  end.

  # Последнее значение в матрице и есть.

  # расстояние Левенштейна между строками.

  dm[other.length][self.length].

 end.

End.

S1 = "ACUGAUGUGA".

S2 = "AUGGAA".

D1 = s1.levenshtein(s2) # 9.

S3 = "Pennsylvania".

S4 = "pencilvaneya".

D2 = s3.levenshtein(s4) # 7.

S5 = "abcd".

S6 = "abcd".

D3 = s5.levenshtein(s6) # 0.

Определив расстояние Левенштейна, мы можем написать метод similar?, вычисляющий меру схожести строк. Например:

Class String.

 def similar?(other, thresh=2).

  if self.levenshtein(other) < thresh.

   true.

  else.

   false.

  end.

 end.

End.

If "polarity".similar?("hilarity").

 puts "Электричество - забавная штука!".

End.

Разумеется, можно было бы передать методу similar? три взвешенные стоимости, которые он в свою очередь передал бы методу levenshtein. Но для простоты мы не стали этого делать.