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

Question

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

Сообщество вики
220 ревизий, 48 пользователей

Я также хотел бы показать пользователю, который «владеет большинством» окончательного содержимого, отображаемого на странице, в процентах от оставшегося текста:

Сообщество вики
220 ревизий, 48 пользователей
кроноз 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 с достойной историей ревизий (не просто повторной маркировкой, но частыми изменениями тела сообщения). Вот хороший, с 15 ревизиями от 14 разных авторов. Кто такой "владелец"?

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

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

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

Приветствуются решения на любом языке , но я предпочитаю решения, которые

1. Довольно легко перевести на c #.
2. Без зависимостей.
3. Поместите простоту перед эффективностью.

Чрезвычайно редко для публикации в SO более 25 ревизий. Но это должно «чувствовать» точно, поэтому, если вы оценили внесенные изменения, вы согласитесь с окончательным решением. Я рекомендую вам проверить свой алгоритм на постах переполнения стека с историями изменений и посмотреть, согласны ли вы с окончательным выводом.

---

Я развернул следующую аппроксимацию, которую вы можете увидеть в действии для каждой новой сохраненной ревизии в сообщениях сообщества Wiki

• делать разность на основе строки каждой ревизии, где изменяется основной текст
• сумма строк вставки и удаления для каждой ревизии как "editcount"
• каждый идентификатор пользователя получает сумму "editcount", которую они внесли
• автор первой ревизии получает 2x * "editcount" в качестве начального балла в качестве основного авторского бонуса
• для определения окончательного процента владения: общее количество отредактированных строк каждого пользователя, поделенное на общее количество отредактированных строк во всех ревизиях

(Существуют также некоторые защитные условия для простых простых условий, таких как 1 ревизия, только 1 автор и т. Д. При использовании различий на основе строк достаточно быстро выполнить пересчет для всех ревизий; в типичном случае, скажем, 10 ревизий это ~ 50 мс .)

Это неплохо работает в моем тестировании. Это немного ломается, когда у вас есть небольшие 1 или 2 посты, которые редактируют несколько человек, но я думаю, что это неизбежно. Принятие ответа Джоэла Нили как наиболее близкого по духу к тому, с чем я пошел, и отказался от всего остального, что казалось работоспособным.

Answer 1

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

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

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

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

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

Answer 2

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

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

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])
}

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

Answer 3

Количество символов хитрых метинков.

Как насчет:

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% слов, вероятно, будет достаточно для определения принадлежности. (Это трудная вещь для компьютера - и она не может быть кэширована)

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

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

Answer 4

Первоначальная концепция должна иметь вес. Исправления правописания должны быть даны веса. Грамматика / структура должны иметь вес. Формулировка должна иметь вес. Краткость должна быть дана весомость. Etc ...

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

Answer 5

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

Пример:

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

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

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

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