String search and fuzzy matching: what a query must return, and how quickly a person will notice

Unit nine showed that the input decides which sort is right. Every search box makes two promises at once: to return what the person meant, including when they mistyped, and to return it while they are still watching the screen. The first is a string-matching problem, the second a response-time problem.

The claim of this unit is that they are one decision. A search interface is judged by what its query returns and by whether the answer arrives inside the person's tolerance for waiting, a tolerance that belongs to the task rather than to a constant. Choosing which near misses the index ranks and how much work fits the budget is one choice made in two places.

Exact matching is cheap; the index is what costs

For exact search the algorithms are settled. Knuth, Morris and Pratt (1977) preprocess the pattern into a shift table so the text is scanned once, in time proportional to the sum of the two lengths. Boyer and Moore (1977) read the pattern from its last character and jump on the mismatching one, so a random English pattern of length five inspects about a quarter of the text before a match. Aho and Corasick (1975) generalise to many patterns: a finite-state machine built from a keyword dictionary processes the text in one pass, with a number of state transitions independent of the dictionary's size, and it ran a library search program five to ten times faster.

The cost that matters is the structure, not the scan. Ferragina and Manzini (2000) give an index whose space is a function of the text's entropy. It stores a text of U symbols in O(H_k(T)) + o(1) bits per symbol, and it reports the occ occurrences of a pattern in O(p + occ log^epsilon U) time. It improves on the suffix array and the suffix tree in space or in query time. So an exact index can be smaller than the text it indexes, and a keystroke can be answered from it.

Near misses need a measure of distance, and distance is expensive at scale

Levenshtein (1966) gave the measure that ranks the near miss, the smallest number of deletions and insertions turning one string into another, showed that it is a metric, and set it beside the reversals of the binary channel. It is the distance a suggestion list ranks by, and Navarro (2001) maps approximate matching, organising the algorithms by the error allowed and the data structures used. The slips it counts belong to a reader writing in a second language, not only to a hurried typist.

The map has a hard edge. Backurs and Indyk (2015) prove that computing edit distance in time O(n^2-delta) would solve satisfiability faster than the strong exponential time hypothesis permits. The near-quadratic cost of the classic dynamic-programming algorithm is therefore likely tight. That bounds one operation rather than fuzzy search, and it bounds the exact one. An interface that computed the exact distance against every document would inherit the quadratic cost, while one that narrows the corpus first does not. A second line has moved anyway. Bringmann, Cassis, Fischer and Kociumaka (2024) give an algorithm that decides in sublinear time whether the edit distance of two strings is at most k or more than about k^1+o(1), in O(n/k + k^2+o(1)) time. A near miss can therefore be detected without computing the exact distance, which is what a suggestion list needs.

Broder (1997) supplies the narrowing. He defines document resemblance and containment as set-intersection problems over shingles and evaluates them by sampling from a fixed-size sketch built with Rabin fingerprints, so similar documents are compared through small sketches. The pipeline is the one search engines use: a cheap sketch supplies candidates, and a distance function re-ranks the survivors.

Broder's own account shows how little is kept. A document is cut into overlapping shingles of a fixed number of words, and its resemblance to another is the number of shingles they share divided by the number of distinct shingles in either. Each document then keeps the smallest shingle under a random ordering rather than every shingle, so a sketch of about a hundred values estimates the resemblance without the two documents meeting. The Web-scale test clustered over 30 million documents gathered by the AltaVista crawler, about 150 gigabytes of text, and found 3.6 million clusters above a 50 per cent resemblance.

The index and the deadline are one decision, and the budget belongs to the task

Read together, the two halves are one budget. The index decides which queries avoid a full scan, and so how cheap the fastest answer to a keystroke is, while the tolerance for waiting decides how much ranking may be spent on it before the person notices. Choosing the entropy-bounded index and setting the response target are one point on one curve, and the link would be rhetorical if the target were fixed.

Miller (1968) refuses a single number. He records that the writing of his time "abounds in controversy about the limits of system response time", and he argues that the disagreement came partly from leaving the question imprecise. His answer is a classification of human purposes, each with its own acceptable delay: 0.1 seconds for a response bound to an immediate mechanical action, two seconds for a routine request, about five for an impromptu complex one, and beyond roughly fifteen seconds conversation fails. The useful question is response time for what.

What lag does to a person, measured

MacKenzie and Ware (1993) measure what a fixed lag costs. In a Fitts' law target-acquisition task with four lag conditions, the highest lag tested, 225 milliseconds, raised movement times by 64 per cent and error rates by 214 per cent against zero lag, and their model treats lag as multiplying the index of difficulty, so a lag costs more as the task gets harder.

Ng and colleagues (2012) measure the floor. Touch systems of the time took 50 to 200 milliseconds to update the display; with a demonstrator reaching about one millisecond, subjects greatly preferred the lower latencies and improvement was still noticeable below 10 milliseconds, so they propose immediate low-fidelity feedback followed by high-fidelity visuals. Doherty and Sorenson (2015) relate response time to flow, the state in which work proceeds without thought about the technology, and poor performance pulls the user out of it, so responsiveness becomes a property of the interaction.

Contested question: is the waiting tolerance a constant or a property of the task?

The literature divides on whether an acceptable delay is a universal threshold or a function of what the person is doing. On the constant side, Card, Moran and Newell (1983) reduce perception, cognition and motor action to cycle times near 100, 70 and 70 milliseconds, from which a task-independent target can be derived, and Ng and colleagues (2012) measure a perceptual floor, since improvement was still noticed below 10 milliseconds. Read this way, latency is a property of perception.

On the task side, Miller (1968) defines acceptable delays per class of action and warns that the older disagreement came from leaving the question imprecise. MacKenzie and Ware (1993) show the cost of lag multiplying a task's difficulty, so 225 milliseconds does more damage on a hard target. Doherty and Sorenson (2015) locate the effect in whether the person stays in flow. Read this way, a target quoted without a task is meaningless.

One experiment would settle the disagreement: vary task difficulty and lag together on one apparatus and record both performance and the latency at which the person reports the interface unusable. Each source holds one variable still: Ng and colleagues vary latency and device but keep the task, MacKenzie and Ware vary lag and difficulty but measure performance rather than acceptability, and Miller classifies tasks without experiment.

Weigh each side by its evidence. Card, Moran and Newell (1983) derive cycle times from earlier studies, an estimate with a wide range rather than a measurement. Ng and colleagues (2012) measure a perceptual floor, but on one apparatus and one task. Miller (1968) classifies tasks without experiment, and MacKenzie and Ware (1993) measure performance rather than acceptability. The strongest objection is that a task-derived budget is hard to know before the task is measured, so a fixed figure, however wrong, is more usable in a specification. While the dispute is open, a designer sets the budget from the task, treats any single figure as a starting point, and sets it for the slowest person reached, who may be in later life, not the fastest tested.

Where the argument is heading

Exact search is absorbed into compact indexes smaller than their texts (Ferragina and Manzini, 2000), and near misses are handled by sketching and re-ranking (Broder, 1997). The measurable floor keeps falling (Ng et al., 2012), and the target is being restated as experiential (Doherty and Sorenson, 2015).

The sources this unit rests on

• Aho, A. V. and Corasick, M. J. (1975). Efficient string matching: an aid to bibliographic search. Communications of the ACM. doi:10.1145/360825.360855 Aho and Corasick build a finite-state machine from a set of keywords so that all occurrences of all keywords are found in one pass over the text, with the number of state transitions independent of the dictionary size. It makes a suggestion dictionary affordable.
• Backurs, A. and Indyk, P. (2015). Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). Proceedings of the forty-seventh annual ACM symposium on Theory of Computing. doi:10.1145/2746539.2746612 Backurs and Indyk prove that computing edit distance in strongly subquadratic time would solve satisfiability faster than the strong exponential time hypothesis permits, so the near-quadratic dynamic-programming cost is likely tight. It bounds one operation, not the whole search.
• Boyer, R. S. and Moore, J. S. (1977). A fast string searching algorithm. Communications of the ACM. doi:10.1145/359842.359859 Boyer and Moore compare the pattern with the text from the pattern's last character and skip on the mismatching one, so a random English pattern of length five inspects about a quarter of the text. It is the cheap exact first pass.
• Bringmann, K., Cassis, A., Fischer, N. and Kociumaka, T. (2024). Faster Sublinear-Time Edit Distance. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). doi:10.1137/1.9781611977912.117 Bringmann, Cassis, Fischer and Kociumaka give a sublinear-time algorithm for the gap edit distance problem, quadratically faster than the previous bound and almost optimal for k up to n^1/3. It decides an approximate distance without computing the exact one.
• Broder, A. Z. (1997). On the resemblance and containment of documents. Proceedings of Compression and Complexity of Sequences. doi:10.1109/sequen.1997.666900 Broder defines resemblance and containment as set-intersection problems over shingles and evaluates them by sampling from a fixed-size sketch built with Rabin fingerprints. The Web-scale test clustered 30 million documents into 3.6 million clusters above 50 per cent resemblance.
• Card, S. K., Moran, T. P. and Newell, A. (1983). The Psychology of Human-Computer Interaction. Lawrence Erlbaum (reprinted by CRC Press). doi:10.1201/9780203736166 Card, Moran and Newell derive the model human processor from the psychological literature, with perceptual, cognitive and motor cycle times of about 100, 70 and 70 milliseconds, giving about 240 milliseconds for a simple action. The constants are estimates.
• Doherty, R. A. and Sorenson, P. (2015). Keeping Users in the Flow: Mapping System Responsiveness with User Experience. Procedia Manufacturing. doi:10.1016/j.promfg.2015.07.436 Doherty and Sorenson relate response time to flow, the state in which work proceeds without thought about the technology, and argue that poor performance pulls the user out of it. It makes responsiveness a property of the interaction.
• Ferragina, P. and Manzini, G. (2000). Opportunistic data structures with applications. IEEE Symposium on Foundations of Computer Science (FOCS). doi:10.1109/sfcs.2000.892127 Ferragina and Manzini give an index whose space is a function of the text's entropy, storing a text in O(H_k(T)) plus o(1) bits per symbol and reporting the occurrences of a pattern in O(p + occ log^epsilon U) time. It improves on the suffix array and the suffix tree.
• Knuth, D. E., Morris, Jr., J. H. and Pratt, V. R. (1977). Fast Pattern Matching in Strings. SIAM Journal on Computing. doi:10.1137/0206024 Knuth, Morris and Pratt preprocess the pattern into a shift table so the text is scanned once, with running time proportional to the sum of the two lengths and a constant low enough for practical use, while noting that other methods are faster on average.
• Levenshtein, V. I. (1966). Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady. https://nymity.ch/sybilhunting/pdf/Levenshtein1966a.pdf Levenshtein defines the smallest number of deletions, insertions and substitutions turning one string into another, shows it is a metric, and uses it to bound error-correcting codes. It is the measure a suggestion list ranks by.
• MacKenzie, I. S. and Ware, C. (1993). Lag as a determinant of human performance in interactive systems. Proceedings of the SIGCHI conference on Human factors in computing systems - CHI '93. doi:10.1145/169059.169431 MacKenzie and Ware measured target acquisition under four lag conditions and found that at 225 milliseconds movement times rose 64 per cent and error rates 214 per cent against zero lag. It makes lag a measured design constraint.
• Miller, R. B. (1968). Response time in man-computer conversational transactions. Proceedings of the December 9-11, 1968, fall joint computer conference, part I on - AFIPS '68 (Fall, part I). doi:10.1145/1476589.1476628 Miller records that the literature of his time abounds in controversy about the limits of system response time, and argues the disagreement came partly from leaving the question imprecise, then lists acceptable delays per class of action. It is a classification without experiment.
• Navarro, G. (2001). A guided tour to approximate string matching. ACM Computing Surveys. doi:10.1145/375360.375365 Navarro surveys approximate string matching, organising the algorithms by the error allowed and by the data structures used, focusing on online searching and mostly on edit distance. It places distance-based and index-based matching in one account.
• Ng, A., Lepinski, J., Wigdor, D., Sanders, S. and Dietz, P. (2012). Designing for low-latency direct-touch input. Proceedings of the 25th annual ACM symposium on User interface software and technology. doi:10.1145/2380116.2380174 Ng, Lepinski, Wigdor, Sanders and Dietz note that touch systems of the time took 50 to 200 milliseconds to update the display, build a demonstrator reaching about one millisecond, and find subjects preferred the lower latencies below 10 milliseconds. It is a user study.