home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 2010 April / PCWorld0410.iso / hity wydania / Ubuntu 9.10 PL / karmelkowy-koliberek-desktop-9.10-i386-PL.iso / casper / filesystem.squashfs / usr / share / doc / libdatrie1 / README < prev   
Encoding:
Text File  |  2009-02-04  |  1.1 KB  |  33 lines
  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 with 
  8. O(1) time complexity for searching. Comparably as efficient as hashing,
  9. trie also provides flexibility on incremental matching and key spelling
  10. manipulation. This makes it ideal for lexical analyzers, as well as spelling
  11. dictionaries.
  12.  
  13. See the details of the implementation at [2]:
  14.   http://linux.thai.net/~thep/datrie/datrie.html
  15.  
  16. Historically, this was first implemented as C++ classes in a library called
  17. midatrie [2], but later simplified and rewritten from scratch in C.
  18.  
  19. --
  20. Theppitak Karoonboonyanan.
  21. September 2006.
  22.  
  23. References
  24. ----------
  25.  
  26. [1] Aoe, J. "An Efficient Digital Search Algorithm by Using a Double-Array 
  27.     Structure". IEEE Transactions on Software Engineering. Vol. 15, 9 
  28.     (Sep 1989). pp. 1066-1077.
  29.  
  30. [2] Karoonboonyanan, T. "An Implementation of Double-Array Trie".
  31.     http://linux.thai.net/~thep/datrie/datrie.html
  32.  
  33.