您可能已经注意到我们现在在社区Wiki帖子上显示编辑摘要:
社区维基
220修订版,48位用户
我还想向"最拥有"页面上显示的最终内容的用户显示剩余文本的百分比:
社区维基
220次修订,48位用户
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个修订版.谁是"老板"？
/sf/ask/17360801/
单击"查看源"以获取每个修订的原始文本.
我应该警告你,纯算法解决方案可能最终成为最长公共子串问题的一种形式.但正如我所提到的,如果它们运作良好,近似值和估计值也很好.
欢迎任何语言的解决方案,但我更喜欢的解决方案
相当容易翻译成c#.
没有依赖.
在效率之前放简单.
SO上的帖子超过25次修订是非常罕见的.但它应该"感觉"准确,所以如果你对编辑进行观察,你就会同意最终的决定.我鼓励您在具有修订历史的堆栈溢出帖子上测试您的算法,看看您是否同意最终输出.
我现在已经部署了以下近似值,您可以在社区Wiki帖子中查看每个新保存的修订版
做一个基于行的DIFF每修订,其中正文变化
将每个修订版的插入和删除行相加为"editcount"
每个userid获得他们贡献的"editcount"的总和
第一修订作者获得2x*"editcount"作为初始分数,作为主要作者奖金
确定最终所有权百分比:每个用户编辑的行数总计除以所有修订版中编辑行的总数
(对于常见的简单条件,例如1个版本,只有1个作者,等等也有一些保护条款.基于行的差异使得所有修订的重新计算速度相当快;在典型的情况下,例如10个修订版,它是〜50ms.)
这在我的测试中运行得相当好.当你有几个人编辑的1或2个小帖子时,它会分解一点,但我认为这是不可避免的.接受Joel Neely的回答是最接近我的精神,并且赞同其他一切似乎可行的东西.
我认为这个想法存在根本缺陷.
如果有人用可怕的拼写和不清楚的例子写出精彩的分析,并且我复制了大量的编辑,我创作了60%的作品吗？显然不是; 结果是衍生品,其中大部分价值来自初始海报.基于字符或单词计数不可能有用的措施,但需要强大的AI级语义分析.
除此之外,根据文章的"所有权"寻求信贷可能完全没有帮助和反维基.例如,在维基百科上,表现得好像拥有文章的人是最具破坏性的影响之一.
早点看到你的推文.从327973链接的显示中可以看出,您已经有了单步差异.基于此,我将专注于多编辑组合:
A,原始海报拥有该职位的100%.
当第二张海报B进行编辑时,例如90%的文本不变,所有权为A:90%,B:10%.
现在C,第三方,改变了50%的文本.(答:45%,B:5%,C:50%)
换句话说,当海报进行编辑以使x%改变并且y =(100-x)%不变时,那么该海报现在拥有文本的x%并且所有先前的所有权乘以y%.
为了让它变得有趣,现在假设......
A进行20%的编辑.然后A拥有"新"20%,剩余所有权现在乘以80%,留下(A:36%,B:4%,C:40%).因此,"净"所有权(A:56%,B:4%,C:40%).
将其应用于您的样本(327973),所有内容均四舍五入到最接近的百分比:
版本0:原始帖子.
保罗·奥斯特:100%
版本1:您当前的差异工具显示纯文本添加,因此所有这些字符都属于第二张海报.
保罗·奥斯特:91%
onebyone:9%
版本2:差异显示单词的替换.新单词属于第三张海报,其余文字属于先前的海报.
保罗·奥伊斯特:90%
onebyone:9%
Blogbeard:1%
版本3:仅标记编辑.由于你的问题是关于文本,我忽略了标签.
保罗·奥伊斯特:90%
onebyone:9%
Blogbeard:1%
第4版:增加文字.
保罗·奥斯特:45%
onebyone:4%
Blogbeard:1%
马克哈里森:50%
我希望这足以让人理解这个提议.它确实有一些限制,但我在你的声明中将这些限制在可接受的近似值中.;-)
它粗暴地强制分配所有先前所有者的变更效果.如果A帖子,B做了纯粹的添加,并且C编辑了B添加的一半,这种简单的方法只是在整个帖子中应用C的所有权,而不试图解析哪个以前的所有权变更最大.
它考虑了添加或更改,但没有为删除提供任何所有权信用,因为删除器会将剩余文本添加0%.您可以将此视为错误或功能.我选择了2号门.
更新:更多关于上面的问题#1.我认为完全跟踪编辑的帖子部分的所有权将需要两件事之一(网页的边缘不足以进行正式证明;-):
更改文本的存储方式以反映文本各个部分的所有权(例如A拥有单词1-47,B拥有单词48-59,A拥有单词60-94,......),应用"剩余多少"在我的提案中处理每个部分,并更新部分所有权数据.
考虑从第一个到最新的所有版本(实际上,即时重新计算部分所有权数据).
所以这是一个很好的例子,可以在快速和肮脏的近似(以精度为代价),整个数据库的更改(以空间为代价)之间进行权衡,或者每次计算都必须考虑整个历史(以时间为代价).
这是我看到示例帖子的所有权的方式(注意,我忘了在文本中添加标签,因此这个示例中不会计算简单的标签更改,但可以轻松添加):
Slap额头:伙计,我使用了修订号而不是用户号.结果重做如下:
User 38193 owns 42% (922 / 2171) of the final post User 2635 owns 28% (625 / 2171) of the final post User 116 owns 24% (529 / 2171) of the final post User 745 owns 3% (76 / 2171) of the final post User 13005 owns 0% (11 / 2171) of the final post User 18941 owns 0% (5 / 2171) of the final post User 8562 owns 0% (3 / 2171) of the final post 53 ms
因此根据我的算法,用户38193(@ Paul Oyster)拥有42%的帖子,而2635(@ Simucal)拥有28%,而用户116(@Mark Harrison)拥有24%,其余的可以忽略不计.
从修订版中,我们可以看到保罗作为原作者,仍然拥有大部分问题,而Simucal和Mark的表现也很好.这些对应于修订版nr.1(原帖),nr.14,这是Simucal的大型编辑,看起来它很好地显示了我的算法中的缺陷(见下文),并且nr.5 Mark添加了bash脚本.
那我怎么得到这个答案呢？嗯,这个算法有一个缺陷,但我会回过头来看,但这是怎么回事:
基本上,原始帖子中的每个字节都被分配了写入它的用户的用户ID.然后我使用一个可以无序处理副本的diff算法,然后将带来新作者复制的字节的用户id.由新作者添加的任何内容都将分配新作者的用户ID.
例如,如果原作者写了两个句子,那么这些句子将用他的用户ID标记.然后另一位作者修改它并在原来的两个之间添加第三个句子.对于diff算法,这看起来像新作者复制了第一个句子,添加了新数据,并复制了第二个句子.因此,句子将正确归因于他们的作者.
由于diff算法适用于字节,因此添加缺少的标点符号或字母等较小的文本更改对所有权的影响可以忽略不计,并且几乎所有原始文本仍应归于原始作者.但是,在某些情况下,由于内部优化,即使只添加了一个字节,它也会使用"添加数据"操作.该算法及其实现最初是为了处理文件差异而创建的,并且在文件版本之间产生尽可能小的补丁,并且有时会优化掉小步骤,如果它将减小文件大小,则将其组合成兄弟操作.
算法中的缺陷来自回滚.我注意到Jeff在评论中写道不会考虑回滚,但是如果用户编辑帖子而不是回滚,只是粘贴旧的东西,实际上反转前一作者的更改,那么所有文本归因于"回滚"的人,而不是提出信息的原始作者.
对于Visual Studio 2008,可以在此处找到此实现的源代码.请注意,该解决方案不执行任何类似于screenscrape或任何操作的内容,并且post内容被硬编码到TestData类的源代码中,正确转义为引号等要替换文本,您需要更改该文件,或实现从程序外部读取内容的方法.
无论如何,这里的算法更详细一些.
创建一个整数数组,只要原始版本(实际上,我通过UTF8将其编码为字节,这是我使用的长度).使用原始作者的用户ID填充此数组,他现在拥有100%的修订版本,每个字符/字节都是他的
将第一个修订与下一个修订进行比较.这种比较将产生一系列操作.这些操作可用于获取原始修订版本,将操作应用于此版本,您将获得下一版本(下面将详细介绍).
假设原始帖子是您准备的用户ID数组(当前只包含一堆等于第一作者ID的值),并将操作应用于此.这将产生一个新的id列表,其中一些将是原作者,一些将是第二作者.
保留第二个修订版本和用户ID的新列表,并在此数据与下一个修订版本和下一个修订版本等之间运行步骤2 + 3,直到您到达底部
此时,您有一个用户ID列表,告诉您哪个用户添加了每个字符.
比较的操作是两个中的一个:
插入新字节
复制一些字节
如何使用比较结果是您获取旧内容(第一篇文章),并将操作应用于它,然后生成下一个修订版.它基本上是一个差异.
当我将操作应用到我的用户ID列表时,当我复制时,我只是复制,当我插入时,我总是插入一些id等于操作中存储的长度.
让我举个例子:
原帖:
This is the first post
下一篇文章:
This is the next post, it is based on the first post.
因此,操作清单将是:
复制12个字符'这是'
插入'下一个'
复制5个字符'发布'
插入17个字符',它基于'
复制14个字符'第一篇文章'
插入1个字符'.'
如果我改为使用用户ID,我会先得到这个数组:
0000000000000000000000 This is the first post
现在我应用操作,对于每个插入,我插入1代替:
00000000000011110000011111111111111111000000000000001 This is the next post, it is based on the first post.
现在我只计算我有多少0和1:
0:31
1:22
用户0拥有该帖子的31 /(31 + 22),而用户1拥有该帖子的22 /(31 + 22).
转换为百分比:用户0拥有58%,用户1拥有42%.
现在,此算法的问题是回滚,并添加丢失/删除的内容.
例如,如果您有用户A,B和C,并且用户A发布了真正勾选用户B的内容,则用户B进入并删除所有内容,并添加"这就是CRAP".当用户C看到这个时,他编辑了帖子,并添加了A发布的所有内容,可能还有修复内容.用户C现在拥有该帖子的100%.
我不知道如何解决上述问题.
如果有意思的话,我会在今晚晚些时候发布代码.
应用于'quick brown fox'示例,将用户重新编号为1-3,我得到:
User 3 owns 75% (45 / 60) of the final post User 1 owns 25% (15 / 60) of the final post
请注意,从列表中删除了仅添加了"有时"部分的用户2,该部分随后被删除.
帖子的ID是这样的:
The quick brown fox jumps over the lazy dog. 11111111111111111111111111111111111111111111 (44 = 100%) The quick brown fox jumps, sometimes. 1111111111111111111111111222222222222 (25 / 12 ~ 68% / 32%) I always see the speedy brown fox jumping over the lazy dog. 333333333333333333333331111111111111113333333333333333333333 (45 / 15 = 75% / 25%)
算法将应对的事情:
如果我在制作新帖子时复制了某些内容,算法将正确归因于复制的元素,即使我现在复制了我也添加的部分内容.例:
This is the first post, which is cool
1111111111111111111111111111111111111
This is the second post, which is the second post.
11111111111122222211111111111111112222222222111111
^-- copied ------^
这个算法的唯一问题,这个帖子的全部内容是我不完全确定它会产生我称之为直观公平的结果.它可能是,我只是将程序整合在一起,但是为了确定它是否真正产生了人们会接受的东西,可能需要进行大量和大量边缘情况的测试.
另外,如果我只是简单地从最初的帖子中移动东西,那么只有少数几个,就像我的一样.由于该算法本质上是一种差异算法,有时输出复制操作仅1或几个字节的成本超过了插入原始数据的成本,因此有时它会将插入的短字节序列处理掉,他们可以从原帖复制.
京公网安备 11010802040832号 | 京ICP备19059560号-6 