April 2007 – OpenLook

미투데이에서 한국어 올바로 쓰기

April 29, 2007 by hyeshik

terra님의 글에서 갑자기 생각이 떠 올라서 한 번 만들어 봤습니다. 🙂
맞춤법 검사기를 직접 만든 건 아니고요, 그냥 부산대학교 정보컴퓨터공학부
인공지능연구실과 (주)나라인포테크가 만든 것에 웹 요청을 해서 받아온 결과를 뿌려줍니다. ^_^;;

사용하시려면 GreaseMonkey를 깔고 다음 링크를 클릭하시면 됩니다~

==> “만박사님의 한국어 시간” 플러그인 설치

자바스크립트에서 인코딩을 변환할 방법을 도저히 못 찾아서, 결국엔 제 서버에 있는 cgi를 거쳐서 euc-kr로 변환해서 보내게 했습니다. 혹시 좋은 방법을 아시는 분은 알려주세요 +_+

OpenSSL에 SEED가 들어갔습니다~

April 26, 2007 by hyeshik

그동안 많은 분의 노력으로 드디어 OpenSSL에 SEED지원이 들어갔습니다!
와와~
이제 모질라, 애플웹킷 등 OpenSSL에 지원이 없어서 못 한다고
기다리고 있던 수많은 프로그램들이 SEED를 지원할 수 있겠군요~

이번 패치는 전에 제가 올렸던 OpenSSL 패치가 들어간 것은 아니고, KISA에서 따로 작업한 패치를 KISA의 지원으로 OpenSSL 개발자가 수정한 것이 적용되었습니다. 사실 소스를 보시게 되면 KISA의 작업 과정 중에서 보통의 오픈소스 프로젝트의 관례에서는 어긋나는 이른바 “이름 지우고 소스 베껴오기”가 많이 적용된 흔적은 자명히 존재하긴 하지만, 그래도 제가 원래 올린 패치가 public domain으로 올렸던 것이기에 이름 지우기가 저작권 위반은 아니라는 것을 미리 알려 둡니다. 🙂

그렇지만 한편으로는 정부기관에서 오픈소스에서의 호환성 지원을 위해 오픈소스 프로젝트에 직접 노력하여 커밋을 재촉하고 실제 적용까지 유도한 사례가 나왔다는 측면에서 굉장히 고무되는 사건임에는 틀림이 없습니다~ 🙂

자주 볼 수 있는 정겨운 깨진 한글들

April 19, 2007 by hyeshik

오늘 IRC에서 얘기하다가 생각나서
예전부터 있었던 정겨운 깨진 한글들 패턴 몇개를 모아서 소개해 봅니다. 🙂

占쏙옙占쏙옙!

주로 맥이나 emacs, gnome-terminal등등 유니코드 처리를 하긴 하는데, 설정을 뭔가 잘못했거나 제대로 못 처리한 경우에 자주 발생하는 놈입니다. 구글에서 검색하면 무려 1450000건이나 나옵니다. -ㅇ-; 가히 깨진 한글 중 최고봉..

이 녀석의 의미는 U+FFFD U+FFFD를 utf-8로 인코딩한 것을 euc-kr로 푼 것입니다. 디코드하는 녀석은 euc-kr을 바라고 있고, 인코딩하는 녀석은 뭔가 안에서 단단히 꼬인 경우죠. U+FFFD는 REPLACEMENT CHARACTER이라고, 뭔가 잘못되면 이걸로 글자 수를 유지하기 위해서 바꾸는 경우가 있습니다. 이 경우 대부분 보내는 놈이 잘못했다고 눈치를 챌 수 있습니다.

홰聆究셀

옛날에 PC통신 하시던 분들은 자주 보셨을 것 같은데, 이것도 지금 구글에서 검색하면 29900건이 나오는 상당히 인기깨진한글 입니다. 홰영구셀은 점쏙옙과는 달리 좌우로 물음표나 좀 불길한 표시가 곁들여진다는 특징이 있죠. 🙂

이 놈의 정체는 바로 euc-kr에서 “안녕하세요”에서 첫 바이트를 떼낸 것입니다. 안녕하세요는 문자열이나 각 줄의 맨 앞에 자주 와서 앞 글자가 잘리는 경우가 유독 많죠~

컴컴컴컴컴컴넴

요새는 컴컴컴컴컴이 나오면 좀 어색하겠지만, 옛날에는 동네 꼬마아이들도 컴컴컴컴을 보면 이게 바로 그거구나! 하고 정겨워할 정도였었죠~ 컴컴컴컴컴에는 옆에 넴이나 백백백, 낡낡이 곁들여 줘야 좀 더 맛이 납니다. 이 놈의 정체는 미국 영어 코드페이지인 cp437에서 좌우로 긋는 선문자입니다. 아직도 와레즈 그룹들은 cp437을 자주 쓰는 관계로 .nfo 파일들에서 컴컴컴컴을 만날 수 있어서 나름대로(?) 반갑습니다;;

이 녀석은 구글에서 검색이 되긴 하는데, 길이에 따라 따로 따로 인덱스되어 있어서 전체적인 수는 정확히 모르겠지만 대략 5000은 될 것 같네요.

덈뀗섏꽭 쩗꿇뀘

요놈은 고정적인 내용을 가지는 것은 아니고 대충 “띠리띠리”가 새끼손가락 콧구멍에 넣고 외계와 통신할 때 내는 소리로 깨지는 형태입니다. 이것도 어설픈 유니코드 프로그램에서 상당히 자주 볼 수 있죠. 이 놈의 정체는 utf-8 인코딩된 것을 cp949로 푼 것입니다. 주로 겹자음과 희한한 받침들이 오는데, 그 이유는 utf-8에서 쓰는 영역이 주로 두 번째 바이트에 0x81~0x9f를 많이 써서, 그 영역이 cp949에서 euc-kr에 추가로 배치한 자주 안 쓰이는 한글 영역과 겹치기 때문입니다.

)C>H3gGO

이것도 고정적인 내용은 아니고 그냥 형태입니다. 주로 대문자, 소문자, 기호 몇가지가 나오고 중간 중간 음표도 곁들여 주며 나오는 이 모양은 8비트를 모두 지원하지 않는 환경에서 EUC-KR에서의 상위 비트가 모두 날아간 놈입니다. 최근에는 볼 일이 거의 없지만, 예전에는 한국IBM같이 도미노 솔루션을 쓰던 곳에서 보낸 메일이 이런식으로 안 보이게 보여서 난감한 경우가 있었죠. 그리고, ISO-2022-KR로 인코드하고 나서 제어문자 필터링에 걸려서 제어문자가 유실되는 경우도 이렇게 됩니다.

¾È³çÇÏ¼¼¿ä~

아마도 가장 흔하게 많이 볼 수 있는 형태가 아닌가 싶네요~ 요건 EUC-KR을 ISO-8859로 보고 디코딩했을 때 발생하는 형태입니다. 즉, 한글 1글자가 EUC-KR에서 높은 2 바이트가 되기 때문에, ISO-8859에서의 추가 문자에 해당하는 것들이 2개씩 나오게 됩니다. 요건 그래도 ISO-8859-1이 256개 모두 할당되어 있어서 정보의 손실은 없어서 복구는 가능하기 때문에, 다른 것들에 비해서 그래도 준수한 편이라고 할 수 있겠죠. 🙂

켓아~

요놈은 대부분의 글자가 보이지만 일부가 고정적으로 다른 글자로 대체되는 형태입니다. 대표적으로 “횽아” -> “켓아”와 “아햏햏” -> “아쥑쥑” 이 있죠. 둘다 구글에서 검색해 보면 용례가 그렇게 많지는 않지만, 의외로 유닉스 프로그램들에서는 상당히 자주 겪는 패턴입니다.
이 경우는 인코딩이 euc-kr이라고 가정하고, 두 번째 바이트 글자의 하위 7비트만 보고 디코딩해서 생기는 문제입니다. cp949의 경우에는 두 번째 바이트에 MSB가 없는 경우가 있기 때문에, 구분해 줘야 글자를 제대로 판단할 수 있겠죠.

우선 생각나는 것은 써 봤는데, 그 외에 자주 봤던 깨진 한글 있으시면 알려주시면 추가하겠습니다. ^_^

KLDP 사용자들이 필요할 만한 스크립트

April 19, 2007 by hyeshik

KLDP BBS에 종종 가시는 분들이라면 필요할 것 같아서
만들어 봤습니다. Greasemonkey안에 플러그인으로 넣는 것이니, 먼저 Greasemonkey를 깔고 아래 URL을 누르시면 됩니다.

imyejinfree.user.js 설치 (greasemonkey)

뭐 하는 스크립트인지 설명하자면, 특정인을 언급할 수 밖에 없어서, 그 분께 폐가 될 것 같아서 설명은 생략합니다. (다른 분들만 쓰세요~)

오픈룩 서버 분산이전

April 18, 2007 by hyeshik

제가 이제 대전에 살기 때문에 서울에 있는 오픈룩 서버가 죽어도 금방 대처할 수가 없게 되어서, 슬슬 관리를 잘 받을 수 있는 환경으로 기존에 서비스하던 것을 옮기고 있습니다. 오픈룩에서 돌던 네임서버와 메일서버는 지난 주에 대전으로 옮기고, 파이썬 마을은 오늘 옮겼습니다~

오픈룩에서 서비스하던 다른 분들이 쓰실 만한 서비스들의 분산 계획은 이렇습니다.

파이썬 마을: Daum DNA 서버로 이전 — 파이썬사용자모임 위키는 그대로 광운대에서 서비스됩니다.
대안언어축제 위키: 엔씨소프트 오픈마루 서버로 이전 (예정)
오픈룩 블로그: 대전의 개인 데스크탑으로 이전 (예정)
파이썬 문서번역 프로젝트: 어떻게 할 지 고민 중 -ㅇ-
사발통문 (동아리): 동아리 내 서버로 이전 (예정)
파이썬 소스 크로스 레퍼런스(pxr), 연세 컴과 플래닛: 폐쇄
학교 식당, 공지사항 RSS: 개인 데스크탑으로 이전 (예정)

혹시 뭔가 문제가 있으신 분은 알려주세요 ^_^

ActiveX없이 보안메일청구서 읽어보기

April 14, 2007 by hyeshik

전화요금이나 인터넷요금, 카드요금 등등 요즘은 많은 청구서들이 이메일로 청구서를 발송하면서 이른바 “보안메일”이라는 것으로 보냅니다. 그런데, 하필이면 보안까지는 좋은데, 보안 솔루션이란게 윈도우 전용이라 다른 곳에서는 읽을 방법이 없죠. 카드 얼마 썼는지도 모르고.. 전화요금이 나와도 뭐가 얼마 나왔는지 모르고.. 무지 답답합니다. 으이구~

그래서 간단하게 읽어볼 방법이 없을까 해서 보안 메일을 열어봤더니, base64로 인코딩되어 있어서 아.. 이때부터 삽질이 시작되었습니다. “어떻게든 프비에서 보안메일 한번 읽어보자!”

우선은 보안메일의 base64부분만 풀어도 상당한 힌트가 들어있는데, SEED/CBC/PKCS5Padding이라는 헤더가 있기 때문에, 중간 어딘가부터 분명 SEED/CBC가 시작될 것이라는 걸 강하게 암시하고 있습니다. 대략적으로 00이 많이 나오는 지역을 제외하면 첫 100~200바이트 내에서 CBC코딩이 시작된다는 것을 알 수 있는데, CBC는 그 특성상 시작부분을 정확하게 안 맞추면 뒷부분도 모두 어긋나기때문에 100~200사이에서 모두 시도해 보는 것으로 시험해 봤습니다.

주민등록번호 뒷자리를 입력하기 때문에, 주민등록번호 뒷자리에 0을 채운것, 진짜 PKCS5 패딩을 한 것, MD5한 것 세 가지를 해 봤는데, 혹시나 했는데 역시나 전혀 안 보이는군요. 크흐.. 그래서, 그 이후로 주민등록번호를 숫자로 코딩한 것, sha1로 해시해서 자른 것, sha1 해시한 것을 또 md5한 것 등등 상상할 수 있는 온갖 것들을 다 시도해 봤는데, 맞는게 없더군요..

하도 안 되니까, 속임수로 SEED/CBC라고 해놓고 실제론
SEED/CTR이나 AES/CBC같은 것 쓰는게 아닌가 해서 이놈들도
다 시도해 봤는데, 전혀 안 되네요.. 결국에는 디버거의 도움을
받아 장시간의 트레이스 끝에 키를 생성해 내는 방법을 알아내서
풀어 내긴 했습니다;;;; (함수 하나가 뭐 이리 긴지;;)

아.. 저 노이즈 속에 진주처럼 반짝반짝 빛나는 HTML이여.. -ㅇ-;;; 이제 본문을 풀어보면!! (이번 달에 만든 카드라 얼마 안 썼습니다 =3)

그런데, 하나 재미없고 곤란하게 된 것은 컴퓨터프로그램보호법 제 12조의 2항 “프로그램코드의역분석”에서의 제약사항 때문에, 지금까지 해서 메일 보는 것까지는 합법적이지만, 공개하는 것은 불법이기 때문에, 코드를 공개하거나 바이너리로라도 배포하는 것이 불가능하다는 점입니다. 아이고.. 공개를 안 하면 무슨 재미로 개발을 하나…. 그런데, 보안메일에서 쓰고 있는 방법은 엄청나게 기이한 과정을 거치기 때문에 역공학없이 메일 내용만 보고 풀어보는 것은 매우 힘들 것 같아서.. 해당 프로그램을 배포하는 쪽에서 직접 만들지 않는 한은 다른 호환 솔루션이 나오는 것은 매우 어려울 것 같군요.

파이썬 소스로 SEED부분을 제외하고 2줄이면 풀리는 간단한 방법인데, 앞으로 이니텍에서 Firefox용 플러그인도 좀 배포를 해 주던지, 아니면 자바스크립트나 플래시로라도 좀 해 줬으면 좋겠네요. 그거 만드는데 얼마나 걸린다고..~

mechanize로 인트라넷 공지사항 RSS로 만들기

April 13, 2007 by hyeshik

보통 학교나 회사에서 알려주지도 않고 뭘 진행해 놓고서 나중에 왜 인트라넷에 공지 올렸는데 안 봤냐고 그러는 경우가 종종 있습니다. 옛날에 있던 학교에서는 그래도 과사에서 여러 방법으로 알려주려고 시도를 많이 했었는데, 새로 온 학교는 이거 거의 알아서 찾아봐야 먹고 사는 분위기네요. 으흐흐. 게다가 인트라넷은 Firefox로는 로그인도 안 돼서 FreeBSD에서는 도대체 볼 수가 없어서, 애로사항이 여간 아닙니다. 으흐~

그래서, 요새 절정의 인기를 구가하고 있는 mechanize로 게시판 긁어오는 스크립트를 만들어서 전에 식당 메뉴 만들듯 RSS로 만들어 보기로 마음 먹었습니다. 요새는 웬만하면 정보가 사람을 찾아와야지 사람이 정보를 찾으러 다니는 시대는 지났응께~

우선, mechanize는 아시다시피 쿠키와 참조URL 처리, 폼 처리를 자동으로 해 주기 때문에, 간단한 홈페이지를 따라가는 데는 더없이 편합니다. 그래서 웬만한 웹 스크래핑에는 항상 따르는 괴로운 순간 (스트레스가 슬슬 머리 위로 올라오면서, 계속 발생하는 예외상황과 이상한 HTML에 내가 이 일을 해서 뭐가 좋다고.. 하는 번뇌 등등..)이 거의 없이 한 페이지 보고 토닥토닥 해서 한 페이지 지나가고 리듬감을 잃지 않고 정보 수집이 끝났습니다. 역시 개발에는 리듬을 깨는 요소가 최대의 적입니다.

그리고, RSS는 지난번에는 손으로 짜서 print했더니 아침놀군이 HanRSS에서 이상하게 나온다고 하여서, 이번엔 제대로 된 RSS제너레이터를 사용했습니다. 훨씬 쉽고 좋네요~

그리하여, 만들어진 것이 이렇게(svn) 되었습니다. 🙂 이제 윈도우 들어가서 ActiveX와 씨름하지 않고도 학교 공지사항을 보고 장학금 신청을 할 수 있게 되었군요. -ㅇ-; (그러나 학점 미달로 인해 장학금 신청 자격이;;;)

혹시 회사나 학교 인트라넷에 불만이 있으시면 직접 한번 RSS로 만들어 보세요~

필요하신 분들을 위한 링크 (1시간 간격 업데이트):
전체
학생
교수
직원
세미나/행사
컴퓨터/네트워크
연구프로젝트
외국인

파이썬 대화모드에서 자동으로 모듈 들여오기

April 9, 2007 by hyeshik

오늘은 통계 숙제를 하다가, math.e math.log 이런 것 누르려다 보니, import math하기가 갑자기 무지 귀찮았습니다. 맥에서는
파이썬 대화모드는 거의 항상 WidgetTerm에 항상 띄워두고 쓰지만, math나 urllib같이 늘 쓰는 모듈을 쓸 때에도 import하고 쓰는게 그렇게 귀찮았구나~ 하고 옛날 생각도 나면서.. 흐흐

그래서 예전에 올라왔던 자동 들여오기 PEP가 생각나서 봤는데, 게으른 모듈(lazy module)을 일일이 다 만드는 방법으로 처리해서, 소스가 상당히 길고 설치하기가 귀찮더군요. 그래서, sys.excepthook을 써서 어떻게 NameError를 잘 지지고 볶으면 될 것 같아서. 한번 해 봤습니다~

# use as a PYTHONSTARTUP script for your interactive env.

import sys, re

def autoimp(tp, value, tb, orighook=sys.__excepthook__, re=re):
    if tp is NameError:
        name = re.findall("name '([^.']+)'", value[0])[0]
        frame = tb.tb_frame

        try:
            mod = __import__(name)
        except ImportError:
            pass
        else:
            print "[[ Module '%s' is implicitly loaded. ]]" % name
            frame.f_locals[name] = mod 
            exec frame.f_code in frame.f_globals, frame.f_locals
            return

    # bypass the exception to the original handler
    orighook(tp, value, tb) 
sys.excepthook = autoimp

del sys, autoimp, re

# use as a PYTHONSTARTUP script for your interactive env.

import sys, re

def autoimp(tp, value, tb, orighook=sys.__excepthook__, re=re):

if tp is NameError:

name = re.findall("name '([^.']+)'", value[0])[0]

frame = tb.tb_frame

try:

mod = __import__(name)

except ImportError:

pass

else:

print "[[ Module '%s' is implicitly loaded. ]]" % name

frame.f_locals[name] = mod

exec frame.f_code in frame.f_globals, frame.f_locals

return

# bypass the exception to the original handler

orighook(tp, value, tb)

sys.excepthook = autoimp

del sys, autoimp, re

실행해 보면~

% PYTHONSTARTUP=autoimp.py python
Python 2.4.4 (#2, Apr  4 2007, 23:05:50) 
[GCC 3.4.6 [FreeBSD] 20060305] on freebsd6
Type "help", "copyright", "credits" or "license" for more information.
&gt;&gt;&gt; math.log(math.pi)
[[ Module 'math' is implicitly loaded. ]]
1.1447298858494002
&gt;&gt;&gt; math.sqrt(_)
1.0699205044532047
&gt;&gt;&gt; len(urllib.urlopen('http://openlook.org').read())
[[ Module 'urllib' is implicitly loaded. ]]
42911

% PYTHONSTARTUP=autoimp.py python

Python 2.4.4 (#2, Apr 4 2007, 23:05:50)

[GCC 3.4.6 [FreeBSD] 20060305] on freebsd6

Type "help", "copyright", "credits" or "license" for more information.

>>> math.log(math.pi)

[[ Module 'math' is implicitly loaded. ]]

1.1447298858494002

>>> math.sqrt(_)

1.0699205044532047

>>> len(urllib.urlopen('http://openlook.org').read())

[[ Module 'urllib' is implicitly loaded. ]]

42911

적당히 디스크 어딘가에 풀어두고, PYTHONSTARTUP 환경변수로 파일이름(전체경로)를 써 주시면 되겠습니다. 셸 프로파일에 적어주시면 편합니다~ ^^

주의사항: 여러 줄 블럭이거나 한 줄에라도 부작용(side effect)이 있는 코드이면 원래 의도와 다르게 동작할 수 있습니다.

오늘의 장난: 아미노산으로 문장 만들기

April 5, 2007 by hyeshik

오늘도 뭔가를 만들다가, 아미노산을 문자열에 쭉 입력해 놓고, 숫자를 세 보고 20개 맞군! 하고 지나가면서 뭔가 “이걸 문장을 만들어서 외워 놓으면 맨날 하나 하나 생각하면서 20개 맞나 세 볼 필요가 없지 않을까!” 하는 생각에 아미노산을 모두 1번 씩 쓰는 문장을 만들면 정말 재미있겠다는 생각을 했습니다. 마치 폰트셋 볼 때 잽싼 여우가 게으른 개를 뛰어 넘는 것 같이 말이죠~ –; 그냥 ‘ACDEFG…VWY’를 메모 프로그램에 적어두거나 모듈로 만들어 저장해 둬도 되겠지만, 이미 재미있는 놀이가 생각난 판에, 다른 좋은 방법이 눈에 들어오지 않았지요;

결과만 올리면 너무 오래 뻘짓만 한 것 같아서 과정을 상세히 써 봅니다. -O-;;

우선 단어 후보를 한번 추려보기로 했습니다. FreeBSD에서 항상 뭔가 장난할 때 쓰이는 webster 단어 목록을 써서 추려봤습니다. 우선 다 읽어서, 아미노산 알파벳만 쓰고 있는 단어를~

&gt;&gt;&gt; words = open('/usr/share/dict/web2').read().split()
&gt;&gt;&gt; aa = 'acdefghiklmnpqrstvwy'
&gt;&gt;&gt; m = re.compile('^['+aa+']+$')
&gt;&gt;&gt; words = [w for w in words if m.match(w.lower())]

>>> words = open('/usr/share/dict/web2').read().split()

>>> aa = 'acdefghiklmnpqrstvwy'

>>> m = re.compile('^['+aa+']+$')

>>> words = [w for w in words if m.match(w.lower())]

한 단어에 같은 알파벳이 들어있다거나, 너무 짧거나 너무 긴단어를 뺐습니다.

&gt;&gt;&gt; words = [w for w in words if len(set(w.lower())) == len(w)]
&gt;&gt;&gt; words = [w for w in words if 2 &lt;= len(w) &lt;= 7 or w in 'Ia']
&gt;&gt;&gt; len(words)
9863

>>> words = [w for w in words if len(set(w.lower())) == len(w)]

>>> words = [w for w in words if 2 <= len(w) <= 7 or w in 'Ia']

>>> len(words)

9863

지금까지 걸러낸 조건에 맞는 단어가 9863개가 있군요~ 뭔가 나올 것 같아서 벌써 기분이 좋습니다 ㅎㅎ;

자 이제 겹치지 않는 단어를 골라야하는데, 각각의 알파벳이 중복되지 않게 조합하는 문제이기 때문에, 정수계획법 (IP)으로 간단하게 풀릴 것 같아서, glpk로 안 겹치는 조건을 프로그래밍 했습니다.

set W; /* Words */
set A; /* Alphabets */
param aw{W,A}, integer; /* # alphabets in each word */
var used{w in W} &gt;= 0, integer; /* words selected */

s.t. alphasmin{a in A}: sum{w in W} aw[w,a] * used[w] &gt;= 1;
minimize aused: sum{a in A} sum{w in W} aw[w,a] * used[w_];

end;

set W; /* Words */

set A; /* Alphabets */

param aw{W,A}, integer; /* # alphabets in each word */

var used{w in W} >= 0, integer; /* words selected */

s.t. alphasmin{a in A}: sum{w in W} aw[w,a] * used[w] >= 1;

minimize aused: sum{a in A} sum{w in W} aw[w,a] * used[w_];

end;

이제 아까 골라낸 파일에서 데이터를 glpk에서 읽을 수 있게 변환~

&gt;&gt;&gt; import sys; sys.stdout = open('data.txt', 'w')
&gt;&gt;&gt; print 'set W :=', ' '.join(words), ';'
&gt;&gt;&gt; print """\
... set A := %(aas)s;
... param aw default 0
... :              %(aas)s :=""" % {'aas': ' '.join(aa)}
&gt;&gt;&gt; for w in words:
...     wlow = w.lower()
...     print w, ' '.join(str(int(a in wlow)) for a in aa)
... 
&gt;&gt;&gt; print ";\nend;"

>>> import sys; sys.stdout = open('data.txt', 'w')

>>> print 'set W :=', ' '.join(words), ';'

>>> print """\

... set A := %(aas)s;

... param aw default 0

... : %(aas)s :=""" % {'aas': ' '.join(aa)}

>>> for w in words:

... wlow = w.lower()

... print w, ' '.join(str(int(a in wlow)) for a in aa)

...

>>> print ";\nend;"

자 그럼 이제 준비가 다 되었으니 돌려봅시다 -ㅇ-

% <b>glpsol --first -m solword.mod -d data.txt -o found.txt</b>
Reading model section from solword.mod...
(중략)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   1.0 secs
Memory used: 37.2M
lpx_print_mip: writing MIP problem solution to `found.txt'...

% <b>glpsol --first -m solword.mod -d data.txt -o found.txt</b>

Reading model section from solword.mod...

(중략)

INTEGER OPTIMAL SOLUTION FOUND

Time used: 1.0 secs

Memory used: 37.2M

lpx_print_mip: writing MIP problem solution to `found.txt'...

으흐흐.. 결과가 나왔군요! (사실은 나오는 데 꽤 걸렸지만 제약조건 다 풀어서 처음 나온 것이 바로 feasible solution이 나온 척 해 봅니다; )

자.. 이제 결과를 해석해 보면.. 단어가 cwm fed glyph qintar skiv 라는군요.. (덜덜덜) 아미노산이 모두 들어있기는 하지만.. 과연 이게 철자 검사기를 통과하기나 할까 싶은 단어들이 막 나오는군요.. 으흐.. webster 단어들은 대단해~ 이걸 뭔가 좀 쉬운 단어들로 바꿔서 해 보고 싶지만, 쉬운 단어를 골라놓은 사전을 쉽게 찾을 수가 없어서 일단은 여기서 중단; 자.. 이제 저걸 외워볼까요 glyph fed cwm qintar skiv~ (곡도 붙여서..) 흑흑흑..

앞의 결과는 너무 쓸모없는 것 같아서 –; 다른 데 하나 응용해 봤습니다. 해리포터에 보면 Tom Marvolo Riddle이름이 볼드모트로 바뀌는 장면이 있길래, 볼드모트랑 철자 구성이 같은 놈을 하나 만들어 보니까.. dom revolt가 나오는군요.. 역시 짧으니까 그다지 문장으로 만들 수가 없는.. 크흐..

오늘의 결론: 여우가 게으른 개 위로 뛰어 넘는다는 문장은 정말 대단하다!

파이썬에서 순열을 구하는 몇 가지 방법

April 5, 2007 by hyeshik

A~Z까지 알파벳으로 이뤄진 5글자 단어를 모두 검색해서 뭔가를 한다거나, 아들 이름 지을 때 성을 제외한 2글자에서 가능한 모든 조합을 하고 싶은 것 같은 경우가 있습니다. 여러 다양한 상황에서 전혀 주먹구구식 알고리즘이 안 나오고 그냥 NP-complete 문제를 위한 정공법으로 전수조사를 해야할 때면 순열을 만드는 것이 가장 간단한 경우가 많겠죠. 순열 만드는 것이 간단하면서도 뭐가 좋을지 고민을 좀 하게 만드는데, 그래서 파이썬에서 순열을 만들 때 쓸만한 방법을 대충 생각나는 것을 모아 봤습니다. ^_^

우선, 일반적으로 나오는 C언어 입문서에서처럼 다 풀어쓰기를 하면 보통 이런 식으로 구현될 것입니다.

alpha = 'ACGU'
u = len(alpha)
depth = 3
# 위 3줄은 앞으로 공통으로 쓰일 것이므로 뒤에는 생략합니다. 

# 1
seqs = []
for a in alpha:
    for b in alpha:
        for c in alpha:
            seqs.append(a + b + c)

alpha = 'ACGU'

u = len(alpha)

depth = 3

# 위 3줄은 앞으로 공통으로 쓰일 것이므로 뒤에는 생략합니다.

# 1

seqs = []

for a in alpha:

for b in alpha:

for c in alpha:

seqs.append(a + b + c)

뭔가 한 눈에 확 들어오는 간단함은 있지만, 반복 수가 변하는 경우에는 루프가 늘어나고, 별로 코드도 중복이 가득해 보이는 것이 그다지 멋있지 않습니다. 그래도, 일단 좀 더 파이썬 코드처럼 보이게 하기 위해 줄여 보면,

# 2
seqs = [a+b+c for a in alpha for b in alpha for c in alpha]

1 2	# 2 seqs = [a+b+c for a in alpha for b in alpha for c in alpha]

이제 1줄로 줄기는 했지만, 내부적으로는 구조는 1번과 다를 것이 없습니다. 반복횟수가 바뀌면 여전히 루프가 늘어납니다.
그래서, 루프를 1개로 줄이고, 보통 많이 쓰이는 나누기 나머지 나누기 나머지 방법을 쓰면 이렇게 약간 일반화를 할 수도 있겠죠.

# 3
seqs = []
for i in range(u**3):
    seqs.append(alpha[i // (u**2)] + alpha[i // u % u] + alpha[i % u])

# 3

seqs = []

for i in range(u**3):

seqs.append(alpha[i // (u**2)] + alpha[i // u % u] + alpha[i % u])

루프는 1개로 줄었지만, 여전히 3개로 제한되어 있기는 마찬가지입니다. 이번에는 alpha에 매핑하는 부분도 일반화를~

# 4
seqs = [''.join(alpha[i // (u**d) % u] for d in range(depth))
        for i in range(u**depth)]

# 4

seqs = [''.join(alpha[i // (u**d) % u] for d in range(depth))

for i in range(u**depth)]

자 이제 코드도 줄고 depth만 바꾸면 길이가 마음대로 바뀝니다~ 그렇지만, 약간 계산 오버헤드가 늘기는 했겠죠. -ㅇ-;

순열이 완전히 다 필요한 경우가 아니라, 일부가 필요한 경우이거나, 순열에서 쓰는 원소의 메모리 크기가 엄청 커서 복잡한 경우 등 여러 독특한 경우에는 순열에서 만들어지는 놈을 필요할 때 계산하는 것이 유용할 수도 있습니다.

# 5
class LazyPermu(list):
    def __getitem__(self, idx):
        i = list.__getitem__(self, idx)
        return ''.join(alpha[i // (u**d) % u] for d in range(depth))
seqs = LazyPermu(xrange(u**3))

# 5

class LazyPermu(list):

def __getitem__(self, idx):

i = list.__getitem__(self, idx)

return ''.join(alpha[i // (u**d) % u] for d in range(depth))

seqs = LazyPermu(xrange(u**3))

자, 이번엔 접근법을 약간 바꿔서 숫자를 안 쓰는 방법을 생각해 봅시다. 빈 것에서 시작해서, 모든 경우를 한 번씩 추가한 것을 원하는 횟수만큼 계속 더해주는 방식으로 하면 되겠죠.

# 6
seqs = ['']
for i in range(depth):
    seqs = [seq+a for seq in seqs for a in alpha]

# 6

seqs = ['']

for i in range(depth):

seqs = [seq+a for seq in seqs for a in alpha]

알고리즘의 계산 복잡도는 약간 안 좋아졌지만 — O(M^N)에서 O(M^N+2)로.. — 짧은 순열에 대해서는 그다지 차이는 안 날 것 같고, 코드도 그런대로 알아보기 쉬워졌습니다~ ^_^

이번엔 또 접근법을 좀 바꿔서, 행운을 믿는 사람이라면 순전히 랜덤 함수에 기대어 빨리 끝나기만 기다릴 수도 있겠습니다;;

# 7
from random import choice
seqs = set()
while len(seqs) != u**3:
    seqs.add(''.join(choice(alpha) for i in range(depth)))

# 7

from random import choice

seqs = set()

while len(seqs) != u**3:

seqs.add(''.join(choice(alpha) for i in range(depth)))

전체 순열이 필요할 때 이걸 실제로 쓰게 되지는 않겠지만, 순열이 굉장히 커서, 전체를 메모리에 담고 있을 수 없을 때, 순간 순간 생성하되 랜덤한 순서가 필요할 때는 이것도 쓸모가 있겠죠;;; (억지로 짜낸 용례 -ㅇ-)

정말 심심할 때는 추후 고객의 업그레이드 유도를 위한 “바쁘게 돌아가는 인터넷 속의 쉼터”(TM)로 이렇게 만들어 볼 수도 있겠습니다;;

# 8
import re
pat = re.compile('[%s]{%d}' % (alpha, depth))
seqs = set()
rnd = open('/dev/random')
while len(seqs) != u**3:
    map(seqs.add, pat.findall(rnd.read(10240)))

# 8

import re

pat = re.compile('[%s]{%d}' % (alpha, depth))

seqs = set()

rnd = open('/dev/random')

while len(seqs) != u**3:

map(seqs.add, pat.findall(rnd.read(10240)))

아하하;;;

자.. 이제 파이썬에서 순열을 구하는 여러가지 방법을 알아 보았는데요, 어느 한 방법이 꼭 좋다기보다는, 상황마다 고려해야할 것이 많이 있겠죠. 예를 들면,

순열이 무지 길고 크고 루프가 오래 돌아간다 –> 순열을 생성하는 놈을 제너레이터로 만들어서 한꺼번에 메모리를 왕창 안 먹고 있게 한다.
분산처리를 해야한다 –> 단일 숫자 인덱스를 기반으로 한 순열이 아무래도 쪼개기가 좋겠죠.
항상 2개가 쌍일 뿐이다 –> 그냥 1번처럼 for루프 2개 돌려도~
순열에 랜덤하게 왔다갔다 접근할 필요는 있는데, 메모리는 적게 쓰고 싶다 –> 5번 같이 순간순간 짠~하고 만들어주는 녀석을 쓰세요~
KS X 1001 글자들 같이, 순열은 순열인데 종종 코드 곳곳이 비어있다! –> 파이썬의 리스트 컴프리헨션 뒤에 if 붙이는 문법은 정말 멋집니다~ -.-b
누구나 금방 알아볼 수 있는 코드로 만들고 싶다 –> 몇개 안 되면 좀 촌스러워도 1번처럼 짜거나, 순열 만드는 놈을 제너레이터로 빼서 이름을 잘 지으세요~