News for hackers. Stuff that matters.
Re:Mapping Strings in C++ by rocqua on Wednesday April 12, 2017 @06:42PM (#14102410)
Suffix tries are an even better example. Donald Knuth once heralded them as the greatest algorithmic break-through of the '70s but in practice, it doesn't quite perform.

The point of suffix tries is finding substrings. I.e. build a suffix trie of all of Shakespear's works in linear time and memory (linear w.r.t. the total length of the string). And then, given a potential quote of length K, see if it is in Shakespear's work in O(K) time. The big draw there is that the complexity of string lookups does not depend on the length of the big text against which you are matching. This finds practical use in genome sequencing.

Re:Mapping Strings in C++ by danieldk on Thursday April 13, 2017 @04:32AM (#14105173)
Suffix arrays, on the other hand, have worse complexity in the typical implementation (O(n) construction, O(k + log(n)) search [1]). However, they work extremely well in practice, because they use (contiguous) arrays.

[1] Though there is an O(k) search approach too: http://www.sciencedirect.com/science/article/pii/S1570866703...

Re:Mapping Strings in C++ by rocqua on Friday April 14, 2017 @10:35AM (#14114672)
If I recall correctly, the linear search approach is based on constant time range minimal query on the suffix array. That feels rather likely to also be worse in real life applications.

Heck, as far as I can tell, this approach is just another way of storing a tree.

Re:Mapping Strings in C++ by jnordwick on Wednesday April 12, 2017 @10:51PM (#14103750)
Or Fibonacci trees. I have seen suffix tries used in the wild. I have yet to see a Fib tree. Shown to be optimal in a number of tree operations, horribly slow in practice..