5 ms·

Doesn't using a map to implement a trie defeat the purpose? I mean, would such an implementation make sense in some situation?

bhaavan 7y ago
Yes, it will, because map has O(1) GET operations, and that's all the trie needs. In terms of space complexity, it does consume more space than a single element / node tree, (especially for maps with super low load factor) but trie data structure can accommodate all that extra space easily.
stabbles 7y ago
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.
panda88888 7y ago
Do you mean using an array instead of map for storing pointer to the next node? Conceptually, an array is just a map that uses an integer and identity function and the hashing function. In practice, the map implementation trades speed for space efficiency. For an array implementation, the entire array of pointers has to be allocated for all possible character set for each node. This leads to wasted space since trie nodes usually only have child pointers for a subset of character sets. Map implementation don’t have to allocate space to store pointers for the entire character set, so it can be more space efficient. However, the hash function is probably an order of magnitude more cycle than that for array (usually just the ascii code with offset and some bound checking).
- stabbles 7y ago
  Well, an unordered_map / hash map is in the end backed by a dynamically sized array, so "Map implementation don’t have to allocate space to store pointers for the entire character set" might not be true for two reasons: (1) there _is_ an additional allocation* that is not present in the std::array case for the dynamic array and (2) there is a default size of this unordered_map when nothing has been inserted yet, are you sure it's smaller than 256 elements? * Well, maybe there is something like small vector optimization going on for small unordered_maps, though.
  - panda88888 7y ago
    Agreed. For the standard implementation, the dynamically allocated array may be bigger than 256. I would imagine, since it’s C++, it’s probably possible to set the initial array size.
saagarjha 7y ago
I have shipped a trie into production that used std::unordered_map to store children and it performed quite well.
- xorz57 7y ago
  That's great!

bhaavan 7y ago

Yes, it will, because map has O(1) GET operations, and that's all the trie needs. In terms of space complexity, it does consume more space than a single element / node tree, (especially for maps with super low load factor) but trie data structure can accommodate all that extra space easily.

stabbles 7y ago

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.

panda88888 7y ago

Do you mean using an array instead of map for storing pointer to the next node? Conceptually, an array is just a map that uses an integer and identity function and the hashing function. In practice, the map implementation trades speed for space efficiency. For an array implementation, the entire array of pointers has to be allocated for all possible character set for each node. This leads to wasted space since trie nodes usually only have child pointers for a subset of character sets. Map implementation don’t have to allocate space to store pointers for the entire character set, so it can be more space efficient. However, the hash function is probably an order of magnitude more cycle than that for array (usually just the ascii code with offset and some bound checking).

stabbles 7y ago
Well, an unordered_map / hash map is in the end backed by a dynamically sized array, so "Map implementation don’t have to allocate space to store pointers for the entire character set" might not be true for two reasons: (1) there _is_ an additional allocation* that is not present in the std::array case for the dynamic array and (2) there is a default size of this unordered_map when nothing has been inserted yet, are you sure it's smaller than 256 elements? * Well, maybe there is something like small vector optimization going on for small unordered_maps, though.
- panda88888 7y ago
  Agreed. For the standard implementation, the dynamically allocated array may be bigger than 256. I would imagine, since it’s C++, it’s probably possible to set the initial array size.

saagarjha 7y ago

I have shipped a trie into production that used std::unordered_map to store children and it performed quite well.

xorz57 7y ago
That's great!