Posso usar um algoritmo Diff de texto simples para rastrear alterações XML?
https://stackoverflow.com/questions/2430083
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Estou trabalhando no FLEX/AS3 (por simplicidade) um editor XML. Eu preciso fornecer funcionalidade de desfazer/refazer.
Obviamente, uma solução é armazenar todo o texto de origem a cada edição. No entanto, para conservar a memória, gostaria de armazenar os diferenciais (essas diferenças também serão usadas para transmitir atualizações ao servidor para economizar automaticamente).
Minha pergunta é: posso usar um algoritmo Diff de texto simples para rastrear essas alterações XML?
Minha pesquisa na internet indica que eu não podes faça isso. No entanto, obviamente estou perdendo alguma coisa. O limite de texto simples fornece a funcionalidade que é supostamente:
diff(text, text') -> diffs
patch(text, diffs) -> text'
XML é simplesmente texto, então por que não posso simplesmente usar o DIFF () e o patch () para transformar o texto de maneira confiável?
Por exemplo: digamos que eu sou um poeta. Quando escrevo poesia, uso muita pontuação descolada ... você sabe <, /e>. (Você pode ver para onde estou indo com isso ...) Se estou escrevendo minha poesia em um aplicativo que usa diffs para fornecer funcionalidade de desfazer/refazer, minha poesia se torna iluminada quando eu desfazer/refazer minhas edições? É apenas texto! Por que faz diferença para o algoritmo?
Obviamente, não tenho algo aqui ... obrigado por explicar! :)
ATUALIZAR:
Alguma discussão que encontrei sobre o Diffing XML com um algoritmo de texto simples:
- http://code.google.com/p/google-diff-match-patch/wiki/plaintext
- Existe uma biblioteca JS Diff contra HtmlString como o Google-Diff-Match-Patch no texto simples?
Além disso, entendo que um padrão de comando é provavelmente uma maneira melhor de implementar o desfazer/refazer. Simplifiquei meu caso de uso por uma questão de simplicidade e ainda acho que a Diffing XML é a melhor abordagem.
Solução
Sou o autor da biblioteca Diff/Match/Match/Patch de texto simples do Google.
A questão principal é se seus patches são exatos. Em um mundo ideal:
diff(old_text, new_text) -> edits
patch(edits, old_text) -> new_text
Observe que o texto base (antigo_text) é o mesmo nas duas operações. Neste caso ideal, um diferencial e patch de texto simples simples funcionarão perfeitamente, independentemente do tipo de conteúdo. Se este caso se aplicar a você, terminará.
A questão está com patches difusos. Aqui está o exemplo correspondente:
diff(old_text, new_text) -> edits
patch(edits, old_forked_text) -> new_forked_text
Observe que o texto base não é o mesmo nas duas operações. Eles devem ser semelhantes, mas a operação do patch agora precisa usar o "julgamento" sobre o que deve fazer. Alguns patches podem se encaixar perfeitamente conforme especificado na edição, outros podem precisar ser ajustados para a posição, outros podem precisar ser ajustados para o contexto alterado, outros podem não se encaixar e devem ser descartados. Se o seu algoritmo de patching não estiver ciente da estrutura do XML ao tomar suas decisões, você poderá muito bem acabar com o XML malfrado. Aqui está uma amostra:
old_text = Jabberwock<SPAN>Hello<SPAN>World</SPAN></SPAN>
new_text = Jabberwock<DIV>Hello<SPAN>World</SPAN></DIV>
diff(old_text, new_text) -> edits
edits = ["SPAN" -> "DIV" @ character 11,
"SPAN" -> "DIV" @ character 41]
old_forked_text = <SPAN>Hello<SPAN>World</SPAN></SPAN>
patch(edits, old_forked_text) -> new_forked_text
new_forked_text = <SPAN>Hello<DIV>World</SPAN></DIV>
Vejamos isso com cuidado. O Diff original retornou duas edições, altere o período mais externo para uma div. Mudança simples. Infelizmente, o texto para o qual este edito está sendo aplicado mudou do original. A palavra "jabberwock" foi removida. Agora, a primeira alteração do Span-> Div corresponde à segunda etiqueta, não a primeira. Como o algoritmo de patch não está ciente das regras do XML, ele resulta em tags aninhadas ilegalmente.
Existem alguns hacks que permitem garantir o XML válido ao usar um patch de texto simples, mas resultam em alguma perda de flexibilidade (a pergunta original já tem um link para a página do Wiki que escrevi sobre isso). É claro que a solução definitiva para corrigir o XML é usar um algoritmo Dif e Patch com reconhecimento de XML. Estes são significativamente mais complicados e caros, mas existem. Google os nomes Tancred Lindholm e Sebastian Rönnau para o excelente trabalho que fizeram no campo XML (particularmente no que diz respeito a Doceng).
Deixe -me saber se houver mais alguma coisa que eu possa acrescentar.
- Neil Fraser
Outras dicas
eu uso Sem comparação o tempo todo para comparar documentos XML. Entende XML, até certo ponto.
Pode ser necessário pré-processar os dois documentos para comparar a comparação textual para fazer o melhor trabalho possível. Por exemplo, em alguns documentos XML, a ordem de alguns elementos pode não importar. Certamente será importante para a sua ferramenta Diff! Pode ser necessário pré-processar o XML usando uma transformação XML que classifique esses elementos em uma ordem comum nos dois arquivos, antes de comparar os dois arquivos classificados.
Você também vai querer usar o mesmo recuo para ambos os documentos. Acho útil iniciar cada elemento em uma nova linha e usar a mesma quantidade de indentação, com espaços, para cada nível. Se o seu documento ficar muito profundo, você desejará usar apenas um ou dois espaços por nível, para que a compare se encaixe na tela. Você pode até querer usar um atributo por linha (e classificar os atributos em uma ordem comum).
Se você é o único "proprietário" dos dados entre seus pontos de desfazer/refazer, é claro que você pode usar o limite simples para eles. Como você aponta, isso equivale a um conjunto de transformações.
Dependendo das operações que você fornece, no entanto, o tipo de texto simples pode não estar remotamente quase ideal para registrar o desfazer/refazer e você pode precisar especializar determinados casos. Imagine apenas gravar um comando replaceall, que pode ser apenas alguns bytes acima da cabeça, mais a string de pesquisa e substituição. Isso pode gerar diferentes pontos de texto simples.
No contexto mais amplo, se você permitir a edição externa desses documentos e está pensando mais em como armazenar deltas no servidor, está imitando o Git ou outros sistemas de controle de versão. Você precisa usar algum tipo de algoritmo Diff, porque apenas gravar seus comandos obviamente não é a única fonte de transformação. Neste ponto, você está começando a misturar o desfazer/refazer com o controle de versão e pode pensar muito em confundir esses conceitos para seus usuários.
Eu mantinha desfazer/refazer como dentro de uma sessão de edição e proibiria a edição externa enquanto o arquivo estiver aberto. Isso permite que você otimize sua gravação de comando para casos amplos, como eu disse acima.
Além disso, use o controle de versão convencional (considere envolver o GIT) ou implemente sua própria maneira de lidar com os arquivos que estão sendo alterados fora do seu editor.
Eu acho que você pode usar o texto de texto para XML, especialmente no seu caso em que o ser humano escreverá a linha XML por linha. Não sei quais informações você tem dizendo que você não pode fazer isso, mas acho que essa afirmação foi baseada no fato de que os personagens espaciais (espaço, guia, newline ...) são um pouco diferentes de que eles estão em um arquivo de texto simples, que Pode resultar em dois arquivos de texto diferentes são idênticos a partir de uma perspectiva XML. Mas, novamente, para um editor direcionado ao ser humano, não vejo por que você não pode.
