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

Property definitions

core $ Text :: levenshtein_distance
	# 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
lib/core/text/abstract_text.nit:1156,2--1213,4