Construction — where it appears
Named by 10 essays across 6 fields — each of them below, with the objects they name alongside it.
More hashes or wider buckets
A cuckoo table with two hash functions and one slot per bucket cannot be built past about half full. Give it a third hash function and it builds to 0.92. Keep two hashes and give each bucket two slots and it builds to 0.89; four slots, past 0.95. Every shape keeps the worst-case lookup the plain table was built for, and every shape pays for its threshold in a different place.
Where the exact rules pay now
With a construction as cheap as the published one, the exact shift rules pay for themselves past eight thousand characters of text at two patterns, four thousand at four, and never at thirty-two — because by thirty-two patterns the two rules make identical decisions.
A parse that will not follow a long chain
A greedy self-referential parse bounds the copy depth by nothing at all — thirty-two copies of a text give a position costing twenty-two phrase follows. Restricting every phrase to sources no deeper than D holds it at D, and the whole question is what that costs.
The case a failure link does not cover
Compute the exact good-suffix rule from the failure links alone and eighteen of twenty-two entries come out too large. The matcher then steps past sixty-six of two thousand and twenty-five occurrences, and every match it does report is a match.
The table the links already knew
The exact good-suffix rule costs 757,058 character comparisons to build from its definition at 128 patterns, and 3,824 from the trie's failure links. Same table, checked at every node — a factor of 198, and the definition was never the algorithm.
The cap an automaton cannot see
A state of a suffix automaton stands for a set of occurrences and hands back one of them. So a capped parse driven by it can ask whether the earliest occurrence is shallow enough and cannot ask whether any occurrence is — which costs up to 9.8% of the phrases, and only at the caps that bind.
The parse in one pass of the text
The same parse, phrase for phrase, from 1,324,336 character comparisons or from 25,420 transitions and suffix-link steps. One of those numbers grows with the text and the other grows with its square, and the difference is why every measurement about a depth cap here was taken on a few thousand characters.
A rectangle over a permutation
Two orderings of one set of boundaries are two permutations, so a phrase index's intersection is a rectangle over a permutation grid — the one point set a wavelet tree stores exactly, at one bit per point per level and no coordinates at all.
The ratio that was an implementation
This collection published a factor of forty-two between two shift rules' preprocessing. Sixty-nine per cent of the denominator was a table the published rule never reads, and the numerator was a definition rather than a construction. The corrected ratio is 1.6.
What a quadratic construction was setting
A depth cap of one costs 90% of an 8,192-character text in phrases, and 86% of a 65,536-character one. The ladder's conclusions hold at thirty-two times the size — and the number the ladder could not reach, the deepest chain a real collection produces, turns out to be fourteen.
Named alongside it
The objects these essays reach for when they reach for this one.
MeasurementTrade offCommentz-walterDefinitionPhraseShift ruleGood-suffix ruleLempel zivMulti patternParsePreprocessingRepetition