Levenshtein distance: what changed

Revision 0 to 1. Removed lines have a minus sign; added lines have a plus sign.

Title: Levenshtein distance

New		Line
1	+	The Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertion, deletion, substitution) required to change one word into the other.
2	+
3	+	This works on both [[ASCII]] and [[UTF-8]] encoding. This implementations use two-dimensional [[Dynamic array\|dynamic array]] to store the distances of prefixes of the words compared.
4	+
5	+	``` pascal
6	+
7	+	uses
8	+	Classes, SysUtils, Math, LazUTF8;
9	+
10	+	function LevenshteinDistance(const s1 : string; s2 : string) : integer;
11	+	function LevenshteinDistanceText(const s1, s2: string): Integer;
12	+
13	+	implementation
14	+
15	+	{------------------------------------------------------------------------------
16	+	Name: LevenshteinDistance
17	+	Params: s1, s2 - UTF8 encoded strings
18	+	Returns: Minimum number of single-character edits.
19	+	Compare 2 UTF8 encoded strings, case sensitive.
20	+	------------------------------------------------------------------------------}
21	+
22	+	function LevenshteinDistance(const s1 : string; s2 : string) : integer;
23	+	var
24	+	length1, length2, i, j ,
25	+	value1, value2, value3 : integer;
26	+	matrix : array of array of integer;
27	+	begin
28	+	length1 := UTF8Length( s1 );
29	+	length2 := UTF8Length( s2 );
30	+	SetLength (matrix, length1 + 1, length2 + 1);
31	+	for i := 0 to length1 do matrix [i, 0] := i;
32	+	for j := 0 to length2 do matrix [0, j] := j;
33	+	for i := 1 to length1 do
34	+	for j := 1 to length2 do
35	+	begin
36	+	if UTF8Copy( s1, i, 1) = UTF8Copy( s2, j, 1 )
37	+	then matrix[i,j] := matrix[i-1,j-1]
38	+	else begin
39	+	value1 := matrix [i-1, j] + 1;
40	+	value2 := matrix [i, j-1] + 1;
41	+	value3 := matrix[i-1, j-1] + 1;
42	+	matrix [i, j] := min( value1, min( value2, value3 ));
43	+	end;
44	+	end;
45	+	result := matrix [length1, length2];
46	+	end;
47	+
48	+	{------------------------------------------------------------------------------
49	+	Name: LevenshteinDistanceText
50	+	Params: s1, s2 - UTF8 encoded strings
51	+	Returns: Minimum number of single-character edits.
52	+	Compare 2 UTF8 encoded strings, case insensitive.
53	+	------------------------------------------------------------------------------}
54	+	function LevenshteinDistanceText(const s1, s2: string): integer;
55	+	var
56	+	s1lower, s2lower: string;
57	+	begin
58	+	s1lower := UTF8LowerCase( s1 );
59	+	s2lower := UTF8LowerCase( s2 );
60	+	result := LevenshteinDistance( s1lower, s2lower );
61	+	end;
62	+
63	+	end.
64	+	```
65	+
66	+	---
67	+	From the Free Pascal wiki, page "Levenshtein distance", as it stood on 2020-06-14 after a change by Wp, out of the wiki's dump of 2024-05-26. Copyright stays with the author who wrote it, according to the old wiki's [[Licensing]] page. If you have concerns about this material, [message the admin](/wiki-contact).

Back to history