Implementation of various string similarity and distance algorithms: Levenshtein, Jaro-winkler, n-Gram, Q-Gram, Jaccard index, Longest Common Subsequence edit distance, cosine similarity. A library implementing different string similarity and distance measures. A dozen of algorithms (including Levenshtein edit distance and sibblings, Jaro-Winkler, Longest Common Subsequence, cosine similarity etc.) are currently implemented. The main characteristics of each implemented algorithm are presented below. The "cost" column gives an estimation of the computational cost to compute the similarity between two strings of length m and n respectively. If the alphabet is finite, it is possible to use the method of four russians (Arlazarov et al. "On economic construction of the transitive closure of a directed graph", 1970) to speedup computation. This was published by Masek in 1980 ("A Faster Algorithm Computing String Edit Distances").
Features
- A few algorithms work by converting strings into sets of n-grams
- The Levenshtein distance between two words is the minimum number of single-character edits
- This distance is computed as levenshtein distance divided by the length of the longest string
- Damerau-Levenshtein distance with transposition
- Optimal String Alignment variant of Damerau–Levenshtein
- Jaro-Winkler computes the similarity between 2 strings
Project Samples
