Comments 19
Было бы неплохо упомянуть автора алгоритма (D.S. Hirschberg) и источник.
Стоит отметить, что в случае естественных текстов предпочитают чуть расширенную версию: расстояние Дамерау-Левенштейна. Оно добавляет в список возможных операций транспозиции — перестановку двух соседних символов. Алгоритм, правда, несколько усложняется (просто добавить четвертый случай «если» недостаточно).
Дамерау показал, что перестановки соседних символов, пропуск символа, добавление нового символа, и ошибка в символе составляют 80% человеческих ошибок при наборе текстов. Таким образом, эту меру похожести слов можно отлично использовать в текстовых редакторах.
Дамерау показал, что перестановки соседних символов, пропуск символа, добавление нового символа, и ошибка в символе составляют 80% человеческих ошибок при наборе текстов. Таким образом, эту меру похожести слов можно отлично использовать в текстовых редакторах.
Хорошо расписано, спасибо.
Добавлю, что не только для текста можно использовать это расстояние, а, к примеру, для распознавания жестов мыши, о чем правда где-то на хабре уже писали.
Добавлю, что не только для текста можно использовать это расстояние, а, к примеру, для распознавания жестов мыши, о чем правда где-то на хабре уже писали.
Банальное табличное динамическое программирование.
В есть ли готовые библиотеки позволящие сравнивать строки на «близость»?
levenshtein distance + добавить нужный язык/технологию по вкусу.
А можно как-то из этого алгоритма получить diff?
Думаю, да — просто сравниваем не символы, а строки (например, хэшами) файла.
Собственно, так обычно diff-ы и работают (в tortoiseHG — точно): ищут Левенштейна, но в качестве «символов» выступают отдельные строки.
именно. а затем, после выполнения синхронизации строк производится сравнения между несовпадающими строками в соответствующих блоках уже посимвольно.
хотя вот майкрософтовская утилита fc (file compare) работает как-то по-другому и иногда дает очень странные результаты.
хотя вот майкрософтовская утилита fc (file compare) работает как-то по-другому и иногда дает очень странные результаты.
затем, после выполнения синхронизации строк производится сравнения между несовпадающими строками в соответствующих блоках уже посимвольно.
Ни разу не видел такого поведения. Обычно даже при добавлении пробела в конец строки просто считают, что изменилась вся строка, и не символ в ней. Или Вы имеете в виду способ хранения этих изменений во внутренностях репозитория? Тогда такое поведение вполне оправдано :).
когда уже свежий Кнут выйдет? )
у него вроде целый том о строках планируется…
у него вроде целый том о строках планируется…
Большое спасибо за статью.
Очень интересная статья, все разжевано и по полочкам разложено!
Еще один способ сэкономить память — упаковать нуклеотиды в биты.
Тогда в 1 байт войдет 4 нуклеотида (по 2 бита каждый) против 1 или 2 байт на один нуклеотид (в зависимости от кодировки)… Ну и битовые операции сдвига и сравнения по определению быстрее :)
Еще один способ сэкономить память — упаковать нуклеотиды в биты.
Тогда в 1 байт войдет 4 нуклеотида (по 2 бита каждый) против 1 или 2 байт на один нуклеотид (в зависимости от кодировки)… Ну и битовые операции сдвига и сравнения по определению быстрее :)
Мне кажется, у Вас в статье закралась ошибка. При склеивании решений Вы считаете сумму в колонке, соответствующей центральному символу, а нужно считать сумму «на стыке». Т.е. у Вас на первом шаге рассматриваются подзадачи (S1[0,6], S2) и (S1[6,11], S2), где буква C (зелёный столбец) входит в обе подзадачи. Склеивание таких решений не всегда работает корректно.
Рассмотрим такой пример:
S1 = ABYCAKZ
S2 = ABYZAKZ
Первая подзадача была бы такой: (ABYC, ABYZAKZ) и (CAKZ, ABYZAKZ).
Важно, что C входит в обе «половинки» первой строки, как это показано на Вашей картинке.
Теперь посмотрим на колонку соответствующую C.
Не сложно проверить, что в строке соответствующей Z будет достигнут минимум суммы стоимостей для следующих пар строк: (ABYX, ABYZ) и (XAKZ, ZAKZ).
Стоимость первой — 1, стоимость второй — 1. Суммарная стоимость — 2.
При этом оптимальное выравнивание
ABYXAKZ
ABYZAKZ
имеет стоимость 1, т.е. стоимость оптимального выравнивания мы не получили.
Это происходит из-за того, что Вы дважды посчитали одно и то же редактирование.
В оригинальном решении строки делятся пополам без общих символов и склеиваются на стыке строк.
Поправьте меня, если я не прав.
Рассмотрим такой пример:
S1 = ABYCAKZ
S2 = ABYZAKZ
Первая подзадача была бы такой: (ABYC, ABYZAKZ) и (CAKZ, ABYZAKZ).
Важно, что C входит в обе «половинки» первой строки, как это показано на Вашей картинке.
Теперь посмотрим на колонку соответствующую C.
Не сложно проверить, что в строке соответствующей Z будет достигнут минимум суммы стоимостей для следующих пар строк: (ABYX, ABYZ) и (XAKZ, ZAKZ).
Стоимость первой — 1, стоимость второй — 1. Суммарная стоимость — 2.
При этом оптимальное выравнивание
ABYXAKZ
ABYZAKZ
имеет стоимость 1, т.е. стоимость оптимального выравнивания мы не получили.
Это происходит из-за того, что Вы дважды посчитали одно и то же редактирование.
В оригинальном решении строки делятся пополам без общих символов и склеиваются на стыке строк.
Поправьте меня, если я не прав.
Посмотрел ещё раз на Вашу картинку внимательнее. Видимо, проблема в том, что правая синяя часть у Вас сдвинута на 1 вверх и 1 влево (у вас в правой части 4 нуля на диагонали, а должно быть три). Похоже, что за счёт сдвига у Вас получается правильное решение, но неправильная картинка: например, в ячейке (10,10) стоит ноль, а должна стоять единица.
(вместо C нужно читать X)
Sign up to leave a comment.
Вычисление редакционного расстояния