ローカルセンシティブハッシュ

11. 07. 2022

Obsah článku

ほとんどのドキュメントフィンガープリントハッシュ関数の原理は、すべての入力に対して常に同じ出力を返すことである。これを決定論的挙動という。同時に、入力が少し変わると出力が大きく変わる（事実上、全く別のハッシュを返す）。特に、入力文書が変更されたかどうかを確認し、変更された場合は全く別のものを取得したい場合に有効である。そのような関数の例として、MD5やSHA1がある。

ハッシュから元の入力の内容を推測したい場合、簡単な方法はなく、ヒットするまで各オプションをブルートフォース（総当り）するほかない。これは、出力の変化が大きいため、目標に近づいているかどうかを反復で判断できないためである。

BCryptのようなハッシュ関数では、同じ入力に対して毎回異なる出力を返すことで、パスワードハッシュに対して堅牢にしているものがある。実は、出力には直接ソルトが含まれており、いわゆる辞書攻撃は不可能なのです。この機能は、パスワードのハッシュ化だけに有効ですが、ドキュメントのレビューにはとても不向きです。

文書の類似性チェックとコンテンツの重複検索

あるWebページがどれだけ変化したかを調べたいWeb検索エンジンのアルゴリズムを解いていると想像してください。あるいは、あるページのテキストが別のページのテキストと似ているか、あるいは完全に重複しているかをすばやくチェックしたい。

これを検証する一つの方法は、各ページを相互に比較することであるが、これは非常にシステムリソースを消費する。SHA1ハッシュを計算する方法もありますが、これは文書全体の内容をハッシュ化するため、ページが1文字でも変わると別のハッシュになってしまうので、今回の目的には適していません。

そこで、文書の異なる領域から異なる方法でハッシュを計算し、ハッシュ関数の出力の変化を調べることが一つの解決策となる。

ロケールセンシティブハッシュの原理

ハッシュを計算したいウェブページのHTMLコードをダウンロードした。正しく設定する必要があるアルゴリズムによって、文書をさまざまな領域（セル）に分割します。

各領域を共通のアルゴリズムで独立にハッシュ化し、その結果を連結して一つの文字列とする。

すると、例えば「3791744029724361934」（このコンテンツハッシュはAhrefsツールから提供されたものです）のように出力することができます。

例えば、ヘッダーの内容が最初の5文字、フッターの内容が最後の5文字を表していることが分かれば、文字列の真ん中がページの内容を表していることが分かるのです。フッターの内容がすべてのページで変わった場合（たとえば、ウェブマスターが新しいリンクを追加した、更新日が変わったなど）、新しいバージョンのページをダウンロードすると、右側の領域のハッシュの数文字だけがわずかに変わり、フッターだけが変わり、中身は変わっていないことがわかるのです。ですから、そのような変更は無視できますし、サイト全体を確認する必要もありません。

Googleはどのようにウェブクローリングを最適化しているのですか？

インターネットボットは、保存できるところは保存しておく必要があります。ウェブクローリングは非常に高価で、更新には計算時間がかかります。

例えば、Googleのロボットアルゴリズムの挙動を観察していると、コンテンツの大きな変化にしか反応しないことが観察されました。ページの変更が少ない場合は、通常の方法でクロールされます。しかし、例えばサイトのフッターやヘッダーが大きく変わった場合、それをリデザインと評価し、一刻も早く新しい姿にするためにサイトの大部分を一気に見直します。

また、同様の方法でサイト間の重複も検出します。ページのグループが非常に似ていたり、同じコンテンツを持っていたりすると、非常に似たハッシュが得られます。ロボットはこのハッシュを使って、ドキュメントが似ていることをすばやく確認し、正規のものを選択して残りを無視することができます。

ハッシュ関数の実装

PHP には、ロケールを考慮したハッシュ関数の既製の実装はありません。同時に、この機能をうまく実装したフリーで使えるパッケージも知らない。

Jan Barášek Více o autorovi

Autor článku pracuje jako seniorní vývojář a software architekt v Praze. Navrhuje a spravuje velké webové aplikace, které znáte a používáte. Od roku 2009 nabral bohaté zkušenosti, které tímto webem předává dál.

Rád vám pomůžu: