[용어 정리] 입 개발자를 위한 TF-IDF

뭔가 아는척을 위해서 알아두면 좋은 단어중에 지난번에 언급했던 Accuracy, Recall, Precision 같은 것들이 있는데, 이것 말고도 알아두면 입 개발자로 아는 척 하기 좋은 단어가 있습니다. 바로 TF-IDF 인데요. 보통, 검색이나 다른쪽을 하시는 분들은 다들 잘 알고 있는 단어이기도 합니다.(개인적으로는 해당 강의 https://www.coursera.org/learn/ml-foundations 를 들으시길 추천합니다.)

그럼 일단 단어를 정리하면 TF-IDF 는 TF와 IDF의 합성어입니다.

TF Term Frequency, 문서에서 해당 단어가 얼마나 나왔는지를 나타내는 단어, 예를 들어,  이 문서에 “입개발”이 10번 나오면 입개발의 TF는 10이라고 할 수 있습니다. 다만 이런 값의 정의는 바꿀 수도 있습니다. 여러번 나와도 1이라고 정의할 수도 있고, 엄청 많은 값을 좀 줄이기 위해서 log 값을 씌우기도 합니다.
DF Document Frequency 입니다. TF는 한 문서에서 나타난 빈도라면, DF는 전체 문서들에서, 몇 개의 문서에 나타나는지에 대한 값입니다.  즉 이에 대한 수식은 대략 (해당 단어가 나타난 문서 수/ 전체 문서 수) 라고 보시면 됩니다.
IDF Inverse Docuemnt Frequency 입니다. DF의 역수를 취했다고 보시면 됩니다. 즉 (전체 문서 수/해당 단어가 나타난 문서 수) 입니다. 그런데 해당 단어가 있는 문서가 없을 수도 있으니 보통 분모에 1을 더해줘서(0 되지 말라고), 해서 (전체 문서 수/1 + 해당 단어가 나타난 문서 수)로 많이 표시합니다.

이제 여기서 중요한 것은 왜 IDF를 사용하는가 입니다. 검색이든, 문서의 유사도 검색을 할 때도 많이 사용하는데, 이런 것들을 할때 중요한 것은 해당 문서의 특징을 뽑아내는 거라고 할 수 있습니다.(지금부터 구라가 작열합니다!!)

먼저 문서의 유사도를 비교한다면 어떻게 할 수 있을까요? “머신러닝” 이렇게 외치시면, 일단 “러닝머신”을 한두시간 타 보시고요. 어려운 방법을 빼고 생각해보면… 단어가 얼마나 일치하는가 보면 될것 같습니다.

  1. 단어들을 모두 분리해서, 각 단어의 개수를 센다.
  2. 해당 단어들의 개수랑 얼마나 일치하는 지 살펴본다.
    1. 그런데 요 부분도 이해하기 어려울 수…

tfidf1

위의 그림을 보면 각 단어의 출현 빈도를 저장하고, 이 값들을 비교해서 다른 문서와 얼마나 유사한지 비교하게 됩니다.

tfidf2

위의 그림도 단순한 유사도를 구하는 예입니다. 여러 가지 방법이 있을 수 있습니다.(여기서는 문서에 많은 단어가 있으면, 그 유사도 값이 너무나 커버리는 이슈도 있어서, 이 값을 normalize 를 시켜야 하는데 이런건 일단 넘어가도록 하겠습니다. )

그런데 문서를 하나 본다면 일단 설명을 쉽게 하기 위해서 영어를 예로 들면, the, a, an, and, or, but 등등의 관사나 조사 같은 것들이 많이 들어있게 됩니다. 그런데 단순히 문서를 단어로만 나눠서 갯수로 비교를 한다면? 위의 기법을 써버리면 엄청 the 가 많아도 다들 비슷한 문서로 생각해 버리게 될겁니다. 그럼 어떤 방법이 있을까요? 간단하게 생각하기에…

  1. 저렇게 쓸모 없는 단어를 다 빼고 비교한다.
    1. 그럼에도 중요한 단어와 중요하지 않은 단어를 구분하지 못하는 문제가…
  2. 그냥 저렇게 중요하지 않을 단어들은 가중치를 낮게 주고 중요한 단어들은 가중치를 올려주자.

위의 두 방법중에, 1번은 꽤 명확한데, 2번은 그럼 중요한 단어를 어떻게 정할 것인가 하는 이슈가 생깁니다. 그런데 지금 이게 무슨 용어를 설명하는 걸까요? 네, 그렇습니다. TF-IDF!!!

즉, TF-IDF가 중요한 단어와 중요하지 않은 단어를 구분할 수 있는 방법인 것입니다. 여기서 일단 TF-IDF의 가정은, 특정 단어가, 해당 문서에서는 자주 출현하지만, 다른 문서에서는 많이 안나오면 중요한 단어일 것이다 라는 것입니다. 왜냐하면 다른 문서들에도 자주 나오는 거면, 아까 말한 the, a, an, of, and, or, but 같은 관사나 접속사등이 많을 것이기 때문입니다.

이제 뭔가 연관이 보이시나요? IDF의 (전체 문서 수/해당 단어가 나타난 문서 수)가 어떤 의미일까요? 즉 해당 단어가 적은 문서에 나타날 수록 IDF 가 커지게 됩니다. DF는 반대로, 해당 단어가 여러 문서에 나타날 수록 값이 커지는거구요.

이제 IDF를 구함으로써, 우리는 문서들 중에서는 적게 나타나는 단어를 찾을 수 있게 되었습니다. 그리고 해당 문서에서 중요한 단어는 TF로 구할 수 있기 때문에, 우리의 핵심 가정 – “해당 문서에서는 자주 나타나고, 전체 문서에는 적게 나타나는 단어”를 구하는 방법이 TF와 IDF를 곱하는 TF-IDF 가 되는 것입니다.

그런데 실제로 아까 제가 말한 공식으로 바로 쓰지는 않습니다. 왜냐하면 해당 값들이 천차 만별로 커지기 때문에, 로그를 씌운다든지, 제곱근을 구한다든지 그렇게 됩니다. 위키디피아에 꽤 설명이 잘 되어 있습니다. https://ko.wikipedia.org/wiki/TF-IDF

[용어 정리] 입개발자를 위한 Accuracy, Recall, Precision

최근에 공부하게 된 내용을 아주 가볍게 정리하고자 합니다. 머신러닝은 못하고 러닝머신도 못하고 있지만(저질 체력이라…) 맨날 공부하자 말만 하고 모르고 있다가… 아는 게 없어서 맨날 구라만 치는 중입니다. 그러던 중, 위의 내용들을 가볍게 설명할 일이 생겼는데… 역시 저의 구라로 시작한 일은 비극적으로 구라가 들통나버리는… 흑흑흑

그래서 좀 더 큰데서 구라를 다시 한번 치기 위해서 용어를 정리합니다. 흑흑흑 그래요 저 이런것도 모릅니다.

table

(해당 그림은 wikipedia 에서 가져왔습니다.)

다들 아시겠지만, 저는 잘 모르니… 먼저 간단하게 정리합니다. 일단 다음 4개의 용어를 먼저 기억해야 합니다.

True Positivie(TP) True 인데, True라고 맞춘 경우(잘한 경우)
False Positive(FP) False 인데, True라고 한 경우(틀렸어요.)
True Negative(TN) False 인데, False라고 맞춘 경우(잘한 경우)
False Negative(FN) True 인데 False 라고 한 경우(틀렸어요.)

TP, TN은 잘 한 경우, FP, FN은 잘못한 경우입니다. 그런데 FP, FN 중에 뭐가 낫냐고 하면, 그건 Case By Case 입니다. 예를 들어 암인데, 암이 아니라고 진단하거나, 암이 아닌데 암이 라고 진단하는 케이스는 어떤 경우가 더 나쁠까요?

그럼 이제 Accuracy, Recall, Precision 에 대해서 알아보도록 하겠습니다. 먼저 Accuracy 는 굉장히 간단합니다. 명확하게 정확도입니다. 정확도라고 생각하면, 즉 전체 중에서 정답을 얼마나 맞춰는가죠.  위의 표를 보시면 total population 이라고 되어 있는데, 그냥 위의 TP+FP+TN+FN, 즉 다 더한겁니다. 즉 전체 합 분의 잘 찾은 경우 즉 TP+TN이 되는 것이죠. 그래서 Accurancy 는 TP+TN/TP+TN+FP+FN 이 됩니다. 간단하죠? 간단하게 말하면, 전체 케이스 중에 정확하게 맞춘 비율입니다.

먼저 precision 은 검출한 것의 정확도라고 할 수 있습니다. 그냥 정확도라고 하면 위의 Accuracy 와 혼동이 오게 되는데, 위의 공식을 보면 TP/Prediction Positive 라고 되어있습니다. Prediction Positive 와 condition positive 가 표에 나오는데 Prediction Positive는 분류를 True 라고 말하는 케이스, Condition Positive 는 실제로 True 인 케이스입니다. 즉 Prediction Positive 는 위의 표에서 TP + FP 가 되구요, Condition Positive 는 TP+FN 이 됩니다. 위의 그림대로입니다. 다시 precision으로 돌아와서 간단하게 TP/TP+FP 입니다. 즉 True라고 분류했으면, 진짜 True 일 확률입니다.

그럼 이제 Recall 은 무엇인가? 검출율이라고 설명하면 쉬운데, 위의 공식을 보면 TP/condition positive 입니다. 즉 TP/TP+FN, 즉 진짜 True 중에 내가 얼마나 TRUE를 제대로 맞췄는가 라고 말할 것인가에 대한 값입니다.

이제 아래의 그림대로 한번 계산을 해보도록 하면…

table2

Accuracy TP+TN/TP+TN+FP+FN 30420/33376 = 0.911
Precision TP/TP+FP 26455/27812 = 0.951
Recall TP/TP+FN 26455/28054 = 0.943

이제 어디가서 좀 아는척 좀 하면 되겠습니다.

[책 리뷰] 파이썬 머신 러닝

해당 리뷰는 지앤선에서 도서를 제공해주셔서 진행하였습니다.

머신러닝이라는 것은 용어가 예전의 클라우드, 빅데이터를 처럼 버즈워드로 시작했다가 어느 순간부터는 대부분의 사람이 알아야 하는 필수가 되어 버렸다. 알파고를 넘어서 “딥러닝”, “강화학습”, 어느 순간 GAN이라는 게 나와서, 스스로 대결해서 스스로 학습해버리는…. 스카이넷이 얼마 남지 않은…

사실 말하기 부끄럽지만, 나름 꽤 많은 머신 러닝 책을 표지만 보고 지나간 사람으로… 내가 공부하기엔 너무 어려운게 아닌가 라는 생각을 여전히 가지고 있습니다. 나름 쉽게 설명하는 머신러닝 강의도 찾아다니고 책도 보는데, 왜 이렇게 어려울까 하는데… 제가 수학이 약했던…

그 중에서 원래 원서가 굉장히 소문이 좋았던 Packt사의 Python Machine Learning 이라는 책이 한국어로 번역이 나와서, 리뷰를 할 수 있는 좋은 기회를 얻었습니다.

 

일단 책의 내용이 굉장히 탄탄합니다. 그러면서 좀 쉽게(여기서의 쉽게는 나름 쉽게고 실제로 아예 여기 관련 내용을 모른다면 꽤 이해하기 어려운… 그래서 제가 잘 이해못하는…) 설명을 하고 있습니다. 실제로 여러 부분을 다루고 있구요. Python 으로 진행하면서, 머신러닝이라는 분야에 대해서 여러가지로 잘 설명하고 있습니다. (전 원래 베이지안이 전부인줄만 알았는데…)

기존의 선형회귀, 로지스틱 회귀, SVM, 에이다 부스팅, K-Means, 딥러닝의 CNN 과 RNN 이야기도 나옵니다.(전 이걸 설명할 능력이 없는…)

사실 이 책의 난이도가, 아무런 배경지식이 없으면 읽기 어렵다고 말씀드릴 수 있습니다. 저도 상당부분은 사실 여전히 이해를 못하고(상당부분 == 거의 다) 그냥 이런게 있구나로만… 머신러닝 책들은 왜 보기만 해도 어느 순간… 눈을 감고 있게 되는지…(기본적으로 수학을 공부하셔야 잘 이해가 될것 같습니다.)

책을 보다보면, 쉬운 부분도 있고, 많이 어려운 부분들도 있는데, 이게 사람마다 체감하는게 완전히 다를 수 있을듯 합니다. 중간에 역전파(백프로파게이션) 을 이해하는데도 한참 걸린… 흑흑흑

그러나 머신러닝은 정말 개발자가 최소한의 지식은 꼭 있어야 할 분야로 보입니다. 다만 이 책은 완전히 초급에서 보기는 그렇고, 최소한 용어가 이해된 중급 수준에서 보면 상당한 도움이 될듯합니다. 한국판 서적중에서 가장 자세한 편입니다.

 

2016년 회고와 2017년 계획

이제 2016년이 정말로 얼마남지 않았다. 이제 곧 2017년…(흑흑흑 나이먹기 싫어요.)
과연 나는 2016년 한해 무엇을 했을까? 먼저 2016년 계획을 찾아보았다.

그런데 검색결과 없다. -_-(그렇다 나의 2016년 계획 따위는 없었던 것이다!!! – 망했어!!!)

그럼 나는 무엇으로 2016년을 회고할 것인가!!!

  1. 인생의 슬픔… 둘째 유산…10월 24일… 뭔가 제대로 확인되지도 못하고 사라진 율율구리 two는 뭔가 슬픔이라는 감정을 느끼기도 전에 무언가 일이 벌어졌던거 같다. 태동을 듣지 못한게, 개인적으로 다행이다 싶기도한… 나보다도 마님이 더 충격적이지 않을까 했는데, 또 그렇게 아무런 기억없이 사라지는… 그냥 뭔가 미안한 마음뿐이다.
  2. RedisConf 2016
    올 한해 일단 가장 큰 기억은 역시 5월 10~11 일에 있었던 redisconf 2016에 참여한 것이다. 미친척 하고 proposal을 던지고, 그게 된지도 모르고 떨어졌다라고 자괴감에 빠져있다가 발표 10일전에 해당 메일을 찾게되서… 부랴부랴 준비했던… 이때 저에게 도움주신 많은 분들에게 감사를… 샌프란에서 몇일 동안 긴장해서 잠도 못자고, 내 발표 끝나고 나서는 한동안 정신을 못차린… 그러나 그 결과는 이제 평생 놀림감으로 남을 유투브 동영상이라니… 그래도 나름 열심히 하긴 했던…
  3. 안식휴가 9월에 한달
    카카오에는 만3년을 다니면 한달을 쉴 수 있는 안식휴가 제도가 있다. 마님과 율율구리와 함께, 한달을 지내는데, 제주도에서 일주일, 부산에서 일주일 정도 지내면서, 뭔가 직장을 다니면서, 안다니는거 같은 느낌을 받았다. 물론 이 시기에도, 버그도 내고, 배포도 하고, 장애도 내는 신기를… 그래도 한달이라는 쉬는 기간은 웬지…

그럼 이제 2017년에는 무엇을 할것인가? 일단 뭔가 2016년에 벌린 일들을 수습하고 새롭게 진행해야 하는데…

  1. 건강
    매년 건강검진때 마다 의사선생님들께 욕 한바가지 먹게 되는게 건강 상태다. 2017년에는 몸무게도 10kg 정도 빼고, 운동을 열심히 해서, 최소한 2016년 올해보다는 좋은 건강상태를 만드는게 1순위
  2. 영어 공부
    매년 얘기하면서도 매년 못하는 영어 공부는 올해는 강제로라도 해보자.
  3. 머신러닝 학습
    올 해는 머신러닝에 대해서도 살짝 공부는 해봐야 겠다.

[입 개발] Google Cloud Engine 에 Redis 설치하기

  • 해당 글은 Google Cloud Engine 로 부터 테스트 지원을 받아서 작성되었습니다.

Redis는 In-Memory Cache/Store 입니다. 또는 In-Memory Key-Value NoSQL 로 불리기도 합니다. 사실 어떻게 불리는가는 특별히 중요하지 않습니다. 굉장히 여러 분야에서, 다양하게 사용되고 있다는게 중요합니다.

그런데 Amazon AWS, Microsoft Azure 의 경우에는 Redis 는 아예 PaaS 형태로 존재하고 있습니다. AWS의 Elastic Cache 라든지, Azure 의 Redis Cache 가 있습니다. (아마도 GCE에서도 뭔가 곧 나오지 않을까 예상합니다. 여기서는 서로 서로 점점 유사해지고 있으니…)

이렇게 PaaS로 제공하는 것은 각각 장점이 있습니다. 편한 대신에, 세밀한 컨트롤이 안된다든가, 반대로 불편한 대신에 좀더 컨트롤이 명확하든가… Elastic Cache의 경우에는 아예 몇가지 쓸 수 없는 명령이 있어서 spring data redis에서 뭔가 이슈가 있기도 합니다.(지금은 수정되었나 모르겠네요.)

일단은 아주 간단하게 최신버전의 Redis를 GCE 에서 설치해보고 간단하게 테스트를 돌려보는 것 까지 확인해 보도록 하겠습니다. 환경은 Ubuntu 16.04 LTS 이지만 어디서든 거의 비슷한 형태로 하시면 가능합니다.

먼저 간단하게 살피고 넘어가면 ssh로 접근하기 위한 키를 생성합니다. 제 환경은 맥이지만, 비슷하니 키 생성은 쉽게 될껍니다. 이 때 주의할 것은 메일 주소를 실제로 사용하는 google 계정으로 하는게 좋은거 같습니다.(뭔가 제 잘못이겠지만, 그냥 public key를 등록했더니 제대로 안되는…)

ssh-keygen -t rsa -C "<구글 계정>"

그리고 이 ssh 키를 전역으로 사용하기 위해서, SSH 키를 미리 등록해둬야 합니다. 아래 그림과 같이 메타데이터 -> SSH 키 -> 수정 을 선택합니다.

gce-ssh-image

그리고 로컬에 생성한 (따로 이름을 지정안했으면 ~/.ssh/id_rsa.pub) public key 파일을 열어서 추가해줍니다. 그럼 자동으로 사용자 이름이 만들어지면서 추가됩니다. 그러면 이제 저장을 누르고 VM 인스턴스 -> 인스턴스 만들기 로 이동합니다.

여기서 해당 서버를 외부에서 바로 접속하고 싶다면, 꼭 네트워크 설정에서 외부를 임시든 고정 IP를 설정해 줘야 합니다. 셋팅안하면 그냥 없음으로 해서 내부 ip만 만들어지는…(물론 이것도 제가 잘못아는 거일 수도 있습니다.)

gce-vm-create

이제 인스턴스가 만들어지면 ssh -i ~/.ssh/id_rsa @ 로 접속하면 됩니다. 여기서 username 은 위에서 만들어진 사용자 이름을 사용하시면 됩니다.

GCE의 IO는 vCPU 수에 비례한다고 합니다. 네트워크도 vCPU에 비례해서 밴드위스가 추가된다고 하네요 이 내용은 benchmark 돌릴때 상당히 중요할듯 합니다.

자 이제 VM 을 생성했으니 여기서 끝내겠습니다. 다들 수고하셨습니다.(퍽퍽퍽)
앗, 그러고보니 이 글의 목표는 Redis 를 까는 거였습니다. -_-;;;
VM 인스턴스를 선택하면 자신의 서버 주소를 알 수 있습니다.
먼저 기본적인 툴들을 설치해야 합니다.

sudo apt update
sudo apt install build-essential libtool tcl

이제 Redis 최신 버전을 받아봅시다.

wget http://download.redis.io/releases/redis-3.2.6.tar.gz

압축을 풀고 빌드를 해봅니다.

tar zxvf redis-3.2.6.tar.gz
cd redis-3.2.6
make

Redis 는 생각보다 빌드가 굉장히 쉽습니다. 필요한 컴파일러만 설치되면 그냥 make 만 하시면됩니다. 이제 테스트를 해보겠습니다. test를 위해서는 tcl 이 필요하고 그래서 위에서 tcl 를 설치해두었습니다.

make test

이제 정상적이면 다음과 같은 로그를 보실 수 있습니다. 정상적으로 완료되었으면 문제는 없습니다. 가끔씩 에러가 날수도 있는데, 타이밍 이슈등이므로, 메모리 검사를 해보고 큰 문제가 없다면 무시하셔도 됩니다.

Testing integration/replication-4
[ok]: BRPOPLPUSH with wrong destination type
[ok]: BRPOPLPUSH maintains order of elements after failure
[ok]: BRPOPLPUSH with multiple blocked clients
[ok]: Linked BRPOPLPUSH
[ok]: Circular BRPOPLPUSH
[ok]: Self-referential BRPOPLPUSH
[ok]: BRPOPLPUSH inside a transaction
[ok]: PUSH resulting from BRPOPLPUSH affect WATCH

그런데 redis 를 실행해놓고 외부에서 접속을 시도해보면 당연히 접속이 안될껍니다. 왜 그럴까요?(일단 bind 는 0.0.0.0 으로 설정해 둔 다음에도요.) 이것은 해당 GCE의 네트웍 방화벽 설정에 6379 port 가 안열려 있어서 그렇습니다. 이걸 풀어주시면 제대로 설정이 될겁니다.

일단은 GCE(Google Cloud Engine) 에서 Redis 를 수동으로 설치하는 방법에 대해서 알아보았습니다. 다음번에는 실제로 이걸로 셋팅을 하고 서비스를 위한 테스트를 어떻게 할지 살펴보도록 하겠습니다.

[입 개발] base64 가 있는데 base62 같은걸 왜 써야 하나요?

몇일 전에 [입 개발] base62와 진법 연산 라는 글을 적었습니다. 이런 내용을 얘기하면 꼭 빠지지 않고 좋은 질문이 하나 꼭 나옵니다.(나오기를 바랍니다.)

“왜 base64가 있는데 base62 같은걸 써야하죠?” 넵 그렇습니다. 다행히도, 이 내용을 제 주변에 설명했을 때도, 들었던 질문이고, 해당 글을 적었을 때도 받은 질문입니다.(좋은 질문해주신 질문자들에게 감사드립니다.)

먼저 간단하게 설명을 시작하기 전에, 10진수는 영어로 decimal 또는 base 10, 8진수는 octet digits 또는 base 8, 그럼 16진수는 넵 hexdecmial 또는 base 16 이 됩니다. 그럼 당연히 base62는 62진법, base64는 64진법이겠죠.

이 얘기를 하면, 위의 질문이 더 좋아집니다. 64진법으로 표현하는게, 62진법으로 표현하는 것 보다, 진법이 크니, 변화된 정보량이 더 작아지지 않는가? 라는 생각을 하게 하니깐요.

그런데 정답부터 말하자면, base64의 정보량이 더 줄어드는것이 맞습니다.(엥 작성자 양반 도대체 무슨 소리를 하는것이오…) 그런데, 이것을 항상 쓸 수 있는가? 라고 물어보면… 그렇지는 않기 때문입니다.(작성자 양반 이것은 또 무슨소리오!!!)

일단 binary로 표현하는 것은 일종의 256진법 표기입니다. base62, 64에 비해서 한 바이트에 많은 정보가 함축되지요. 그런데, 이제 다음과 같은 질문이 추가로 나와야 할듯 합니다. base64는 왜 나왔을까요? 아무데나 다 쓸 수 있나요? 아래는 base64에서 사용하기 위한 인코딩 표입니다. base62와 비교하면, 사실 +,/,= 해서 3개를 더 쓰고 있습니다.(마지막에 =는 사실 padding 입니다. 값이 없다라는 것을 알려주기 위해서이죠.)

base64

자, 이제 다시 한번 질문드립니다. 위의 base64 문자표에 있는 값으로 구성을 하면, 웹 url 형태의 query string으로 넘겼을 때 제대로 처리가 될까요? 자자 열심히 머리를 굴려봅시다.(이 질문을 하는 이유는… 심지어 이 글을 쓰는 이유는 여기서 뭔가 제대로 처리가 되지 않기 때문이겠죠?

https://charsyam.wordpress.com/abc?q===query=abcd+/=

위의 query string ㅔ서 q== 이 key 이고 query=abcd+/= 가 value라고 하면 뭔가 이상합니다. 하지만, key와 value 가 모두 base64로 인코딩이 된다면, 가능한 일입니다. 그럼 이제 패드는 안쓴다고 해봅시다. 그래도 다음과 같은 형태는 가능합니다.

https://charsyam.wordpress.com/abc?q+/+=query+/

그래서 url safe base64 라는 형태를 찾아보면 위의 표에서 ‘+’, ‘/’ 를 각각 ‘-‘,’_’ 등으로 바꾸고, ‘=’도 ‘.’ 이나 다른 문자로 바꾸는 경우가 있습니다. 즉 base64의 테이블표를 변경해야 하는 이슈가 생기는 것입니다.

실제로 base64는 이메일에서 안전하게 메일을  보내기 위한 인코딩 방법으로 출발했습니다. (rfc1341 를 참고하세요.)예전에는 ascii 만이 세상의 표준이므로 대부분의 서비스들이 7bit 까지만 인식하고 8bit로 된 데이터는 뭔가 처리하는데 에러가 있는 시대였습니다. 그래서 우리의 EUC-KR로 표현되던 한글이나 2byte 언어 국가 CJK 같은 경우는 메일로 첨부파일도 못보내고, 더 심한건, 그냥 한글로는 메일을 못보낸다는 것입니다.(EUC-KR 등에서는 한글 표현을 위해서 2byte를 사용하는데, 확장 표시를 위해서 두 byte의 첫 bit를 1로 셋팅했습니다.) 그래서 여기서 좀 안전한 방법을 찾자가 quoted-printed 와 base64 가 나오게 되었습니다.(quoted-printed는 url-encode 와 유사하게 128보다 큰 문자는 %AB 이런식으로 3글자로 표시하는 방식입니다.)

위와 같은 이유로 base64가 나오게 된 것입니다. 경우에 따라서 테이블을 변경해서 쓰거나 해야 안전해 지는 것이죠. 그런데… base64에서 사용하는 문자들을 또 특정한 시스템에서 쓸 수 없다면 어떻게 될까요? 8bit 표현을 6bit 로 줄인것 처럼, 64로 표시할 수 있는 데이터를 다시 더 줄여야 할 필요가 생길 수 있습니다. base62 또한 그런 상황에서 필요가 되어서 만들어 진 것이죠. 예를 들어 web에서 사용하는데 벌써 ‘-‘, ‘_’ 는 예약 문자등으로 쓰여서 쓸 수 없거나 하는…

그래서 base62, base36, base26, base10 등 얼마든지 만들어 나갈 수 있습니다. encoding, decoding 이라는 것은, 이러한 상황에서의 문제를 풀기 위해서고, 이런 문제는 얼마든지 다시 발생할 수 있으니까요. 설명이 되었으면 좋겠습니다.

[입 개발] base62와 진법 연산

혹시 shorten url 서비스 같은 것을 어떻게 구현할 것인가에 대해서 고민해 본적이 있으신가요?
이런 서비스를 제공할려고 보면, 겹치지 않는 유니크한 값을 만들어야 합니다. 이건[입 개발] Global Unique Object ID 생성 방법에 대한 정리 를 참고하시면 됩니다.

그런데 이런 값을 그냥 스트링 형태로 표현하면, 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)
        ret.insert(0,CODEC[idx])

    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진법도 가능한거죠. 자 이제 자기만의 진법 표현으로 숫자등을 한번 줄여보시기 바랍니다.