Алгоритм сравнения символов / аннотаций - PullRequest
Новая
       5

Алгоритм сравнения символов / аннотаций

4 голосов
/ 22 февраля 2011

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

Мне нужен относительно эффективный алгоритм, позволяющий комментировать подстроки документа с версией, из которой они пришли.

Например, если история документа была такой: 

Rev1: The quiet fox
Rev2: The quiet brown fox
Rev3: The quick brown fox

Алгоритм даст: 

The quick brown fox
1111111331222222111

т.е.. «Qui» был добавлен в ревизии 1, «ck» был добавлен в ревизии 3, «» был добавлен в ревизии 1, «коричневый» был добавлен в ревизии 2 и, наконец, «fox» был добавлен в ревизии 1.

Ответы [ 3 ]

3 голосов
/ 22 февраля 2011

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

Библиотека находится здесь: DiffLib на CodePlex (вы также можете установить его через NuGet.)

Сценарий для вашего примера в вопросе находится здесь (вы можете запустить его в LINQPad , если добавите ссылку на сборку DiffLib): 

void Main()
{
    var revs = new string[]
    {
        "The quiet fox",
        "The quiet brown fox",
        "The quick brown fox",
        "The quick brown fox.",
        "The quick brown fox jumped over the lazy dog.",
        "The quick brown fox jumped over the lazy cat.",
        "The Quick Brown Fox jumped over the Lazy Cat.",
    };

    string current = revs[0];
    List<int> owner = new List<int>();
    foreach (char c in current)
        owner.Add(1); // owner 1 owns entire string

    Action<int> dumpRev = delegate(int rev)
    {
        Debug.WriteLine("rev " + rev);
        Debug.WriteLine(current);
        Debug.WriteLine(new string(owner.Select(i => (char)(48 + i)).ToArray()));
        Debug.WriteLine("");
    };
    dumpRev(0);

    for (int index = 1; index < revs.Length; index++)
    {
        int ownerId = index + 1;
        var diff = new DiffLib.Diff<char>(current, revs[index]).ToArray();
        int position = 0;
        foreach (var part in diff)
        {
            if (part.Equal)
                position += part.Length1;
            else
            {
                // get rid of old owner for the part that was
                // removed or replaced
                for (int index2 = 0; index2 < part.Length1; index2++)
                    owner.RemoveAt(position);

                // insert new owner for the part that was
                // added or did replace the old text
                for (int index2 = 0; index2 < part.Length2; index2++)
                    owner.Insert(position, ownerId);
                position += part.Length2;
            }
        }
        current = revs[index];
        dumpRev(index);
    }
}

Выход: 

rev 0
The quiet fox
1111111111111

rev 1
The quiet brown fox
1111111111222222111

rev 2
The quick brown fox
1111111331222222111

rev 3
The quick brown fox.
11111113312222221114

rev 4
The quick brown fox jumped over the lazy dog.
111111133122222211155555555555555555555555554

rev 5
The quick brown fox jumped over the lazy cat.
111111133122222211155555555555555555555556664

rev 6
The Quick Brown Fox jumped over the Lazy Cat.
111171133172222271155555555555555555755557664
1 голос
/ 22 февраля 2011

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

Вывод должен быть довольно тривиально преобразован в тот тип оценки, который вы хотите (патч назначения кредита за патчем).

0 голосов
/ 22 февраля 2011

Разве ваш формат истории уже не предоставляет эту информацию? Если так, то это просто вопрос отображения. Разумеется, наиболее эффективный метод будет зависеть от формата, в котором хранится ваша история, поэтому никто здесь не сможет предоставить это вам, не зная этого формата.

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

...