levenshtein’s distance implementation in python and javascript, with very detailed comments in the python version (in french)

levenshtein.js

function levenshtein(w1, w2, costs) {
	var line_i = [];
	if (costs === undefined) costs = [1,1,1]; //Cost of addition, deletion, replacement
	for(var k=0; k<=w1.length; k++) line_i.push(k);
	for (var i=1; i<=w2.length; i++) {
		var prev_line = line_i;
		var line_i = [i];
		for (var k=1; k<=w1.length; k++) {
			cost = (w1[k-1] == w2[i-1]) ? 0 : costs[2];
			line_i[k] = Math.min(line_i[k-1]+costs[0], prev_line[k]+costs[1], prev_line[k-1]+cost);
		}
	}
	return line_i[w1.length];
}

levenshtein.py

#Ophir LOJKINE
#coding: utf8
def levenshtein(mot1,mot2):
	# ligne_i est un tableau tel que tout au long de l'algorithme,
	# ligne_i[k] contienne la distance de levenshtein entre les k premières lettres de mot1
	# et les i premières lettres de mot2
	# Au début, i=0, et la distance entre les k premières lettres de mot1 et la chaîne vide
	# vaut bien sûr k. (il faut faire k suppressions pour passer des k premières lettres de mot1
	# à la chaîne vide)
	ligne_i = [ k for k in range(len(mot1)+1) ]
	# i va ensuite varier de 1 à len(mot2)
	for i in range(1, len(mot2) + 1):
		# i vient d'être incrémenté. On stocke dans ligne_prec la valeur de la ligne numéro i-1
		ligne_prec = ligne_i
		# On crée la nouvelle ligne, dont le premier élément (l'élement numéro 0) doit être
		# la distance de levenshtein entre la chaîne vide ("") et les i premières lettres de mot2, soit i
		# (il faut faire i additions pour passer de la chaîne vide aux i premières lettres de mot2)
		ligne_i = [i]*(len(mot1)+1)
		# On va ensuite remplir le reste de la ligne i, c'est-à-dire calculer ligne_i[k] pour k allant de 1 à len(mot1)
		for k in range(1,len(ligne_i)):
			# La variable cout vaut 0 si la kième lettre de mot1 est la même que la ième lettre de mot2, et 1 sinon
			#La kième lettre de mot1 s'obtient avec mot1[k-1], les indices commencent à 0
			cout = int(mot1[k-1] != mot2[i-1])
			#Voilà enfin le sel de l'algorithme, le calcul de ligne_i[k] pour i et k quelconques,
			# connaissant ligne_prec[k-1], ligne_prec[k] et ligne_i[k-1]
			ligne_i[k] = min(ligne_i[k-1] + 1, ligne_prec[k] + 1, ligne_prec[k-1] + cout)
	# Lorsque l'on sort de la boucle, i vaut len(mot2)
	#Ce que l'on cherche est la distance de levenshtein entre les len(mot1) premières lettres de mot1
	# et les len(mot2) premières lettres de mot2, qui est stockée dans ligne_i[len(mot1)]
	return ligne_i[len(mot1)]
print (levenshtein("chiens", "niche"))

Salut, merci pour le code, juste deux corrections je crois pour le code en js

function levenshtein(w1, w2, costs) {
var line_i = [];
if (costs === undefined) costs = [1,1,1]; //Cost of addition, deletion, replacement
for(var k=0; k<=w1.length; k++) line_i.push(k);
for (var i=1; i<=w2.length; i++) {
var prev_line = line_i;
var line_i = [i]; <---------- line est déjà déclaré donc pas de var
for (var k=1; k<=w1.length; k++) {
cost = (w1[k-1] == w2[i-1]) ? 0 : costs[2]; <---------- cost jamais déclaré du coup un var ou const ou let
line_i[k] = Math.min(line_i[k-1]+costs[0], prev_line[k]+costs[1], prev_line[k-1]+cost);
}
}
return line_i[w1.length];
}