词语相似性比较，最容易想到的就是编辑距离，也叫做Levenshtein Distance算法。在Python中是有现成的模块可以帮助做这个的，不过代码也很简单，我这边就用scala实现了一版。
编辑距离
编辑距离是指一个字符串改编成另一个字符串的最短距离，它描述了两个字符串的相近程度。比如:
son -> sun ,只需要把o改成u即可，编辑距离为1
xing -> long,需要把x改成l，i改成o，编辑距离为2
o->long，需要在前面加上l，在后面加上ng，编辑距离为3
因此所有修改，移动，删除，新增都算是一次编辑操作。
算法很简单:
初始化
-
x
i
n
g
-
0
1
2
3
l
1
0
0
0
o
2
0
0
0
n
3
0
0
0
g
4
0
0
0
挨个计算值
某个位置的值，等于它
左边的值+1，
右边的值+1，
左上角的值不同时加1；相同时加0
上面三个数的最小值
-
x
i
n
g
-
0
1
2
3
l
1
1
0
0
o
2
0
0
0
n
3
0
0
0
g
4
0
0
0
一直计算到右下角的值
-
x
i
n
g
-
0
1
2
3
l
1
1
2
3
o
2
2
2
3
n
3
3
3
2
g
4
4
4
3
Breeze
在python中有numpy可以做矩阵的各种操作，在scala中可以使用breeze，spark mllib底层也是基于它实现的。
文档参考：
https://github.com/scalanlp/breeze/wiki/Quickstart
常用的操作有：
创建为0的的矩阵：
DenseMatrix.zeros[Int](s1_length, s2_length)
breeze另一个很好用的地方就是默认支持修改，在scala中很多集合默认都是不可变的，比如Array，很烦～
算法实现
def editDist(s1:String, s2:String):Int ={
val s1_length = s1.length+1
val s2_length = s2.length+1
val matrix = DenseMatrix.zeros[Int](s1_length, s2_length)
for(i <- 1.until(s1_length)){
matrix(i,0) = matrix(i-1, 0) + 1
}
for(j <- 1.until(s2_length)){
matrix(0,j) = matrix(0, j-1) + 1
}
var cost = 0
for(j <- 1.until(s2_length)){
for(i <- 1.until(s1_length)){
if(s1.charAt(i-1)==s2.charAt(j-1)){
cost = 0
}else{
cost = 1
}
matrix(i,j)=math.min(math.min(matrix(i-1,j)+1,matrix(i,j-1)+1),matrix(i-1,j-1)+cost)
}
}
matrix(s1_length-1,s2_length-1)
}
应用的场景
这种词语之间的编辑距离主要应用在两个文本判断是否相近，比如我输入一个词，想要查找到数据库里面跟他最匹配的词。比如阿迪想要匹配到阿迪达斯，或者结账买单匹配到节帐埋单等等。不过在耐克nike跟nike耐克这种场景下就不适合了...
后续会介绍n-gram来计算相似性的方法，比较适合这种场景。
发表评论