HTML diffとは？

• Microsoft Wordの「変更履歴の記録」機能のように、HTMLのレンダリング結果画面の変更部分を検出し、その内容を視覚化して表示する機能です。
• HTMLテキストのタグと属性データを解析して、ツリーのようなデータ構造で構造化し、構造化されたツリーを比較して変更内容を検出した後、検出された変更内容をHTMLレンダリングされた原文に視覚化して、ユーザーに表示します。
• したがって、HTMLパーサ、HTML構造化機能（HTML→ツリー）、ツリーdiff、diff内容の可視化機能を実装する必要があります。

動作シーケンス図

HTMLパーサ

HTMLパーサとして、すでにjsoupのようなオープンソースがあります。しかし、特定のタグのデータ解析には適していても、すべてのタグを1つ1つ検知することには適していません（.getNextNode()関数などが未実装）。したがって直接、HTMLパーサを実装することにしました。

実装プロセス

まず解析単位を決めます。方法は、1行ずつ解析する方法、1つの文字列で解析する方法の2つがあります。

• 1行ずつ解析する場合、タグ、属性、内容などを明確に解析できますが、1行に複数のタグがあったり、scriptタグのJavaScriptコードで改行されてしまう等、不確実性なケースに完全に対応できないため、使用しません。
• 全体のHTMLテキストを1つの文字列として解析すると、どのようなケースでも解析可能でHTMLパーサに適しています。しかし、HTMLテキストが長くなるほど、パフォーマンスが低下します。パフォーマンスの問題は、機能を実装した後に言及します。

タグタイプは「<」「>」を基準に、タグの内容はタグタイプを基準に、属性値は「=」「 “」を基準に解析します。インデックスに基づいて解析するため、Stringクラスに絶対的に依存します。したがって、HTMLテキストの長さに比例して、パフォーマンスが低下します（.split()、.substring()などStringのパフォーマンスの問題）。インデックスをもとに解析すると、少しの違いでも解析エラーが発生し、例外処理が多くなるので、JUnitを用いてTDD開発に切り替えました。

TDD開発、例外処理

• 各データ（タグタイプ、タグの内容、属性（attribute、value））の追加/削除/変更を組み合わせた約12個のテストケースを用意し、テストケースを約25個に増やして、例外処理を補強しました。
• 例外処理のうち、最も困難だったのがscriptタグです。scriptタグの内容に別のHTMLテキストを含めた場合、解析が円滑に進行しない問題がありました。そのため最初にscriptタグにヒットした場合、終了タグ（end tag）までのテキストを無条件でscriptタグのタグ内容で解析する例外処理を行い、scriptタグも円滑に解析できるようにしました。
• ユーザーの予期せぬミスを防止する例外も考慮しました。<p/>のようにスラッシュが後にあったり、<s/cript>のようにタイプミスをした場合も、解析できるように正規表現に合わせてスラッシュの位置を正常に変える方式を適用しました。
• 同様に、空白スペースをデータとして認識する場合も正規表現で例外的に処理しました。

パフォーマンスの問題

• 実装したHTMLパーサの性能は、Stringクラスに絶対的に依存します。したがってHTMLテキストの長さと時間は比例します。
• オープンソースjsoupより性能が劣ることを確認し、パフォーマンス向上のためコードを検討しました。

パフォーマンス改善作業

String クラスへの依存度軽減

• パーサで主に使用されるStringクラスの関数は、.indexOf()、.replace()、.substring()があります。.indexOf()関数は、パフォーマンスに影響しないことを確認し、.replace()関数と.substring()関数は、改善が必要でした。

.replace() 関数

• Stringクラスの.replace()関数は、正規表現で実装され、文字列の長さに比例してパフォーマンスが遅くなります。性能を改善した他の関数とStringBuilderクラスの関数を使用した場合でパフォーマンスを比較しました。
• 結果は以下のとおりです。

• Stringクラス内蔵の関数が最も遅く、別途実装した関数は同様のパフォーマンスを示しました。しかし、最も速い関数は、StringBuilderクラス関数でした。StringからStringBuilderに変換する必要があるにもかかわらず、String関数よりも速かったです。よって実装したパーサの.replace()関数をすべてStringBuilder関数に置き換えました。

.substring() 関数

• .substring()関数も.replace()関数のような結論が出ました。ただし、文字列の長さが約12,000字程度になると、StringとStringBuilderのパフォーマンスがほぼ同じになります。確認した結果、単に関数のパフォーマンスではなく、StringからStringBuilderに変換する過程のオーバーヘッドが原因でした。したがって、純粋な関数のパフォーマンスはStringBuilderの方が速いですが、Stringの再変換がある場合、文字列の長さを考慮する必要があります。
• HTMLパーサは12,000字以上の文字列を一度に解析することが一般的ではないので、StringBuilder関数を使用しました。

解析ロジックの改善

空白スペースの削除

• デバッグを通して、正規表現で空白スペースを削除する関数が、全体HTMLテキストを対象に適用されており、パフォーマンスの低下を誘発することを確認しました。そのため、その関数を空白の除去が必要な部分のみ適用するように修正しました。
  • 修正後、5.5秒→0.4秒に改善

解析ユニット

• 最もパフォーマンスに影響を与える部分であるHTMLテキストを読み込む部分を修正しました。既存のパーサは、1回で全体のHTMLテキストを読んで順次解析しますが、無条件でHTMLテキスト全体を解析するため、パフォーマンスが低下するしかありませんでした。
• 1回に1行ずつ解析して、1行が長い場合は3000字単位に分けて解析を進める方法で実装しました。
• 3000字単位に分けて解析すると、scriptタグとstyleタグの開始タグと終了タグ間の文字列を無条件にcontentに解析するロジックのため、3000字内に終了タグがないと例外が発生します。この場合、さらに3000字を解析する例外処理を適用して解決しました。
  • 修正後、0.4秒→0.05秒に改善

改善結果

• 既存のパーサより8倍、jsoupより2倍、高速化されました。
• 1行ずつ解析するときに発生する不確実ケースに対応するために、1回に読む文字列の単位のみを変更し、既存のコードは変更しませんでした。
• jsoupとは解析の方法が少し異なりますが（実装した方式：文字列を読み取り、文字列から解析/ jsoup方式：文字列を文字単位で読みながら解析）、1字ずつ読むjsoup方式は、毎回文字を読むたびに解析可否を判断する必要があり、実装した方式は、文字列単位で読むたびに解析可否を判断します。解析可否の判断回数の違いが、パフォーマンスの差異になったようです。

HTML構造の機能

実装プロセス

• HTMLの構造化には、上下関係が明確で、順序を反映するHTML属性がそのまま反映されるデータ構造であるツリーが最適です。
• 開始タグと終了タグがあるHTMLの特性を活かして、開始タグをスタックに追加し、終了タグを検出したら対応する開始タグをスタックから削除するように試みました。しかし、2次元構造であるHTML DOM Treeを1次元のスタックに実装するのは完璧ではありません。（AタグのサブタグとしてA/B/Cタグがあった場合、スタックの実装では、Cの上位タグがどのAタグか分からない）リストも同様な理由から採用せず、マップは手順を考慮できなかったので除外しました。結局、HTML DOMのようにツリーが最も適していました。
• 構造化の途中でも必要な機能をすぐに追加できるように、TreeクラスとNodeクラスを実装し、HTMLタグを解析したら、ルートノードから下位ノードに追加することで実現しました。このとき、HTMLの構造をそのままツリーに反映する必要があるため、子ノードとして追加するか、兄弟ノードとして追加するかを決めなければなりません。決定基準は、終了タグを満たすかどうかで、実装プロセスは、以下のとおりです。
  • 現在のノードに次のタグを追加するとき、終了タグにヒットした後は、現在のノードを親ノードに上げ、子ノードを追加します。（兄弟ノードの追加）
  • 終了タグにヒットしない状態では、そのまま子ノードを追加します。（下位ノードを追加）
• voidタグのように終了タグがない場合は、終了タグを満たした状態で適用するように例外処理しました。
• JUnitを用いてTDD開発に実装しました。テストケースは、HTMLパーサのものとは別に作成しました。

ツリーdiff

ツリーのdiffを計算するために、最も長い共通のノードリストを計算する必要があります。2つのツリーの共通ノードを除けば、追加/削除/変更されたノードを取得できるからです。
既存の最長共通ノードリストを計算するすべてのアルゴリズムは文字列を対象に適用されるため、ツリーに適用するには他の方法が必要です。
ノードに直接diffのアルゴリズムを適用するのは難しいので、ツリーをノードのキー値で構成されるリストに変換してdiffのアルゴリズムを適用します。しかし、diffのアルゴリズムを文字列で構成されリストに適用できるように変更が必要です。

diffノード設計

ツリー構造のdiffを求めるので、同じツリー構造を作成し、diffの内容を追加して実装しようとしましたが、比較前後のツリー構造に違いがあるほど処理が難しくなるので、他の方法を検討します。そこで単純にdiffの内容を記入したノードをリストに追加する方法で実装しました。

• 演算（operation）の適用範囲を考慮する必要があります。diffノードに直接演算を適用すると、ノードのどの部分に適用される演算か分からないので適していません。ノードのデータ（type、content、attribute、value）ごとに演算を適用すると、正確にどのデータにどの演算が適用されるか分かります。
• 属性値の場合（attribute、value）いろいろな値を持つ可能性があるため、やはり1つの演算では処理できません。したがって属性の値に1つ1つの演算を適用します。
• diffノードはtext、changeText変数を追加します。textは同一、または追加/削除された（EQUAL / INSERT / DELETE）テキストを取得し、changeTextは変更されたテキストのうち、変更後のテキストを保存します。つまりCHANGE演算の場合にのみ使用され、textは変更前のテキストを、changeTextは変更後のテキストを持ちます。
• クラス図は、次のとおりです。

演算分類

ノード単位のdiffを計算するために、演算の種類を決める必要があります。

• 文字列の場合、EQUAL / INSERT / DELETEのみ考慮すればよいのですが、ノードは変更される場合も含めて考慮する必要があります。
• ノードのデータは同じで位置だけが異なる場合（移動した場合）、深さ、インデックス、親、子などの情報をもとに移動したノードを検出するアルゴリズムを実装しました。しかし、レンダリング結果の変化をみると、最終的に変更された内容（CHANGE）と大差がないため考慮しませんでした。
• 最終的にノードの演算は、EQUAL / INSERT / DELETE / CHANGEに決定しました。
  • CHANGE演算が適用される変更されたノードとは、属性が変更されたり（ex.<p style=”color:red”>→ <p style=”color:blue”>）タグの内容が変更された（ex. <p>内容</p>→ <p>追加内容</p>）ノードを意味しますが、このような場合は、文字列のように単純にDELETE / INSERTに分けずに、変更された部分だけを別々に表示すると、より直感的に変更箇所が分かります。
  • 変更されたノードの基準はタグタイプで、タグタイプの変更は考慮しません。

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はリストに適用できるので、ツリーをリストに変換する必要があります。ツリーを巡回してノードを順番にリストに追加すればよいのですが、ツリーdiffの実装過程であるため、順序を考慮する必要があります。順序は、実際のHTMLテキストと同じ手順をとるためpre-orderを適用します。
• ノード単位のLCSを別々に実装するよりも、文字列単位のLCSを適用する方が早いので、ノードのキー値でLCSを適用します。
• ノードのキー値は保持するすべてのデータを組み合わせてハッシュして生成されます。全く同じノードでない限り、キー値はユニークです。

LCSアルゴリズムの実装プロセスは、以下のとおりです。

• すべてのノードのキー値をリストにし（pre-order）、文字列LCSを適用して、共通のノードリストを生成します。
• 共通のノードリストを基準に、それぞれのツリーノードが同一になるまで検知します。
• 同一（全ノードの値）ノードは、EQUALで処理します。
• 共通ノードまでのノードは、各タグのタイプを基準に、再び共通タイプのリストを生成します。
• 共通タイプのリストを基準に、残りのノードが同一になるまで検知します。
• サンプル
• 同一ではないノードは順番にDELETE / INSERTで処理します。（変更前のノードはDELETE、変更後のノードはINSERT）
• 同一ノードは、タグの内容、属性をそれぞれ比較して、当該演算を付与してdiffリストに追加します。
• 上記のサイクルを共通のノードリストが終わるまで繰り返します。
• 共通のノードリストをすべて検知し、残ったノードのタグタイプで共通タイプのリストを作成し、上記ループをそのまま適用します。
• 属性値（attribute、value）もリストで構成されているので、共通のリストを作成して演算を決定し、diffリストに追加します。

LCSアルゴリズムの適用範囲

実装したLCSは、次のすべてに適用されます。

• diffリストのノードを基準に適用
• 完全一致しないノードのタイプに基づいて適用
• ノードの属性（attribute、value）を基準に適用

LCSアルゴリズムの性能

• LCSアルゴリズムは動的計画法で実装され、時間複雑度がO(N^2)と比較するリストの長さに比例して時間がかかる欠点がありました。
• ノード数が約2000個の場合、diffの計算過程だけでも約12秒かかります。
• パフォーマンス向上のため、性能面で優れているマイヤーズアルゴリズム（Myers Algorithm、Eugene W.Myers）を適用します。

マイヤーズアルゴリズム

• マイヤーズアルゴリズムは2つの文字列間のdiffを計算するアルゴリズムで、実装したHTML diffに必要な共通のノードリストを取得できます。
• HTML diffでLCSアルゴリズムを使用した理由は、解析した2つのツリーの共通のノードリストを取得できるからです。マイヤーズアルゴリズムも同様に、共通のノードリストを取得でき、直接的にマイヤーズアルゴリズムを適用する代わりに、共通のノードリストを取得するLCSアルゴリズムをマイヤーズアルゴリズムに置き換えます。
• マイヤーズアルゴリズムの時間の複雑性は、基本的にO(ND)です（N：比較する2つの文字列の長さの合計、D：変更された文字の数）。
• マイヤーズアルゴリズムは、従来のLCSのアルゴリズムとは異なり、動的計画法ではすべての場合を参照していません。代わりにSES（Shortest Edit Script）アルゴリズムと貪欲アルゴリズムを同時に使用して、最長共通ノードリストを取得すると同時に追加や削除された（INSERT、DELETE、）部分まで見ることができます。※参考

実装プロセス

• マイヤーズアルゴリズムは、文字列を対象に適用されます。しかし、HTML diffではノードリストを対象に適用する必要があるため、LCSアルゴリズムを修正したときと同様に、適用対象を文字列から文字列のリストに変更する作業が必要です。
• 実装にはGoogleのオープンソースを活用しました。Stringクラスは対応するが、Listクラスには対応しない関数をすべて実装し、「段落分け」のような文字列は有するが、リストにはない特徴を活用したロジックは削除・修正して、文字列のリストに適用できるように実装しました。

パフォーマンスの比較

• ノード数が少ないと大差ないが、ノード数が多くなるほどマイヤーズアルゴリズムがより速いことが分かります。

diff内容の可視化

リスト構造で作られたdiffの内容をJSON形式に変換して、Javaスクリプトでそのまま使用します。元のHTMLテキストはレンダリングし、含まれるすべてのタグを配列し、diffリストと比較して、diffの内容（演算はEQUALではなく、すべてのタグ）をレンダリング結果画面に表示します。

視覚化方式（タグの内容を変更）

レンダリングされたHTMLテキストの.innerHTML()関数とjQueryの関数を使用してタグを挿入し、追加/削除を視覚化します。変更された内容（CHANGE）はLCS（Longest Common Substring）アルゴリズムを適用して同じ文字列を除いた部分を追加/削除に分けて視覚化します。視覚化されるCSSは、以下のとおりです。

• 追加：黄緑の背景/緑字
• 削除：オレンジの背景/赤文字/取消線
• 変更：薄紫色の背景/紫字
• 同一：既存のCSSを適用

視覚化方式（タグタイプ、属性の変更）

Microsoft Wordのように右側の空き領域に変更内容をテキストで追加し、対応するタグと下線で結ぶ方式で実装しようとしましたが、結果画面で対象部分を結ぶ作業が想像以上に難しかったです。代わりにタグの左上に変更内容のテキストを追加して表示する方式で適用しました。

• サンプル
  
  タグのoffset座標（top、left）を取得して、適切な位置に表示されるように位置補正演算を実行した後、元のHTMLに挿入します。

元のHTMLタグの中から変更されたタグをターゲット

変更された部分の内容はdiffリストにありますが、正確に元のHTMLのどのタグが変更されたか情報がありません。したがってdiffリストの変更内容を元のHTMLタグと連結させる過程が必要です。

• タグタイプを基準に検索してターゲティングしようとしましたが、同じタグがある場合はエラーが発生します。
• diffリストのノード数は、必ずタグ配列のタグの数よりも同じであるか、または多いです。diffリストのノードには基本的にタグ配列のタグが含まれており（変更後のHTMLに基づいて生成したため）、タグ配列のタグと一致しないDELETEノード（変更前HTMLにあったタグ）があるためです。
• したがってdiffリストのノードとタグ配列のタグを1つずつ比較して、同一の場合はdiffノードの演算で処理し、異なる場合は元のHTMLにタグを追加してdeleteClassを適用します。このとき、タグのインデックスを1増加させてターゲットに問題が生じないようにします。
• diffリストには、EQUAL演算を持つノードも含まれるため、元のHTMLのすべてのタグ配列を取得して、1つ1つ順番に比較すると、正確なターゲティングが可能です。
• しかし、diffリストのノードとタグ配列のタグが完全に一致しないため、（DELETE / INSERTなどの変更ノードは2つずつ追加されたり、DELETEされたタグはHTMLタグの配列に存在しない）インデックスを同期させながら、ターゲットを進行する必要があります。

ターゲットしたタグにアクセス

変更された内容のうち、直接的にレンダリングされる（ex.タグの内容）部分は、元のHTMLを変更して視覚化するため、タグを削除して挿入する方法を使用しようとしたが、上下関係が歪むことが多く（通常、子ノードとして追加）適用できませんでした。
元のHTMLを変更する方法がより簡単だったので、spanタグでタグの内容を別々に囲んで実装しました。追加/削除/変更の表現は、CSSでクラス単位で適用し、spanタグにinsertClass / deleteClass / chageClassを適用して、可読性を向上させました。

変更されたタグの可視化

変更部分はchangeClassを適用しましたが、変更前/後が一目で分からないので、他の方式を適用しました。

• マイヤーズアルゴリズムを適用して追加/削除された部分をそれぞれ表示する方法がありますが、視覚的に追加/削除が交互で表示されると読みにくいです。何よりもdiffノードに追加/削除された部分を1つ1つ入れるのは不可能で（可能ですが、diffノードの追加で順次参照する既存の方式に影響します。）適切ではありません。
• 基準を定めて追加/削除部分のみを表示する方法は、現在のナビゲーション方式にも反せず、視覚的にも大きな問題はありません。基準は、LCS（Longest Common Substring）アルゴリズムを適用し、最も長い共通の文字列は変更されていない部分なので元のまま保存して、LCSの文字列を基準に前/後に追加/削除された部分のみを表示します。すでに実装したinsertClassとdeleteClassを適用して実装しました。

例外処理

• 元のHTMLテキストに含まれるscriptタグが別途JavaScriptコードとして読まれたため、元のHTMLが壊れる問題が発生しました。HTML解析コードに<script>を<script>に変えるコードを追加して解決しました。
• 削除されたタグは変更後のHTMLテキストに存在しないため、別で追加します。元のHTMLにタグを追加するとdiffリストと比較したHTMLタグ配列のインデックスが変わる問題が発生しました。追加するタグの数だけインデックスに加える方法で解決しました。
• 変更されたタグの処理については、LCS（Longest Common Substring）アルゴリズムを適用して、変更された部分と変更されていない部分を分割するとき、.split()関数を使って実装しましたが、変更された部分（基準文字列）が2つ以上ある場合、.split()関数が誤動作することがありました。.split()関数ではなく.indexOf()関数で、変更された部分のインデックスに基づいて、前/後を分けて解決しました。

最終的な結果例

タグの内容：h5→h1 / Hooray！→Dooray！/ delete text equal text→equal text insert text

おわりに

ここでは、diffアルゴリズム関連の資料を調査して実装しました。パーサとJavaのStringクラスの実装方法を中心に検討しました。関数の実装、性能比較、実装時の長所、短所などが分かり、個人的に有意義な時間になりました。

今までにオープンソースを使って分析作業をすることはありましたが、ソースを丸ごと修正したり、すべてのコードを剥がしてみたりするのは初めての経験で、特にHTMLパーサの性能改善作業では、jsoupの実装方法と比較するためコードを熱心に分析しました。
diffアルゴリズムのパフォーマンス改善作業も難しかったです。LCSアルゴリズムを実装してみましたがパフォーマンスが悪く、マイヤーズアルゴリズムに置き換えてオープンソース自体を修正しながら実行しました。マイヤーズアルゴリズムが思ったよりも複雑で実装に時間がかかりましたが、オープンソースを参考にすることで実装するのに役立ちました。