Вот как я вижу право собственности на пример сообщения (обратите внимание, я вообще забыл добавить теги к тексту, поэтому простые изменения тегов здесь не учитываются, но могут быть легко добавлены):
Хлоп по лбу : Чувак, я использовал номера ревизий вместо номеров пользователей. Результаты переделаны ниже:
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 (@ Пол Ойстер ) владеет 42% поста, тогда как пост 2635 (@ Simucal ) имел 28%, а пользователь 116 ( @ Марк Харрисон ) имеет 24%, остальные незначительны.
Из ревизий мы можем видеть, что Павел, который является первоначальным автором, по-прежнему владеет большей частью вопроса, а Симукал и Марк приходят с хорошим номером. 2 и 3. Это соответствует редакции №. 1 (оригинальный пост), № 14, который является большим редактором Simucal, и который выглядит так, как будто он довольно неплохо показывает недостаток в моем алгоритме (см. Ниже), и nr. 5, где Марк добавил скрипт bash.
Так как я пришел к этому ответу? Ну, у алгоритма есть недостаток, но я вернусь к нему, но вот как это происходит:
Обычно каждому байту в исходном сообщении присваивается идентификатор пользователя, который его написал. Затем я использую алгоритм сравнения, который может обрабатывать копии не по порядку, что затем приведет к идентификатору пользователя байтов, скопированных новым автором. Любому добавленному новым автором присваивается идентификатор нового автора.
Например, если оригинальный автор напишет два предложения, они будут помечены его идентификатором пользователя. Затем другой автор пересматривает его и добавляет третье предложение между двумя оригиналами. Для алгоритма сравнения это выглядит так, как будто новый автор скопировал первое предложение, добавил новые данные и скопировал второе предложение. Таким образом, предложения будут правильно приписаны их авторам.
Поскольку алгоритм diff работает с байтами, незначительные текстовые изменения, такие как добавление пропущенных знаков препинания или букв, должны оказывать незначительное влияние на владение, и почти весь исходный текст по-прежнему следует отнести к первоначальному автору. Однако в некоторых случаях он будет использовать операцию «добавленные данные», даже если был добавлен только один байт из-за внутренней оптимизации. Алгоритм и его реализация изначально создавались для обработки различий в файлах и создания наименьших возможных исправлений между версиями файлов, а иногда оптимизируют незначительные шаги в пользу объединения его в одноуровневую операцию, если это уменьшит размер файла.
Ошибка в алгоритме происходит от отката. Я отмечаю, что Джефф написал в комментарии, что откаты не будут рассматриваться, но если пользователь редактирует сообщение, а не откатывает его, и просто вставляет старый материал, по сути, отменяя изменения предыдущего автора, тогда все текст приписывается человеку, «откатившемуся» вместо оригинального автора, который придумал информацию.
Исходный код для этой реализации можно найти здесь , для Visual Studio 2008. Обратите внимание, что решение не делает ничего похожего на скриншот или что-то в этом роде, а содержимое публикации жестко закодировано в исходном коде в Класс TestData, правильно экранированный для кавычек и т. Д. Чтобы заменить текст, вам нужно изменить этот файл или реализовать способ чтения содержимого извне программы.
Во всяком случае, вот алгоритм более подробно.
- Создайте массив целых чисел, если исходная ревизия (на самом деле, я закодировал его в байты через UTF8, и это длина, которую я использовал). Заполните этот массив идентификатором пользователя первоначального автора , теперь он владеет 100% ревизии, каждый символ / байт его
- Сравните первую ревизию со следующей ревизией. Это сравнение даст список операций. Эти операции можно использовать для получения исходной ревизии, применения к ней операций, и вы получите следующую ревизию (подробнее об этом ниже).
- Представьте, что исходный пост - это массив подготовленных вами идентификаторов пользователей (который в настоящее время содержит только набор значений, равных идентификатору первого автора), и примените к нему операции. Это создаст новый список идентификаторов, некоторые из них будут первоначальным автором, некоторые будут вторым автором.
- Сохраняйте вторую ревизию и этот новый список идентификаторов пользователей и выполняйте шаги 2 + 3 между этими данными, следующей ревизией, следующей ревизией и т. Д., Пока не дойдете до дна
На данный момент у вас есть список идентификаторов пользователей, который сообщает вам, какой пользователь добавил каждый символ.
Операции из сравнения - одна из двух:
- Вставить новые байты
- Скопировать несколько байтов
Как используется результат сравнения, вы берете старое содержимое (первое сообщение) и применяете к нему операции, а затем производите следующую ревизию. Это в основном diff.
Когда я применяю операции к своему списку идентификаторов пользователей, когда я копирую, я просто копирую, когда вставляю, я всегда вставляю количество идентификаторов, равное длине, сохраненной в операции.
Позвольте мне привести пример:
Оригинальное сообщение:
This is the first post
Следующее сообщение:
This is the next post, it is based on the first post.
Список операций будет таким:
- Копировать 12 символов 'Это'
- Вставить «следующий»
- Скопируйте 5 символов 'post'
- Вставьте 17 символов ', он основан на'
- Скопируйте 14 символов 'первый пост'
- Вставить 1 символ '.'
Если бы я вместо этого работал с идентификаторами пользователя, я бы сначала получил этот массив:
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 * 1100 *
Пользователь 0 владеет 31 / (31 + 22) постом, а пользователь 1 владеет 22 / (31 + 22) постом.
Переводится в процентах: пользователю 0 принадлежит 58%, пользователю 1 принадлежит 42%.
Теперь проблема с этим алгоритмом заключается в откатах и добавлении обратно потерянного / удаленного контента.
Например, если у вас есть пользователи A, B и C, и пользователь A публикует что-то, что действительно отключает пользователя B, пользователь B входит и удаляет все, и добавляет просто «ЭТО СЛУЧАЙ». Когда пользователь 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, который добавил только часть «иногда», которая впоследствии была удалена, удаляется из списка.
Идентификаторы сообщений:
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 ------^
Единственная проблема с этим алгоритмом, и этот пост полностью состоит в том, что я не совсем уверен, что он дает то, что я бы назвал интуитивно честным результатом. Может быть, я только что взломал программу, но гораздо больше тестов с большим количеством крайних случаев, вероятно, было бы для того, чтобы определить, действительно ли она производит то, что люди примут.
Кроме того, если я просто перенесу материал с начального поста, только второстепенные кусочки, например, несколько процентов, будут моими. Поскольку в основе лежит алгоритм diff-алгоритма, иногда стоимость вывода операции копирования всего за 1 или пару байтов перевешивает стоимость простой вставки необработанного кода, поэтому иногда он будет обрабатывать короткую последовательность байтов как вставленную, хотя они могли быть скопированы из исходного поста.