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

Контрольный код циклической избыточности (Cyclic Redundancy Checksum, CRC) — хорошо известный способ получить «сигнатуру» файла или произвольного массива байтов. CRC обладает тем свойством, что вероятность получения одинакового кода для разных входных данных равна 1/2**N, где N — число битов результата (чаще всего 32).

Вычислить его позволяет библиотека zlib, написанная Уэно Кацухиро (Ueno Katsuhiro). Метод crc32 вычисляет CRC для строки, переданной в качестве параметра.

require 'zlib'

include Zlib

crc = crc32("Hello")        # 4157704578

crc = crc32(" world!",crc)  # 461707669

crc = crc32("Hello world!") # 461707669 (то же, что и выше)

В качестве необязательного второго параметра можно передать ранее вычисленный CRC. Результат получится такой, как если бы конкатенировать обе строки и вычислить CRC для объединения. Это полезно, например, когда нужно вычислить CRC файла настолько большого, что прочитать его можно только по частям.

2.35. Вычисление МD5-свертки строки

Алгоритм MD5 вырабатывает 128-разрядный цифровой отпечаток или дайджест сообщения произвольной длины. Это разновидность свертки, то есть функция шифрования односторонняя, так что восстановить исходное сообщение по дайджесту невозможно. Для Ruby имеется расширение, реализующее MD5; интересующиеся могут найти его в каталоге ext/md5 стандартного дистрибутива.

Для создания нового объекта MD5 есть два эквивалентных метода класса: new и md5:

require 'md5'

hash = MD5.md5

hash = MD5.new

Есть также четыре метода экземпляра: clone, digest, hexdigest и update. Метод clone просто копирует существующий объект, а метод update добавляет новые данные к объекту:

hash.update("Дополнительная информация...")

Можно создать объект и передать ему данные за одну операцию:

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

Если задан строковый аргумент, он добавляется к объекту путем обращения к методу 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)

  # Инициализировать первую колонку.