Программирование на языке Ruby, Фултон Хэл

Программирование на языке Ruby

на обложку

Фултон Хэл

Шрифт:

Если задан строковый аргумент, он добавляется к объекту путем обращения к методу

update

. Повторные обращения эквивалентны одному вызову с конкатенированными аргументами:

# Эти два предложения:

сryptic.update("Данные...")

cryptic.update(" еще данные.")

# ... эквивалентны одному такому:

cryptic.update("Данные... еще данные.")

Метод

digest

возвращает 16-байтовую двоичную строку, содержащую 128-разрядный дайджест.

Но

наиболее полезен метод

hexdigest

, который возвращает дайджест в виде строки в коде ASCII, состоящей из 32 шестнадцатеричных символов, соответствующих 16 байтам. Он эквивалентен следующему коду:

def hexdigest

ret = ''

digest.each_byte {|i| ret << sprintf{'%02x' , i) }

ret

end

secret.hexdigest # "b30e77a94604b78bd7a7e64ad500f3c2"

Короче говоря, для получения MD5-свертки нужно написать:

require 'md5'

m = MD5.new("Секретные данные").hexdigest

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

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

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

dm[other.length][self.length]

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

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

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

end

Разумеется, можно было бы передать методу

similar?

три взвешенные стоимости, которые он в свою очередь передал бы методу

levenshtein

. Но для простоты мы не стали этого делать.

2.37. base64-кодирование и декодирование

Алгоритм base64 часто применяется для преобразования двоичных данных в текстовую форму, не содержащую специальных символов. Например, в конференциях так обмениваются исполняемыми файлами.

Простейший способ осуществить base64-кодирование и декодирование — воспользоваться встроенными возможностями Ruby. В классе

Array

есть метод

pack

, который возвращает строку в кодировке base64 (если передать ему параметр

"m"

). А в классе

string

есть метод

unpack

, который декодирует такую строку: