[lltx] pattern loading in luatex

Stephan Hennig mailing_list at arcor.de
Sun Mar 6 14:24:33 CET 2011

schrieb Taco Hoekwater:

> Almost. It refers to a hash with pre-calculated fall-back transitions
> (both hash and trie are words for actual data structures).

But there is a difference.  A hash is about laying out data in physical
memory, i.e., mapping data to addresses.  A trie, on the other hand,
makes no assumptions about the actual storage technique, but is a
mapping of states to transitions and an associated value.  (Where
transitions again are a mapping of characters to states.)  It is a much
more top-level data structure than a hash and should better be compared
to lists, trees etc.

Let me put it this way:  In LuaTeX, the top-level data structure to
organize the patterns of a language is still a trie, with additional
data attached (fall-back transitions) that make the trie behave like a
finite state automaton.  Would that be wrong?

BTW, am I correctly assuming that the reason for switching from a packed
array data structure to a hash is that the former only works as long as
the keys (characters) are from a finite range.  Which is the case for a
7 or 8 bit character encoding.  But with Unicode characters this is
(practically) not the case?

Best regards,
Stephan Hennig

More information about the lualatex-dev mailing list