PrefixTreeLL Class Reference

A linked list prefix tree. More...

#include <PrefixTreeLL.h>

List of all members.

Public Member Functions
void	clear ()
	Deallocate memory.
void	show (std::ostream &out)
	Print internal arrays.
bool	has (const char *word)
	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
unsigned int	size
	size of internal arrays
char *	letter
	letters array
int *	next
	positions of alternative letters
Friends
class	PrefixGraphBuilder

---

Detailed Description

A linked list prefix tree.

It's linked list implementation of prefix tree structure.

Note:

Probably you should use PrefixGraph class in your program. PrefixGraph is both faster and less memory consuming with the same funcionality. PrefixTreeLL is provided only to help building PrefixGraph.

---

Member Function Documentation

int PrefixTreeLL::build

(

const char *

filename

)

Build a trie from words listed in file.

Words have to be sorted alphabetically. Every word ends with \n, not with \0.

Returns:

0 if succeed.

Todo:

Check malloc/realloc return values.

bool PrefixTreeLL::has

(

const char *

word

)

Check if trie contains a word.

Parameters:

word

ends with \0.

void PrefixTreeLL::load

(

const char *

filename

)

Load trie from file.

File should be created by save(filename). It's faster than building it from a list of words. It throws an exception if something wrong.

void PrefixTreeLL::show

(

std::ostream &

out

)

Print internal arrays.

Use only for small dictionaries.

---

Member Data Documentation

int* PrefixTreeLL::next [protected]

positions of alternative letters

For dictionary:
 ma
 mama
 tama

Notice that words "ma" and "mama" have the same prefixe.
The trie structure compresses all redundant prefixes into one:
 ma
   ma
 tama

Contents of arrays:
 letters = m  a \n  m  a \n  t  a  m  a \n
 next    = 6 -1  3 -1 -1 -1 -1 -1 -1 -1 -1

 next[0] = 6 because letter[6] = 't' is the next alternative letter (both 'm' and 't' are on the same position in words "ma" and "tama")
 next[2] = 3 because letter[3] = 'm' is the next alternative letter ( letter[2] = '\\n', this is the end of word character )
 If there is no next letter then value -1 is in the array.

---

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

• /home/th/Pulpit/PrefixTreeV01/PrefixTreeLL.h
• /home/th/Pulpit/PrefixTreeV01/PrefixTreeLL.cpp