3 ms·

What is the best alternative still supporting UTF8? Yeah, sure, if you only support ASCII input you could use std::array<std::unique_ptr<Node>, 128>. Edit: wel

What is the best alternative still supporting UTF8? Yeah, sure, if you only support ASCII input you could use std::array<std::unique_ptr<Node>, 128>. Edit: well, of course you could break up the UTF8 string in bytes and stick with a `std::array<std::unique_ptr<Node>,256>` structure. Is this how people do it (supposing normalizing the string is not an option)?.

burntsushi 7y ago
> well, of course you could break up the UTF8 string in bytes and stick with a `std::array<std::unique_ptr<Node>,256>` structure. Is this how people do it (supposing normalizing the string is not an option)? There are lots of options, but to a first approximation, yes, that's standard. The key is to think of a trie as a special case of a finite state machine: 1. Your transition table should be a single contiguous block of memory. Namely, going from state s1 for byte b should be something like `trans[s1 * 256 + b]`. This reduces the amount of pointer chasing at search time. 2. With a small runtime cost (typically imperceptible for a large enough FSM), you can map your 256-sized alphabet down to a set of equivalence classes. e.g., Only to a set of bytes that discriminate a match. So your transition lookup becomes `trans[si * num_equiv_classes + equiv_class(b)]`. Although, this is harder to pull off if your trie supports mutation. 3. Instead of storing state identifiers in your transition table, you can store premultiplied state identifiers, which avoids the additional stride calculation at search time. So your transition lookup then becomes `trans[si + equiv_class(b)]`. Those all mostly apply to dense representations. But if memory is more important, then you can use a sparse representation. In a sparse representation, the size of each state is variable, which means moving to the next transition is more costly. But it uses much less space.

burntsushi 7y ago

> well, of course you could break up the UTF8 string in bytes and stick with a `std::array<std::unique_ptr<Node>,256>` structure. Is this how people do it (supposing normalizing the string is not an option)? There are lots of options, but to a first approximation, yes, that's standard. The key is to think of a trie as a special case of a finite state machine: 1. Your transition table should be a single contiguous block of memory. Namely, going from state s1 for byte b should be something like `trans[s1 * 256 + b]`. This reduces the amount of pointer chasing at search time. 2. With a small runtime cost (typically imperceptible for a large enough FSM), you can map your 256-sized alphabet down to a set of equivalence classes. e.g., Only to a set of bytes that discriminate a match. So your transition lookup becomes `trans[si * num_equiv_classes + equiv_class(b)]`. Although, this is harder to pull off if your trie supports mutation. 3. Instead of storing state identifiers in your transition table, you can store premultiplied state identifiers, which avoids the additional stride calculation at search time. So your transition lookup then becomes `trans[si + equiv_class(b)]`. Those all mostly apply to dense representations. But if memory is more important, then you can use a sparse representation. In a sparse representation, the size of each state is variable, which means moving to the next transition is more costly. But it uses much less space.