algorithm 短縮url api - URL短縮名を作成するにはどうすればよいですか?





13 Answers

なぜあなたはハッシュを使いたいのですか?

自動インクリメント値を英数字の値に単純に変換するだけで使用できます。 基本変換を使って簡単に行うことができます。 文字スペース(AZ、az、0-9など)が40文字あるとし、そのIDを40進数に変換して文字を数字として使用します。

方法 実装 自前

私は長いURLを入力フィールドに書くことができるURL短縮サービスを作成したいし、サービスはURLを " http://www.example.org/abcdef "に短縮します。

" abcdef "の代わりに、 az, AZ and 0-9を含む6文字の他の文字列を使用できます。 それは56〜570億の文字列を可能にします。

私のアプローチ:

私は3つの列を持つデータベーステーブルを持っています:

  1. id、整数、自動インクリメント
  2. long、string、ユーザーが入力した長いURL
  3. 短い、文字列、短縮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.

これは、その数がもはや割り切れない迄繰り返すことができます。 これは良いアプローチだと思いますか? あなたは良いアイデアを持っていますか?

このトピックへの関心が継続しているので、 JavaScriptPHPPythonJava実装により、 GitHubの効率的なソリューションを公開しました あなたのソリューションを追加したい場合は:)




あなたの質問に対する答えではありませんが、大文字と小文字を区別した短縮URLは使用しません。 彼らは覚えがたく、通常は読めない(多くのフォントは1と1と0とOと他の文字を非常によく似ているので、違いを伝えることは不可能である)と間違いやすい。 大文字または小文字のみを使用してください。

また、あらかじめ定義された形式で数字と文字を混在させる形式を試してください。 人々が他のフォームよりも優れた1つのフォームを思いつく傾向があることを示す研究があります(電話番号は特定の形式でグループ化されています)。 num-char-char-num-char-charのようなものを試してみてください。 特に大文字と小文字の区別がない場合は、組み合わせを減らすことができますが、より使いやすく有用なものになります。




ここに私のPHP 5クラスがあります。

<?php
class Bijective
{
    public $dictionary = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

    public function __construct()
    {
        $this->dictionary = str_split($this->dictionary);
    }

    public function encode($i)
    {
        if ($i == 0)
        return $this->dictionary[0];

        $result = '';
        $base = count($this->dictionary);

        while ($i > 0)
        {
            $result[] = $this->dictionary[($i % $base)];
            $i = floor($i / $base);
        }

        $result = array_reverse($result);

        return join("", $result);
    }

    public function decode($input)
    {
        $i = 0;
        $base = count($this->dictionary);

        $input = str_split($input);

        foreach($input as $char)
        {
            $pos = array_search($char, $this->dictionary);

            $i = $i * $base + $pos;
        }

        return $i;
    }
}



あなたはURL全体をハッシュすることができますが、idを短縮したい場合は、marcelが示唆したようにします。 私はこのPythonの実装を書いた:

Python




alphabet = map(chr, range(97,123)+range(65,91)) + map(str,range(0,10))

def lookup(k, a=alphabet):
    if type(k) == int:
        return a[k]
    elif type(k) == str:
        return a.index(k)


def encode(i, a=alphabet):
    '''Takes an integer and returns it in the given base with mappings for upper/lower case letters and numbers 0-9.'''
    try:
        i = int(i)
    except Exception:
        raise TypeError("Input must be an integer.")

    def incode(i=i, p=1, a=a):
        # Here to protect p.                                                                                                                                                                                                                
        if i <= 61:
            return lookup(i)

        else:
            pval = pow(62,p)
            nval = i/pval
            remainder = i % pval
            if nval <= 61:
                return lookup(nval) + incode(i % pval)
            else:
                return incode(i, p+1)

    return incode()



def decode(s, a=alphabet):
    '''Takes a base 62 string in our alphabet and returns it in base10.'''
    try:
        s = str(s)
    except Exception:
        raise TypeError("Input must be a string.")

    return sum([lookup(i) * pow(62,p) for p,i in enumerate(list(reversed(s)))])a

それは誰にでも必要な私のバージョンです。




Node.jsとMongoDBのソリューション

MongoDBが12バイトの新しいObjectIdを作成するために使用するフォーマットを知っているからです。

  • Unixエポックからの秒を表す4バイトの値、
  • 3バイトのマシン識別子、
  • 2バイトのプロセスID
  • ランダムな値で始まる3バイトのカウンター(あなたのマシン内)。

例(ランダムシーケンスを選択する) a1b2c3d4e5f6g7h8i9j1k2l3

  • a1b2c3d4は、Unixエポックからの秒数を表し、
  • 4e5f6g7はマシン識別子を表し、
  • h8i9はプロセスIDを表します。
  • j1k2l3はカウンタを表し、ランダムな値で始まります。

同じマシンにデータを格納する場合、カウンタは一意になるため、重複することは疑いなく取得できます。

そのため、短いURLがカウンタになります。ここでは、サーバーが正しく動作していることを前提としたコードスニペットが表示されます。

const mongoose = require('mongoose');
const Schema = mongoose.Schema;

// Create a schema
const shortUrl = new Schema({
    long_url: { type: String, required: true },
    short_url: { type: String, required: true, unique: true },
  });
const ShortUrl = mongoose.model('ShortUrl', shortUrl);

// The user can request to get a short URL by providing a long URL using a form

app.post('/shorten', function(req ,res){
    // Create a new shortUrl */
    // The submit form has an input with longURL as its name attribute.
    const longUrl = req.body["longURL"];
    const newUrl = ShortUrl({
        long_url : longUrl,
        short_url : "",
    });
    const shortUrl = newUrl._id.toString().slice(-6);
    newUrl.short_url = shortUrl;
    console.log(newUrl);
    newUrl.save(function(err){
        console.log("the new URL is added");
    })
});



誰もがこれを見つけられるかどうかわかりません - それは「ハックアンドスラッシュ」の方法ですが、シンプルであり、特定の文字だけが必要な場合にうまく機能します。

$dictionary = "abcdfghjklmnpqrstvwxyz23456789";
$dictionary = str_split($dictionary);

// Encode
$str_id = '';
$base = count($dictionary);

while($id > 0) {
    $rem = $id % $base;
    $id = ($id - $rem) / $base;
    $str_id .= $dictionary[$rem];
}


// Decode
$id_ar = str_split($str_id);
$id = 0;

for($i = count($id_ar); $i > 0; $i--) {
    $id += array_search($id_ar[$i-1], $dictionary) * pow($base, $i - 1);
} 



なぜあなたのIDを文字列に変換しないのですか? あなたは、例えば0と61の間の数字を1文字(大文字/小文字)または数字にマッピングする関数が必要です。 次にこれを適用して4桁のコードを作成すると、1470万のURLがカバーされます。




同様のプロジェクトでは、新しいキーを取得するために、ハッシュテーブルでまだ使用されていない文字列を取得するまで、ジェネレータを呼び出すランダムな文字列ジェネレータの周りにラッパー関数を作成します。 あなたの名前空間がいっぱいになったら、このメソッドは遅くなりますが、あなたが言ったように、わずか6文字でさえ、あなたは多くの名前空間を扱うことができます。




非常に良い答え、私はbjfのGolangの実装を作成しました:

package bjf

import (
    "math"
    "strings"
    "strconv"
)

const alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

func Encode(num string) string {
    n, _ := strconv.ParseUint(num, 10, 64)
    t := make([]byte, 0)

    /* Special case */
    if n == 0 {
        return string(alphabet[0])
    }

    /* Map */
    for n > 0 {
        r := n % uint64(len(alphabet))
        t = append(t, alphabet[r])
        n = n / uint64(len(alphabet))
    }

    /* Reverse */
    for i, j := 0, len(t) - 1; i < j; i, j = i + 1, j - 1 {
        t[i], t[j] = t[j], t[i]
    }

    return string(t)
}

func Decode(token string) int {
    r := int(0)
    p := float64(len(token)) - 1

    for i := 0; i < len(token); i++ {
        r += strings.Index(alphabet, string(token[i])) * int(math.Pow(float64(len(alphabet)), p))
        p--
    }

    return r
}

githubでホストされていhttps://github.com/xor-gate/go-bjfhttps://github.com/xor-gate/go-bjf : https://github.com/xor-gate/go-bjf




Scalaでの実装:

class Encoder(alphabet: String) extends (Long => String) {

  val Base = alphabet.size

  override def apply(number: Long) = {
    def encode(current: Long): List[Int] = {
      if (current == 0) Nil
      else (current % Base).toInt :: encode(current / Base)
    }
    encode(number).reverse
      .map(current => alphabet.charAt(current)).mkString
  }
}

class Decoder(alphabet: String) extends (String => Long) {

  val Base = alphabet.size

  override def apply(string: String) = {
    def decode(current: Long, encodedPart: String): Long = {
      if (encodedPart.size == 0) current
      else decode(current * Base + alphabet.indexOf(encodedPart.head),encodedPart.tail)
    }
    decode(0,string)
  }
}

Scalaテストによるテスト例:

import org.scalatest.{FlatSpec, Matchers}

class DecoderAndEncoderTest extends FlatSpec with Matchers {

  val Alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

  "A number with base 10" should "be correctly encoded into base 62 string" in {
    val encoder = new Encoder(Alphabet)
    encoder(127) should be ("cd")
    encoder(543513414) should be ("KWGPy")
  }

  "A base 62 string" should "be correctly decoded into a number with base 10" in {
    val decoder = new Decoder(Alphabet)
    decoder("cd") should be (127)
    decoder("KWGPy") should be (543513414)
  }

}



O、0、iを目的のために省略しましたか?

Ryanのソリューションに基づいたPHPクラスを作成しました。

<?php

    $shorty = new App_Shorty();

    echo 'ID: ' . 1000;
    echo '<br/> Short link: ' . $shorty->encode(1000);
    echo '<br/> Decoded Short Link: ' . $shorty->decode($shorty->encode(1000));


    /**
     * A nice shorting class based on Ryan Charmley's suggestion see the link on  below.
     * @author Svetoslav Marinov (Slavi) | http://WebWeb.ca
     * @see http://.com/questions/742013/how-to-code-a-url-shortener/10386945#10386945
     */
    class App_Shorty {
        /**
         * Explicitly omitted: i, o, 1, 0 because they are confusing. Also use only lowercase ... as
         * dictating this over the phone might be tough.
         * @var string
         */
        private $dictionary = "abcdfghjklmnpqrstvwxyz23456789";
        private $dictionary_array = array();

        public function __construct() {
            $this->dictionary_array = str_split($this->dictionary);
        }

        /**
         * Gets ID and converts it into a string.
         * @param int $id
         */
        public function encode($id) {
            $str_id = '';
            $base = count($this->dictionary_array);

            while ($id > 0) {
                $rem = $id % $base;
                $id = ($id - $rem) / $base;
                $str_id .= $this->dictionary_array[$rem];
            }

            return $str_id;
        }

        /**
         * Converts /abc into an integer ID
         * @param string
         * @return int $id
         */
        public function decode($str_id) {
            $id = 0;
            $id_ar = str_split($str_id);
            $base = count($this->dictionary_array);

            for ($i = count($id_ar); $i > 0; $i--) {
                $id += array_search($id_ar[$i - 1], $this->dictionary_array) * pow($base, $i - 1);
            }
            return $id;
        }
    }
?>



私のPython 3バージョン

base_list = list("0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
base = len(base_list)

def encode(num: int):
    result = []
    if num == 0:
        result.append(base_list[0])

    while num > 0:
        result.append(base_list[num % base])
        num //= base

    print("".join(reversed(result)))

def decode(code: str):
    num = 0
    code_list = list(code)
    for index, code in enumerate(reversed(code_list)):
        num += base_list.index(code) * base ** index
    print(num)

if __name__ == '__main__':
    encode(341413134141)
    decode("60FoItT")



Related