		Adaptive Cache-efficient Trie Search
		====================================

This is an C++ implementation of the cache-adaptive trie search algorithm  
described in paper:

	Anurag Acharya, Huican Zhu, and Kai Shen, Adaptive Algorithms for 
	Cache-efficient Trie Search. ACM and SIAM Workshop on Algorithm 
	Engineering and Experimentation, Jan, 1999.

A postscript version of this paper is enclosed in this release (trie.ps).

This release contains two separate trie search algorithms, each resides in 
one subdirectory:

Dictionary/	dictionary trie search (alphabet are restricted to English
		characters, hyphen and apostrophe)
		dict_test.dat is a sample input file which includes an 
		insert and a search phase. 
		After compiling the code, run "trie -i dict_test.dat" to 
		try the sample input file.

general/	trie search with arbitrary alphabet
		general_test.dat is a sample input file which includes an 
		insert and a search phase.
		After compiling the code, run "trie -i general_test.dat" 
		to try the sample input file.

If you need to support different input file format, timing mechanism and 
etc, you should modify Main.C under each subdirectory. Other source files 
are expected to be unchanged.

Please refer to the paper trie.ps for more details about the algorithm.
