Программирование на языке Ruby
вернуться

Фултон Хэл
Шрифт:

# 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. Замена символов табуляции пробелами и сворачивание пробелов в табуляторы

Бывает, что имеется строка с символами табуляции, а мы хотели бы преобразовать их в пробелы (или наоборот). Ниже показаны два метода, реализующих эти операции: