Difference Algorithm and Its Variations

← →
Сайбель Алексей © (2006-04-18 11:56) [0]

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

Задача эта решались и не раз..
В total commander"e есть, или тот же diff в линуксе..

Есть у кого-нибудь описание алгоритма? на русском желательно
Вроде в у Бакнела в книге было что-то подобное..

Наковырял большой исходник diff на си, но там оптимизация, куча вообщем кода,
а тексты сравниваться будут небольшие,
поэтому интересует алгоритм собсно в лоб.

← →
MBo © (2006-04-18 11:58) [1]

>Вроде в у Бакнела в книге было что-то подобное..
Да, было, LCS - самая длинная общая подпоследовательность, но diff этим далеко не исчерпывается.

← →
Сайбель Алексей © (2006-04-18 12:31) [2]

MBo © [1]
Задача то у меня попроще, чем написать свой diff :O)

Т.е. оптимальное решение задачи сводится к поиску самой большой общей подпоследовательности в двух сравниваемых текстах?

← →
MBo © (2006-04-18 13:05) [3]

LCS не дает непосредственного ответа на вопрос о последовательности удалений и вставок.
кое-что можно посмотреть здесь:
http://algolist.manual.ru/search/index.php

← →
Ketmar © (2006-04-18 14:10) [4]

даёт, но с бубном. %-)

← →
kilkennyCat © (2006-04-18 14:29) [5]

> MBo © (18.04.06 13:05) [3]

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

← →
Ketmar © (2006-04-18 14:32) [6]

PPMd как вполне эффективнй метод сжатия текстов. и относительно просто реализуемый.

← →
kilkennyCat © (2006-04-18 14:53) [7]

> Ketmar © (18.04.06 14:32) [6]

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

← →
Ketmar © (2006-04-18 14:59) [8]

LZMA, BWT.

← →
kilkennyCat © (2006-04-18 15:12) [9]

> Ketmar © (18.04.06 14:59) [8]

неа.

предположим, весь текст состоит из кучи слов, имеющих один корень, который весит процентов 60 - 90 от слова. оптимальное сжатие будет, если выделить этот корень, все повторяющиеся приставки, суффиксы и окончания в одну таблицу, слова же превратить в ссылки на таблицу.
эффективность такого сжатия будет выше любого архиватора. под эффективностью в данном случае я подразумеваю оптимальное сочетание степени сжатия - скорости доступа в применении к моей задаче.
Опять же, предполагая, что у меня будут только маленькие буквы, только русский язык и прочие нюансы, позволяет написать специализированный, наиболее эффективный архиватор.
Нахождение самых длинных общих подпоследовательностей - это как раз один из кирпичиков... Сейчас изучим.

← →
MBo © (2006-04-18 15:46) [10]

kilkennyCat
бывал на http://compression.ru/ ?

А кто мешает посмотреть исходники diff ?

> Наковырял большой исходник diff на си, но там оптимизация,
> куча вообщем кода,
> а тексты сравниваться будут небольшие,
> поэтому интересует алгоритм собсно в лоб.

если небольшие, то алгоритм в лоб элементарно:

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

Заофтопили.. ))

2 Игорь Шевченко © [12]
Я [0]
Наковырял большой исходник diff на си, но там оптимизация, куча вообщем кода,
а тексты сравниваться будут небольшие,
поэтому интересует алгоритм собсно в лоб.

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

Алгоритмы на английском
http://www.xmailserver.org/diff2.pdf

Еще есть реализация на delphi open source
http://angusj.com/delphi/textdiff.html
Алгоритм автор запихнул в компонент TDiff

> Сайбель Алексей © (18.04.06 11:56)
> Поставили задачу - написать программу для нахождения различий
>
> (удаленные, добавленные строки) в двух текстах.

Если, действительно, только строки, делай проще...
Грузишь оба текста в 2 разных Tmemo
И в цикле сравниваешь
Дешево и сердито
:)))

Difference Algorithm and Its Variations Найти похожие ветки