algorithm - यूआरएल शॉर्टनर को कैसे कोड करें?




url (18)

मैं एक यूआरएल शॉर्टनर सेवा बनाना चाहता हूं जहां आप एक इनपुट क्षेत्र में एक लंबा यूआरएल लिख सकते हैं और सेवा यूआरएल को " http://www.example.org/abcdef " से छोटा कर देती है।

संपादित करें: इस विषय में चल रहे ब्याज के कारण, मैंने JavaScript , PHP , Python और Java कार्यान्वयन के साथ गिटहब के लिए एक कुशल समाधान प्रकाशित किया है। यदि आप चाहें तो अपने समाधान जोड़ें :)

" abcdef " के बजाय az, AZ and 0-9 युक्त छः वर्णों वाली कोई अन्य स्ट्रिंग हो सकती है। यह 56 ~ 57 अरब संभावित तार बनाता है।

मेरा दृष्टिकोण:

मेरे पास तीन कॉलम वाला डेटाबेस टेबल है:

  1. आईडी, पूर्णांक, ऑटो-वृद्धि
  2. लंबे, स्ट्रिंग, उपयोगकर्ता द्वारा दर्ज किया गया लंबा यूआरएल
  3. छोटा, स्ट्रिंग, छोटा यूआरएल (या केवल छः अक्षर)

मैं फिर तालिका में लंबा यूआरएल डालेंगे। फिर मैं " id " के लिए ऑटो-वृद्धि मूल्य का चयन करूंगा और इसके एक हैश का निर्माण करूंगा। तब हैश को " short " के रूप में डाला जाना चाहिए। लेकिन मुझे किस प्रकार का हैश बनाना चाहिए? एमडी 5 जैसे हैश एल्गोरिदम बहुत लंबे तार बनाते हैं। मैं इन एल्गोरिदम का उपयोग नहीं करता, मुझे लगता है। एक स्वयं निर्मित एल्गोरिदम भी काम करेगा।

मेरा विचार:

" http://www.google.de/ " के लिए मुझे स्वत: वृद्धि आईडी 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.

यह तब तक दोहराया जा सकता है जब तक संख्या अब विभाजित नहीं हो जाती है। क्या आपको लगता है कि यह एक अच्छा दृष्टिकोण है? क्या आपके पास एक बेहतर विचार है?


एक नोड जेएस और mongodb समाधान

चूंकि हम उस प्रारूप को जानते हैं जो mongodb 12 बाइट्स के साथ एक नया ऑब्जेक्ट आईडी बनाने के लिए उपयोग करता है।

  • एक 4-बाइट मान यूनिक्स युग के बाद से सेकंड का प्रतिनिधित्व करता है,
  • एक 3-बाइट मशीन पहचानकर्ता,
  • एक 2-बाइट प्रक्रिया आईडी
  • एक 3-बाइट काउंटर (आपकी मशीन में), एक यादृच्छिक मूल्य से शुरू होता है।

उदाहरण (मैं एक यादृच्छिक अनुक्रम चुनता हूं ) a1b2c3d4e5f6g7h8i9j1k2l3

  • ए 1 बी 2 सी 3 डी 4 यूनिक्स युग के बाद से सेकंड का प्रतिनिधित्व करता है,
  • 4e5f6g7 मशीन पहचानकर्ता का प्रतिनिधित्व करता है,
  • h8i9 प्रक्रिया आईडी का प्रतिनिधित्व करता है
  • j1k2l3 एक यादृच्छिक मान से शुरू, काउंटर का प्रतिनिधित्व करता है।

चूंकि काउंटर अद्वितीय होगा यदि हम उसी मशीन में डेटा संग्रहीत कर रहे हैं तो हम इसे बिना किसी संदेह के प्राप्त कर सकते हैं कि यह डुप्लिकेट होगा।

तो छोटा यूआरएल काउंटर होगा और यहां एक कोड स्निपेट माना जाता है कि आपका सर्वर ठीक से चल रहा है।

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");
    })
});

Xeoncross कक्षा में आधारित समारोह

function shortly($input){
$dictionary = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','0','1','2','3','4','5','6','7','8','9'];
if($input===0)
    return $dictionary[0];
$base = count($dictionary);
if(is_numeric($input)){
    $result = [];
    while($input > 0){
        $result[] = $dictionary[($input % $base)];
        $input = floor($input / $base);
    }
    return join("", array_reverse($result));
}
$i = 0;
$input = str_split($input);
foreach($input as $char){
    $pos = array_search($char, $dictionary);
    $i = $i * $base + $pos;
}
return $i;
}

आप पूरे यूआरएल को हश कर सकते हैं, लेकिन अगर आप आईडी को छोटा करना चाहते हैं, तो मार्सेल के सुझाव के अनुसार करें। मैंने इस पायथन कार्यान्वयन को लिखा:

Python


आपके प्रश्न का उत्तर नहीं है, लेकिन मैं केस-संवेदनशील शॉर्ट यूआरएल का उपयोग नहीं करता। उन्हें याद रखना कठिन होता है, आमतौर पर अपठनीय (कई फोंट 1 और एल, 0 और ओ और अन्य पात्रों को बहुत समान होते हैं कि वे अंतर बताने के लिए असंभव हैं) और निचली त्रुटि प्रवण होती है। केवल निचले या ऊपरी मामले का उपयोग करने का प्रयास करें।

साथ ही, प्रारूप बनाने का प्रयास करें जहां आप संख्याओं और अक्षरों को एक पूर्वनिर्धारित रूप में मिश्रित करते हैं। ऐसे अध्ययन हैं जो दिखाते हैं कि लोग दूसरों के मुकाबले बेहतर रूप से एक फॉर्म को याद करते हैं (फ़ोन नंबरों को सोचें, जहां संख्याओं को एक विशिष्ट रूप में समूहीकृत किया जाता है)। Num-char-char-num-char-char जैसे कुछ आज़माएं। मुझे पता है कि इससे संयोजन कम हो जाएंगे, खासकर यदि आपके पास ऊपरी और निचले मामले नहीं हैं, लेकिन यह अधिक उपयोगी और इसलिए उपयोगी होगा।


क्या आपने ओ, 0, मैं उद्देश्य पर छोड़ दिया?

रयान के समाधान के आधार पर बस एक 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 {
        /**
         * Explicitely 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;
        }
    }

?>

क्यों न केवल अपनी आईडी को एक स्ट्रिंग में अनुवाद करें? आपको बस एक ऐसे फ़ंक्शन की आवश्यकता है जो एक अक्षर (ऊपरी / निचले मामले) या अंक के बीच, 0, 61 के बीच एक अंक को मानचित्र करे। फिर इसे 4-अक्षर कोड बनाने, कहने के लिए लागू करें, और आपके पास 14.7 मिलियन यूआरएल शामिल हैं।


पता नहीं है कि किसी को यह उपयोगी लगेगा - यह 'हैक एन स्लैश' विधि से अधिक है, फिर भी सरल है और यदि आप केवल विशिष्ट वर्ण चाहते हैं तो अच्छी तरह से काम करता है।

$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);
} 

बहुत अच्छा जवाब, मैंने बीजेएफ का गोलांग कार्यान्वयन बनाया है:

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-bjf


मेरा पायथन 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")

मेरे पास समस्या का एक रूप है, जिसमें मैं कई अलग-अलग लेखकों से वेब पेज स्टोर करता हूं और अनुमान के अनुसार पृष्ठों की खोज को रोकने की आवश्यकता है। तो मेरे छोटे यूआरएल पृष्ठ संख्या के लिए बेस -62 स्ट्रिंग में कुछ अतिरिक्त अंक जोड़ते हैं। ये अतिरिक्त अंक पेज रिकॉर्ड में जानकारी से उत्पन्न होते हैं और वे सुनिश्चित करते हैं कि केवल 3844 यूआरएल में से केवल 1 मान्य हैं (2-अंक बेस -62 मानते हैं)। आप http://mgscan.com/MBWL पर एक रूपरेखा विवरण देख सकते हैं।


मैं डेटाबेस में प्रति डोमेन एक पूर्णांक अनुक्रम को Hashids और एक यूआरएल पथ में पूर्णांक को एन्कोड करने के लिए Hashids का उपयोग करता Hashids

static hashids = Hashids(salt = "my app rocks", minSize = 6)

मैंने यह देखने के लिए एक स्क्रिप्ट चलाई कि यह चरित्र की लंबाई समाप्त होने तक कितना समय लगता है। 6 अक्षरों के लिए यह 164,916,224 लिंक कर सकता है और फिर 7 वर्ण तक चला जाता है। बिट 7 अक्षरों का उपयोग करता है। 5 वर्णों के तहत मेरे लिए अजीब लग रहा है।

Hashids यूआरएल पथ को एक पूर्णांक पर डीकोड कर सकते हैं लेकिन एक सरल समाधान पूरे लघु लिंक sho.rt/ka8ds3 को प्राथमिक कुंजी के रूप में उपयोग करना है।

यहां पूरी अवधारणा है:

function addDomain(domain) {
    table("domains").insert("domain", domain, "seq", 0)
}

function addURL(domain, longURL) {
    seq = table("domains").where("domain = ?", domain).increment("seq")
    shortURL = domain + "/" + hashids.encode(seq)
    table("links").insert("short", shortURL, "long", longURL)
    return shortURL
}

// GET /:hashcode
function handleRequest(req, res) {
    shortURL = req.host + "/" + req.param("hashcode")
    longURL = table("links").where("short = ?", shortURL).get("long")
    res.redirect(301, longURL)
}

यदि आप पहिया को पुन: आविष्कार नहीं करना चाहते हैं ... http://lilurl.sourceforge.net/


यहां PHP के लिए एक सभ्य यूआरएल एन्कोडिंग फ़ंक्शन है ...

// From http://snipplr.com/view/22246/base62-encode--decode/
private function base_encode($val, $base=62, $chars='0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ') {
    $str = '';
    do {
        $i = fmod($val, $base);
        $str = $chars[$i] . $str;
        $val = ($val - $i) / $base;
    } while($val > 0);
    return $str;
}

यहां मेरा 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;
    }
}

स्कैला में कार्यान्वयन:

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)
  }
}

स्कैला परीक्षण के साथ टेस्ट उदाहरण:

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)
  }

}

सी # संस्करण:

public class UrlShortener 
{
    private static String ALPHABET = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    private static int    BASE     = 62;

    public static String encode(int num)
    {
        StringBuilder sb = new StringBuilder();

        while ( num > 0 )
        {
            sb.Append( ALPHABET[( num % BASE )] );
            num /= BASE;
        }

        StringBuilder builder = new StringBuilder();
        for (int i = sb.Length - 1; i >= 0; i--)
        {
            builder.Append(sb[i]);
        }
        return builder.ToString(); 
    }

    public static int decode(String str)
    {
        int num = 0;

        for ( int i = 0, len = str.Length; i < len; i++ )
        {
            num = num * BASE + ALPHABET.IndexOf( str[(i)] ); 
        }

        return num;
    }   
}

/**
 * <p>
 *     Integer to character and vice-versa
 * </p>
 *  
 */
public class TinyUrl {

    private final String characterMap = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    private final int charBase = characterMap.length();

    public String covertToCharacter(int num){
        StringBuilder sb = new StringBuilder();

        while (num > 0){
            sb.append(characterMap.charAt(num % charBase));
            num /= charBase;
        }

        return sb.reverse().toString();
    }

    public int covertToInteger(String str){
        int num = 0;
        for(int i = 0 ; i< str.length(); i++)
            num += characterMap.indexOf(str.charAt(i)) * Math.pow(charBase , (str.length() - (i + 1)));

        return num;
    }
}

class TinyUrlTest{

    public static void main(String[] args) {
        TinyUrl tinyUrl = new TinyUrl();
        int num = 122312215;
        String url = tinyUrl.covertToCharacter(num);
        System.out.println("Tiny url:  " + url);
        System.out.println("Id: " + tinyUrl.covertToInteger(url));
    }
}

// simple approach

$original_id = 56789;

$shortened_id = base_convert($original_id, 10, 36);

$un_shortened_id = base_convert($shortened_id, 36, 10);




url