It's 1000x compared to a very naive baseline, exhaustive traversal of the matching subtree. Nobody in practice would do that, storing the maximum score for each subtree so you can prune is a very common technique, definitely not novel here.
Even doing a Levenshtein-bounded beam search along the trie is pretty much common practice, see for example this paper [1] from 2011.
There are more sophisticated ways of doing this in space-efficient ways, for example this paper [2] I co-authored in 2013.
Even doing a Levenshtein-bounded beam search along the trie is pretty much common practice, see for example this paper [1] from 2011.
There are more sophisticated ways of doing this in space-efficient ways, for example this paper [2] I co-authored in 2013.
[1] https://www.microsoft.com/en-us/research/wp-content/uploads/...
[2] https://www.microsoft.com/en-us/research/wp-content/uploads/...