XML 변경을 추적하기 위해 일반 텍스트 Diff 알고리즘을 사용할 수 있습니까?
https://stackoverflow.com/questions/2430083
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
XML 편집기 인 Flex/AS3 ON (단순화)에서 작업하고 있습니다. 실행 취소/레디 기능을 제공해야합니다.
물론 하나의 솔루션은 각 편집 할 때 전체 소스 텍스트를 저장하는 것입니다. 그러나 메모리를 보존하기 위해 DIFF를 대신 저장하고 싶습니다 (이러한 DIFF는 자동 절약을 위해 서버에 업데이트를 전송하는 데 사용됩니다).
내 질문은 - 이러한 XML 변경을 추적하기 위해 일반 텍스트 Diff 알고리즘을 사용할 수 있습니까?
인터넷에 대한 나의 연구는 내가 나타났습니다 할 수 없습니다 그렇게하십시오. 그러나 나는 분명히 무언가를 놓치고 있습니다. 일반 텍스트 Diff는 다음과 같은 기능을 제공합니다.
diff(text, text') -> diffs
patch(text, diffs) -> text'
XML은 단순히 텍스트이므로 Diff () 및 Patch ()를 사용하여 텍스트를 안정적으로 변환 할 수없는 이유는 무엇입니까?
예를 들어 : 내가 시인이라고 가정 해 봅시다. 시를 쓸 때, 나는 많은 펑키 구두점을 사용합니다 ... 당신은 <, /, 및>와 같이 알고 있습니다. (당신은 내가 어디로 가고 있는지 알 수 있습니다 ...) diffs를 사용하여 실행 취소/레디 기능을 제공하는 응용 프로그램에시를 쓰는 경우, 편집을 실행 취소/재조정 할 때시가 엉망이됩니까? 그것은 단지 텍스트입니다! 왜 알고리즘에 차이가 있습니까?
나는 분명히 여기에 뭔가를 얻지 못한다 ... 설명해 주셔서 감사합니다! :)
업데이트:
평범한 텍스트 알고리즘으로 XML 차이와 관련하여 발생한 일부 토론 :
- http://code.google.com/p/google-diff-match-patch/wiki/plaintext
- 일반 텍스트의 Google-Diff-Match-Patch와 마찬가지로 htmlstring에 대한 JS Diff 라이브러리가 있습니까?
또한 명령 패턴이 실행 취소/Redo를 구현하는 더 나은 방법임을 이해합니다. 단순성을 위해 사용 사례를 단순화했으며 XML Diffing이 최선의 방법이라고 생각합니다.
해결책
저는 Google의 일반 텍스트 Diff/Match/Patch Library의 저자입니다.
주요 질문은 패치가 정확한지 여부입니다. 이상적인 세상에서 :
diff(old_text, new_text) -> edits
patch(edits, old_text) -> new_text
기본 텍스트 (Old_Text)는 두 작업에서 동일합니다. 이 이상적인 경우에는 콘텐츠 유형에 관계없이 간단한 일반 텍스트 차이와 패치가 완벽하게 작동합니다. 이 사건이 귀하에게 적용되면 완료됩니다.
이 문제는 퍼지 패치와 관련이 있습니다. 해당 예는 다음과 같습니다.
diff(old_text, new_text) -> edits
patch(edits, old_forked_text) -> new_forked_text
기본 텍스트는 두 작업 모두에서 동일하지 않습니다. 그것들은 비슷해야하지만 패치 작업은 이제해야 할 일에 대해 "판단"을 사용해야합니다. 일부 패치는 편집에 지정된대로 완벽하게 맞을 수 있으며, 다른 패치는 위치를 위해 조정해야 할 수도 있고, 다른 패치는 변경된 컨텍스트를 위해 조정해야 할 수도 있고, 다른 부분은 전혀 맞지 않아야 할 수도 있고 떨어 뜨려야 할 수도 있습니다. 패치 알고리즘이 결정을 내릴 때 XML의 구조를 인식하지 못하는 경우, XML로 인한 XML로 끝날 수 있습니다. 다음은 샘플입니다.
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>
이것을 조심스럽게 봅시다. 원래의 Diff는 두 편집을 반환하고 가장 바깥 쪽 범위를 div로 변경했습니다. 간단한 변화. 불행히도이 편집이 적용되는 텍스트는 원본에서 변경되었습니다. "Jabberwock"이라는 단어가 제거되었습니다. 이제 첫 번째 스팬-> div 변경은 첫 번째 스팬 태그가 아니라 두 번째 스팬 태그와 일치합니다. 패치 알고리즘은 XML의 규칙을 알지 못하므로 불법적으로 중첩 된 태그가 발생합니다.
일반 텍스트 패치를 사용할 때 유효한 XML을 보장 할 수있는 일부 해킹이 있지만 유연성이 약간 상실됩니다 (원래 질문에는 이미 Wiki 페이지에 대한 링크가 있습니다). XML 패치를위한 궁극적 인 솔루션은 물론 XML-AWARE DIFF 및 패치 알고리즘을 사용하는 것입니다. 이것들은 훨씬 더 복잡하고 비싸지 만 존재합니다. Google은 XML 필드 (특히 Doceng과 관련하여)에서 수행 한 위대한 작업에 대해 Lindholm과 Sebastian Rönnau의 이름을 지정했습니다.
추가 할 수있는 다른 것이 있으면 알려주세요.
- 닐 프레이저
다른 팁
나는 사용한다 비할 바 없는 항상 XML 문서를 비교하기 위해. XML을 어느 정도 이해합니다.
텍스트 비교를 위해 최상의 작업을 수행하려면 두 문서를 사전 처리해야 할 수도 있습니다. 예를 들어, 일부 XML 문서에서는 일부 요소의 순서가 중요하지 않을 수 있습니다. Diff 도구에 확실히 중요합니다! 두 개의 정렬 된 파일을 비교하기 전에 이러한 요소를 두 파일에서 공통 순서로 정렬하는 XML 변환을 사용하여 XML을 사전 프로세스해야 할 수도 있습니다.
또한 두 문서 모두에 동일한 계약을 사용하고 싶을 것입니다. 새 라인에서 각 요소를 시작하고 각 레벨마다 공백과 동일한 양의 압입을 사용하는 것이 유용합니다. 문서가 매우 깊어지면 레벨 당 하나 또는 두 개의 공간 만 사용하여 비교가 화면에 적합합니다. 한 줄 당 하나의 속성을 사용하고 속성을 공통 순서로 정렬 할 수도 있습니다.
당신이 당신의 실행 취소/레디 포인트 사이의 데이터의 유일한 "소유자"라면 물론 그들에게 일반 텍스트 diff를 사용할 수 있습니다. 지적한 바와 같이, 그것은 일련의 변환에 해당합니다.
그러나 제공하는 작업에 따라 일반 텍스트 Diff는 원격으로 거의 최적이 아니며 실행 취소/REDO를 녹음하는 데 가장 적합하지 않을 수 있으며 특정 사례를 전문화해야 할 수도 있습니다. 몇 바이트 오버 헤드와 검색 및 교체 문자열 일 수있는 replaceall 명령을 녹음한다고 상상해보십시오. 그것은 대규모 일반 텍스트 차이를 생성 할 수 있습니다.
더 넓은 맥락에서, 이러한 문서를 외부 편집을 허용하고 서버에 Deltas를 저장하는 방법에 대해 더 많이 생각하면 GIT 또는 기타 버전 제어 시스템을 모방하고 있습니다. 명령을 녹음하는 것이 분명히 변환의 유일한 소스는 아니기 때문에 어떤 종류의 DIFF 알고리즘을 사용해야합니다. 이 시점에서 UNDO/REDO를 버전 제어와 혼합하기 시작했으며 사용자를위한 이러한 개념을 혼동하는 것에 대해 열심히 생각할 수 있습니다.
편집 세션 내에서 실행 취소/Redo를 유지하고 파일이 열려있는 동안 외부 편집을 금지합니다. 이를 통해 위에서 언급 한 것처럼 광범위한 케이스에 대한 명령 기록을 최적화 할 수 있습니다.
그 외에도 기존 버전 컨트롤을 사용하거나 (포장 고려) 편집기 외부에서 변경되는 파일에 대처하는 자신의 방법을 구현하십시오.
특히 인간이 XML 라인을 라인으로 쓸 수있는 경우 XML에 텍스트 차이를 사용할 수 있다고 생각합니다. 나는 당신이 그렇게 할 수 없다고 말하는 정보를 알지 못하지만 그 진술은 우주 문자 (공간, 탭, Newline ...)가 일반 텍스트 파일에 있다는 사실에 근거한 것이라고 생각합니다. XML 관점에서 두 개의 다른 텍스트 파일이 동일 할 수 있습니다. 그러나 다시, 인간을 대상으로하는 편집자에게는 왜 당신이 할 수 없는지 모르겠습니다.
