字符差异/注释算法

Question

字符差异/注释算法

4

我有一组字符串，表示文档的历史记录。每个字符串都是整个文档 - 还没有进行任何差异分析。

我需要一个相对高效的算法，可以让我注释文档的子字符串以及它们来自哪个版本。

例如，如果文档历史记录如下：

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

该算法将给出以下结果：

The quick brown fox
1111111331222222111

例如，“qui”在版本1中添加，“ck”在版本3中添加，“ ”在版本1中添加，“brown”在版本2中添加，最后“fox”在版本1中添加。

- ICR

这些文档是纯文本吗？ - Lasse V. Karlsen

是的，它们是纯文本的。在现实生活中，每个文档都是一个由大约500到2000个字符组成的纯文本字符串，包含大约5到200个版本修订。 - ICR

你能否上传或发布一个样例文档的压缩文件到某个地方？我有一个实现（我将在下面添加答案），我想对其进行测试。我已经成功复制了您的示例，但我想看看在典型数据集上的性能表现。 - Lasse V. Karlsen

当Rev4为“The quick brown fox and black fox”，而Rev5为“the quiet fox”时会发生什么？ - mhum

你找到你想要的了吗？ - Lasse V. Karlsen

3个回答

1

你想使用Google实现的Myers差异算法。它非常快速，并且有很多语言的实现，你可以提供超时值，以防止它在搜索复杂差异时浪费太多时间。

输出结果应该很容易转换为你所需的评分方式（逐个补丁进行信用分配）。

- Rex Kerr

0

你的“历史”格式已经提供了那些信息，不是吗？如果是这样的话，那么只需要显示它就可以了。当然，最有效的方法取决于你的历史记录存储的格式，所以没有人能在不知道这个格式的情况下为你提供更好的建议。

需要注意的是，如果你要将输出发送到某种显示设备(例如:屏幕)，那么一般来说，你的算法必须非常愚蠢才会比显示设备本身导致更大的延迟。

- T.E.D.

“历史”格式只是在特定版本中文档内容的有序集合。因此从给出的例子来看，历史记录为 ["The quiet fox", "The quiet brown fox", " The quick brown fox"]。这并不能很容易地展示信息，即最新版本的“fox”中的“f”是在第一版中添加的，而“brown”中的“b”是在第二版中添加的。 - ICR

@ICR - 所以它不仅仅是存储差异以节省空间吗？这是一个真实世界修订历史系统的典型设置。 - T.E.D.

原始文件可能会有。不幸的是，我只能查询特定版本的文档。我无法更改这个。 - ICR

@ICR - 我很难相信它会这样做，然后不提供您在两个版本之间获取“版本差异”的某种方式，因为这实际上比提取最新版本更少的工作量。 - T.E.D.

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Lasse V. Karlsen · Accepted Answer

我有一个类库可以轻松完成这个任务，但是我不知道它在处理大量或多个修订时的性能表现如何。

这个库在这里：DiffLib on CodePlex（你也可以通过NuGet安装）。

你问题中的示例脚本在这里（如果你添加对DiffLib程序集的引用，可以在LINQPad中运行它）：

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);
    }
}

输出结果:

版本 0
安静的狐狸
1111111111111
版本 1
安静的棕色狐狸
1111111111222222111
版本 2
敏捷的棕色狐狸
1111111331222222111
版本 3
敏捷的棕色狐狸。
11111113312222221114
版本 4
敏捷的棕色狐狸跳过懒狗。
111111133122222211155555555555555555555555554
版本 5
敏捷的棕色狐狸跳过懒猫。
111111133122222211155555555555555555555556664
版本 6
敏捷的棕色狐狸跳过懒猫。
111171133172222271155555555555555555755557664