zuloodreams.blogg.se

There are two variants of Damerau-Levenshtein string distance: Damerau-Levenshtein with adjacent transpositions (also sometimes called unrestricted Damerau–Levenshtein distance) and Optimal String Alignment (also sometimes called restricted edit distance). But the algorithm has a memory requirement O(m.n²) and was thus not implemented here. Larsen proposed an algorithm that computes the length of LCS in time O(log(m).log(n)). In "Length of Maximal Common Subsequences", K.S. This method has not been implemented (yet). The resulting computation cost is thus O(mn/log(m)). Usually, t is choosen as log(m) if m > n. This lookup table can then be used to compute the string similarity (or distance) in O(nm/t). Each possible block is precomputed to produce a lookup table. This method splits the matrix in blocks of size t x t. This was published by Masek in 1980 ("A Faster Algorithm Computing String Edit Distances"). "On economic construction of the transitive closure of a directed graph", 1970) to speedup computation. If the alphabet is finite, it is possible to use the method of four russians (Arlazarov et al. The original algorithm uses a matrix of size m x n to store the Levenshtein distance between string prefixes. For Levenshtein distance, the algorithm is sometimes called Wagner-Fischer algorithm ("The string-to-string correction problem", 1974). In this library, Levenshtein edit distance, LCS distance and their sibblings are computed using the dynamic programming method, which has a cost O(m.n). The "cost" column gives an estimation of the computational cost to compute the similarity between two strings of length m and n respectively. The main characteristics of each implemented algorithm are presented below.

This library requires Java 8 or more recent. Shingles (n-gram) based similarity and distance.Normalized, metric, similarity and distance.

Check the summary table below for the complete list. A dozen of algorithms (including Levenshtein edit distance and sibblings, Jaro-Winkler, Longest Common Subsequence, cosine similarity etc.) are currently implemented. A library implementing different string similarity and distance measures.