PrefixGraph Class Reference

A lighting fast bitwise prefix tree. More...

Classes
struct	Node
Public Types
typedef uint64_t	Head
typedef uint32_t	DataIndex
typedef uint32_t	Data
Public Member Functions
bool	has (const char *word)
	Check if trie contains a word.
bool	has (const char *word, unsigned int &match)
	Check if trie contains a word.
int	build (const char *filename)
	Build a trie from words listed in file.
void	save (const char *filename)
	Write trie into file.
void	load (const char *filename)
	Load trie from file.
Protected Attributes
long	size
	size of the data array
Head *	codes
	lookup table for conversing a character to a coresponding bit
Data *	data
	data array

Detailed Description

A lighting fast bitwise prefix tree.

By default tree is compressed to directed acyclic graph to reduce memory consumption.

This structure may be usefull for:

int PrefixGraph::build ( const char * filename )

Build a trie from words listed in file.

Requirements:

Words have to be sorted alphabetically. Every word ends with \n, not with \0. Refer to PrefixTreeLL::build.
Only characters defined in PrefixNodeBase::prepareCodes. Notice that only lowercase letters were defined.

Check if trie contains a word.

Parameters:

	word	ends with \0.
`[out]`	match	index of the first letter in word that not match (the length of matched prefix). It will not count \0.

bool PrefixGraph::has ( const char * word ) [inline]

Check if trie contains a word.

Parameters:

word

ends with \0.

void PrefixGraph::load ( const char * filename )

Load trie from file.

File should be created by save(filename).

Data* PrefixGraph::data [protected]

data array

All nodes of the trie are writen to one array.

Advantages:

avoiding use of pointers what substantially reduces the memory comsumption, especially on 64 bits systems
reducing memory fragmentation.
faster loading and writing the structure to files

Price:

The documentation for this class was generated from the following files: