> ## Content Index
> Fetch the complete content index at: https://www.popit.kr/llms.txt
> Use this file to discover other available public pages before exploring further.

# [입 개발] base62와 진법 연산
- URL: https://www.popit.kr/base62-and-radix-arithmetic/
- Published: 2016-11-03T16:42:08.000Z
- Updated: 2016-11-06T11:33:31.000Z
- Author: charsyam
- Tags: #소프트웨어, base62, shorten url

혹시 shorten url 서비스 같은 것을 어떻게 구현할 것인가에 대해서 고민해 본적이 있으신가요?  
이런 서비스를 제공할려고 보면, 겹치지 않는 유니크한 값을 만들어야 합니다. 이건[\[입 개발\] Global Unique Object ID 생성 방법에 대한 정리](https://charsyam.wordpress.com/2012/12/26/%EC%9E%85-%EA%B0%9C%EB%B0%9C-global-unique-object-id-%EC%83%9D%EC%84%B1-%EB%B0%A9%EB%B2%95%EC%97%90-%EB%8C%80%ED%95%9C-%EC%A0%95%EB%A6%AC/?ref=popit.kr) 를 참고하시면 됩니다.

그런데 이런 값을 그냥 스트링 형태로 표현하면, 123456789 은 binary 로는 4byte 이지만, 문자로 표현하면 9byte가 사용됩니다. 그렇다고 바이너로 표현하면 눈에 보이지 않는 형태이므로, 뭔가 전달하기가 어렵습니다.

123456789 이 각각 1,2,3,4,5,6,7,8 이 한바이트이므로, 이걸 뭔가 줄이는 방법이 없을까요?  
이진수로 11111111은 16진수로 표현하면 FF 입니다. 그냥 스트링으로만 보면 8byte 가 2바이트로 줄었습니다. 그러나 123456789를 16진수 스트링으로 표현하면 0x075BCD15 가 됩니다.(Big Endian 입니다.)

그래도 9bytes 가 8bytes로 한바이트가 줄었습니다. 뭔가 더 줄이는 방법이 없을까요? 16진법으로 좀 줄었으니... 진법을 좀 올리면 어떨까요? 대략 62진법 정도로? 그럼 이걸 어떻게 표현해야 할까요?(base62를 설명하기 위한 이 대놓고 설정이라니..)

자 먼저 간단한 예를 들어봅시다. 12233 이라는 값을 62진법으로 표현하기 위해서는 어떻게 해야할까요?  

```
1) 몫은 197, 나머지는 19
      197 
   |-----
 62|12233
    12214
    -----
       19 

2) 몫은 3, 나머지는 11
        3 
   |-----
 62|  197
      186
    -----
       11

3) 몫은 0, 나머지는 3
        0 
   |-----
 62|    3
        0
    -----
        3
 

4) 계산하면 3 * 62^2 + 11 * 62^1 + 19 * 62^0 = 12233 이 됩니다.

```

즉 12233 은 62진법으로 \[3, 11, 19\] 로 표현이 됩니다.  
그럼 이 값을 이제 각 자리르 62진법으로 표시하기 위한 symbol로 변환해주면 62진법처럼 보일껍니다.  

```
CODEC = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

```

운좋게도 a-z,A-Z,0-9까지를 합치면 62글자가 됩니다. 각각 0부터 61까지 표현한다고 하면...  
\[3, 11, 19\]는 CODEC\[3\], CODEC\[11\], CODEC\[19\]가 됩니다. 그러면 결과는 간단히 dlt 가 됩니다.

그러면 위의 공식대로 간단하게 코드를 작성해 볼까요?  
3, 11, 19 는 실제로 나머지(mod) 라고 보시면 됩니다.  

```
def to_base62(v):
    ret = []
    while v > 0:
        v, idx = divmod(v, 62)
        ret.insert(0,CODEC[idx])

    return ''.join(ret)

```

그럼 다시 디코딩은 어떻게 할 수 있을까요? 반대로 하면 됩니다. 문자를 위의 CODEC에서의 위치에서 찾아서, 그 값 곱하기 62^자리수 승을 해주면 됩니다.  

```
CODEC = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
CODECMAP = {}

c = 0
for i in CODEC:
    CODECMAP[i] = c
    c += 1

def from_base62(v):
    ret = 0
    i = 0
    for s in reversed(v):
        ret += (pow(62, i) * CODECMAP[s])
        i += 1

    return ret

```

이제 전체코드를 볼가요?  

```
import sys

CODEC = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
CODECMAP = {}

c = 0
for i in CODEC:
    CODECMAP[i] = c
    c += 1

def to_base62(v):
    ret = []
    while v > 0:
        v, idx = divmod(v, 62)

    return ''.join(ret)
    

def from_base62(v):
    ret = 0
    i = 0
    for s in reversed(v):
        ret += (pow(62, i) * CODECMAP[s])
        i += 1

    return ret

r = to_base62(int(sys.argv[1]))
v = from_base62(r)
print(r)
print(v)

```

우리가 이렇게 수를 특정 진법으로 표현할 수 있다는 것이 핵심입니다. 62진법이 중요한건 아니라는 거죠. 예를 들어, 대소문자를 구별할 수 없는 시스템이라면 이걸 줄여서 알파벳 26글자 + NUMERIC 10글자를 하면 36진법으로도 표현이 가능합니다. 숫자를 못쓰면 26진법도 가능한거죠. 자 이제 자기만의 진법 표현으로 숫자등을 한번 줄여보시기 바랍니다.