-1

サイトの URL 短縮機能を構築しています。

現時点でわかっていること:

  • URL ( http://www.google.com ) を取得して sha1 すると、40 文字のハッシュ (738ddf35b3a85a7a6ba7b232bd3d5f1e4d284ad1) になります。
  • sha1 ハッシュを取得し、それを base62 (基本的に AZ、az、0-9) にエンコードし、元の sha1 にデコードできる 28 文字のハッシュ (jNMYchEoche67ro1k5gsCcHfDzmR) になります。

sha1 を使用する理由は、ユーザーが現在または過去の URL から次の URL を推測できないようにするためです。

base62 を使用する理由は、URL を有効にしてユーザーが読み取れるようにするためです。

ドメインに追加される 28 文字の「短い URL」 ( http://www.google.com/r/jNMYchEoche67ro1k5gsCcHfDzmRis ) は、特に Twitter の文字制限を考慮すると、少し長すぎます。

現在検討しているのは、sha1 を約 20 文字削減することです。これにより、14 文字の短縮 URL が生成されますが、さらに削減すると、衝突が早すぎるのではないかと懸念されます。

大きな数値 (または文字列) を小さな値に圧縮することも考えましたが、それには 28 文字または 14 文字のハッシュを 2 つに分割して並べ替える必要があり、そこから元のハッシュに戻す方法がわかりません。

私たちに何ができるか考えている人はいますか？URL を構築するためにデータベースに依存しないソリューションを希望しますが、DB が必要な場合は、Redis / MongoDB に限定されていることに注意してください (つまり、自動インクリメント整数フィールドはありません)。

4

1 に答える 1

0

私はあなたの要件をすべて理解しているかどうか確信が持てませんが、ここに私が考えていることがあります..

sha1 を削減するのが正しいアプローチのようです。

DB にすべての短い URL を「登録」すると、衝突時に別の短い URL を割り当てようとすることで、衝突を回避できます (DB でハッシュが既に見つかっている場合は、衝突が発生しています)。

次のように機能します。

  1. 新しいハッシュを割り当てて、必要なだけsha1をカットしてみてください。結果としてHASH1が得られます
  2. DBで衝突チェック、衝突なし、HASH1をDBに登録して終了
  3. 衝突が発生した場合は、新しいハッシュの割り当てを試みます。たとえば、sha1 を 1 文字少なくして (結果としてハッシュが長くなります)、結果として HASH2 が得られます。
  4. 衝突をチェック.. (ステップ 2) など

ハッシュの正しい長い URL を検索するたびに、もちろん DB を参照する必要があります。sha1 は元に戻せないので、それはあなたがすでに行っていることだと思います。

最初に sha1 をどこまで削減する必要がありますか? 次の URL を推測するのが難しくなるという要件を満たしている限り、可能な限り多くのことを言いたいと思います。sha1 の 5 バイト (つまり 40 ビット) だけを残すことは、推測するのが非常に難しいと思います.. (DB に 100 万の短い URL がある場合でも、100 万分の 1 になります)

于 2013-01-31T16:18:38.460 に答える