TRIE를 구현할때 ARRAY로 구현하면 RANDOM INDEX가 가능하기 때문에
속도 측면에서 엄청난 이득을 얻을수 있다.
다만 array를 사용하게 되면 많은 메모리를 차지하는 문제가 발생하는데
이 문제를 array를 중복사용할수 있도록한 아이디어와 sparse matrix를 세개의 배열( triple array : base, next, check )로 변환하여
저장하는 방식으로 메모리 문제와 속도문제를 동시에 해결한 방법을 소개한다.
참고 : http://linux.thai.net/~thep/datrie/#Tripple
참고 : http://www.cs.princeton.edu/courses/archive/fall09/cos521/Handouts/storingasparse.pdf
'알고리즘' 카테고리의 다른 글
| norvig spell checker (0) | 2013.08.28 |
|---|---|
| get tf and df using suffix array (0) | 2013.07.30 |
| 희소행렬 (sparse matrix) - yale format (0) | 2013.05.09 |
| YAHOO_LDA (0) | 2013.01.25 |
| LDA ( LATENT DIRICHLET ALLOCATION ) (0) | 2013.01.24 |