3 ms·
"On lookup, compress the key and do a binary search" That binary search will be hampered a bit by the fact that your keys have variable length. So, you either
by Someone 11y ago
"On lookup, compress the key and do a binary search"
That binary search will be hampered a bit by the fact that your keys have variable length. So, you either need to use a separator and search for the word start in each iteration, or you have to pad your words to equal lengths.
Also, space-efficient designs will not chase pointers. The dawg will store relative offsets (20 bits will often be more than enough there) not pointers.
Also, i expect that a N-ary trie (with N=26 or even larger) will be more cache-friendly than a binary search because its depth is smaller by a factor 4 to 5.
I doubt this will beat a dawg, space-wise, either. The big advantage of a dawg is that it collapses the tails of words with similar variants into one. All those nouns ending in "tion", with plural "tions", and adverbial form "tional" will share their tail nodes.