| 1 |
datrie - Double-Array Trie Library |
| 2 |
================================== |
| 3 |
|
| 4 |
This is an implementation of double-array structure for representing trie, |
| 5 |
as proposed by Junichi Aoe [1]. |
| 6 |
|
| 7 |
Trie is a kind of digital search tree, an efficient indexing method in which |
| 8 |
search time is independent of database size. It only takes O(m) search time, |
| 9 |
where m is the length of the search string. Comparably as efficient as hashing, |
| 10 |
trie also provides flexibility on incremental matching and key spelling |
| 11 |
manipulation. This makes it ideal for lexical analyzers, as well as spelling |
| 12 |
dictionaries. |
| 13 |
|
| 14 |
See the details of the implementation at [2]: |
| 15 |
https://linux.thai.net/~thep/datrie/datrie.html |
| 16 |
|
| 17 |
Historically, this was first implemented as C++ classes in a library called |
| 18 |
midatrie [2], but later simplified and rewritten from scratch in C. |
| 19 |
|
| 20 |
-- |
| 21 |
Theppitak Karoonboonyanan. |
| 22 |
September 2006. |
| 23 |
|
| 24 |
References |
| 25 |
---------- |
| 26 |
|
| 27 |
[1] Aoe, J. "An Efficient Digital Search Algorithm by Using a Double-Array |
| 28 |
Structure". IEEE Transactions on Software Engineering. Vol. 15, 9 |
| 29 |
(Sep 1989). pp. 1066-1077. |
| 30 |
|
| 31 |
[2] Karoonboonyanan, T. "An Implementation of Double-Array Trie". |
| 32 |
https://linux.thai.net/~thep/datrie/datrie.html |
| 33 |
|