2.36. Вычисление расстояния Левенштейна между двумя строками
Расстояние между строками важно знать в индуктивном обучении (искусственный интеллект), криптографии, исследовании структуры белков и других областях.
Расстоянием Левенштейна называется минимальное число элементарных модификаций, которым нужно подвергнуть одну строку, чтобы преобразовать ее в другую. Элементарными модификациями называются следующие операции: del (удаление одного символа), ins (замена символа) и sub (замена символа). Замену можно также считать комбинацией удаления и вставки (indel).
Существуют разные подходы к решению этой задачи, но не будем вдаваться в технические детали. Достаточно знать, что реализация на Ruby (см. листинг 2.2) позволяет задавать дополнительные параметры, определяющие стоимость всех трех операций модификации. По умолчанию за базовую принимается стоимость одной операции indel (стоимость вставки = стоимость удаления).
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. Но для простоты мы не стали этого делать.
2.37. base64-кодирование и декодирование
Алгоритм base64 часто применяется для преобразования двоичных данных в текстовую форму, не содержащую специальных символов. Например, в конференциях так обмениваются исполняемыми файлами.
Простейший способ осуществить base64-кодирование и декодирование — воспользоваться встроенными возможностями Ruby. В классе Array есть метод pack, который возвращает строку в кодировке base64 (если передать ему параметр "m"). А в классе string есть метод unpack, который декодирует такую строку:
str = "\007\007\002\abdce"
new_string = [str].pack("m") # "BwcCB2JkY2U="
original = new_string.unpack("m") # ["\a\a\002\abdce"]
Отметим, что метод unpack возвращает массив.
2.38. Кодирование и декодирование строк (uuencode/uudecode)
Префикс uu в этих именах означает UNIX-to-UNIX. Утилиты uuencode и uudecode — это проверенный временем способ обмена данными в текстовой форме (аналогичный base64).
str = "\007\007\002\abdce"
new_string = [str].pack("u") # '(P<"!V)D8V4''
original = new_string.unpack("u") # ["\a\a\002\abdce"]
Отметим, что метод unpack возвращает массив.
2.39. Замена символов табуляции пробелами и сворачивание пробелов в табуляторы
Бывает, что имеется строка с символами табуляции, а мы хотели бы преобразовать их в пробелы (или наоборот). Ниже показаны два метода, реализующих эти операции:
class String
def detab(ts=8)
str = self.dup
while (leftmost = str.index("\t")) != nil