영어사전에서 영어단어 검색 속도

저의 처음 발제글은 100만개의 단어를 순차검색 했을때,

(1) 최선의 경우: 영어단어 1번 비교 --> 10마이크로(10의-5승)초
(2) 최악의 경우: 영어단어 100만번 비교 --> (10의6승) x (10의-5승) --> 10초
(3) 평균: 최악의 경우 / 2 --> 5초
이러한 시간이 걸린다는 것이었습니다.

앞에서 말씀하신 것처럼, 이진검색을 많이 사용하는데,
이진검색은 기본적으로 검색대상이 정렬되어 있어야 하며,
100만개의 단어를 정렬하는 시간이 필요하다는 단점이 있습니다.
그래서, 100만개의 단어가 처음에 입력될때부터 정렬되는 순서대로 메모리에
저장시키는 방식으로 이진탐색트리(Binary Search Tree)가 있습니다.
BST 자료구조를 사용하면 정렬시간이 필요없게 됩니다.
그런데, BST의 단점은 트리의 깊이(height)가 깊어질 수 있습니다.
이 단점을 보안한 것이 BTree입니다. BST는 order가 2인 BTree라고 볼 수 있습니다.
order가 10인 BTree에 100만개의 단어를 저장하면,
BTree의 깊이(height)는 log(10의6승) --> 6이 됩니다.
따라서, BTree에서는 단어를 최소 6번, 최대 6번 x order --> 60번만 비교하면 되고,
시간으로 산출하면,

(1) 최소: 6번 비교 --> 6 x 10마이크로초 --> 60마이크로초
(2) 최대: 60번 비교 --> 60 x 10마이크로초 --> 600마이크로초 --> 0.6미리초

100만개의 단어중에서 하나의 단어를 검색할때 최대 0.6미리초만에 검색해 낼 수 있다는 것인데,
대단하지 않나요?
BTree 알고리즘은 1970년에 보잉사에서 연구원으로 일하던 R.Bayer에 의해서 이미 개발된 알고리즘입니다.
(Bayer의 발표 논문은 제가 http://www.kernel.bz/db/02/db0201.htm 에 번역해 두었습니다)
그런데 BTree는 몇가지 단점을 가지고 있었는데,

(1) 할당된 메모리의 50% 정도만 사용함 --> B*Tree로 개선됨.
(2) 포인터와 데이터가 하나의 노드에 있어 알고리즘 효율이 다소 떨어짐 --> B+Tree로 개선됨.

이렇게 개선되어 왔습니다. 또 어떤 알고리즘들이 있을까요?

저의 관심사는 휴대용(스마트)기기에 영어단어사전을 구축하고 영어번역학습기를 구현하는 것이고,
더 나아가 자연어 기계 번역에 도전하려 합니다. 자연어 번역은 하면 할수록 재미있는 주제인듯 합니다.
컴퓨터에 구현할 수 있는 고급 알고리즘 지식들을 총동원하여 응용개발 및 개선해야 할듯합니다.
휴대용기기에서 상용 DBMS(오라클,MSSQL,MySQL,Sybase...)을 포팅하여 사용하는것은 많은 부하가 걸립니다.
그래서 영어번역학습 맞춤형 자료구조와 알고리즘을 구현하는것이 중요하고 어느정도 구현하였습니다.
앞으로 꾸준히 그 결과물들을 공유해 나갈 예정입니다.
저의 발제에 관심 있거나, 좋은 알고리즘들을 같이 학습하고 서로 검증해 보고자 하는 결과물이
있다면 서로 연락하고 토론했으면 합니다.

from 알지비(rgbi3307(at)nate.com) on the www.kernel.bz