Feature request #1828: Think about alternative data structures for greater speed

Right now performance is ok, except for some pathological degenerate cases.

Think about ways of speeding things up, most space-for-time tradeoffs or up-front-time-for-later-time tradeoffs.

Ideas I've been thinking about: whether trees, tries or sets/hashes could help me speed up some checks.

At the extreme end of the spectrum, we have a trie structure which basically pre-calculates the scores for pretty much all possible query strings up front. Evidently impractical, but the ultimate example of trading up-front set-up cost for run-time speed.

As a compromise position, perhaps there is a space-for-time trade-off that can be made here, where we populate such a trie at run-time. Basically, the first time we scan the tree we store the intermediate results, so that the second time we scan the tree we only have to calculate results we haven't considered yet.

Not sure whether this would be practical for very large trees (space costs may be prohibitive), or sufficiently performant to warrant the additional complexity.