Space-efficent storage of a trie as array of integers

Question

I'm trying to efficiently store a list of strings in an array with the following constraints:

• All strings consist of 8-bit characters (0..255).
• The final trie is static, i.e. once it is built, no strings have to be inserted or removed.
• Looking up a string of length $m$ must be done in $O(m)$ with a constant factor as low as possible.
• Looking up a string should be possible in an incremental manner, i.e. the end of a string to look up isn't known in advance.
• The only available memory structure to store the data is an array of integers. In particular, there are no pointers or dynamic memory allocation.
• Once an array is allocated, it cannot be resized and its memory cannot be released anymore.
• Memory is rare, so the final data structure should be as compact as possible and no unnecessarily long arrays should be allocated.
• Computation time is not important for the building phase, but for memory usage the consraints above apply.

The aim is to have a data structure to quickly find prefix matches of a long string. For example, if the input string is foobar, the match results will vary if the array has stored the strings foo and bar, or just foobar. For this incremental lookup is important.

Preface

My current approach is a trie that is stored in the array with the following structure:

$$ \fbox{$\vphantom{^M_M} \;i_0 \;\ldots\;i_{255}\;$}\, \fbox{$\vphantom{^M_M} \;i^*_0 \;\ldots\;i^*_{255}\;$}\, \fbox{$\vphantom{^M_M} \;w\;$}\, \fbox{$\vphantom{^M_M} \;\mathit{last}\;$}\, \fbox{$\vphantom{^M_M} \;B_0\;$}\,\fbox{$\vphantom{^M_M} \;B_1\;$}\,\ldots $$

where $i_k$ is a mapping from each unique input character $k$ to an integer $1 \leq i_k(c) \leq w$ with $i^*$ being the corresponding reverse mapping of $i$. Each node in the trie is stored as a block $B$ of size $w+1$. The mapping $i$ is used to reduce the size of each block, because not the whole character range has to be stored but only the number of characters actually used. This comes at the expense of having one more indirection when looking up words. (The field $\mathit{last}$ here is used as a pointer to the field after the last block in the array, used to find the next allocation point.)

Each block looks like this:

$$ \fbox{$\vphantom{^M_M} \;b\;$}\, \fbox{$\vphantom{^M_M} \;c_1 \;\ldots\;c_w\;$} $$

$b$ is either 1 if the word represented by that block is in the trie, and 0 otherwise. $c_i$ represent all unique input characters (after the $i$ mapping). If the value of $c_i$ is equal to 0, there is no entry for this character. Otherwise $c_i$ is the index into the array at which the block to the following letter starts.

To build the trie, the first step is calculate the bijection $i$/$i^*$ and $w$. Then new blocks are added with each prefix that isn't already present in the trie.

Problem

While this approach works so far, my main problem is memory usage. The current approach is extremly memory expensive when only few words share longer prefixes (which is usally the case). Some tests show that the typical number of non-empty fields is only about 2-3% of the whole array. Another problem is that the final number of needed array fields is only available after the trie has already been built, i.e. I have to be conservative when allocating the memory to not get out of memory while adding new blocks.

My idea now was to use a compressed trie/radix trie instead with two types of blocks: 1) the ones above that represent nodes with several children, and 2) compressed blocks (similar to C char arrays) that represent suffixes in the trie. For example, when the words apple juice and apple tree should be stored in the tree, there would be seven normal blocks for the common prefix apple and a compressed block for each juice and tree. (Perhaps that would also allow to merge common suffixes for words with different prefixes.)

The problem with this is that is may lead to gaps in the array while building the trie. Consider the situation in the above example, in which only apply juice is stored as a compressed block in the trie. Now apple tree is inserted, which would lead to a removal of the apple juice block and addition of juice and tree blocks instead, which will not fit into the left hole in general.

Under the given constraints, can anyone see an algorithm to store strings most efficiently in the array while keeping the linear lookup time?

Answer 1

Instead of a trie, here is an alternative approach that is compact and easy to implement:

Sort the list of strings. Store the sorted list. Use binary search for lookups.

To store the string, have two arrays: $A[1..n]$ is an array with $n$ entries, where $n$ is the number of strings; $B[1..M]$ is an array with $M$ characters, where $M$ is the sum of lengths of all of the strings. $B$ stores the concatenation of all of the strings, in sorted order. $A[i]$ holds an offset into $B$ where the $i$th string is stored. In other words, the $i$th string is $B[A[i]..A[i+1]-1]$.

To look up a string, use binary search into the sorted list of strings. You'll be able to look up a string of length $m$ in at most $O(m \log n)$ time, and perhaps less (we're at the point where asymptotic analysis is not useful for distinguishing between these running times, as the constant factors may be more significant than the $\log n$ or $\log \log n$ terms).

Note that this can support character-by-character online lookups. In particular, suppose we have seen the first $k$ characters of the search query $Q$. Assume that we have used binary search to find the index $i_\ell$ of the first string that starts with $Q[0..k-1]$ and the index $i_u$ of the last string that starts with $Q[0..k-1]$. Now, we receive the $k+1$st character of the search query, namely, $Q[k]$. Then we can update $i_\ell$ and $i_u$ using binary search (within the narrow range of indices $i_\ell..i_u$); this takes $O(\log(i_u-i_\ell))$ steps of binary search.

As a performance optimization, notice that since you know all strings within $i_\ell..i_u$ start with the same $k$ characters, during the binary search, you don't need to compare all $k+1$ characters of the search query to the first $k+1$ characters of each string in your list. Rather, you can look only at the $k+1$st character: e.g., compare $Q[k]$ to $B[A[i]+k]$, when examining index $i$ during the binary search. As a result, each step of the binary search takes only $O(1)$ time. So, the entire binary search for processing a single character takes $O(\log(i_u-i_\ell))$ time, and it allows you to update the set of all matches in an online fashion as you receive the search query character-by-character.

This approach will be very compact, supports online searches, is easy to implement, and might be competitive in running time.