Определение "Владелец" текста, измененного несколькими пользователями

Ответ 1

Пила твит раньше. С дисплея ссылки 327973, похоже, у вас уже есть одношаговый diff на месте. Исходя из этого, я сосредоточусь на многорежимной композиции:

• A, оригинальный плакат владеет 100% сообщения.

• Когда B, второй плакат, делает изменения, такие как, например, 90% текста не изменяется, право собственности составляет: 90%, B: 10%.

• Теперь C, третья сторона, изменяет 50% текста. (A: 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: diff показывает замену слова. Новое слово принадлежит третьему плакату, а оставшийся текст принадлежит предыдущим плакатам.

• Пол Ойстер: 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,...), применяя подход "сколько остается" в моем предложении каждой части и обновление данных о собственности на часть.

• Рассмотрение всех версий от первого до текущего (фактически, перераспределение данных о собственности на часть на лету).

Итак, это хороший пример компромисса между быстрым и грязным приближением (ценой точности), изменением всей базы данных (ценой пространства) или каждым вычислением, которое нужно смотреть на протяжении всей истории (за счет времени).

Ответ 2

Я думаю, что идея фундаментально испорчена.

Если кто-то пишет блестящий анализ с ужасными орфографическими и нечеткими примерами, и я скопирую его очень широко, я создал 60% работы? Ясно, что нет; результат - производная, где большая часть стоимости исходит от первоначального плаката. Полезная мера невозможна на основе количества символов или слов, но требует сильного семантического анализа уровня AI.

Кроме того, поиск кредита, основанного на "собственности" на статьи, скорее всего, будет абсолютно бесполезным и анти-вики. Например, в Википедии люди, которые действуют так, как будто они принадлежат к статьям, являются одним из самых разрушительных влияний.

Ответ 3

Вот как я вижу право собственности на пример сообщения (заметьте, я забыл добавлять теги к тексту вообще, поэтому простые изменения тегов здесь не учитываются, но их можно легко добавить):

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%, остальное - незначительно.

Из revisions мы видим, что Пол, являющийся оригинальным автором, по-прежнему владеет большинством вопросов, а Симукаль и Марк идут на хорошие Н.Р.. 2 и 3. Это соответствует ревизиям nr. 1 (исходное сообщение), nr. 14, который является большим редактированием Simucal, и похоже, что он довольно хорошо показывает недостаток в моем алгоритме (см. Ниже) и nr. 5, где Марк добавил bash script.

Итак, как я пришел к этому ответу? Ну, у алгоритма есть недостаток, но я вернусь к нему, но вот как оно идет:

В основном каждому байту в исходном сообщении присваивается идентификатор пользователя пользователя, который его написал. Затем я использую алгоритм diff, который может обрабатывать копии не по порядку, а затем вводит идентификатор пользователя байтов, скопированный новым автором. Все, что добавляет новый автор, присваивается идентификатору пользователя нового автора.

Например, если исходный автор пишет два предложения, они будут помечены его идентификатором пользователя. Затем другой автор пересматривает его и добавляет третье предложение между двумя оригиналами. Для алгоритма diff это похоже на то, что новый автор скопировал первое предложение, добавил новые данные и скопировал второе предложение. Таким образом, предложения будут правильно отнесены к их авторам.

Поскольку алгоритм diff работает на байтах, незначительные текстовые изменения, такие как добавление отсутствующих знаков пунктуации или букв, должны иметь незначительное влияние на право собственности, и почти весь исходный текст все равно должен быть отнесен к оригинальному автору. Однако в некоторых случаях он будет использовать операцию "добавленных данных", хотя был добавлен только один байт из-за внутренних оптимизаций. Алгоритм и его реализация были первоначально созданы для обработки различий файлов и создания наименьших возможных патчей между версиями файлов, а иногда оптимизируют незначительные шаги в пользу объединения его в операцию sibling, если это уменьшит размер файла.

Недостаток алгоритма исходит из откатов. Я отмечаю, что у Джеффа есть комментарий в комментарии о том, что откаты не будут рассмотрены, но если пользователь редактирует сообщение вместо того, чтобы откатывать его, и просто вставляет в старый материал, фактически изменяя изменения предыдущим автором, тогда все текст приписывается человеку "откат", а не оригинальному автору, который придумал эту информацию.

Исходный код этой реализации можно найти здесь, для Visual Studio 2008. Обратите внимание, что решение не делает ничего подобного скриншоту или что-либо еще, а содержимое сообщения жестко закодировано в исходный код в классе TestData, правильно экранировано для кавычек и т.д. Чтобы заменить текст, вам нужно изменить этот файл или реализовать способ чтения содержимого извне программы.

В любом случае, здесь алгоритм немного более подробно.

• Создайте массив целых чисел, пока исходная ревизия (фактически, я закодировал его в байтах через UTF8, и это длина, которую я использовал). Заполните этот массив идентификатором пользователя оригинального автора, которому он теперь владеет 100% версии, каждый символ/байт - это
• Сравните первую ревизию со следующей версией. Это сравнение даст список операций. Эти операции можно использовать для первоначальной ревизии, применить к ней операции, и вы получите следующую ревизию (подробнее об этом ниже).
• Притвориться, что исходное сообщение - это массив идентификатора пользователя, который вы подготовили (тот, который содержит только пучок значений, равный первому идентификатору автора) и применяет к нему операции. Это приведет к созданию нового списка идентификаторов, некоторые из них будут оригинальным автором, некоторые из них станут вторым автором.
• Сохраните вторую ревизию и этот новый список идентификаторов пользователя и пройдите через шаг 2 + 3 между этими данными и следующей ревизией, а затем следующую ревизию и т.д., пока не дойдете до нижней части

На этом этапе у вас есть список идентификаторов пользователя, который сообщает вам, какой пользователь добавил каждый символ.

Операции из сравнения являются одним из двух:

• Вставить новые байты
• Скопируйте несколько байтов

Как используется результат сравнения, вы берете старое содержимое (первое сообщение) и применяете к нему операции, а затем создаете следующую ревизию. Это в основном diff.

Когда я применяю операции к моему списку идентификаторов пользователя, когда я копирую, я просто копирую, когда я вставляю, я всегда вставляю число id, равное длине, хранящейся в операции.

Позвольте мне привести пример:

Оригинальное сообщение:

This is the first post

Следующая запись:

This is the next post, it is based on the first post.

Таким образом, список операций будет следующим:

• Скопировать 12 символов 'Это'
• Вставить 'next'
• Скопировать 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's: 31
• 1's: 22

Пользователь 0 владеет 31/(31 + 22) сообщения, а пользователю 1 принадлежит 22/(31 + 22) сообщения.

Переведено в проценты: пользователю 0 принадлежит 58%, пользователю 1 принадлежит 42%.

Теперь проблема с этим алгоритмом заключается в откатах и ​​добавлении обратно потерянного/удаленного содержимого.

Например, если у вас есть пользователи A, B и C, а пользователь A размещает то, что действительно отключает пользователя B, пользователь B входит и удаляет все, и добавляет только "ЭТО ТАКОЙ 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, который только добавил часть "иногда", которая впоследствии была удалена, удаляется из списка.

Идентификатор для сообщений таков:

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 или пару байтов перевешивает стоимость просто вставки ее в исходное состояние, поэтому иногда она обрабатывает короткую последовательность байтов как вставленную, хотя они могли быть скопированы с оригинального сообщения.

Ответ 4

Если я правильно понимаю ваш вопрос, похоже, вы пытаетесь сделать то, что IBM еще раз провела с исследовательским проектом в Википедии. А именно, видя, кто пересматривает текст, где наиболее приемлемы другие пользователи и как общий текст со временем менялся. Название проекта поток истории и поток истории - как он работает дает довольно хороший обзор того, как работает их алгоритм.

Ответ 5

Как насчет простого вычисления расстояние Левенштейна каждого человека, отредактировавшего предыдущую версию. Затем суммируйте оценки расстояния для каждого пользователя и вычислите процент пользователя от суммы оценок всех пользователей.

Здесь некоторый код С# для вычисления расстояний.

Ответ 6

Сверху моей головы я бы сделал что-то вроде этого:

• Я думаю, что подсчет слов в отличие от строк или символов имеет смысл
• Обозначьте исходную версию в словах и присоедините автора к каждому
• Пройдите через историю изменений и добавьте слова, присоедините к ним автора.
• Если слова удалены, просто забудьте их.
• Если слова изменены, вы можете считать их как delete/insert или иметь какой-то порог, основанный на символах, так что исправления орфографии не приписываются новому автору.
• В итоге вы получите список слов о том, кто изначально написал их.

Ответ 7

Это будет работать, если вы хотите реализовать/использовать алгоритм diff ala Python difflib - вам, вероятно, придется в какой-то мере выполнять какой-либо diff. Этот фрагмент вызывает пользователя с наибольшим оттоком текста победителем.

Извините мое hardcoding.

#!/usr/bin/env python

import collections
import difflib
import logging
import pprint
import urllib2
import re

class OwnageDeterminer(object):

    add_coefficient = 1
    remove_coefficient = .5

    def __init__(self, edits):
        self.edits = edits
        self.counts_by_username = {}

    def __call__(self):
        edits, counts_by_username = self.edits, self.counts_by_username
        for i, edit in enumerate(edits):
            username = edit['username']
            unique_counts = {'added': 0, 'removed': 0}
            existing_text = edits[i-1]['text'] if i > 0 else ''
            new_text = edits[i]['text']
            for char_diff in difflib.ndiff(existing_text, new_text):
                if char_diff.startswith('+'):
                    unique_counts['added'] += 1
                elif char_diff.startswith('-'):
                    unique_counts['removed'] += 1
            user_counts = counts_by_username.get(username, collections.defaultdict(int))
            user_counts['removed'] += self.remove_coefficient * unique_counts['removed']
            user_counts['added'] += self.add_coefficient * unique_counts['added']
            counts_by_username[username] = user_counts
        winner = None
        winning_score = 0
        score_by_username = {}
        for username, counts in counts_by_username.iteritems():
            score = counts['removed'] + counts['added']
            if score > winning_score:
                winner = username
                winning_score = score
            score_by_username[username] = score
        logging.debug('Scores: %s', pprint.pformat(score_by_username))
        return winner


if __name__ == '__main__':
    logging.basicConfig(level=logging.DEBUG)
    site = urllib2.urlopen('http://stackoverflow.com/revisions/327973/list')
    contents = site.read()
    regex = re.compile(r'(/revisions/viewmarkup/\d+).*?/users/\d+/([\w-]+)',
                       re.MULTILINE|re.DOTALL)
    revisions = regex.findall(contents)
    print revisions
    edits = []
    for reluri, username in sorted(revisions, key=lambda t: t[0]):
        text = urllib2.urlopen('http://stackoverflow.com{0}'.format(reluri)).read()
        edit = {'username': username, 'text': text}
        edits.append(edit)
    od = OwnageDeterminer(edits)
    print od()

Выход:

DEBUG:root:Scores: {'blorgbeard': 0.5,
 'dave-markle': 0.5,
 'dbr': 1172.0,
 'gatekiller': 69.5,
 'joseph-ferris': 0.0,
 'lkessler': 0.0,
 'mark-harrison': 592.0,
 'mdb': 3.0,
 'onebyone-livejournal-com': 0.0,
 'paul-oyster': 482.0,
 'rob-wells': 0.0,
 'simucal': 1070.5,
 'skiphoppy': 0.0,
 'thesoftwarejedi': 701.0}
dbr

Difflib docs по сложности:

Сроки: базовый Ratcliff-Obershelp алгоритм является кубическим временем в худшем случай и квадратичное время в ожидаемый случай. SequenceMatcher - квадратичное время для наихудшего случая и имеет зависящее от ожидаемого случая поведение сложным образом на сколько элементы, которые имеют общие последовательности; наилучшее временное время является линейным.

Еще одна приятная вещь: вычисление победителя является линейным, поэтому вы можете кэшировать исходные результаты и инкрементно обновлять новые изменения, несмотря на большую загрузку инициализации.

Ответ 8

Никто не владеет этим. Присуждение собственности нарушает дух "вики сообщества" и может привести к контрпродуктивным правящим войнам.

Ответ 9

Вопрос заключается в том, насколько удалены ли символы, как их добавление. Использование Diff может работать хорошо, но не всегда следует, что человек, который добавил больше всего, является самым правильным редактором (некоторые могут писать в 10 символов, что другие берут на страницу для записи).

Итак, я думаю, что у вас есть два фактора:

• Количество изменений
• Качество изменений

Следовательно, у меня возникнет соблазн написать что-то, что просто отображает слова, добавленные/удаляемые до очков. Добавляя к этому некоторый качественный фактор (это должен был быть внешний параметр), и комбинированное значение затем можно было бы использовать при сортировке.

Возможно, вы могли бы создать какой-то примитивный "коэффициент качества" на основе расстояния, которое потребовалось до того, как элемент был отредактирован. Так что, если что-то, что я написал, не было изменено до 12-го редактирования, тогда оно не могло бы быть слишком неправильным (по сравнению с чем-то меньшим качеством, измененным, как только оно было добавлено).

Ответ 10

Это вики-почему не позволяют каждому редактору выбирать значение его или ее изменения? Предоставьте раскрывающееся меню что-то вроде...

Подтвердите свое право:

• Несколько незначительных изменений (орфография, грамматика и т.д.)
  • Многие незначительные изменения
  • Несколько значительных изменений (изменения конкретных фактов, цифр и т.д.)
  • Много значительных изменений
  • Несколько основных изменений (изменения в тезисе, заключение и т.д.)
  • Многие основные изменения

Затем используйте комбинированные ответы для оценки собственности.

Ответ 11

Как насчет этой идеи?

• Отображается оригинальное имя плаката, пока сообщение не будет изменено более чем на% от исходного текста.
• Этот процент отображается как что-то вроде "x users, y edits, z% от оригинала"
• Последнее редактируемое в настоящее время редактируемое значение также может иметь разницу - так, например, это дает понять, что первое редактирование вашего вопроса было незначительным дополнением.

Дело в том, что после определенного количества изменений на самом деле не имеет значения, кто его владеет. Я согласен с пользователями, говоря, что попытка присвоить "владельцам" вики-контент является контрпродуктивным.

Ответ 12

Количество символов затруднительно.

Как насчет:

Break latest revision into a set of sentences. 
//Sentence is any text fragment surrounded by punctuation

For each Sentence
    Find which user created that sentence. 
    Add 1 to the user who created the sentence 
    Add 1 to the number of sentences

For Each user 
    % ownership = Count for that user / Number of sentences. 

Поиск того, кто создал это предложение.
Согласование предложения с ревизией легко, если вы хотите получить точное соответствие, но я был бы более счастлив с частичным совпадением.

Чтобы выполнить это частичное совпадение...

Разделите общие слова из фрагмента предложения и найдите этот фрагментированный фрагмент в разделенной версии каждой ревизии. Самый ранний удар - это предложение, написанное владельцем.

Параметры: (вместо общего удаления слов)

• Для каждого слова в предложении уплотнение каждого слова первому и последнему символам. Это будет объяснять орфографические ошибки и т.д.
• Используйте только первый и последний два слова в фрагменте предложения.
• Соответствие 80% слов, вероятно, будет достаточно хорошим, чтобы атрибут собственности. (Это сложная задача для компьютера - и его нельзя кэшировать)

Удаление общих слов

Вы уже делаете это для поиска, поэтому библиотеки и т.д. уже есть. Даже если вы используете формулу elses для кого-то, вы должны, возможно, использовать CommonWordStrip каждую ревизию перед запуском.

Ответ 13

Ключом к хорошему решению этой проблемы является получение дополнительной информации о том, что происходит с редактированием. Дополнительная информация, доступная на этом носителе, - это вопрос голосования и ответа на вопросы. Поэтому, если кто-то редактирует, что приводит к тому, что вопрос получает много голосов, комментариев и ответов, их редактирование было очень ценным. Особые случаи, вероятно, существуют для совершенно нового без ответа вопроса, который редактируется до того, как он был на сайте в течение очень долгого времени.

Вы должны посмотреть, насколько изменился пост, используя алгоритм расстояния Левенштейна, а затем весить их редактирование по количеству голосов, комментариев и ответов, которые получает вопрос после их редактирования.

Let n = total revisions
Let m = the revision number of a poster
Let post[it] = array with text of post at revision 'it'
Let votes[it] = votes that revision 'it' received (also add bonus for comments/answers)
value = 0
for (it = m; it < n; ++it) {
  value += (Levenshtein(post[it-1], post[m]) / average_length_post) * (votes[it])
}

Если вы вычисляете значение для каждого сообщения, то владение почтой - это общее значение всех прав пользователя, разделенное на сумму всех значений редактирования для этого сообщения.

Ответ 14

Не уверен, что это возможно, но вы можете подсчитать количество добавленных символов.

Пример:

• Пользователь 1 отправляет вопрос с 400 символами (Пользователь 1 имеет 400 из 400).
• Пользователь 2 удаляет 40 и добавляет 60 (Пользователь 1 имел 360, а Пользователь 2 - 60).

Если вы вернетесь, вы также должны вернуться к предыдущему счету пользователя/символа.

Но... возможно, просто проще и правдоподобнее назвать оригинальный плакат...

С другой стороны, я много редактирую, но я никогда не считаю себя "владельцем" текста, потому что просто изменяю презентацию (формат и грамматику), но не содержимое.

Ответ 15

Первоначальному понятию должен быть задан вес. Для исправления орфографии необходимо дать вес. Грамматике/структуре необходимо придавать вес. Формулировка должна иметь вес. Для краткости нужно дать вес. Etc...

Массы - единственный справедливый способ сделать это, но также невозможно определить.