[lltx] pattern loading in luatex
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?
More information about the lualatex-dev