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

с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 (стоимость вставки = стоимость удаления).

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

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

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

class String

 def detab(ts=8)

  str = self.dup

  while (leftmost = str.index("\t")) != 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

    if temp =~ /+/

     match=Regexp.last_match[0]

     endmatch = Regexp.new(match+"$")

     if match.length>1

      temp.sub!(endmatch,"\t")

     end

    end

   end

   newstr += temp

  end

  newstr

 end

end

foo = "Это всего лишь тест. "

puts foo

puts foo.entab(4)

puts foo.entab(4).dump

Отметим, что этот код не распознает символы забоя.

2.40. Цитирование текста

Иногда бывает необходимо напечатать длинные строки текста, задав ширину поля. Приведенный ниже код решает эту задачу, разбивая текст по границам слов и учитывая символы табуляции (но символы забоя не учитываются, а табуляция не сохраняется):

str = <<-EOF

  When in the Course of human events it becomes necessary

  for one people to dissolve the political bands which have

  connected them with another, and to assume among the powers

  of the earth the separate and equal station to which the Laws

  of Nature and of Nature's God entitle them, a decent respect

  for the opinions of mankind requires that they should declare the

  causes which impel them to the separation.

EOF

max = 20

line = 0

out = [""]

input = str.gsub(/\n/, " ")

words = input.split(" ")

while input ! = ""

 word = words.shift

 break if not word

 if out[line].length + word.length > max

  out[line].squeeze!(" ")

  line += 1

  out[line] = ""

 end

 out[line] << word + " "

end

out.each {|line| puts line} # Печатает 24 очень коротких строки.

Библиотека Format решает как эту, так и много других схожих задач. Поищите ее в сети.

2.41. Заключение

Мы обсудили основы представления строк (заключенных в одиночные или двойные кавычки). Поговорили о том, как интерполировать выражения в строку в двойных кавычках; узнали, что в таких строках допустимы некоторые специальные символы, представленные управляющими последовательностями. Кроме того, мы познакомились с конструкциями %q и %Q, которые позволяют нам по своему вкусу выбирать ограничители. Наконец, рассмотрели синтаксис встроенных документов, унаследованных из старых продуктов, в том числе командных интерпретаторов в UNIX.

В этой главе были продемонстрированы все наиболее важные операции, которые программисты обычно выполняют над строками: конкатенация, поиск, извлечение подстрок, разбиение на лексемы и т.д. Мы видели, как можно кодировать строки (например, по алгоритму base64) и сжимать их.

Пришло время перейти к тесно связанной со строками теме — регулярным выражениям. Регулярные выражения — это мощное средства сопоставления строк с образцами. Мы рассмотрим их в следующей главе.

Глава 3. Регулярные выражения

Я провела бы его по лабиринту, где тропы орнаментом украшены…

Мощь регулярных выражений как инструмента программирования часто недооценивается. Первые теоретические исследования на эту тему датируются сороковыми годами прошлого века, в вычислительные системы они проникли в 1960-х годах, а затем были включены в различные инструментальные средства операционной системы UNIX. В 1990-х годах популярность языка Perl привела к тому, что регулярные выражения вошли в обиход, перестав быть уделом бородатых гуру