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

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

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 привела к тому, что регулярные выражения вошли в обиход, перестав быть уделом бородатых гуру

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

Во время работы над данной книгой язык Ruby находился в переходном состоянии. Старая библиотека регулярных выражений заменялась новой под названием Oniguruma. Этой библиотеке посвящен раздел 3.13 данной главы. Что касается интернационализации, то это тема главы 4.

3.1. Синтаксис регулярных выражений

Обычно регулярное выражение ограничено с двух сторон символами косой черты. Применяется также форма %r. В таблице 3.1 приведены примеры простых регулярных выражений:

Таблица 3.1. Простые регулярные выражения

Сразу после регулярного выражения можно поместить однобуквенный модификатор. В таблице 3.2 приведены наиболее часто употребляемые модификаторы.

Таблица 3.2. Модификаторы регулярных выражений

Дополнительные примеры будут рассмотрены в главе 4. Чтобы завершить введение в регулярные выражение, в таблице 3.3 мы приводим наиболее употребительные символы и обозначения.

Таблица 3.3. Общеупотребительные обозначения в регулярных выражениях

Умение работать с регулярными выражениями - большой плюс для современного программиста. Полное рассмотрение этой темы выходит далеко за рамки настоящей книги, но, если вам интересно, можете обратиться к книге Jeffrey Friedl, Mastering Regular Expressions.

Дополнительный материал вы также найдете в разделе 3.13.

3.2. Компиляция регулярных выражений

Для компиляции регулярных выражений предназначен метод Regexp.compile (синоним Regexp.new). Первый параметр обязателен, он может быть строкой или регулярным выражением. (Отметим, что если этот параметр является регулярным выражением с дополнительными флагами, то флаги не будут перенесены в новое откомпилированное выражение.)

pat1 = Regexp.compile("^foo.*") # /^foo.*/

pat2 = Regexp.compile(/bar$/i) # /bar/ (i не переносится)

Если второй параметр задан, обычно это поразрядное объединение (ИЛИ) каких-либо из следующих констант: Regexp::EXTENDED, Regexp::IGNORECASE, Regexp::MULTILINE. При этом любое отличное от nil значение приведет к тому, что регулярное выражение не будет различать регистры; мы рекомендуем опускать второй параметр.

options = Regexp::MULTILINE || Regexp::IGNORECASE

pat3 = Regexp.compile("^foo", options)

pat4 = Regexp.compile(/bar/, Regexp::IGNORECASE)

Третий параметр, если он задан, включает поддержку многобайтных символов. Он может принимать одно из четырех значений:

"N" или "n" означает отсутствие поддержки

"Е" или "е" означает EUC