From: Jean Privat <jean@pryen.org>
Date: Fri, 18 Dec 2015 17:44:50 +0000 (-0500)
Subject: core: add Text::levenshtein_distance
X-Git-Tag: v0.8~23^2
X-Git-Url: http://nitlanguage.org

core: add Text::levenshtein_distance

Signed-off-by: Jean Privat <jean@pryen.org>
---

diff --git a/lib/core/text/abstract_text.nit b/lib/core/text/abstract_text.nit
index cacee99..d4873ad 100644
--- a/lib/core/text/abstract_text.nit
+++ b/lib/core/text/abstract_text.nit
@@ -974,6 +974,65 @@ abstract class Text
 		return s.plain_to_s
 	end
 
+	# Return the Levenshtein distance between two strings
+	#
+	# ~~~
+	# assert "abcd".levenshtein_distance("abcd") == 0
+	# assert "".levenshtein_distance("abcd")     == 4
+	# assert "abcd".levenshtein_distance("")     == 4
+	# assert "abcd".levenshtein_distance("xyz")  == 4
+	# assert "abcd".levenshtein_distance("xbdy") == 3
+	# ~~~
+	fun levenshtein_distance(other: String): Int
+	do
+		var slen = self.length
+		var olen = other.length
+
+		# fast cases
+		if slen == 0 then return olen
+		if olen == 0 then return slen
+		if self == other then return 0
+
+		# previous row of distances
+		var v0 = new Array[Int].with_capacity(olen+1)
+
+		# current row of distances
+		var v1 = new Array[Int].with_capacity(olen+1)
+
+		for j in [0..olen] do
+			# prefix insert cost
+			v0[j] = j
+		end
+
+		for i in [0..slen[ do
+
+			# prefix delete cost
+			v1[0] = i + 1
+
+			for j in [0..olen[ do
+				# delete cost
+				var cost1 = v1[j] + 1
+				# insert cost
+				var cost2 = v0[j + 1] + 1
+				# same char cost (+0)
+				var cost3 = v0[j]
+				# change cost
+				if self[i] != other[j] then cost3 += 1
+				# keep the min
+				v1[j+1] = cost1.min(cost2).min(cost3)
+			end
+
+			# Switch columns:
+			# * v1 become v0 in the next iteration
+			# * old v0 is reused as the new v1
+			var tmp = v1
+			v1 = v0
+			v0 = tmp
+		end
+
+		return v0[olen]
+	end
+
 	# Copies `n` bytes from `self` at `src_offset` into `dest` starting at `dest_offset`
 	#
 	# Basically a high-level synonym of NativeString::copy_to