GitHub

CH-Trie is the official C library of the coordinate hash trie. See the Coordinate Hash Trie section.

CH-Trie is designed for arbitrary symbols, not just characters. Instead of providing high-level string set/dictionary interfaces, CH-Trie provides low-level interfaces making you implement your own trie-based data structures. See the Usage section.

Table of Contents

The coordinate hash trie is a trie variant balancing between time, space, and simplicity.

The basic idea is very simple. We use a global hash table to store all edges in a Trie. Each edge is stored as a dictionary item (from, symb)->to.

We use a special hash function:

, where m is the size of the alphabet, and H is the number of slots in the hash table. For a trie with n nodes, we take H = (n-1)/alpha where alpha is the constant load factor. No rehashing, resizing, or reallocation is required.

We could prove that the time complexity of transition from one node to another, is O(1) for the average case and O(m) for the worst case. The space complexity is O(n), unrelated to m.

See my paper for the analysis and proof.

Compared to other compressed trie variants like double array trie, or using n hash tables each for a node, this variant provides stable space consumption and is very easy to implement.

CH-Trie requires a C89 compiler and POSIX errno definitions.

To install CH-Trie as header files and a static library into the system:

By default, CH-Trie is installed to /usr/local. To link CH-Trie, use the -l chtrie option on your compiler.

It's also simple to embed CH-Trie into your project. Just include chtrie.h. Compile and link chtrie.c.

CH-Trie provides low-level interfaces. It's not designed in the concepts of strings and trees, but symbols and nodes.

Each node is indexed by a non-negative integer less than the maximum number of nodes specified by the chtrie_alloc() call. The root node is indexed by 0.

Each symbol is a non-negative integer less than the alphabet size specified by the chtrie_alloc() call.

You could use the chtrie_walk() function to walk from one node to its child. The chtrie_walk() function also provides an argument that determines whether to create a new node if the child didn't exist.

Because nodes are indexed by non-negative integers, it's easy to associate additional information with nodes, by using external data structures. For example, we could define an array nchild[] where nchild[i] stores the number of children of node i, or you could maintain whether a node is a termination node, which node is its parent node, and so on.

The low-level nature brings both flexibility and simplicity to CH-Trie. There are only one public type and four functions of CH-Trie.

typedef ... chtrie

A chtrie instance represents a trie.

chtrie *chtrie_alloc(int n, int m)

Allocate a trie with at most n nodes, and the alphabet size m.

If n or m is less than 1, they will be regulated to 1.

Nodes in the trie are indexed by non-negative integers less than n. The root node is indexed by 0. Symbols are non-negative integers less than m.

Upon success, return a pointer to the trie. Otherwise, return NULL and set errno.

int chtrie_walk(chtrie *tr, int from, int sym, int creat)

Walk from one node to its child.

If the child didn't exist and creat is non-zero, a new node will be created.

from must be a valid node index, and sym must be a non-negative integer less than the alphabet size, or the behavior is undefined.

Upon success, return the index of the child which is a non-negative integer less than the maximum number of nodes specified by the chtrie_alloc() call.

Otherwise, return -1.

If creat is non-zero and this routine fails, errno will be set.

void chtrie_del(chtrie *tr, int from, int sym)

Delete a child node.

The child node must be a leaf if it exists, or the behavior is undefined.

If the child doesn't exist, the trie shall be left unchanged.

from must be a valid node index, and sym must be a non-negative integer less than the alphabet size, or the behavior is undefined.

void chtrie_free(chtrie *tr)

Free the trie.

The following program builds a trie with words from the dict array excluding those that are also in the stop array.

After the trie is built, it reads lines from the standard input. For each line, the program prints 1 if the line is in the trie. Otherwise, the program prints 0.

This example illustrates the common usage of CH-Trie, e.g. how to associate additional information with a node.