본문 바로가기
Dev.Stuff

짧게 줄인 URL 알고리즘 고찰 (Shortened URL Algorithm)

by Devkin 2012. 7. 7.

일전의 포스팅에서 짧은 URL 의 오리지널 URL 확인 방법에 대해 알아보았는데, URL Shortening 에 대한 알고리즘에 대해서도 궁금해져 알아보았다. 일단 모양새는 일반적인 Hash function 이나 Base64 인코딩과 유사해 보인다.

2012/06/27 - [Dev.Stuff] - 짧게 줄인 URL의 실제 URL 확인 원리 및 방법 (How to know original URL of shortened URL)

다음은 본 블로그 URL로 몇몇 서비스들에서 줄인 URL 목록이다. 공통적으로 숫자, 알파벳 소문자/대문자로 이루어진 5~7개의 문자 조합이다. 어차피 Short URL에 대한 Original URL 정보를 DB로 관리하여 리다이렉트 하는거고, 줄인 URL 자체가 읽기에 쉽거나 의미있는 조합은 아니니, 차라리 DB Index 와 매칭되는 숫자로만 조합하는 것도 생각해 봤지만 이 경우 10진법 조합으로는 서비스 URL 수가 늘어감에 따라 숫자 단위가 지나치게 커질 우려가 있으니, 특정 알고리즘이 나온 것이겠다.

  • metalkin.tistory.com
    • http://goo.gl/S8Ehy
    • http://bit.ly/I5Ba8C
    • http://durl.me/2pqa8c
    • http://me2.do/5jAeXPo 

우선, 오리지널 URL 을 알려진 몇몇 인코딩 방법으로 인코딩 해보자.

Hash functions

다음은 온라인 사이트에서 얻어낸 Hash function 들에 대한 결과값들이다. 일단 문자길이 자체가 조건을 만족하지 못하고, 알파벳 소문자, 숫자의 조합이다.

Original text metalkin.tistory.com
Original bytes 6d:65:74:61:6c:6b:69:6e:2e:74:69:73:74:6f:72:79:2e:63:6f:6d (length=20)
Adler32 5530080f
CRC32 46c30dbb
Haval 8c8ef61efca0b8cba0a93335b8ca8a82
MD2 301769973e396281f27cd3cce4fc8d01
MD4 099055d3fbde71d62bf833c5c6ca5594
MD5 94371523a07cd67fda2fd47b6b5c7885
RipeMD128 d107030a416d986c276112aabad3fe38
RipeMD160 5444db26fec85e0f309186a1d09eecf96f60d7a1
SHA-1 40ab8d195910f388e60fd7e860583627a0c7a5f3

Base64 Standard

다음은 일반적인 Base64 Encoding 을 통한 결과이다. 역시나 길이도 길이지만, 바이트 패딩으로 =가 붙어있다. URL-Safe 하지 않은 +, / 캐릭터 사용으로 인해, Short URL에 바로 적용하기에는 적합하지 않다. URL Percent Encoding 으로 가능은 하겠지만, 역시 길이가 지나치게 길어진다.

Original text metalkin.tistory.com
Original bytes 6d:65:74:61:6c:6b:69:6e:2e:74:69:73:74:6f:72:79:2e:63:6f:6d (length=20)
Base64 bWV0YWxraW4udGlzdG9yeS5jb20=

Base64 For URL

URL Application 을 위해 수정된 Base64 의 경우, +, / 대신 -, _ 를 사용하여 URL Percent Encoding 으로 인한 불필요한 길이를 없앨 수 있고, '=' 바이트패딩도 생략하여 필드 세퍼레이터와의 혼동도 없앨 수 있다. 역시나 적용하기에는 길이가 문제이다.

오리지널 URL을 대체할 소스가 필요

오리지널 URL 자체를 인코딩해서는 도저히 효과적으로 길이를 줄일 수 없을 것 같다. 증가하는 숫자 조합 아이디어를 좀더 연장하여, Database 저장 시, 증가하는 ID (Base10, 10진법, Integer)를 Base64(64진법)로 인코딩하여 Short URL 로 사용하는 방법을 고려해보자. 5개 문자로 서비스 가능한 URL 수를 비교해보면, 10^5(100,000) 와 64^5(1,073,741,824) 는 고려하기에 충분할 만큼 큰 차이를 보여준다.

Using 'Base64 For URL' To Encode ID(Integer)

간단히 작성한 코드로 테스트를 해보았다. 서비스가 호황을 이뤄 DB 에 저장된 URL 수가 엄청 늘어났다고 가정하고, 다음번에 저장될 DB 의 인덱스 ID가 1,042,432,728가 된다고 하면 Base64 로 인코딩한 결과는 ylKi-로 나왔다. 만족스러운 길이다. 재차 강조하자면, 인덱스 ID 는 String value 가 아니라 Integer value 이다.

헌데, 위에서 테스트한 Short URL 서비스들에서는 대쉬- 나 언더스코어_ 가 붙어 나오는 경우를 보지 못했다. [a~z][A~Z][0~9] 조합은 확실해 보이지만 -, _ 가 생략되어 있다. Alpha-numeric 조합에 -,_ 가 붙으면 보기에 좋지 않아서라고도 하는데, 개인적으로는 어차피 의미없는 문자집합인데 크게 문제될것처럼 보이진 않는다. 게다가 효율적인 측면에서는 -,_ 를 제외한 Base62 보다는 Base64 가 표현할 수 있는 수도 많고 2배수로 Bitwise operation 을 통한 연산에도 용이해 보인다.

단순히, PC나 모바일에서 해당 링크를 클릭만 하는 경우라면 상관없지만 만일 해당 Short URL 을 모바일에서 타이핑 하여 SMS, MMS 또는 트위터로 보내는 경우를 생각해보면, - 나 _ 가 붙어 있을 경우에는, 보통 모바일에서는 자판의 옵션키등을 눌러 다른 자판으로 전환하여 입력해야 한다. 해당 URL 에서 _ 가 중간에 띄엄띄엄 섞여 있는 경우라면 자판 전환이 영 짜증나지 않을 수 없다. 요즘은 사용자 편의의 UI/UX 의 시대이니 이 경우가 유력해보인다. (혹시, Base64 대신 Base62 를 사용한 다른 이유에 대한 아이디어가 있으시면 제보 부탁드립니다.)

마침내 Base62

Short URL 서비스들에서 Database Integer ID 를 Base62로 인코딩하는 알고리즘을 사용하고 있다고 보장할 수 없으나, 해당 알고리즘이 가장 유력해 보이긴 하다. 다음은 C 로 작성한 Base62 Encode/Decode 예제로, 참고를 위해서 작성하였으며 성능/메모리 등은 고려되지 않았다. 유사한 로직으로 PHP, Python, Javascript 등에서도 구현 가능하겠다. 아마 ansi-c 보다는 진법변환에 유용한 펑션들이 있을것으로 본다.

예상 시나리오는, Database 에 ID(Integer), Long URL(String), Short URL(String) 칼럼을 두고 증가하는 ID value 를 Base62 인코딩하여 Short URL 로 사용하여 해당 테이블에 각각의 정보를 저장한다. 반대의 경우에는, Short URL 을 Base62 디코딩하여 나온 Integer(Base10) value 로 해당 ID의 Long URL 를 검색.

const char table[] = {"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"};
#define BASE    62

int strpos(const char *s, int c)
{
    char *p = strchr(s, c);
    if(p)
        return (p - s);
    
    return -1;
}

void strrvr(char *s)
{
    char c;
    int len = strlen(s);
    int half = len >> 1;

    for (int i = 0; i < half; i++)
    {
        c = s[i];
        s[i] = s[len - i - 1];
        s[len - i - 1] = c;
    }
}

void toBase62(long id, char *pBase62)
{   
    int i = 0;
    
    do {
        int mod = id % BASE;
        pBase62[i] = table[mod];
        i++;
    } while ((id = id / BASE));
    strrvr(pBase62);
}

long fromBase62(char *pBase62)
{
    long dec = 0;
    long mul = 1;
    int pos = 0;

    strrvr(pBase62);
    for(int i = 0; i < strlen(pBase62); i++)
    {
        pos = strpos(table, pBase62[i]);
        dec += pos * mul;
        mul *= BASE;
    }
    
    return dec;
}

int main (int argc, const char * argv[])
{
    char szBase62[16] = {0x00,};
    long dec = 0;
    
    toBase62(1042432728, szBase62);
    printf("Base62:[%s]\n", szBase62);

    dec = fromBase62(szBase62);
    printf("Base10:[%ld]\n", dec);

    return 0;
}

lilURL (Opensource PHP/MySQL Script)

현재 서비스 되고 있는 TinyURL, TightURL 의 클론 소스로 해당 소스로 바로 Short URL 웹 서비스 구축이 가능하다. 위와 동일한 컨셉으로 Base62 대신, Base36([0~9][a~z]) 인코딩이 사용되었다.

REFERENCE

반응형
저작자표시 비영리 변경금지

관련글

댓글

티스토리툴바