개발자 도구 · 텍스트 비교
텍스트 차이가 변경된 줄을 찾는 방법: LCS 및 마이어스 알고리즘
· 작동 방식
텍스트 비교 알고리즘 개발자 워크플로
라인 기반 비교의 이면에 있는 최장 공통 하위 수열 아이디어와 Myers 알고리즘이 브라우저 탭 내에서도 즉시 실행할 수 있을 만큼 빠른 이유를 설명합니다.
두 개의 파일, 하나의 질문: 어떤 줄이 살아남았나요? — 줄 번호를 일치시키는 것이 아니라 두 버전에 공통된 가장 긴 줄을 찾는 프레임 비교
어떤 줄이 살아남았는지 알려주는 라벨과 함께 두 개의 개정판이 도착하지 않습니다. ToolAcre는 먼저 각 텍스트를 순서가 지정된 목록으로 분할한 다음 두 목록에 동일한 순서로 나타나는 긴 하위 시퀀스를 검색합니다. 공유된 척추 외부의 선은 추측된 수정이 아니라 추가 또는 제거가 됩니다.
결과는 양쪽 모두에 대해 원래의 1 기반 위치를 전달합니다. 변경되지 않은 행은 양쪽에 숫자를 소유하고 왼쪽에서만 제거되고 오른쪽에서만 추가됩니다. 이러한 설명을 통해 반복되는 줄이 둘 이상의 그럴듯한 정렬을 제공하는 경우에도 표시된 스토리를 검토할 수 있습니다.
diff가 문자가 아닌 줄에서 작동하는 이유 — 개행에서 분할이 텍스트를 일련의 비교 가능한 단위로 변환하는 방법과 산문이 코드와 다르게 동작하는 이유
구현에서는 전체 행을 비교 단위로 처리합니다. 따라서 개행 경계는 결과를 형성합니다. 한 줄에 저장된 단락 내의 한 단어 편집은 전체 줄을 대체하는 반면, 문장별로 배열된 동일한 산문은 훨씬 더 작은 영역을 분리할 수 있습니다.
줄 비교는 다른 디스플레이 뒤에 숨겨진 문자 분석이 아닙니다. `splitLines`은 배열을 생성하고 LCS 테이블은 한 라인 키를 다른 라인 키와 비교합니다. 이러한 예측 가능한 세분성은 소스 및 구성 파일에 적합하지만 일치하는 대체 항목 내에서 변경된 정확한 문자를 강조 표시할 수는 없습니다.
일반 용어로 가장 긴 공통 부분 수열 — 5줄 예제를 통해 LCS 아이디어를 살펴보고 부분 수열 외부의 모든 것이 어떻게 삽입 또는 삭제가 되는지 보여줍니다.
왼쪽 선 A, B, C, D, E와 오른쪽 선 A, C, E를 상상해 보세요. A, C, E는 순서가 지정된 공통 하위 시퀀스를 형성합니다. B와 D는 그 밖에 있으므로 결과는 제거된 행을 대체 행과 쌍으로 연결할 필요 없이 두 개의 제거와 세 개의 변경되지 않은 행을 보고합니다.
테이블은 나머지 모든 위치 쌍에 대해 거기에서 사용 가능한 최상의 공유 길이를 기록합니다. 재건은 이러한 가치를 통해 나아갑니다. 등호 키는 양쪽으로 진행됩니다. 그렇지 않으면 더 큰 이웃 값에 따라 왼쪽 제거 또는 오른쪽 추가를 내보낼지 여부가 결정됩니다.
Myers 알고리즘과 속도가 중요한 이유 — 공식 없이 가장 짧은 편집 스크립트를 추적하여 수천 줄의 파일에서 빠른 비교를 유지하는 방법을 설명합니다.
통합 문서에는 Myers라는 이름이 있지만 `diff.js`는 일반 최장 공통 하위 시퀀스 동적 프로그래밍을 명시적으로 구현합니다. 주석에는 서로 다른 중간에 대한 O(n·m) 시간과 메모리가 명시되어 있습니다. Myers 요청 또는 최단 편집 그래프 동작은 실제로 제공되는 코드에 대해 친숙한 알고리즘을 대체합니다.
ToolAcre는 할당 전 비용을 제한합니다. 동일한 접두사와 접미사는 선형 패스에서 벗겨지며, 서로 다른 중간에는 최대 2,000 줄이 포함될 수 있습니다. 매트릭스는 `Uint32Array`입니다. 문서화된 최악의 허용 사각형은 무한한 상자 값이 아닌 약 16MB를 차지합니다.
ToolAcre는 개요에 명명된 Myers 알고리즘이 아닌 LCS 테이블을 사용합니다.
"추가된 검색", "고정된 내보내기" 및 "업데이트된 도움말"이 포함된 변경 로그를 첫 번째 및 세 번째 항목을 유지하지만 마지막 항목 앞에 "추가된 필터"를 삽입하는 개정판과 비교합니다. 공통 항목은 경로를 고정하고 "고정 내보내기"가 제거되고 "추가된 필터"가 추가됩니다.
알고리즘은 수정된 라인 쌍을 호출하지 않습니다. 행 어휘는 동일하고 추가 및 제거이므로 텍스트 교체는 한 번의 제거와 한 번의 추가로 나타납니다. 요약에서는 해당 작업을 별도로 계산하고 두 값이 모두 0인 경우에만 텍스트를 동일하게 표시합니다.
두 개의 올바른 diff가 다르게 보일 수 있는 이유 — 동일하게 짧은 편집 스크립트 간의 연결이 왜 한 도구는 빈 줄을 비난하고 다른 도구는 닫는 괄호를 비난하는지 설명합니다.
반복되거나 상호 교환 가능한 라인은 동일한 길이의 여러 공통 하위 시퀀스를 생성할 수 있습니다. ToolAcre는 인접한 두 테이블 값이 동일할 때 제거를 선호하여 하나의 동점을 해결합니다. 또 다른 올바른 구현은 추가 항목을 먼저 선택하고 동일한 편집 비용으로 다르게 보이는 정렬을 제공할 수 있습니다.
그렇기 때문에 빈 줄이나 닫는 중괄호가 도구 전체의 다른 덩어리에 첨부되어 나타날 수 있습니다. 불일치가 자동으로 비교 내용 손실을 의미하지는 않습니다. 표시 차이점을 경쟁적인 사실 주장으로 처리하기 전에 원래 줄 번호와 변경되지 않은 주변 행을 읽으십시오.
여기서 다루지 않는 내용 — 의미적 또는 구조적 비교, 이동 감지 및 단어 수준 강조 표시는 줄 기반 diff가 계산하는 범위를 벗어납니다.
이 경로의 어떤 것도 구문 트리를 구문 분석하고, 이름이 바뀐 식별자를 인식하고, 이동된 블록에 레이블을 지정하거나, 산문의 의미를 이해하지 못합니다. 이동된 단락은 공유 순서 요구 사항을 위반하며 한 번은 제거된 상태로, 한 번은 추가된 상태로 나타날 수 있습니다. 또한 이 도구는 행 내부의 문자 또는 단어 수준 강조 표시를 계산하지 않습니다.
이러한 누락은 숨겨진 모드가 아니라 경계입니다. 의미론적 주장을 위해 언어 인식 검토자를 사용하고 병합 기록의 버전 제어를 사용합니다. 텍스트 비교는 두 개의 정렬된 라인 시퀀스가 어떻게 다른지에 대한 더 좁은 질문에 답한 다음 해당 텍스트 편집이 중요한지 여부를 인간이 해석할 수 있도록 합니다.
요점: 강조 표시된 줄이 실제로 의미하는 것 — 줄 차이를 편집의 가장 짧은 이야기로 읽는 방법과 ToolAcre의 텍스트 비교가 아무것도 업로드하지 않고 탭에서 이를 실행하는 방법을 요약합니다.
작성자 의도에 대한 증거가 아닌 하나의 LCS 파생 설명으로 녹색 및 빨간색 행을 읽습니다. 접두사 및 접미사 트리밍은 작업량을 변경하지만 최종 라인 계산은 변경하지 않습니다. 대소문자 또는 공백 옵션이 일치를 위해 더 느슨한 키를 제공하는 경우에도 원본 텍스트는 모든 행에 유지됩니다.
비교는 가져온 브라우저 모듈을 통해 실행되고 DOM 텍스트 노드로 렌더링됩니다. 도구 경로에 변환 끝점이 없습니다. 5줄 예제를 시도하고, 측면을 바꾸고, 패치 모양의 출력을 다운로드하여 의미 체계를 고안하지 않고 방향이 추가 항목을 제거 항목으로 어떻게 변경하는지 확인하세요.