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

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

"Files, A".upto "Files, X" do | letter |

 puts "Opening: #{letter}"

end

# Выводится 24 строки.

Еще раз подчеркнем, что эта возможность используется редко, да и то на ваш страх и риск. Кстати, метода, возвращающего «предшествующую» строку, не существует.

2.34. Вычисление 32-разрядного CRC

Контрольный код циклической избыточности (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)