Overview
Jaro-Winkler distance is useful for short names or records where early-character agreement is especially meaningful.
ExtendedSource checked
Jaro-Winkler Distance
Scores string similarity with extra weight for shared prefixes.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pattern Matching
- Difficulty
- Intermediate
- Family
- String Similarity
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
matching windowtransposition countprefix booststring similarity
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n + m)
Average
O(n + m)
Worst
O(n m)
Space
O(n + m)
When to Use
- Use when text search needs matching window.
- Use when the input matches the assumptions behind string Similarity.
When Not to Use
- Avoid when a simpler exact search is enough and approximate scoring is unnecessary.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Scores string similarity with extra weight for shared prefixes
- Uses matching window and transposition count to guide the work.
- Produces matches.
Use Cases
- Text search
- Sequence comparison
- Similarity detection
Inputs
- Pattern or query sequence
- Text or target sequence
Outputs
- Matches
- Score
- Alignment or index
Key Formulas (1)
Jaro-Winkler score
jw = jaro + prefix · scale · (1 − jaro)
jw = jaro + prefix * scale * (1 - jaro)Boosts strings that share an early prefix.
Pseudocode
- 1.Prepare the inputs and state needed for Jaro-Winkler Distance.
- 2.Apply the matching window step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return matches.
Canonical Example
- Input
- Jaro-Winkler Distance input with a small representative case
- Output
- Matches
- Explanation
- Jaro-Winkler Distance applies matching window to produce matches.
Implementation Notes
- Normalize input consistently before building indexes or comparing sequences.
- Keep the matching window step separate enough to test independently.
Common Pitfalls
- Changing tokenization or distance definitions changes the match result.
- Forgetting to check edge cases can make Jaro-Winkler Distance look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow matched positions, dynamic-programming cells, or candidate buckets.
Input:ABABABCABAB
Window:ABAB
Step 1 of 4: Prepare the inputs and state needed for Jaro-Winkler Distance.
pattern-matching-mechanismNotes
Jaro-Winkler Distance should be used with the assumptions and tradeoffs of string Similarity in mind.
Sources (2)
What each reference supports for this entry.
Flexible Pattern Matching in Strings
BookPattern-matching reference covering Jaro-Winkler Distance approximate matching model, string similarity measure, or bit-parallel search strategy.
NIST DADS Jaro-Winkler
EncyclopediaNIST algorithm dictionary reference for Jaro-Winkler string similarity and prefix adjustment.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toLevenshtein Distance
Jaro-Winkler and Levenshtein distance are string similarity measures with different error models.
Related Algorithms
Tags
Pattern MatchingStringsSimilarityEdit Distance