grep

Engineering

HTML diff

NHN

2017년 12월 21일

원문에서 보기 ↗

HTML diff란?

HTML 파서

HTML 파서로는 jsoup같이 잘 구현한 오픈 소스가 이미 있다. 그러나 특정 태그의 데이터를 파싱하는 데에는 적합하지만 모든 태그를 하나하나 탐색하기에는 적합하지 않다(.getNextNode()같은 함수 등 미구현). 따라서 직접 HTML 파서를 구현했다.

구현 과정

파싱에 앞서서 파싱 단위를 결정해야 한다. 한 줄씩 파싱하거나 하나의 문자열로 파싱하는 방법 두 가지가 있다.

태그 타입은 '<', '>'를 기준으로, 태그 내용은 태그 타입을 기준으로, 속성값은 '='과 '"'을 기준으로 파싱한다. 즉 인덱스를 바탕으로 파싱하기 때문에 String 클래스에 절대적으로 의존한다. 따라서 HTML 텍스트가 길면 길수록 성능이 저하된다(.split(), .substring() 등 String의 성능 문제). 인덱스를 바탕으로 파싱하다 보니 조금만 차이가 나도 파싱에 오류가 생겨서 처리할 예외들이 많이 생겨서 JUnit을 사용하여 TDD개발로 전환했다.

TDD개발, 예외 처리

성능 문제

성능 개선 작업

String 클래스 의존도 완화

.replace() 함수

2.png

.substring() 함수

파싱 로직 개선

공백 제거

파싱 단위

개선 결과

HTML 구조화 기능

구현 과정

트리 diff

트리의 diff를 계산하기 위해서 최장 공통 노드 리스트를 계산해야 한다. 두 트리의 공통 노드를 제외하면 추가/삭제/변경된 노드를 구할 수 있기 때문이다. 기존 최장 공통 노드 리스트를 계산하는 모든 알고리즘은 문자로 이루어진 문자열을 대상으로 적용하기 때문에, 트리에 적용하기 위해서는 다른 방법을 사용해야 한다. 직접적으로 노드에 diff 알고리즘을 적용하기는 힘들기 때문에 트리를 노드의 키값으로 이루어진 리스트로 변환해서 diff 알고리즘을 적용한다. 그러나 diff 알고리즘을 문자열로 이루어진 리스트에 적용할 수 있게 수정해야 한다.

diff 노드 설계

트리 구조의 diff를 구하는 것이므로 똑같은 트리 구조를 만들고 diff 내용만 추가해서 구현하려고 했으나 비교하는 변경 이전/이후 트리 구조가 다르면 다를수록 처리하기가 까다로워져서 다른 방법을 고려해야 한다. 따라서 단순하게 diff 내용을 담은 노드를 리스트에 추가하는 식으로 구현했다.

연산 분류

노드 단위의 diff를 계산하기 위해 연산의 종류를 결정해야 한다.

LCS(Longest Common Subsequence) 알고리즘 구현

기존의 문자열(문자 리스트)이 아닌 문자열(문자열 리스트)에 적용하는 리스트 기반 LCS 알고리즘을 먼저 구현했고, 코드는 다음과 같다.

public List<String> getLcsList(List<String> listA, List<String> listB) {
    int[][] dp = new int[listA.size() + 1][listB.size() + 1];

    for (int i = 0; i < listA.size(); i++) {
        for (int j = 0; j < listB.size(); j++) {
            if (listA.get(i).equals(listB.get(j)))
                dp[i + 1][j + 1] = 1 + dp[i][j];
            else
                dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]);
        }
    }

    LinkedList<String> results = new LinkedList<>();
    for (int x = listA.size(), y = listB.size(); x != 0 && y != 0;) {
        if (dp[x][y] == dp[x - 1][y])
            x--;
        else if (dp[x][y] == dp[x][y - 1])
            y--;
        else {
            assert listA.get(x - 1).equals(listB.get(y - 1));
            results.addFirst(listA.get(x - 1));
            x--;
            y--;
        }
    }

    return results;
}

LCS 알고리즘 적용

LCS를 적용하기 위해 다음을 고려한다.

LCS 알고리즘 구현 과정은 다음과 같다.

LCS 알고리즘 적용 범위

구현한 LCS는 다음에 모두 적용된다.

LCS 알고리즘 성능

마이어스 알고리즘

구현 과정

성능 비교

5.png

diff 내용 시각화

리스트 자료구조로 만든 diff 내용을 JSON포맷으로 변환해서 자바스크립트에서 그대로 사용한다. 원본 HTML 텍스트는 렌더링하고, 포함한 모든 태그를 배열로 만들어서 diff 리스트와 비교하며 diff 내용(연산이 EQUAL이 아닌 모든 태그)을 렌더링 결과 화면에 함께 시각화한다.

시각화 방식(태그 내용 변경)

렌더링된 HTML 텍스트에 .innerHTML()함수와 jQuery의 함수를 사용해서 직접 태그를 삽입하여 추가/삭제를 시각화한다. 변경된 내용(CHANGE)은 LCS(Longest Common Substring) 알고리즘을 적용해서 동일 문자열을 제외한 부분을 추가/삭제로 나눠서 시각화한다. 시각화되는 css는 다음과 같다.

시각화 방식(태그 타입, 속성 변경)

MS워드처럼 우측 빈 공간에 변경된 내용의 텍스트를 추가하고 해당하는 태그와 선을 그어서 연결하는 방식으로 구현하려고 했으나 결과 화면에서 해당 태그와 변경된 내용의 텍스트를 연결하는 선을 긋는 것이 생각보다 어려웠다. 대신 해당 태그 좌측 상단에 변경된 내용의 텍스트를 추가해서 표시하는 방식을 적용했다.

원본 HTML 태그 중에서 변경된 태그 타겟팅

변경된 부분의 내용은 diff 리스트에 있지만 정확히 원본 HTML의 어떤 태그의 변경 내용인지에 대한 정보는 없다. 따라서 diff 리스트의 변경 내용을 원본 HTML 태그와 연결하는 과정이 필요하다.

타겟팅 한 태그에 접근

변경된 내용 중에서 직접적으로 렌더링되는(ex. 태그 내용)부분은 원본 HTML을 수정해서 시각화 하는데, 태그를 삭제하고 삽입하는 방법을 사용하려고 했으나 상하관계가 꼬이는 경우가 많아서(보통 자식 노드로 추가) 적용하지 못했다. 원본 HTML을 수정하는 방법이 더 쉬워서 span 태그로 태그 내용을 따로따로 감싸는 식으로 구현했다. 추가/삭제/변경의 표현은 css에서 class단위로 적용하고 span 태그에 insertClass/deleteClass/chageClass를 적용해서 가독성을 향상시켰다.

변경된 태그 시각화

변경된 부분은 통째로 changeClass를 적용했는데, 변경 이전/이후가 한눈에 들어오지 않아서 다른 방식을 적용했다.

예외 처리

최종 결과 예시

태그 내용 : h5 → h1 / Hooray! → Dooray! / delete text equal text → equal text insert text 7-1.png

후기

먼저 diff 알고리즘 관련 자료를 공부하고, 구현했습니다. 파서를 구현하면서 자바의 String 클래스가 어떻게 구현됐는지를 위주로 공부했습니다. 함수들이 어떻게 구현됐고 왜 이렇게 구현했는지를 고민한 것이 정말 큰 도움이 된 것 같습니다. 직접 함수들의 성능을 비교해보기도 하고 다른 방법으로 직접 구현한 함수와 비교하면서 이렇게 구현했을 때의 장점, 이유 등을 알게 되면서 재밌게 프로젝트를 진행했습니다.

오픈 소스를 직접 사용해보기도 하고 분석하기도 했는데, 통째로 수정하고 모든 코드를 뜯어 본 적은 처음이었습니다. 특히 HTML 파서의 성능 개선 작업을 진행하면서 jsoup의 구현 방법과 비교하기 위해 코드를 열심히 분석했습니다. 다행히 규모가 엄청나게 큰 오픈 소스는 아니라 좀 더 수월했던 것 같습니다. jsoup에서 좋아보이는 부분은 적용하고 고치면 더 좋을 것 같은 부분은 고쳐서 파서를 개선했습니다. jsoup보다 빨리 파싱하는 걸 보고 뿌듯했습니다.

diff 알고리즘 성능 개선 작업도 어려웠습니다. LCS 알고리즘을 구현했지만 성능이 너무 나빠서 마이어스 알고리즘으로 대체했는데, 오픈 소스 자체를 수정하면서 구현했습니다. 마이어스 알고리즘 자체가 생각보다 복잡해서 구현을 잘 못하고 있었는데, 오픈 소스를 참고하는게 구현에 도움이 됐습니다.

이번에 인턴 기간동안 이 프로젝트를 진행하면서 지금까지 진행해본 어떤 프로젝트보다 많이 배우고 공부한 것 같습니다. 검색의 벽에 막힐 때 마다 다들 도와주셔서 더 원활히 진행할 수 있었습니다. 자바와 자바스크립트 공부도 많이 했지만, 앞으로 어떤 식으로 공부해야되는지를 배운게 더 큰 경험인 것 같습니다. 고맙습니다.