はじめに
TextCompareLab (https://textcomparelab.com/) は、2つのテキストの差分をブラウザの中だけで表示するツールです。貼り付けたテキストはサーバーにアップロードされません。この記事では、その実装のうち次の3点を説明します。
- 行単位の差分(最長共通部分列、LCS)
- 変更された行の中の単語ハイライト
- 2つのテキストをURLのフラグメントに入れて共有する仕組み(Web Crypto による暗号化は任意)
1. 行単位の差分: 最長共通部分列(LCS)
入力を改行で分割して行の配列 A, B を作り、動的計画法で LCS を求めます。
- 先頭と末尾で一致している行を先に取り除く
- 残った部分(長さ N と M)について、後ろから順に表 dp を埋める
- 先頭から表をたどり、一致なら "="、そうでなければ値の大きい方へ進んで "-" または "+" を出力する
for (i = N - 1; i >= 0; i--) {
for (j = M - 1; j >= 0; j--) {
dp[i*W+j] = a[i] === b[j]
? dp[(i+1)*W+j+1] + 1
: Math.max(dp[(i+1)*W+j], dp[i*W+j+1]);
}
}
表は Uint16Array に入れています。取り除いた後の短い方の行数が 65534 を超える場合、または N×M が 3600万を超える場合は計算せず、「ブラウザで比較するには大きすぎる」と表示します。
連続した削除と追加は、同じ数まで対応づけて「変更行」として表示し、余った分を純粋な削除・追加として扱います。時間とメモリは O(N×M) です。
2. 変更行の中の単語ハイライト
変更行として対応づけた2つの行は、さらにトークンに分割して同じ LCS で比較します。トークンの分け方は次の正規表現です。
var TOK = /\s+|[\p{L}\p{N}_]+|[^\s\p{L}\p{N}_]/gu;
空白の連続、文字・数字・アンダースコアの連続、それ以外の記号1文字、の3種類です。\p{L} を使っているので、日本語を含む英語以外の文字もトークンになります。ただし日本語の単語区切りは判定せず、続いている文字列は1つのトークンになります。異なるトークンは で囲んで表示し、出力する前に必ず HTML エスケープしています。
3. 比較オプション
- 空白を無視: 連続する空白を1つにして前後を削除してから比較する
- 大文字小文字を無視: 小文字にそろえてから比較する
- 変更行のみ: 変更の前後3行だけを表示する
最初の2つは、比較する前の文字列の正規化で実現しています。元の表示は元の文字列のままです。
4. 共有リンク: URLフラグメントに入れる
テキストをサーバーに保存せずに共有するため、2つのテキストと比較オプションを URL の # 以降に入れます。# 以降はブラウザがサーバーへ送るリクエストには含まれません。作り方は次の通りです。
- 2つのテキストとオプションを JSON にする
- CompressionStream("deflate-raw") が使える場合は圧縮する
- パスワードありの場合は暗号化する(下記)
- 先頭に形式を示す1バイト(1: 暗号化あり、2: 暗号化なし)と圧縮の有無を示す1バイトを付け、Base64URL にして #s= の後ろに付ける
パスワードありの場合は、まずランダムなパスワードを生成します。紛らわしい文字(0/O、1/I/L など)を除いた31種類の文字から16文字を選ぶので、約79ビット分の選択肢があります。画面にはハイフンで区切って表示し、入力時は英数字以外を取り除きます。このパスワードから PBKDF2(SHA-256、150,000回)で AES-GCM の256ビット鍵を導出し、暗号化します。salt(16バイト)と IV(12バイト)はデータの先頭に付けています。
crypto.subtle.deriveKey(
{ name: 'PBKDF2', salt: salt, iterations: 150000, hash: 'SHA-256' },
keyMaterial,
{ name: 'AES-GCM', length: 256 }, false, ['encrypt', 'decrypt']);
読み込み側は、先頭の1バイトで暗号化あり・なしを判別します。暗号化なしのリンクは、パスワードを聞かずにそのまま内容を開きます。展開後のサイズには上限(2MB)を設けて、細工された圧縮データで大量のメモリを使わないようにしています。
共有リンクの制約
- パスワードなしのリンクは暗号化されていません。リンクを知っている人は誰でも内容を読めます。
- パスワードありの場合も、リンクとパスワードの両方を持っている人は読めます。パスワードはリンクとは別のメッセージで送ることを前提にしています。
- リンクを無効にしたり、1回限りに制限したりすることはできません。
- URL の長さには限りがあるため、作成したリンク全体が8000文字を超える場合は共有できません。
おわりに
処理がすべてブラウザの中で完結するため、サーバー側に保存の仕組みを持たずに済みます。その代わり、リンクの取り消しや大きな入力には対応していません。実装についてのご指摘や質問があれば、コメントでお知らせください。
※ この記事の日本語は、機械翻訳・AI の支援を受けて作成しました。コードや数値は TextCompareLab の実際の実装と照合していますが、不自然な表現があればお知らせください。