Edit Distance Vocabulary

Edit distance is exactly this: edit distance is the minimum number of single-character insertions, deletions, and substitutions needed to transform one string into another, and its standard dynamic-programming solution builds up a table of the minimum cost for every pair of prefixes of the two strings. A hash collision is an unrelated hash-table concept about two keys sharing a bucket. This build-up-over-every-prefix-pair approach is exactly why edit distance can be computed in time proportional to the product of the two strings' lengths, instead of trying every possible sequence of edits.

Edit distance here provides Efficient fuzzy-matching by scoring exactly how many edits separate two strings, since the minimum edit cost for a given pair of prefixes only depends on minimum costs already computed for slightly shorter prefixes, so dynamic programming solves each distinct sub-problem once and reuses it, instead of trying every possible sequence of edits. Trying every possible sequence of insertions, deletions, and substitutions costs exponential time as the strings get longer. This reuse-of-overlapping-prefix-sub-problems behavior is exactly why edit distance underlies practical spell-checkers and typo-tolerant search features.

This is a missed edit-distance opportunity, since building up a table over every pair of prefixes, the way the edit-distance dynamic-programming solution does, would reuse overlapping sub-problems instead of trying every possible sequence of edits. A cache eviction policy is an unrelated concept about discarded cache entries. This brute-force-enumeration pattern is exactly the kind of avoidable exponential cost a reviewer flags once queries and terms are long enough for it to matter.

Rewriting the comparison logic using edit distance's dynamic-programming approach eliminates the exponential edit-sequence enumeration. Continuing to try every possible sequence of edits to compare a query and a stored term regardless of how long the queries and stored terms are is exactly what caused the issue described in this incident. This dynamic-programming approach is the standard fix once brute-force edit-sequence enumeration is shown to be the actual bottleneck.

Edit distance counts the minimum number of insertions, deletions, and substitutions needed to transform one string into another, which is exactly what a typo-tolerance score needs, while the longest common subsequence instead finds the longest shared, in-order sequence of characters, a related but different question better suited to highlighting unchanged content in a line-based diff. This is exactly why the two dynamic-programming techniques, despite similar tables, serve different practical purposes.