Compare text similarity using the Levenshtein distance Sample Clauses

Compare text similarity using the Levenshtein distance. The Levenshtein distance [12] is a string metric for measuring the amount of difference between two character sequences. This can be used to compare text in RSS format with full text in HTML in order to perform approximate string matching and define the element location and attributed of the corresponding RSS element and full text from the HTML. Computing the Levenshtein distance is based on the observation that if we reserve a matrix to hold the Levenshtein distances between all prefixes of the first string and all prefixes of the second, then we can compute the values in the matrix by flood filling the matrix, and thus find the distance between the two full strings as the last value computed. This algorithm, an example of bottom-up dynamic programming, is discussed, with variants, in the 1974 article by Xxxxxx and Xxxxxxx [13]. A straightforward implementation, as pseudo code for a function LevenshteinDistance (Table 5) that takes two strings, s of length m, and t of length n, and returns the Levenshtein distance between them is listed below: Table 5 – Pseudocode for the Xxxxxxxxxx distance algorithm. int LevenshteinDistance(char s[1..m], char t[1..n]) { // for all i and j, d[i,j] will hold the Levenshtein distance between // the first i characters of s and the first j characters of t; // note that d has (m+1)x(n+1) values declare int d[0..m, 0..n] for i from 0 to m // the distance of any first string to an empty second string d[i, 0] := i for j from 0 to n // the distance of any second string to an empty first string d[0, j] := j for j from 1 to n { for i from 1 to m { if s[i] = t[j] then d[i, j] := d[i-1, j-1] else d[i, j] := minimum // no operation required ( d[i-1, j] + 1, // a deletion d[i, j-1] + 1, // an insertion d[i-1, j-1] + 1 // a substitution ) } } return d[m,n]