algorithm - 判断多用户编辑文本 "Owner"

Question

您可能已经注意到我们现在在社区 Wiki 帖子上显示编辑摘要:

community wiki
220 revisions, 48 users

我还想显示“最拥有”页面上显示的最终内容的用户，作为剩余文本的百分比:

community wiki
220 revisions, 48 users
kronoz 87%

是的，可能有前 (n) 个“所有者”，但现在我想要前 1 个。

假设您有这个数据结构，一个按发布时间顺序排列的用户/文本对列表:

User Id     Post-Text-------     ---------12          The quick brown fox jumps over the lazy dog.27          The quick brown fox jumps, sometimes.30          I always see the speedy brown fox jumping over the lazy dog.

哪些用户最“拥有”最终文本？

我正在寻找一个合理的算法——它可以是一个近似值，它不一定是完美的——来确定所有者。理想情况下以百分比分数表示。

请注意，我们需要考虑编辑、删除和插入，以便最终结果感觉合理且正确。您可以使用任何具有良好修订历史记录的 stackoverflow 帖子(不仅仅是重新标记，而是频繁的帖子正文更改)作为测试语料库。这是一个很好的版本，有来自 14 位不同作者的 15 次修订。谁是“主人”？

https://stackoverflow.com/revisions/327973/list

单击“查看源代码”以获取每个修订版的原始文本。

我应该警告您，纯算法解决方案最终可能会成为 Longest Common Substring Problem 的一种形式。 .但正如我所提到的，近似值和估计值如果运行良好也很好。

欢迎使用任何语言的解决方案，但我更喜欢这样的解决方案

1. 相当容易翻译成 c#。
2. 没有依赖性。
3. 将简单置于效率之前。

关于 SO 的帖子有超过 25 次修订是非常罕见的。但它应该“感觉”准确，所以如果你仔细观察了编辑，你就会同意最终决定。我鼓励您在具有修订历史记录的堆栈溢出帖子上测试您的算法，看看您是否同意最终输出。

---

我现在已经部署了以下近似值，您可以在社区 Wiki 帖子上看到每个新保存的修订版的实际效果

• 做一个line based diff正文更改的每个修订版
• 将每个修订的插入和删除行加起来为“editcount”
• 每个 userid 得到他们贡献的“editcount”的总和
• 第一修订作者获得 2x *“editcount”作为初始分数，作为主要作者奖金
• 确定最终所有权百分比:每个用户的总编辑行数除以所有修订中的总编辑行数

(对于常见的简单条件也有一些保护条款，例如 1 个修订版，只有 1 个作者，等等。基于行的差异使得重新计算所有修订版的速度相当快；在典型情况下，例如 10 个修订版，它是 ~50 毫秒.)

这在我的测试中效果很好。当你有几个人编辑的 1 行或 2 行小帖子时，它确实会有点崩溃，但我认为这是不可避免的。接受乔尔·尼利 (Joel Neely) 的回答，认为它在精神上与我所接受的最接近，并对其他似乎可行的所有内容投了赞成票。

Answer 1

我认为这个想法存在根本性缺陷。

如果有人写了一篇精彩的分析，但拼写糟糕且示例不明确，而我对其进行了大量复制编辑，那么我是否完成了 60% 的工作？显然不是；结果是衍生品，其中大部分值(value)来自初始发布者。基于字符数或字数不可能进行有用的衡量，但需要强大的 AI 级语义分析。

除此之外，基于文章的“所有权”寻求信用可能完全没有帮助并且反维基。例如，在维基百科上，表现得好像自己拥有文章的人是最具破坏性的影响之一。