url shortener

url_short.md

最合理的办法是通过发号策略, 每来一个长地址, 发一个号.

https://tech.meituan.com/MT_Leaf.html

https://www.zhihu.com/question/29270034/answer/46446911

url_short.py

lut_size = 82

# 82
alphabet_lut = [
    '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',
    '-', '_', '.', '~',
    '!', '*', '\'', '(', ')', ';', ':', '@', '&', '#', '$', ',', '/', '?', '[', ']'
]

chat2num_lut = {
    45: 62, 95: 63, 46: 64, 126: 65,
    33: 66, 42: 67, 39: 68, 40: 69, 41: 70, 59: 71, 58: 72, 64: 73,
    38: 74, 35: 75, 36: 76, 44: 77, 47: 78, 63: 79, 91: 80, 93: 81
}


def _shorten_char(c):
    n = ord(c)
    if n >= 97 and n <= 122:
        return n - 97
    elif n >= 65 and n <= 90:
        return n - 65 + 26
    elif n >= 48 and n <= 57:
        return n - 48 + 52
    else:
        if n in chat2num_lut:
            return chat2num_lut[n]
        else:
            raise Exception("Invalid character.")


def encode(longUrl: str):
    ret = 0
    for i in range(0, len(longUrl)):
        ret = ret * lut_size + _shorten_char(longUrl[i])

    return ret


def decode(num):
    ret = ""
    while num > 0:
        ret = ret + str(alphabet_lut[num % lut_size])
        num = num // lut_size

    return ret[::-1]


val = encode("https://leetcode.com/problems/design-tinyurl")
# val = encode("baba")
print(val)
print(decode(val))

urlshortener.lua

getmetatable('').__index = function(s, i)
    return string.sub(s, i, i)
end

local alphabet_lut = {
    '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',
}

local metatbl = {
    __call = function(t, k)
        local n = string.byte(k)
        if n >= 97 and n <= 122 then
            return n - 97 + 1
        elseif n >= 65 and n <= 90 then
            return n - 65 + 27
        else
            return n - 48 + 53
        end
    end
}

setmetatable(alphabet_lut, metatbl)

local function encode(num)
    local ret = ""
    while num > 0 do
        local idx = math.mod(num, 62) + 1
        ret = ret .. alphabet_lut[idx]
        num = math.floor(num / 62)
    end

    return string.reverse(ret)
end

local function decode(str)
    local ret, len = 0, string.len(str)
    for i = 1, len do
        ret = ret * 62 + alphabet_lut(str[i]) - 1
    end

    return ret
end