基于編輯距離來判斷詞語相似度方法（scala版）

詞語相似性比較，最容易想到的就是編輯距離，也叫做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
	1	2	3
l
o
	4

挨個計算值

某個位置的值，等于它

• 左邊的值+1，
• 右邊的值+1，
• 左上角的值不同時加1；相同時加0

上面三個數的最小值

一直計算到右下角的值

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來計算相似性的方法，比較适合這種場景。

作者：xingoo

出處：http://www.cnblogs.com/xing901022

本文版權歸作者和部落格園共有。歡迎轉載，但必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接！