Diferença eficiente em rede entre duas cordas em JavaScript

Question

Eu tenho um aplicativo da Web em que um editor do lado do cliente está editando um texto realmente grande, conhecido no lado do servidor.

O cliente pode fazer qualquer tipo de modificações neste texto.

O que é o máximo eficiente de rede Maneira de transmitir a diferença de resultado de uma maneira que o servidor entende? Além disso, como isso acontecerá no lado do cliente (JavaScript), eu também gostaria que fosse 'rápido' (ou pelo menos não visivelmente lento)

Alguns cenários:

• O usuário modifica um personagem
• O usuário modifica várias frases em posições aleatórias
• O usuário apaga tudo e resulta em um texto em branco.

Não posso usar sintaxe do tipo Diff, pois não é eficácia da rede, verifica as linhas, onde os exemplos 1 e 3 produzirão diferenças horríveis (especialmente a última, onde o resultado será mais do que o próprio antigo).

Alguém tem experiência neste assunto? O usuário opera em um conjunto realmente grande de dados-cerca de 3-5 MB de texto e o upload de todo o conteúdo "novo" é um grande não-não.

Para deixar claro, estou procurando um "protocolo" de transferência, a comparação de string não é o problema.

Answer 1

Não estou muito familiarizado com este tópico, mas posso apontar para um projeto de código aberto (Apache License 2.0), que pode ser muito útil.

É uma biblioteca Diff, Match e Patch escrita em vários idiomas, incluindo JavaScript, de um engenheiro do Google e é usado em vários serviços de edição colaborativa on -line.

Aqui estão uma lista de recursos:

• o Diff, combinação e patch projeto
• o Mobwrite Projeto (implementação do editor com base no projeto acima)
• "Sincronização diferencial" (Uma palestra do Google Tech do engenheiro)

Answer 2

Uma abordagem simples, assumindo que você sabe que a cópia do servidor não vai mudar, seria apenas enviar uma lista de edições (exclusões e adições), com as deleções representadas como um índice de partida e final, e as adições representadas representadas como um índice de início e o texto a ser inserido.

Se você tem mais do que um simples algoritmo de diff para trabalhar (não tenho certeza exatamente do que você quer dizer com "Comparação de String não é o problema"), você também pode detectar pedaços movidos ou copiados de texto e enviá -los como o início e o índice final da peça de texto movida ou copiada, bem como o destino para inseri -lo.

Observe que você precisará acompanhar se seus índices se referem ao documento original ou ao documento como editado até agora. Uma abordagem fácil para evitar esse problema é sempre executar as edições desde o final do documento no início; Em seguida, as edições anteriores não afetarão as compensações especificadas por edições posteriores.

Para um exemplo de uma abordagem como essa, veja o ed Formate isso diff -e saídas. Isso é basicamente insumado que pode ser alimentado no ed Editor de texto orientado a linha. Se você deseja que as menores diferenças absolutas sejam enviadas, você pode querer fazer indexação baseada em caracteres, em vez de indexação baseada em linha, mas a mesma abordagem básica pode funcionar.

Answer 3

Qualquer edição que o desempenho do usuário possa ser dividido com eficiência em: excluir de x para o comprimento y; Insira no texto x "qualquer coisa". X e Y são compensações em caracteres desde o início do texto; Y é um número de caracteres; "O que quer que" seja qualquer sequência de caracteres. Você diz que não precisa de ajuda para calcular o diferencial, mas um exemplo é aqui, exceto que é mais rico em sua saída do que você precisa, mas identifica "remoções e inserções"; portanto, basta alterar a parte de saída.

O formato exato em que você envia os dados para o servidor pode ser ajustado, mas não acho que haja muita quilometragem em fazer isso - medição pendente, eu começaria enviando os comandos como D para excluir ou para inserir, Os números em decimal, a sequência inserida no formulário citado. Depois de ter algumas estatísticas sobre transferências reais sendo realizadas, você pode ver quanto custa no número (decimal vs binário) e citações, mas suspeito das coisas que você pode tentar, como dar compensações do ponto mais recente de inserção ou exclusão, e não sempre desde o início, para tornar as coisas mais rapidamente).

Você pode provar o que o usuário está fazendo a cada poucos segundos e apenas enviar as mudanças incrementais nos últimos segundos (se houver) - dessa maneira, cada pacote que você está enviando será pequeno e se a conexão líquida ou o usuário Crash em computador/navegador, o usuário não terá perdido muito trabalho.

Answer 4

Você pode simplesmente enviar alterações a cada 500ms, portanto, quaisquer que fossem feitas alterações nos últimos 500ms, mas você apenas envia dados quando houve uma alteração.

Nisso, você pode enviar a posição das palavras alteradas e apenas enviar a palavra inteira, mas eu teria a posição da frente do texto.

Não serão várias frases que valem a pena, mas pode haver várias palavras envolvidas, mas, se você as enviar em ordem de alteração, o resultado deve ser consistente.

Answer 5

Porque existem muitas maneiras de fazer edições-mesmo em curtos períodos de tempo, como 500ms-incluindo arrastando e soltando, ou cortando e colando grandes seções de texto em torno do documento ou de fora dele-Não sei se haverá algo que abrangerá todos os cenários muito bem. Isso certamente é uma resposta à sua pergunta pelo valor nominal, mas eu consideraria cuidadosamente o problema de desenvolver e manter algo assim em comparação com a alteração da interface para restringir o tamanho do texto e quebrar textos existentes em peças menores.

Talvez isso não seja possível em sua situação, mas se for, eu acho que seria muito menos problemas no final se esquivar da questão dessa maneira e apenas enviar documentos completos após uma edição.