Concept

Shared prefix — where it appears

The leading characters two or more strings have in common. A dynamic program over a string depends on its input only through the prefix consumed so far, so work done for a shared prefix is work that serves every string carrying it — which is what a trie makes structural.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

The comparison that is not one comparison

Sorting 512 keys costs 3,955 comparisons whatever the keys are, and between 7,849 and 134,409 character examinations depending only on how much those keys have in common. The first number is the one every bound so far is stated in. The second is the one the machine pays, it grows without limit, and nothing here has ever counted it.

text · Symbol

The columns the candidates share

Three thousand tables against one query, and most of them begin the same way. Stored as a trie, the 2,424-word vocabulary has 7,710 distinct prefixes holding 17,239 letters, and a search that computes one column per prefix reads 61,449 cells against 156,714 — before it applies any bound at all. Apply the bound at a prefix instead of at a word and it reads 16,958, beating a list search that was told the answer in advance.

tables · Table

Named alongside it

The objects these essays reach for when they reach for this one.

Character comparison Comparison sort Corpus Cost model Distinguishing prefix Dynamic programming Edit distance Evaluation order Lower bound Measured count Merge sort Output-sensitive

All concepts