Книга: Программирование на языке Ruby
2.36. Вычисление расстояния Левенштейна между двумя строками
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.1. Представление обычных строк
- 2.2. Альтернативная нотация для представления строк
- 2.3. Встроенные документы
- 2.4. Получение длины строки
- 2.5. Построчная обработка
- 2.6. Побайтовая обработка
- 2.7. Специализированное сравнение строк
- 2.8. Разбиение строки на лексемы
- 2.9. Форматирование строк
- 2.10. Строки в качестве объектов ввода/вывода
- 2.11. Управление регистром
- 2.12. Вычленение и замена подстрок
- 2.13. Подстановка в строках
- 2.14. Поиск в строке
- 2.15. Преобразование символов в коды ASCII и обратно
- 2.16. Явные и неявные преобразования
- 2.17. Дописывание в конец строки
- 2.18. Удаление хвостовых символов новой строки и прочих
- 2.19. Удаление лишних пропусков
- 2.20. Повтор строк
- 2.21. Включение выражений в строку
- 2.22. Отложенная интерполяция
- 2.23. Разбор данных, разделенных запятыми
- 2.24. Преобразование строки в число (десятичное или иное)
- 2.25. Кодирование и декодирование строк в кодировке rot13
- 2.26. Шифрование строк
- 2.27. Сжатие строк
- 2.28. Подсчет числа символов в строке
- 2.29. Обращение строки
- 2.30. Удаление дубликатов
- 2.31. Удаление заданных символов
- 2.32. Печать специальных символов
- 2.33. Генерирование последовательности строк
- 2.34. Вычисление 32-разрядного CRC
- 2.35. Вычисление МD5-свертки строки
- 2.36. Вычисление расстояния Левенштейна между двумя строками
- 2.37. base64-кодирование и декодирование
- 2.38. Кодирование и декодирование строк (uuencode/uudecode)
- 2.39. Замена символов табуляции пробелами и сворачивание пробелов в табуляторы
- 2.40. Цитирование текста
- 2.41. Заключение
- Миграция между различными версиями InterBase
- 3.4. Отношения между классами
- Мост между физической и логической структурой базы данных
- Работа со строками
- Глава 2 Вычисление
- Распределение функциональных обязанностей между должностями
- Правило 16. Группируйте связанные между собой элементы
- 6.4.2. Передача номенклатурных позиций между ячейками склада
- Как быстро переключаться между двумя пользователями, не закрывая их программ?
- Как узнать скорость соединения между компьютерами?
- Обмен данными между гостевой и хостовой ОС
- Как в документе Microsoft Word изменить расстояние между двумя словами?