華怡價帽가 하늘을 바라보며

자연어 처리에 있어서 중요한 것은 Knowledge Base라고 할 수 있겠습니다. 사전과 문법, 패턴 뭐 이런 것들이 사실 가장 중요합니다. 그래서 전산과 출신인 저로서는 난감한 Position입니다. ^^;;; formalism은 언어학 대가들께서 만들어 주시고, 지식은 언어학 출신의 훈련된 지식 엔지니어가 해주면 되는 일인데....

그래도 전산과에서 해줄 수 있는 일은, 컴퓨터에서 동작되도록 해주는 일인것 같습니다. 그중에 가장 자주 사용되는 (저만 일수도..) 자료구조가 TRIE 입니다.

TRIE에 대해서는 누군가 블로그에 잘 써놓은 글을 읽어보시면 될 것같습니다. [TRIE]  혹은 여러 검색엔진에서 검색하면 정의나 뭐 그런것 들이 나오겠지요. 그건 기본이니깐.

최근에 제가 해낸 것이 하나 있어서 ^^;;

일본에서 개발한 것인데, Double Array TRIE라는 것이 있습니다.

속도도 빠르고 나름데로 좋은 것 같습니다. 프로그램 소스도 있으니까 이것을 익히면 될 것도 같습니다.

double array trie 는 일본에서 개발한 것이라서, 자존심상 좀 더 좋은 것을 가지고 있고 싶었습니다. 이전에 가지고 있던 것과 비교를 해보니, 화일 Size는 제것이 훨씬 작은데, 속도는 좀 느리더군요....

이 TRIE는 구현이 정말 쉽습니다. 메모리에 모두 Loading을 했다가, 각 노드별로 화일에 써주면 Compile된 TRIE가 생성됩니다. 이때 Link address를 미리 계산해서 link를 char array의 address로 해주면 됩니다. 화일은 char array와 똑 같습니다. fseek(i) 하는 것과 str [i]하는 것이 동일하니까요.....

그런데 Search Time에 걸려있는 모든 노드를 linear search 하는 방식이라서 속도가 좀 늦었던 것 같습니다. (50만건 탐색에 3초정도)

그래서 Darts에는 지지 않고 싶어서 머리를 짜냈습니다. Binary Search로 하면 아무래도 빠를테니깐....

이렇게 그림을 바꾸어 놓고 보면 뭐, 별차이는 아니지만 속도가 대략 2배 이상 빨라집니다. ^^

 

그림에는 나타나지 않았지만, 각 노드에는 하나의 글자(character)가 들어가는 것으로 Building은 하고 String Optimize(중간 글자 node를 지우고, 앞 노드에 글자를 붙여주는 것)하면 쓸데없이 중간에 끼어 있는 노드는 없어집니다. 그러니까, 위의 그림에서 노드에는 String이 들어 가게 됩니다. (선수만 이해하려나???)

이제 50만건 탐색에 1.4초정도 걸리면서도 Darts 보다 공간은 30% 정도만 사용하는 TRIE를 만드는 알고리즘입니다.

 

논문으로 쓰려다가 블로그도 논문과 무엇이 다를까 싶어서, 그리고 논문보다 딱딱하지 않아도 되고, 교수도 아닌 제가 논문 편수를 높이는게 뭐 그리 중요할까 싶어서... 간단하게 블로그-논문을 올려보네요...