Edit distance
Edit distance is the minimum number of permitted operations needed to transform one string or sequence into another, commonly counting insertions, deletions, and substitutions.
Natural Language Processing in Action, Second Edition
A string distance equal to the minimum number of single-character insertions, deletions, and substitutions needed to transform one string into another.
- How it is used
- Supports approximate character-level matching for chatbots and other NLP systems when exact string comparison is insufficient.
- How deep it goes
- Defines the metric and demonstrates brute-force retrieval, but does not develop its algorithmic internals or scaling behavior.
- Examples
- Uses ChatterBot's stored statement–response pairs and a brute-force comparison against the latest user statement.
- What you can do after
- Apply it via ChatterBot-style retrieval to select responses from statements with the smallest character-level distance.
Read how Natural Language Processing in Action, Second Edition explains edit distance →
Advanced Algorithms and Data Structures
Edit distance is the minimum number of character insertions, deletions, or substitutions needed to transform one string into another.
- How it is used
- Uses character-edit counts to rank spell-checker suggestions and compare a string against many dictionary or biological sequences.
- How deep it goes
- Explains the definition, trie row maintenance, threshold pruning, stored-key selection, and comparison complexity.
- Examples
- Uses the target “amt” to show row reuse, threshold search, unavailable intermediate keys, and tied stored suggestions.
- What you can do after
- Apply edit distance through trie traversal to find, rank, and prune approximate string matches.
Read how Advanced Algorithms and Data Structures explains edit distance →
Clojure: The Essential Reference
Levenshtein distance is a metric counting the minimum single-character insertions, deletions, or substitutions needed to transform one string into another.
- How it is used
- Supports spelling correction by ranking dictionary words according to their distance from user input.
- How deep it goes
- Defines the metric and demonstrates a recursive implementation with empty-string cases, then optimizes repeated calls through memoization.
- Examples
- Uses the misspelled word "achive" and dictionary candidates such as "achieve", "achime", and "active".
- What you can do after
- Apply it via a memoized Clojure function to rank likely spelling corrections efficiently.
Read how Clojure: The Essential Reference explains edit distance →
Elasticsearch in Action, Second Edition
The Levenshtein distance algorithm computes the minimum number of insertions, deletions, and substitutions needed to transform one string into another.
- How it is used
- Supports Elasticsearch searches that tolerate user spelling mistakes and retrieve similar-looking terms.
- How deep it goes
- Defines insertions, deletions, and substitutions, then applies distances through fuzzy queries without deriving the algorithm internally.
- Examples
- Uses “Komputer” versus “Computer,” “rama” versus “drama,” and “cake” versus similar words as spelling examples.
- What you can do after
- Apply it via Elasticsearch fuzzy, match, or query_string queries to retrieve results containing spelling variations.
Read how Elasticsearch in Action, Second Edition explains edit distance →
AI-Powered Search
Edit distance is a measure of the minimum number of character-level insertions, deletions, substitutions, or related edits needed to transform one string into another.
- How it is used
- Uses character differences to generate spelling corrections from search-query signals.
- How deep it goes
- Implements distance calculation and length-based thresholds, but does not develop the edit algorithm’s internal dynamic programming.
- Examples
- Demonstrates moden→modem, iphone3→iphone, latop→laptop, and multiterm query corrections.
- What you can do after
- Apply it via NLTK, pandas, and query-frequency data to produce candidate spelling corrections.
Build Financial Software with Generative AI (From Scratch)
Levenshtein distance is a string metric counting the minimum single-character insertions, deletions, and substitutions needed to transform one string into another.
- How it is used
- Supports fuzzy name screening for ACH transactions, account opening checks, and periodic financial-institution scans.
- How deep it goes
- Defines edit-based similarity and demonstrates normalized PostgreSQL scoring, while stopping short of explaining the algorithm’s internal dynamic programming.
- Examples
- Uses normalized PPD and IAT names, sanctions-list aliases, SQL similarity scores, and an 80-percent filtering threshold.
- What you can do after
- Apply it via PostgreSQL fuzzystrmatch to rank potentially misspelled or altered transaction names for screening review.
Read how Build Financial Software with Generative AI (From Scratch) explains edit distance →
Related concepts
- Damerau–Levenshtein distanceincludes · Damerau–Levenshtein distance is the minimum number of insertions, deletions, substitutions, and adjacent transpositions required to transform one string into another.
- ChatterBotused by · ChatterBot is an open-source Python chatbot project that generates replies from stored statement-response pairs.
- Elasticsearchused by · Elasticsearch is a distributed search and analytics engine that indexes data for searching, retrieval, and analysis.
- fuzzy queryused by · A fuzzy query is an Elasticsearch query that matches terms within a permitted edit distance of the supplied term.
- fuzzinessused by · Fuzziness is a search setting that controls the permitted edit distance between a query term and matching indexed terms.
- fuzzystrmatchused by · fuzzystrmatch is a PostgreSQL extension that provides string-similarity and phonetic-matching functions.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.