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. Но для простоты мы не стали этого делать.
Алгоритм
Простейший способ осуществить 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 возвращает массив.
Префикс 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 возвращает массив.
Бывает, что имеется строка с символами табуляции, а мы хотели бы преобразовать их в пробелы (или наоборот). Ниже показаны два метода, реализующих эти операции:
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
Отметим, что этот код не распознает символы забоя.
Иногда бывает необходимо напечатать длинные строки текста, задав ширину поля. Приведенный ниже код решает эту задачу, разбивая текст по границам слов и учитывая символы табуляции (но символы забоя не учитываются, а табуляция не сохраняется):
str = <<-EOF
When in the Course of human events it becomes necessary