投稿例の所有権を確認する方法を次に示します (注: テキストにタグを追加するのをまったく忘れたため、この例では単純なタグの変更はカウントされませんが、簡単に追加できます)。
額を平手打ち: おい、ユーザー番号の代わりにリビジョン番号を使った。結果は以下に書き直されました:
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% を所有しており、残りは無視できます。
改訂版から、元の著者である Paul がまだ問題のほとんどを所有しており、Simucal と Mark が適切な nr. に参加していることがわかります。2 および 3。これらはリビジョン番号に対応します。1 (元の投稿)、番号。14、これは Simucal による大規模な編集であり、私のアルゴリズムの欠陥を非常によく示しているように見えます (以下を参照)。5 マークが bash スクリプトを追加した場所。
では、どうやってこの答えにたどり着いたのでしょうか。アルゴリズムには欠陥がありますが、それについては後で説明しますが、その方法は次のとおりです。
基本的に、元の投稿の各バイトには、それを書いたユーザーのユーザー ID が割り当てられます。次に、順不同でコピーを処理できる diff アルゴリズムを使用します。これにより、新しい作成者によってコピーされたバイトのユーザー ID が取得されます。新しい作成者によって追加されたものにはすべて、新しい作成者のユーザー ID が割り当てられます。
たとえば、元の著者が 2 つの文を書いた場合、これらは彼のユーザー ID でタグ付けされます。その後、別の著者がそれを修正し、元の 2 つの文の間に 3 番目の文を追加します。diff アルゴリズムにとって、これは新しい作成者が最初の文をコピーし、新しいデータを追加し、2 番目の文をコピーしたように見えます。したがって、文はその作成者に正しく帰属します。
diff アルゴリズムはバイト単位で機能するため、句読点の欠落や文字の追加などの小さなテキストの変更は所有権にほとんど影響を与えず、ほとんどすべての元のテキストは元の作成者に帰属するはずです。ただし、内部の最適化により、1 バイトだけ追加された場合でも、「追加データ」操作を使用する場合があります。アルゴリズムとその実装は、ファイルの差分を処理し、ファイル バージョン間で可能な限り最小のパッチを生成するために最初に作成されました。
アルゴリズムの欠陥は、ロールバックに起因します。Jeff がロールバックは考慮されないというコメントを書いていることに注意してください。ただし、ユーザーが投稿をロールバックする代わりに編集し、古いものを貼り付けるだけの場合、事実上、前の作成者による変更が元に戻されます。テキストは、情報を思いついた元の作成者ではなく、「ロールバック」した人に起因します。
この実装のソース コードは、Visual Studio 2008 の場合、ここにあります。このソリューションでは、スクリーンスクレイプなどの処理は行われず、投稿の内容は TestData クラスのソースにハードコードされ、引用符などで適切にエスケープされることに注意してください。テキストを置き換えるには、そのファイルを変更するか、プログラムの外部からコンテンツを読み取る方法を実装する必要があります。
とにかく、アルゴリズムをもう少し詳しく説明します。
- 元のリビジョンと同じ長さの整数の配列を作成します (実際には、UTF8 を使用してバイトにエンコードしました。これが使用した長さです)。この配列に元の作成者のユーザー ID を入力し、元の作成者が現在リビジョンの 100% を所有しています。すべての文字/バイトは彼のものです。
- 最初のリビジョンと次のリビジョンを比較します。この比較により、操作のリストが生成されます。これらの操作を使用して元のリビジョンを取得し、それに操作を適用すると、次のリビジョンを取得できます (詳細は後述)。
- 元の投稿が、準備したユーザー ID の配列 (現在、最初の作成者の ID に等しい値の束のみを含むもの) であると仮定し、これに操作を適用します。これにより、ID の新しいリストが生成されます。そのうちのいくつかは最初の作成者であり、いくつかは 2 番目の作成者になります。
- 2 番目のリビジョンとユーザー ID のこの新しいリストを保持し、このデータ、次のリビジョン、次のリビジョンなどの間でステップ 2 + 3 を最後まで実行します。
この時点で、どのユーザーが各文字を追加したかを示すユーザー ID のリストが表示されます。
比較による操作は、次の 2 つのいずれかです。
- 新しいバイトを挿入
- いくつかのバイトをコピーします
比較結果の使い方は、古いコンテンツ（最初の投稿）に操作を適用して、次のリビジョンを作成するというものです。基本的に差分です。
操作をユーザー ID のリストに適用する場合、コピーする場合は単純にコピーし、挿入する場合は常に、操作に格納されている長さと同じ数の ID を挿入します。
例を挙げましょう：
元の投稿:
This is the first post
次の投稿:
This is the next post, it is based on the first post.
したがって、操作のリストは次のようになります。
- コピー 12 文字 'This is the '
- 「次」を挿入
- 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 は入ってすべてを削除し、「THIS IS CRAP」だけを追加します。ユーザー C はこれを見て、投稿を編集し、A が投稿したものすべてを追加して、場合によっては修正します。ユーザー C は現在、投稿の 100% を所有しています。
しかし、上記の問題を解決する方法がわかりません。
興味深い場合は、今夜遅くにこれを行うコードを投稿します。
「クイック ブラウン フォックス」の例に適用して、ユーザーの番号を 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 バイトまたは数バイトのコピー操作を出力するコストが、それをそのまま挿入するコストを上回ることがあります。それらは元の投稿からコピーされた可能性があります。