nicht angemeldet
Hi,
genau das ist mein Ziel, eine Art Wikipedia.
Aber eigentlich ist das nur der Anfang, ich will sowas wie eine CVS haben.
Du bist Dir schon darüber im Klarem, das mir hier die Frage schier auf der Zunge brennt, warum Du nichts Fertiges nimmst?
Schon jetzt zeichnet sich ab, daß ich eine sehr umfangreiche algorithmische Bibliothek brauche.
Nein, eigentlich nicht, da es natürlich auch Brute-Force funktioniert. Eine sehr schnelle Methode, da Du dazu das Dateisystem selber nutzen kannst, aber natürlich mit dem Nachteil behaftet extrem viel Speicher zu verbrauchen. In einem Zeitalter mit Festplattenpreisen von rund 50 Eurocent das Gigabyte zwar fast schon überlegenswert aber das soll ja nicht Sinn der Übung sein, oder?
Also müssen die Datenmengen verkleinert werden. Intuitiv würde man einfach nur die Differenzen zwischen den einzelnen Versionen festlegen und speichern. Das kann man linear machen (A\B, B\C, C\D) oder auf Kosten der Datenmenge alle Differenzen gleichzeitig festlegen und speichern (A\B, A\C, A\D, B\C, B\D, C\D).
Ein Problem dabei ist die nicht voraussehbare Größe der Differenzen. Wenn zwei oder gar mehrere sich streiten und dabei immer wesentliche Teile ändern, dann schnellt der Speicherverbrauch schnell in die Größenordnung des Brute-Force. Die Sicherheitsmaßnahme bei Wikipedia und anderen dagegen ist der händische Eingriff. Der ist dort aber hauptsächlich dazu da Streitereien auf Kosten des Benutzers einzudämmen, weniger dazu die Datenmenge klein zu halten.
Das kann man ja schließlich je nach Art der Daten und des Streites auch selber. Meist ist es ja mehr oder weniger ein C&P-Krieg. Ein Vergleich der Versionen würde das ergeben.
Es ist allerdings recht rechenintensiv jedesmal mit allen Versionen zu vergleichen. Eine Prüfsumme würde das erleichtern. Da die meisten Prüfsummen jedoch exakte Gleichheit erfordern und bereits zuschlagen wenn auch nur ein Buchstabe geändert wird ist eine etwas andere Methode nötig. Wenn man davon ausgeht, das bei normalen Texten, was auch immer das sein mag, bei kleinen Änderungen die Wortstellung und Interpunktion kaum bis gar nicht geändert wird kann man das benutzen:
a) durch Extraktion aller "is(w)space()" Zeichen
b) durch Extraktion aller "is(w)punct()" Zeichen
c) a + b
Die so extrahierten Zeichen werden in der Reihenfolge des Fundes aneinandergereiht und entweder direkt benutzt oder in einen Hash komprimiert. Das direkte Benutzen hat den Vorteil, das kleinere Änderungen über die Edit-Distanz o.ä. festgelegt und dann je nach Schwere auch ignoriert werden können. Die Kompression in einen Hash hat wiederum den Vorteil, das diese Hashes in einem Bloomfilter vorgehalten werden können und so mit einer gewissen aber einstellbaren Wahrscheinlichkeit festgestellt werden kann, ob die fragliche Version irgendwo in den 2.593 vorherigen Versionen schon einmal vorkommt. Dieser Vorteil wirkt sich also erst bei vielen Versionsnummern wirklich aus. Bei Problemen mit "Crosspostings" würde übrigens ein globaler Bloomfilter hilfreich sein.
Es gibt da diverse Verfeinerungen und teilweise auch andere Methoden, insbesondere bei den Differenzen, aber es sollte ja nur ein recht grober Aufriß sein, damit Du weißt, wo Du ansetzen kannst. Sei kreativ!
so short
Christoph Zurnieden