Rete efficiente differenza tra le due stringhe in Javascript

Question

Ho un'applicazione web in cui un client lato editor per la modifica davvero di testo di grandi dimensioni che si è conosciuta sul lato server.

Il client è in grado di effettuare qualsiasi tipo di modifiche a questo testo.

Che cosa è più rete efficiente modo per trasmettere il risultato di differenza, in modo che il server capisce?Inoltre, dal momento che questo accadrà sul lato client (Javascript), vorrei anche essere 'veloce' (o almeno non visibilmente lento)

Alcuni scenari:

• Utente modifica UN carattere
• Utente modifica diverse frasi in posizioni casuali
• Utente cancella tutto e si traduce in un testo vuoto.

Io non posso usare diff-come sintassi non essendo di rete efficiente, controlla righe, in cui gli esempi 1 e 3 produrrà orribile differenze (soprattutto l'ultima, in cui il risultato sarà più che il vecchio se stesso).

Qualcuno ha esperienza in materia?Utente opera su un davvero ampio set di dati circa 3-5MB di testo, e il caricamento di tutta la "nuova" il contenuto è un grande no-no.

Per essere chiari, sto cercando un "protocollo" di trasferimento, per il confronto di stringhe non è il problema.

Answer 1

Non ho molta familiarità con questo argomento, ma vi posso puntare a un open source (licenza Apache 2.0) progetto che può essere molto utile.

Si tratta di una libreria Diff, Match e patch scritte in diverse lingue, tra cui JavaScript, da un ingegnere di Google e viene utilizzato in diversi servizi di editing collaborativo on-line.

Ecco un elenco delle risorse:

• Il Diff, Match e Patch progetto
• Il MobWrite (implementazione Editor sulla base del progetto di cui sopra) del progetto
• "Sincronizzazione differenziale" (A Google Tech Talk dal tecnico)

Answer 2

Un approccio semplice, assumendo che si conosce la copia sul server non ha intenzione di cambiare, sarebbe solo per inviare un elenco delle modifiche (cancellazioni e aggiunte), con le eliminazioni rappresentati come un indice di inizio e di fine, e le aggiunte rappresentati come un indice di partenza ed il testo da inserire.

Se si dispone di più di un semplice algoritmo diff per lavorare con (non sono sicuro esattamente che cosa si intende per "confronto di stringhe non è il problema"), si potrebbe anche rilevare pezzi spostato o copiato di testo, e inviare quelli come l'inizio e la fine dell'indice del pezzo spostato o copiato del testo, così come la destinazione per inserirla.

Si noti che è necessario fare in modo di tenere traccia di se i vostri indici fanno riferimento al documento originale, o il documento come modificato finora. Un approccio semplice per evitare questo problema è quello di eseguire sempre le modifiche a partire dalla fine del documento verso l'inizio; quindi le modifiche precedenti non influenzerà gli offset specificati da modifiche successive.

Per un esempio di un approccio come questo, si veda il formato ed che uscite diff -e . Questo è fondamentalmente ingresso che può essere alimentato nel ed line-oriented editor di testo . Se si desidera che i più piccoli diff assoluti di inviare in tutto si può decidere di fare l'indicizzazione basato carattere linea basata indicizzazione piuttosto che, ma lo stesso approccio di base potrebbe funzionare.

Answer 3

Eventuali modifiche dell'utente di eseguire, possono essere efficacemente suddivisi in:eliminazione da X per la lunghezza Y;inserire la X di testo "qualunque".X e Y sono gli offset in caratteri dall'inizio del testo;Y è un numero di caratteri;"qualunque cosa" è una stringa di caratteri.Dici di aver bisogno di aiuto non di calcolo diff, ma un esempio è qui, tranne che è più ricco di uscita di cui avete bisogno, ma identifica il "traslochi e inserzioni", è così, basta cambiare la parte di uscita.

Il formato esatto in cui si inviano i dati al server può essere accordata, ma non credo che c'è molto di percorrenza fare -- in attesa di misura, mi piacerebbe iniziare inviando i comandi D per eliminare o io per inserire i numeri in decimale, la stringa inserita nel citato modulo.Una volta che avete alcune statistiche sui trasferimenti eseguiti, si può vedere quanto sovraccarico è nei numeri (decimali vs binario) e citazioni, ma ho il sospetto che potrebbe non essere così significativo (se risulta essere, ci sono tutte le specie di cose che si possono provare, come mi offset dall'ultimo punto di inserimento o l'eliminazione, piuttosto che sempre dall'inizio, per rendere le cose più velocemente).

Si può gustare ciò che l'utente fa ogni pochi secondi, e di inviare le modifiche incrementali nel corso degli ultimi pochi secondi (se presente) -- in questo modo, ogni pacchetto che si sta inviando sarà piccolo, e se la connessione di rete o il computer dell'utente/arresto anomalo del browser, l'utente non ha perso molto lavoro.

Answer 4

Si può solo inviare le modifiche ogni 500ms, quindi, tutti i cambiamenti sono stati fatti negli ultimi 500 ms sarebbe stata inviata, ma solo inviare i dati quando ci fu un cambiamento.

In questo si può quindi inviare la posizione della parola mutato (s) e basta inviare l'intera parola, ma avrei la posizione sia dalla parte anteriore del testo.

Non sarà più frasi vale la pena, ma ci possono essere più parole coinvolti, ma, se li si invia in ordine di cambiamento, allora il risultato dovrebbe essere coerente.

Answer 5

Perché ci sono tanti modi per fare modifiche - anche nel breve periodo di tempo, come 500ms - tra cui drag and drop o taglia e incolla, grandi sezioni di testo attorno all'interno del documento o dal di fuori di esso - non so se ci sara 'qualcosa che coprirà tutti gli scenari davvero bene. Questo è certamente un non-risposta alla tua domanda al valore nominale, ma vorrei considerare con attenzione il problema di sviluppare e mantenere qualcosa di simile rispetto a cambiare l'interfaccia per limitare la dimensione del testo e la rottura testi esistenti in piccoli pezzi.

Forse questo non è possibile nella vostra situazione, ma se lo è, direi che sarebbe stato molto meno problemi, alla fine, per schivare la questione in questo modo e basta inviare documenti completi dopo una modifica.