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
