资 源 简 介
Darts-clone: A clone of Darts (Double-ARray Trie System)
Darts-clone is a clone of Darts (Double-ARray Trie System), which is a C++ header library for double-array structure.
The major advantages of Darts-clone are as follows:
Half-size units
While Darts allocates 8 bytes to each unit, Darts-clone allocates only 4 bytes to each unit. This feature simply halves the size of dictionaries.
More sophisticated structure
While Darts uses a trie to implement a dictionary, Darts-clone uses a Directed Acyclic Word Graph (DAWG), which is derived from a trie by merging its common subtrees. Darts-clone thus requires less units than Darts if a given keyset contains many duplicate values.
Due to these advantages, Darts-clone achieves more compact dictionaries without degrading search performance.
Project URL: http://code.google.com/p/darts-clone/
