Netzwerkeffizienter Unterschied zwischen zwei Zeichenfolgen in JavaScript

Question

Ich habe eine Webanwendung, bei der ein Client -Side -Editor einen wirklich großen Text bearbeitet, der auf der Serverseite bekannt ist.

Der Kunde kann alle Art von Änderungen an diesem Text vornehmen.

Was ist am meisten netzwerk effizient Möglichkeit, den Ergebnisunterschied in einer Art und Weise zu übertragen, die der Server versteht? Da dies auf der Clientseite (JavaScript) passieren wird, möchte ich auch, dass es „schnell“ ist (oder zumindest nicht merklich langsam).

Einige Szenarien:

• Benutzer modifiziert einen Zeichen
• Der Benutzer modifiziert mehrere Sätze in zufälligen Positionen
• Der Benutzer löscht alles und führt zu einem leeren Text.

Ich kann keine diff-ähnliche Syntax verwenden, da es nicht ein Netzwerk-Effizienz ist. Es überprüft Linien, wobei Beispiele 1 und 3 schreckliche Unterschiede erzeugen (insbesondere das letzte, bei dem das Ergebnis mehr als das alte selbst sein wird).

Hat jemand Erfahrung in dieser Angelegenheit? Der Benutzer arbeitet mit einem wirklich großen Datensatz-rund 3-5 MB Text, und das Hochladen des gesamten "neuen" Inhalts ist ein großes Nein-Nein.

Um klar zu sein, ich suche nach einem "Protokoll" der Übertragung, String -Vergleich ist nicht das Problem.

Answer 1

Ich bin mit diesem Thema nicht sehr vertraut, aber ich kann Sie auf ein Open -Source -Projekt (Apache -Lizenz 2.0) verweisen, das möglicherweise sehr nützlich ist.

Es handelt sich um eine Diff-, Match- und Patch -Bibliothek, die in mehreren Sprachen, einschließlich JavaScript, von einem Google -Ingenieur geschrieben wurde und in mehreren Online -Kollaborationsbearbeitungsdiensten verwendet wird.

Hier sind eine Liste von Ressourcen:

• Das Diff, Übereinstimmung und Patch Projekt
• Das Mobwrite Projekt (Editorimplementierung basierend auf dem obigen Projekt)
• "Differentielle Synchronisation" (Ein Google Tech -Vortrag des Ingenieurs)

Answer 2

Ein einfacher Ansatz, bei dem Sie wissen, dass Sie wissen, dass die Kopie auf dem Server nicht ändert als Startindex und der zu fügige Text.

Wenn Sie mehr als einen einfachen Diff -Algorithmus zum Arbeiten haben (ich bin mir nicht sicher, was Sie unter "String -Vergleich nicht das Problem" meinen), können Sie auch bewegte oder kopierte Textbrocken erkennen und diese als Start senden und Endindex des bewegten oder kopierten Textstücks sowie des Ziels zum Einfügen.

Beachten Sie, dass Sie sicherstellen müssen, dass sich Ihre Indizes auf das Originaldokument oder das bisher bearbeitete Dokument beziehen. Ein einfacher Ansatz, um dieses Problem zu vermeiden, besteht darin, die Änderungen immer vom Ende des Dokuments vom Anfang durchzuführen. Dann wirken sich frühere Änderungen nicht auf die von späteren Änderungen angegebenen Offsets aus.

Für ein Beispiel für einen solchen Ansatz siehe das ed Format das diff -e Ausgänge. Dies ist im Grunde genommen Eingabe, der in die eingespeist werden könnte ed zeilenorientierter Texteditor. Wenn Sie möchten, dass die absolut kleinsten Diffs hinweg senden möchten, möchten Sie möglicherweise eine charakterbasierte Indexierung anstelle einer zeilenbasierten Indexierung durchführen, aber der gleiche grundlegende Ansatz könnte funktionieren.

Answer 3

Alle Änderungen, die der Benutzer ausführt, kann effizient unterteilt werden in: Löschen von x für die Länge y; Fügen Sie am X -Text "was auch immer" ein. X und y sind von zu Beginn des Textes Offsets in Zeichen; Y ist eine Reihe von Zeichen; "Was auch immer" ist eine Zeichenfolge von Zeichen. Sie sagen, Sie brauchen keine Hilfe beim Berechnen des Diffs, aber ein Beispiel ist hier, Außer es ist reicher in seiner Ausgabe als Sie benötigen, identifiziert jedoch "Entfernungen und Einfügungen". Ändern Sie also einfach den Ausgangsteil.

Das genaue Format, in dem Sie die Daten an den Server senden, kann abgestimmt werden, aber ich glaube nicht, dass es viel Kilometerleistung gibt. Die Zahlen in Dezimalzahlen, die eingefügte Zeichenfolge in zitierter Form. Sobald Sie einige Statistiken über die tatsächlichen Übertragungen haben, können Sie sehen, wie viel Overhead in den Zahlen (Dezimal- und Binär-) und Zitaten ist, aber ich vermute, dass dies möglicherweise nicht so aussagekräftig ist (wenn es sich, als ob es sich als alle Art erweist, gibt es alle Art. Von Dingen, die Sie ausprobieren können, z. B. Aussets vom neuesten Einfügen oder Löschen und nicht immer von Anfang an, um die Dinge schneller zu machen).

Sie können probieren, was der Benutzer alle paar Sekunden tut, und senden einfach die inkrementellen Änderungen in den letzten Sekunden (falls vorhanden). Auf diese Weise ist jedes Paket, das Sie senden Computer/Browser -Absturz, der Benutzer hat nicht viel Arbeit verloren.

Answer 4

Sie konnten einfach alle 500 ms Änderungen senden, so dass alle Änderungen in den letzten 500 ms gesendet würden, aber Sie senden nur Daten, wenn sich eine Änderung vorliegt.

Darin könnten Sie dann die Position der geänderten Wort (n) senden und einfach das gesamte Wort senden, aber ich hätte die Position von der Vorderseite des Textes.

Es werden nicht mehrere Sätze wert sein, aber es kann mehrere Wörter beteiligt sein, aber wenn Sie sie in der Reihenfolge der Änderung senden, sollte das Ergebnis konsistent sein.

Answer 5

Weil es so viele Möglichkeiten gibt, Änderungen vorzunehmen-auch innerhalb von kurzen Zeiträumen wie 500 ms-einschließlich Ziehen und fallen lassen oder schneiden und einfügen, große Textabschnitte innerhalb des Dokuments oder von außen-Ich weiß nicht, ob es etwas geben wird, das alle Szenarien wirklich gut abdecken wird. Dies ist sicherlich ein Nicht-Anspruch auf Ihre Frage zum Nennwert, aber ich würde die Mühe, so etwas zu entwickeln und zu pflegen, sorgfältig in Betracht ziehen, um die Schnittstelle zu ändern, um die Textgröße einzuschränken und vorhandene Texte in kleinere Stücke zu zerlegen.

Vielleicht ist das in Ihrer Situation nicht möglich, aber wenn dies der Fall ist, wäre es am Ende viel weniger Probleme, dem Problem auf diese Weise auszuweichen und nach einer Bearbeitung nur vollständige Dokumente zu senden.