# Главное сравнение.
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-кодирование и декодирование — воспользоваться встроенными возможностями Ruby. В классе Array есть метод pack, который возвращает строку в кодировке base64 (если передать ему параметр 'm'). А в классе string есть метод unpack, который декодирует такую строку:
str = ' 07 07 02abdce'
new_string = [str].pack('m') # 'BwcCB2JkY2U='
original = new_string.unpack('m') # ['aa 02abdce']
Отметим, что метод unpack возвращает массив.
2.38. Кодирование и декодирование строк (uuencode/uudecode)
Префикс uu в этих именах означает UNIX-to-UNIX. Утилиты uuencode и uudecode — это проверенный временем способ обмена данными в текстовой форме (аналогичный base64).
str = ' 07 07 02abdce'
new_string = [str].pack('u') # '(P<'!V)D8V4''
original = new_string.unpack('u') # ['aa 02abdce']
Отметим, что метод unpack возвращает массив.
2.39. Замена символов табуляции пробелами и сворачивание пробелов в табуляторы
Бывает, что имеется строка с символами табуляции, а мы хотели бы преобразовать их в пробелы (или наоборот). Ниже показаны два метода, реализующих эти операции:
class String
def detab(ts=8)
str = self.dup
while (leftmost = str.index(' ')) != nil
space = ' '* (ts-(leftmost%ts))
str[leftmost]=space
end
str
end
def entab(ts=8)
str = self.detab
areas = str.length/ts
newstr = ''
for a in 0..areas
temp = str[a*ts..a*ts+ts-1]
if temp.size==ts
