最近、次の仮定で Web ページをハッシュするには何ビットあれば十分かという質問がありました。
- 10億のWebページがあります
- Web ページの平均の長さは 300 語です
- 私たちは英語で250,000語を持っています
- ページは ASCII です
どうやらこの問題に対する唯一の正解はないようですが、質問の目的は、一般的な方法がどのように機能するかを確認することです。
質問する
169 次
1 に答える
2
「Web ページをハッシュする」とはどういう意味かを定義していません。そのフレーズは、この質問とインターネット上の他のいくつかのページに表示されます。sha1sumこれらの他のページでは、コンテンツが完全であることを確認するためにチェックサムを計算することを意味するために使用されます (たとえば、 を使用)。それがあなたの言いたいことなら、「ハッシュ」されるページのすべてのビットが必要です。平均すると、300 * 8 * 平均的な英単語の長さになります。この質問では英単語の長さの平均は指定されていませんが、5 文字とスペースの場合、1 ページあたりの平均ビット数は 6*300*8 または 14400 です。
代わりに、すべての Web ページのすべての単語をインデックス構造に入れて、任意の単語セットを含むすべての Web ページを検索できるようにする場合、1 つの答えは約 10^13 ビットです。 10億ページ。各参照は log_2(1G) ビット、または参照が単純に格納されている場合は約 30 ビットを使用します。したがって、9 兆ビット、つまり約 10^13 になります。また、10 億個の URL のナイーブ ストレージは、それよりも少なくとも 1 桁小さく、最大で 10^12 ビットであることがわかります。特別な方法を使用して参照ストレージを数桁削減することもできますが、URL は (たとえばトライを介して) 圧縮またはコンパクトに保存する方が簡単であるため、参照ストレージは URL の格納に必要な量よりもはるかに多くなる可能性があります。 .
于 2012-10-11T02:03:38.350 に答える