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

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. Но для простоты мы не стали этого делать.

Данный текст является ознакомительным фрагментом.



Поделитесь на страничке

Похожие главы из других книг:

(6.14) Как настроить роутинг между двумя подсетями на W2kPro?

Из книги автора

(6.14) Как настроить роутинг между двумя подсетями на W2kPro? Это нужно когда на машине с W2k имеется две сетевые карты, одна из которых смотрит в одну подсеть, а другая в другую. Для того что бы компьютеры из разных подсетей могли видеть друг друга, на машине с W2k надо прописать


8.4.1 Протоколы вектора расстояния

Из книги автора

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


С двумя источниками напряжения

Из книги автора

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


Цепи с двумя накопителями энергии

Из книги автора

Цепи с двумя накопителями энергии Схемы с двумя различными накопителями энергии содержат катушку индуктивности L и конденсатор С вместе с одним или несколькими резисторами R. Когда схема содержит последовательно включенные R, L и С, различают переходные процессы трех


Регулировка расстояния

Из книги автора

Регулировка расстояния Команда 3DDISTANCE устанавливает режим интерактивного трехмерного просмотра, приближение к объектам и удаление от них. Команда вызывается из падающего меню View ? Camera ? Adjust Distance или щелчком на пиктограмме Adjust Distance на плавающей панели инструментов Camera


7.17. Вычисление разности между двумя моментами времени

Из книги автора

7.17. Вычисление разности между двумя моментами времени Можно вычислить интервал между двумя моментами времени. В результате вычитания одного объекта Time из другого получаем число секунд:today = Time.local(2000,11,10)yesterday = Time.local(2000,11,9)cliff = today - yesterday # 86400 секунд.И снова оказывается


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

Из книги автора

11.12. Вычисление расстояния между векторами ПроблемаТребуется найти евклидово расстояние между векторами.РешениеЕвклидово расстояние между векторами определяется как квадратный корень суммы квадратов разностей соответствующих элементов. Рассчитать его можно так, как


Регулировка расстояния

Из книги автора

Регулировка расстояния Команда 3DDISTANCE устанавливает режим интерактивного трехмерного просмотра, приближение к объектам и удаление от них. Команда вызывается из падающего меню View ? Camera ? Adjust Distance или щелчком на пиктограмме Adjust Distance на плавающей панели инструментов


Поиск различий между двумя файлами

Из книги автора

Поиск различий между двумя файлами Рассмотрим следующую задачу. Имеются две версии исходного файла, одна из которых - более поздняя, содержащая ряд изменений. Как выяснить различия между этими двумя файлами? Какие строки были добавлены, а какие удалены? Какие строки


Регулировка расстояния

Из книги автора

Регулировка расстояния Команда 3DDISTANCE устанавливает режим интерактивного трехмерного просмотра, приближение к объектам и удаление от них. Команда вызывается из падающего меню View ? Camera ? Adjust Distance или щелчком на пиктограмме Adjust Distance на плавающей панели инструментов Camera


Пример A-8. days-between: Подсчет числа дней между двумя датами

Из книги автора

Пример A-8. days-between: Подсчет числа дней между двумя датами #!/bin/bash# days-between.sh: Подсчет числа дней между двумя датами.# Порядок использования: ./days-between.sh [M]M/[D]D/YYYY [M]M/[D]D/YYYYARGS=2 # Ожидается два аргумента из командной строки.E_PARAM_ERR=65 # Ошибка в числе ожидаемых


Расстояния между словами и строками, поля

Из книги автора

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


6. Расстояния

Из книги автора

6. Расстояния Признаки слева направо (рис. 186):• расстояния между словами маленькие, слова написаны тесно;• расстояния между словами большие, слова стоят широко;• расстояния между строками достаточно большие, пропорциональные;• расстояния между строками маленькие; Рис.


У14.3 Геометрические объекты с двумя координатами

Из книги автора

У14.3 Геометрические объекты с двумя координатами Опишите класс TWO_COORD, задающий объекты с двумя вещественными координатами, среди наследников которого были бы классы POINT (ТОЧКА), COMPLEX (КОМПЛЕКСНОЕ_ЧИСЛО) и VECTOR (ВЕКТОР). Будьте внимательны при помещении каждого компонента на