I read post of the BK-tree referred by HN [1], and in the post, an interesting
algorithm called Levenshtein distance [2] is used. Levenshtein distance (LD) is
a measure of the similarity between two strings, the minimum number of
single-character edits (insertions, deletions or substitutions) required to
change one string into the other.
The recursive implementation of LD in Wikipedia is not very difficult, so I
port the code from C to Go as an exercise.
packageld// lenS and lenT are the number of characters in string s and t respectivelyfuncRecursive(s[]rune,lenSint,t[]rune,lenTint)int{varcostint// base case: empty stringsiflenS==0{returnlenT}iflenT==0{returnlenS}// test if last characters of the strings matchifs[lenS-1]==t[lenT-1]{cost=0}else{cost=1}// return minimum of delete char from s, delete char from t, and delete char from bothreturnminimum(Recursive(s,lenS-1,t,lenT)+1,Recursive(s,lenS,t,lenT-1)+1,Recursive(s,lenS-1,t,lenT-1)+cost,)}funcLevenshteinDistance(s,tstring)int{srs:=StringToRuneSlice(s)trs:=StringToRuneSlice(t)returnRecursive(srs,len(srs),trs,len(trs))}