succinct_trie

A succinct (pointer-free) trie for dictionary-based longest-match word segmentation, built once from word lists and serialized to a compact on-disk format that loads back as flat arrays — no per-node objects, no pointers.

What it is

A classic pointer trie wastes memory: every node is an object holding a dict of child pointers. This implementation builds that trie once, then encodes it into a level-order (LOUDS-style) succinct representation — three flat arrays instead of a node graph:

Array	Holds
node_idx_to_char	the character at each node, in BFS order
end_of_word	end-of-word marker / count per node
index_of_0	per-node offset used to locate that node's child block

Navigation never dereferences a pointer. To walk to a child you compute the child block directly from the offset array:

first_child = index_of_0[node] - node
length      = index_of_0[node + 1] - index_of_0[node] - 1

Because children of a node are stored contiguously, a lookup is just a scan over that small block. The structure is immutable by design — build (or rebuild) from a word list; no per-key insert/delete. That's the trade that makes the compact encoding possible.

Why it's interesting

• Near-minimal memory. Dropping per-node pointers/objects is the whole point of succinct data structures — you store close to the information-theoretic minimum and still support fast traversal.
• Build once, load cheap. The trie is serialized to a text file (trie/trie.txt) and reconstructed on load, so the expensive build is amortized across runs.
• Practical target: word segmentation. The matcher does dictionary longest-match word breaking — useful for languages written without spaces (e.g. Thai), where you must segment a run of characters into known words.

Layout

Trie.py    # TrieClass: build + serialize + load + longest-match segmentation
create.py  # build a trie from dict/word_dict.txt and save it to trie/
load.py    # load a saved trie and run longest_match_word_break on a sentence
dict/      # input word lists
trie/      # serialized succinct trie

Run it

No dependencies beyond the standard library (os), so any Python 3 works.

Build the trie from a word list:

python create.py

Load it and segment a sentence:

python load.py

API

from Trie import TrieClass

# build from word lists and save
trie = TrieClass(create_trie_folder="trie", dict_path_list=["dict/word_dict.txt"])

# or load a previously built trie
trie = TrieClass(load_trie_path="trie/trie.txt")

trie.longest_match_word_break(sentence)   # -> list of matched words, left to right
trie.rfind_longest_word(sentence)         # -> rightmost (index, word) match

Status

A learning project exploring succinct data-structure encoding. Working and runnable; intentionally small in scope, and immutable once built.