@d-zero/page-cluster

v0.6.4

Published

8 days ago

Clusters crawled HTML pages by DOM-structure similarity — assigns the same key to pages sharing a template, ignoring text content. CLI-first, with library APIs.

0High
0Medium
0Low

yusukehirao

dz_furukawa

dz_kumazawa

`@d-zero/page-cluster`

大量クロール HTML の重複・類似ページを構造トークンで検出するパッケージ。HTML ページ集合を受け取って、同一テンプレートと判定できるページに同じクラスタキーを振る。テキストは無視して DOM 構造だけを見るので、本文が違っても同じテンプレートを使うページ群は 1 つのクラスタにまとまる。単一サイトで数万〜十数万ページ規模のクロール成果物を、テンプレート単位に畳んで概観したいときに使う。CLI が主、ライブラリ関数群がオマケ。

Installation

yarn add @d-zero/page-cluster

インストールすると page-cluster コマンドが node_modules/.bin/ 配下に入る。

Usage

CLI

page-cluster [--content-block-attribute <name>] [--cluster-reasons-file <path>] < pages.jsonl > clusters.jsonl

入力: JSONL 1 行 1 ページ。フィールドは以下。html 以外はすべて任意（paths / stylesheetHrefs がないと粗い分類になる）。

{
	"id": "任意の識別子",
	"html": "<html>...</html>",
	"paths": ["news", "1"],
	"stylesheetHrefs": ["/a.css"],
	"host": "example.com"
}

出力: JSONL 1 行 1 ページ、入力順。

{ "id": "任意の識別子", "clusterKey": "..." }

--cluster-reasons-file <path> を指定すると、処理完了後に別ファイルとして「クラスタ選定理由」を書き出す。ページ単位ではなくクラスタ単位（clusterKey をキーにしたオブジェクト、1 クラスタにつき 1 エントリ）なので、ファイルサイズはページ数ではなくクラスタ数に比例する — ページ単位のレポートと違い、コーパスサイズの上限はない。各エントリは「なぜこのページ達が同じクラスタになったか」の根拠を構造化データとして返す: ブロッキング理由（共有 stylesheet 集合 or URL パスプレフィックス）、クラスタ内で共有されている DOM 構造トークンのコア、landmark タイプ（header/footer/nav/aside/form/search）ごとのクラスタ内共通性、そして同一ブロッキンググループ内で分岐した兄弟クラスタのキー一覧。

{
	"[\"path:news\",\"cluster:0\"]": {
		"memberCount": 42,
		"blocking": [
			{ "blockKey": "path:news", "reason": { "kind": "path", "pathKey": "news" } }
		],
		"structuralCoreTokens": ["body>main>article", "..."],
		"landmarks": {
			"header": {
				"presenceRate": 1,
				"chromeRate": 1,
				"shellTokens": ["..."],
				"memberCountWithInstance": 42
			},
			"aside": {
				"presenceRate": 0.3,
				"chromeRate": 0,
				"shellTokens": [],
				"memberCountWithInstance": 13
			}
		},
		"siblingClusterKeys": ["[\"path:news\",\"cluster:1\"]"]
	}
}

上の例は、header はクラスタ全体で共通の chrome（chromeRate: 1）である一方、aside は 42 ページ中 13 ページにしか無く chrome とは判定されていない（chromeRate: 0）ことを示す。つまり「ヘッダーは共通だが、サイドナビの有無で分かれているページがある」という状況を数値で表している。siblingClusterKeys は同じブロッキンググループ内で Stage A/B が結局別クラスタのままにした相手のキーで、それぞれの ClusterReason を突き合わせれば「何が違って分かれたか」を呼び出し側で解釈できる。理由は構造化データのみで、文言化（「ヘッダーが共通です」等）は呼び出し側の責務。

landmark の位置情報そのもの（HTML 内のどこにあるか）が必要な場合は、ライブラリの extractLandmarks（ステートレス・公開 API）をページの HTML に対して自分で呼び、その結果と ClusterReason.landmarks[type].shellTokens を突き合わせて isChromeLandmarkInstance（同じく公開 API）で chrome 判定すればよい。詳細は Library 節を参照。

クローラ出力が JSON 配列の場合は jq で line-delimited に変換して食わせる:

jq -c '.[]' crawl-output.json | page-cluster > clusters.jsonl

オプション

--content-block-attribute <name> — CMS が自由編集コンテンツブロックに付与している属性名（例: data-bgb）が分かっている場合に指定する。指定すると比較前にその属性を持つ要素配下を無視するので、同じテンプレートで本文構成だけ違うページを混同しなくなる。唯一の site-specific なオプションで、未指定でも <main> / role="main" を起点にした自動深さキャップが常時働く（詳細は resolve-page-cluster-keys.ts の JSDoc を参照）
--cluster-reasons-file <path> — 上記の「クラスタ選定理由」を <path> に JSON として書き出す。ページ数の上限はない。20,000 ページ以下のコーパスでは、指定すると進捗表示（後述）は出なくなる（進捗を出さない非ストリーミング経路に常に振り分けられるため。20,000 ページ超のストリーミング経路では進捗表示・クラスタ理由の両方が動く）
--validation-file <path> — 分類結果の事後検証レポート（下記「分類結果の事後検証」参照）を <path> に JSON として書き出す。指定すると、レポートの検出結果のうち安全に統合できるもの（構造トークン集合が完全一致、またはミラー軸による裏付けあり）が stdout の clusterKey にも自動的に反映される
--help / -h — ヘルプを表示する
--version / -v — バージョンを表示する

進捗表示

処理中は stderr に進捗を出す。stdout の JSONL 出力は影響を受けない。

対話端末（TTY）: アニメーション付きの単一ヘッダー行が in-place に書き換わり、現在のフェーズ・進捗・経過時間を表示する。

🌏 page-cluster — clustering 12/47 blocks (elapsed 23s)

非 TTY（パイプ・ファイルリダイレクト・CI）: [page-cluster] ... 形式の行を追記する。pass0: / pass1: / pass1b: / stage-b: の phase トークンを含むので grep / awk 互換。

[page-cluster] reading input pages...
[page-cluster] read 10000 pages, clustering...
[page-cluster] pass0: 10000 pages read
[page-cluster] pass1: clustered block 12/47
[page-cluster] pass1b: 30000/70000 pages assigned
[page-cluster] stage-b: merging 47 units
[page-cluster] done — 10000 pages in 47 clusters (elapsed 87s)

silence したい場合は 2>/dev/null。ログに残したい場合は 2> progress.log。

Library

サブパスエクスポート構成。import パスと提供関数の対応は以下。

| import パス | 提供関数 | | ---------------------------------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | @d-zero/page-cluster | tokenize — <body> 配下を構造トークン列に変換する低レベルプリミティブ | | @d-zero/page-cluster/resolve-page-cluster-keys | resolvePageClusterKeys（非同期・ファクトリ入力・メモリ有界のメインエントリー）、resolvePageClusterKeysFromArray（array 入力ラッパー）、resolvePageClusterKeysInMemory（同期・array 入力）。onClusterReason コールバックを渡すと、確定したクラスタごとに 1 回だけ ClusterReason を通知する | | @d-zero/page-cluster/build-cluster-reason | ClusterReason / LandmarkClusterProfile 型、buildClusterReason — クラスタ選定理由の型定義と組み立て関数（通常は resolvePageClusterKeys の onClusterReason 経由で使うので直接呼ぶ必要はない） | | @d-zero/page-cluster/extract-landmarks | extractLandmarks — header / footer / nav / aside / form / search / main の 7 種を抽出し、インスタンスごとの生 HTML と HTML 内の位置（line/column・文字列オフセット）を返す | | @d-zero/page-cluster/resolve-landmark-variant-keys | resolveLandmarkVariantKeys — 特定ランドマークのデザインバリアントでページを分類 | | @d-zero/page-cluster/is-chrome-landmark-instance | isChromeLandmarkInstance — 1 つの landmark インスタンスのトークン集合と ClusterReason.landmarks[type].shellTokens のようなシェルトークン集合を突き合わせて chrome/content を判定するステートレス関数 | | @d-zero/page-cluster/jaccard-similarity | jaccardSimilarity — 2 つのトークン集合の Jaccard 類似度。ClusterReason 同士（structuralCoreTokens や shellTokens）を比較して兄弟クラスタとの差分を調べる用途などに使う | | @d-zero/page-cluster/validate-cluster-partition | ClusterPartitionReport 型、validateClusterPartition — 分類済みの clusterKey を、分類そのものではなく分類結果同士を突き合わせて事後検証する（下記「分類結果の事後検証」参照）。通常は resolvePageClusterKeys の onPartitionReport 経由で使うので直接呼ぶ必要はない | | @d-zero/page-cluster/find-cross-cluster-duplicates | ClusteredPage 型、CrossClusterDuplicate 型、findCrossClusterDuplicates — 別クラスタに分かれているが同一テンプレートらしいページ対を検出する | | @d-zero/page-cluster/compute-cluster-cohesion | ClusterCohesion 型、computeClusterCohesion — クラスタ内メンバーが互いにどれだけ似ているかを分布として報告する（無関係なテンプレートが混ざったクラスタの検出に使う） | | @d-zero/page-cluster/detect-mirror-axis | MirrorAxis 型、detectMirrorAxis — 言語ディレクトリなど、URL のあるセグメントだけを変えてサイトの一部をミラーしている「軸」を、事前知識なしに URL パス集合から発見する | | @d-zero/page-cluster/normalize-path-by-mirror-axis | normalizePathByMirrorAxis — 検出した軸に沿ってページの URL パスを正規化し、ミラー元同士を同じ形状に揃える | | @d-zero/page-cluster/normalize-href-by-mirror-axis | normalizeHrefByMirrorAxis — 検出した軸に沿って URL（主に stylesheet href）を正規化する | | @d-zero/page-cluster/merge-validated-clusters | mergeValidatedClusters — 確認済みのクラスタ対の統合を clusterKey 配列に適用する純関数 |

import { resolvePageClusterKeysFromArray } from '@d-zero/page-cluster/resolve-page-cluster-keys';

const keys = await resolvePageClusterKeysFromArray([
	{
		paths: ['news', '1'],
		stylesheetHrefs: ['/a.css'],
		html: '<body><article>one</article></body>',
	},
	{
		paths: ['news', '2'],
		stylesheetHrefs: ['/a.css'],
		html: '<body><article>two</article></body>',
	},
	{
		paths: ['about'],
		stylesheetHrefs: ['/a.css'],
		html: '<body><section>about</section></body>',
	},
]);
// keys[0] === keys[1]（同一テンプレート）、keys[2] は別クラスタ

オプション・型・設計判断の WHY はすべて各関数の JSDoc に記載している。CLI 経由で十分な場合は読み飛ばして OK。

アルゴリズム概観

clusterKey がどう決まるかを知っておくと、出力の解釈（なぜこの 2 ページが同じキーなのか）とオプションの選択がしやすくなる。実装詳細の WHY は各ソースファイルの JSDoc が正。

全体パイプライン

flowchart TD
    IN[入力ページ集合] --> P0["Pass 0: ブロッキング<br>URL パス + first-party CSS 集合 → blockKey<br>（orphan ページの再割当を含む）"]
    P0 --> GATE{"ページ数 ≤ 20,000?"}

    GATE -- "yes（in-memory）" --> CHROME_ALL["chrome discovery（コーパス全体）<br>ランドマーク署名の度数分布に auto-cut<br>→ グローバル chrome 除外 / ローカル chrome 再注入"]
    CHROME_ALL --> SA_ALL["Stage A × 全ブロック<br>深さキャップ → tokenize →<br>complete-linkage + auto-cut → 包含割当"]

    GATE -- "no（ストリーミング）" --> RES["ブロックごとにリザーバサンプリング<br>（各ブロック最大 100 ページ、決定的シード）"]
    RES --> SA_SAMPLE["chrome discovery + Stage A<br>（サンプルのみ、ブロック単位で逐次 flush）"]
    SA_SAMPLE --> P1B["Pass 1b: 非サンプルページを<br>max-Jaccard で最寄りクラスタへ割当"]

    SA_ALL --> SB["Stage B: ブロック越えマージ<br>（不動点ループ、下図）"]
    P1B --> SB
    SB --> OUT["clusterKey を入力順に出力"]

Pass 0（ブロッキング） — HTML を読まず、URL パスと first-party stylesheet 集合だけで粗く分割する。高価な構造比較を同一ブロック内に閉じ込め、コーパス全体の比較コストを O(n²) から劇的に減らす。stylesheet を持たない orphan ページは同一セクションの CSS ブロックへ再割当される
chrome discovery — 全ページのランドマーク署名の度数分布に auto-cut を当て、閾値以上を「グローバル chrome」（サイト共通のヘッダー等）として比較から除外し、閾値未満かつ 2 ページ以上に出現するものを「ローカル chrome」（セクション固有のナビ等）としてトークン再注入する
Stage A（ブロック内クラスタリング） — ブロックごとに直線的な処理。<main> の深さキャップ（候補深度を全走査して knee を探す自動選択）→ tokenize → complete-linkage 階層クラスタリング → max-gap auto-cut でカット高を決定 → 最後に包含関係にあるクラスタを吸収する包含割当（割当チェーンを辿り、循環はメンバー最大のクラスタをルートに選んで解決）
Pass 1b（ストリーミング時のみ） — 20,000 ページ超では各ブロックをリザーバサンプリング（最大 100 ページ、ブロックキーをシードにした決定的乱数）で代表させ、サンプル外のページは Stage A 完了後に max-Jaccard で最寄りクラスタへ一括割当する。メモリ使用量はコーパス全体ではなくサンプルサイズに比例する
Stage B（ブロック越えマージ） — ブロック分割はあくまで比較コスト削減のためなので、最後に同一テンプレートがブロックを跨いで分かれていないか再統合する。これが唯一の反復処理（次節）。収束後、onClusterReason が指定されていれば、確定した最終クラスタごとに ClusterReason を 1 回ずつ組み立てて通知する — 追加の全コーパススキャンではなく、Stage A/B が既に計算済みの中間データ（quorum core、landmark インスタンス、ブロッキング根拠）を再利用するだけなので、クラスタ数にしか比例しない

Stage B: ブロック越え統合の不動点ループ

flowchart TD
    START["ラウンド開始（最大 10 ラウンド）"] --> CORE["現在のプール済みメンバーから再計算:<br>文書頻度 → distinctive tokens → quorum core（80%）"]
    CORE --> FINE["fine stage（単一 union-find 上で 3 経路）:<br>① complete-linkage（固定 0.8）<br>② 包含割当（0.9、チェーン走査 + サイクル解決）<br>③ shape-Jaccard（0.9、複数ページユニットのみ）"]
    FINE --> Q1{"fine でマージ発生?"}
    Q1 -- yes --> APPLY1["マージ適用（メンバー統合）"]
    APPLY1 --> START
    Q1 -- no --> L2["L2 stage:<br>L2 signature 包含 + shell 相互裏付け<br>（shell は auto-cut で自己発見）"]
    L2 --> Q2{"L2 でマージ発生?"}
    Q2 -- yes --> APPLY2["マージ適用"]
    APPLY2 --> START
    Q2 -- no --> DONE["収束 — 全ユニットのキーが不動点に到達"]

マージが起きるとユニットのメンバー構成が変わり、文書頻度も quorum core も変わる。そのため毎ラウンド、統合後のプールから全指標を再計算してマージを再試行する。fine stage・L2 stage の両方でマージが 1 件も出なくなった時点で不動点に到達したとみなして収束する（安全弁として最大 10 ラウンド。実データでは 7 ラウンド以内に収束）。L2 stage は fine stage が空振りしたラウンドでしか実行されない最後の粗い経路で、誤マージ防止のために shell（ランドマーク由来トークン）の相互裏付けを要求する。

fine stage・L2 stage いずれの経路で提案されたマージも、適用前に凝集度ガードを通る: 統合後の quorum core が統合前の core に対して一定比率を下回るなら、そのマージは破棄される。個々の経路が「統合前のペア類似度」だけを見て提案する一方、複数ラウンドにわたる連鎖的な統合は「統合後に実際どれだけまとまっているか」を悪化させ得る（無関係なテンプレート同士が少しずつ吸収し合う catch-all 化）ため、経路をまたいだ単一のチェックポイントとして機能する。あわせて、L2 stage 自体もラウンド開始前に判別力を検査し、参加ユニット全体が同一の署名形状に潰れている（main 直下の浅い階層しか手がかりが残っていない等）場合は、そのラウンドの L2 比較を丸ごとスキップする。詳細は merge-cross-block-clusters.ts の filterMergesByCohesion / hasDiscriminatingL2Signatures の JSDoc を参照。

Self-tuning

閾値の多くは max-gap auto-cut（度数分布の隣接ギャップ最大の中点を境界とする）でデータから自己発見される。① Stage A のカット高、② Stage B の shell 判定、③ chrome discovery のグローバル/ローカル判定、④ Pass 0 の URL パス深さ選択、の 4 箇所で同一プリミティブを再利用しているので、サイトごとにハイパーパラメータをチューニングする必要はない。詳細は autoCutThreshold の JSDoc を参照。例外的に Stage B fine stage の complete-linkage だけは固定閾値 0.8 を使う（理由は merge-cross-block-clusters.ts の JSDoc を参照）。

分類結果の事後検証

Stage A/B は「クラスタリング中に」正しい判断をしようとするが、判断材料はその時点でのペア類似度に限られる。分類が終わったあとで、確定したパーティション同士を突き合わせて検証する方が、同じ種類の誤りをかえって見つけやすい場合がある: マージ中は局所的なペア情報とマージ順序しか持たないが、事後なら分割全体を一度に見られるからだ。この事後検証は Stage A/B のアルゴリズムに一切依存しないので、resolvePageClusterKeys 以外で作られた分類結果（保存済みの clusterKey をアーカイブから読み戻した場合など）にも使える。

3 つのチェックを行う。

クラスタ間重複検出（findCrossClusterDuplicates） — 別クラスタに分かれているページ対のうち、構造トークン集合が完全一致するもの（軸の裏付けなしで確定）と、ミラー軸で裏付けられる近似一致のものを検出する
クラスタ内凝集度（computeClusterCohesion） — クラスタ内のメンバー同士がどれだけ似ているかを中央値・10 パーセンタイル・最小値の分布として報告する。無関係なテンプレートが混ざったクラスタは、共通のシェル由来トークンだけが一致する形で structuralCoreTokens 自体は非空のまま残ることがあるため、core の有無だけでは過剰マージを検出できない
ミラー軸の自動発見（detectMirrorAxis） — 言語ディレクトリのように、URL のあるセグメントだけを変えてサイトの一部をミラーしている構造を、言語コード等の事前知識なしに発見する。同じ値集合が何種類の異なるパス骨格にわたって反復するかを数え、autoCutThreshold で「たまたま値が 2 つ以上あるだけの兄弟ページ」と「サイト全体を貫く軸」を切り分ける

validateClusterPartition はこの 3 つをまとめて呼び出すエントリポイント。ClusterReason と同じく、判断結果ではなく構造化データだけを返す — 検出された重複をどう扱うか（統合するかどうか、suspicious フラグをどう解釈するか）は呼び出し側の責務。実際に統合を適用する場合は mergeValidatedClusters に確認済みのクラスタ対を渡す。

import { mergeValidatedClusters } from '@d-zero/page-cluster/merge-validated-clusters';
import { validateClusterPartition } from '@d-zero/page-cluster/validate-cluster-partition';

const report = validateClusterPartition(pages); // pages: { clusterKey, tokens, paths, stylesheetHrefs }[]
const safeToMerge = report.crossClusterDuplicates.filter(
	(d) => d.similarity === 1 || d.corroboratedByMirrorAxis,
);
const mergedKeys = mergeValidatedClusters(clusterKeys, safeToMerge);

resolvePageClusterKeys に onPartitionReport コールバックを渡すと、この検証が Stage B 完了直後に自動的に走り、上記と同じ安全な統合ポリシー（完全一致、またはミラー軸による裏付けあり）が返り値の clusterKey にもそのまま反映される。onClusterReason と同じくオプトインで、渡さない限り既存の挙動・出力は一切変わらない。詳細はその JSDoc を参照。