Speicherung von Revisionsänderungen einer Nachricht

Question

Welche Algorithmen und Prozesse sind an der Speicherung von Revisionsänderungen beteiligt, wie es bei Stackoverflow und Wikipedia der Fall ist?

Wird nur eine Kopie der Nachricht aufbewahrt? Und wenn ja, ist es nur die letzte Kopie? Werden dann nur Änderungen, die zu der/den vorherigen Version(en) zurückführen, von dort gespeichert? (Dies würde eine schnellere Anzeige der Hauptnachricht ermöglichen). Oder werden komplette Nachrichten gespeichert? Und wenn ja, wird der Vergleich zwischen diesen bei jeder Anzeige durchgeführt?

Welche Algorithmen sind am besten geeignet, um die genauen Änderungen in der Nachricht zu bestimmen? Wie werden diese Daten in einer Datenbank gespeichert?

Wenn jemand genau weiß, was wikipedia oder stackoverlfow macht, würde ich das gerne wissen.

Answer 1

Mediawiki (die Software für Wikipedia) speichert den vollständigen Text für alle Revisionen, siehe die Datenbankschema . Jeder Eintrag in der Texttabelle in Mediawiki hat Flags, die angeben, ob der Inhalt z.B. gziped wurde, die Verwendung einer Standardkompression ist oft die sauberste Option.

Ich kann Ihnen nicht sagen, wie man die Diffs algorithmisch durchführt, aber welchen Algorithmus Sie auch immer verwenden, Sie sollten zwei Vollversionen des Textes verwenden. Das heißt, man holt die vollständige Version des alten und des neuen Objekts aus der Datenbank und führt dann den Vergleich durch. Auf diese Weise lässt sich der Algorithmus für den Vergleich leicht ändern.

Git ist ein großartiges Beispiel für eine Unix-Anwendung, die eine sehr billige (speicher- und geschwindigkeitsmäßig) Deltaspeicherung durchführen kann. Es gibt Wikis, die Git verwenden können, z.B. ikiwiki aber ich nehme an, Sie wollen das mit einer Datenbank machen.

Answer 2

Normalerweise werden Nachrichten als vollständige Schnappschüsse gespeichert. Frühere Versionen sind deaktiviert, und die aktuellste wird angezeigt. Es kann Optimierungen geben, wie z. B. die Zwischenspeicherung der aktuellsten Version.

Answer 3

El Algorithmus für die längste gemeinsame Teilzeichenkette kann verwendet werden, um Unterschiede zwischen den Versionen zu erkennen, ist aber begrenzt. So wird z. B. das Verschieben von Text nicht als solches erkannt, sondern als unzusammenhängendes Entfernen und Einfügen.

Ich nehme an, dass Websites normalerweise die letzte Kopie vollständig speichern und von dort aus Reverse Diffs anwenden. Dies ist auch der Weg CVS funktioniert, aber Subversion verwendet Forward Diffs, was zu langsameren Checkouts führt.

Um dies in einer Datenbank zu speichern, könnte man eine Haupttabelle mit den neuesten Versionen führen und eine separate Tabelle mit den umgekehrten Unterschieden haben. Diese Tabelle würde Zeilen in folgendem Format enthalten (article_id, revision_id, differences) .

Answer 4

Typische Revisionsänderungen werden mit einem Delta-Algorithmus gespeichert, so dass die einzigen gespeicherten Daten die Änderungen in jeder Revision im Verhältnis zum Original sind. Ich bin mir nicht sicher, wie Wikipedia oder Stackoverflow dies implementiert haben.

Answer 5

Ich würde die folgende Technik anwenden:

• Speichern Sie die aktuelle Nachricht als vollständigen Text.
• Speichern Sie die Historie nach dem Delta-Algorithmus.

So bleibt die Leistung bei regelmäßiger Anzeige gut und der Speicherbedarf für die Historie gering.