[解決済み] 短縮URLの作成方法を教えてください。[クローズド］

質問

入力フィールドに長いURLを書くと、そのURLを"に短縮してくれるサービスを作りたいのですが、どうすればいいですか？ http://www.example.org/abcdef となります。

の代わりに、" abcdef を含む6文字の文字列を使用することができます。 a-z, A-Z and 0-9 . つまり、560〜570億個の文字列の可能性があるのです。

私のアプローチ

私は3つのカラムを持つデータベースのテーブルを持っています。

1. id, 整数, オートインクリメント
2. long, 文字列, ユーザーが入力した長いURL
3. short, 文字列, 短縮されたURL(または6文字のみ)

そして、長いURLをテーブルに挿入します。そして、"の自動インクリメントの値を選択します。 id "のハッシュを構築します。このハッシュは、" short "です。しかし、どのようなハッシュを作ればいいのでしょうか？MD5のようなハッシュアルゴリズムでは、長すぎる文字列が作成されてしまう。私はこのようなアルゴリズムは使わないと思う。自分で作ったアルゴリズムでもいい。

私のアイデアです。

に対して、"。 http://www.google.de/ 自動インクリメントの ID を取得します。 239472 . そして、次のような手順で行っています。

short = '';
if divisible by 2, add "a"+the result to short
if divisible by 3, add "b"+the result to short
... until I have divisors for a-z and A-Z.

それを、割り切れない数字がなくなるまで繰り返せばいいんです。これは良い方法だと思いますか？もっといいアイデアはないでしょうか？

<サブ このトピックへの関心が続いているため、私は 効率的な解決策をGitHubに公開 に対する実装を含む。 JavaScript , PHP , Python および ジャワ . もしよろしければ、あなたのソリューションを追加してください :)

解決方法は？

私は、あなたの「数値を文字列に変換する」アプローチを継続します。しかし、あなたの提案したアルゴリズムは、あなたのIDが 素数かつ52より大きい .

理論的背景

が必要です。 射影関数 f . これは、逆関数を求めるために必要です。 g('abc') = 123 に対して f(123) = 'abc' 関数を使用します。ということになります。

• があってはならない。 x1、x2 (x1≠x2であること) を作ることになる。 f(x1) = f(x2) ,
• で、すべての y を見つけることができなければなりません。 x そのため f(x) = y .

IDを短縮URLに変換する方法

1. 使いたいアルファベットを考える。あなたの場合、それは [a-zA-Z0-9] . これには 62文字 .

2. 自動生成されたユニークな数値キー（自動インクリメントされた id は、例えばMySQLのテーブルのようなものです。）

   この例では、125 <サブ 10 (10を底とする125)。

3. ここで、125を変換する必要があります <サブ 10 をX <サブ 62 (62番台)になります。

   125 <サブ 10 = 2×62 ¹ + 1×62 ⁰ = [2,1]

   これには、整数の除算とモジュロの利用が必要です。擬似的なコード例です。

   digits = []
   
   while num > 0
     remainder = modulo(num, 62)
     digits.push(remainder)
     num = divide(num, 62)
   
   digits = digits.reverse
   
   

   ここで インデックス 2 と 1 をアルファベットに変換します。このようなマッピング（例えば配列の場合）は、次のようになります。

   0  → a
   1  → b
   ...
   25 → z
   ...
   52 → 0
   61 → 9
   
   

   2→cと1→bで、cbを受け取ります。 <サブ 62 を短縮URLとします。

   http://shor.ty/cb
   
   

短縮URLを初期IDに解決する方法

逆はもっと簡単です。アルファベットで逆引きをすればいいのです。

1. e9a <サブ 62 は "アルファベットの4番目、61番目、0番目の文字" に解決されます。

   e9a <サブ 62 = [4,61,0] = 4×62 ² + 61×62 ¹ + 0×62 ⁰ = 19158 <サブ 10

2. ここで、データベース・レコードを WHERE id = 19158 で、リダイレクトを行います。

実装例（コメント欄よりご提供いただきました）

• C++
• Python
• ルビー
• ハスケル
• C#
• コーヒースクリプト
• パール