두 문자열 사이의 변경 사항을 가져 오는 방법 (삽입, 삭제 또는 동일)?

Question

두 문자열 간의 거리를 얻기 위해 Levenshtein 알고리즘을 사용했지만 실제로 필요한 것은 두 번째 문자열에서 (인덱스) 삽입 또는 삭제가 발생했거나 동일한 상태를 유지하는 것입니다.
JavaScript (또는 다른 C#)에서이 작업을 수행 할 수있는 구현이 있습니까?

Answer 1

Google은 사용자가 요청한 작업을 수행 할 수있는 강력한 알고리즘이 포함 된 Diff Match 및 Patch 라이브러리를 제공합니다. 이러한 라이브러리는 Java, JavaScript, Python, C++, C#, Objective-C, Lua 및 Dart에서 사용할 수 있습니다.

1. DIFF : DIFF 두 텍스트를 받아 차이점을 발견한다. 이 구현은 문자 단위로 작동합니다. diff의 결과에는 출력을 복잡하게하는 관련성이없는 작은 공통점이 포함될 수 있습니다. post-diff 정리 알고리즘은 이러한 사소한 공통점을 제외합니다.
2. 일치 : 큰 텍스트에서 패턴을 찾습니다. 일치하는 구현은 퍼지 (fuzzy)합니다. 즉, 패턴에 오류가 포함되어 있어도 텍스트에있는 내용과 정확히 일치하지 않는 경우에도 일치하는 항목을 찾을 수 있습니다. 이 구현은 예상되는 위치를 받아들이 기 때문에 그 근처에서 일치 항목을 찾아야합니다. 후보자 성냥은 a) 패턴과 텍스트 사이의 철자 차이의 수와 b) 후보자 성냥과 예상되는 위치 사이의 거리에 따라 득점됩니다. 일치 거리 매개 변수는이 두 측정 항목의 상대적 중요성을 설정합니다.
3. 패치 : 두 텍스트를 서로 비교하여 패치 목록을 생성 할 수 있습니다. 이 패치는 세 번째 텍스트에 적용될 수 있습니다. 세 번째 텍스트에 자체 편집 내용이있는 경우이 패치 버전은 최선의 노력으로 변경 사항을 적용하고 어떤 패치가 성공했는지, 어떤 패치가 실패했는지보고합니다.

자세한 내용은 here에서 확인할 수 있습니다.