解決問題 Python (3)

教學目標

主要解決如何判斷兩個字串差別程度,以利針對傳送文字內容適當回答的問題。

重點概念

首先當我們在開發聊天機器人時,要如何了解使用者傳送文字內容中的關鍵資訊呢?這時我們就能夠透過編輯距離計算兩個字串差別的程度,就能夠初步了解使用者傳送文字內容中的關鍵資訊,同時回答正確的關鍵資訊。

接著所謂編輯距離,又稱萊文斯坦距離,在 1965 年由俄羅斯科學家弗拉基米爾·萊文斯坦提出此概念,概念主要是指兩個字串之間,由第一個字串轉換成第二個字串所需的最小編輯操作次數,其中編輯過程包括下述三種操作,分別為:

  1. 替換字元
  2. 插入字元
  3. 刪除字元

在 Python 中有提供「Python-Levenshtein」套件能夠讓我們方便計算編輯距離,所以我們必須先安裝套件。

安裝套件

1
$ sudo pip install python-Levenshtein

再來我們就能夠透過「Python-Levenshtein」套件計算編輯距離,我們假設的應用情境為有個關鍵字為「安裝步驟」,然後我們有三個使用者傳送文字內容,此時我們想要判斷與關鍵字的差異,主要可以使用 distance(字串一, 字串二) 函式計算萊文其坦距離和 Levenshtein.ratio(字串一, 字串二) 函式計算萊文斯坦比。

萊文斯坦距離

計算萊文斯坦距離主要是由第一個字串轉換成第二個字串所需的最小編輯操作次數,其中編輯過程包括下述三種操作,其演算法實作是以動態規劃為主。

萊文斯坦比

計算萊文斯坦比公式為 r = (sum - ldist) / sum,其中 sum 為字串一和字串二的長度總和,ldist 是萊文斯坦距離,但請注意此時萊文斯坦距離中刪除字元為加一計算和替換字元為加二計算。

程式範例

levenshtein_distance.py

1
2
3
4
5
6
7
8
9
10
11
12
#coding:utf-8
import Levenshtein
keyword = '安裝步驟'
message1 = '我想了解安裝的步驟'
message2 = '請問安裝到底有哪些步驟呢?'
message3 = '我想請問安裝到底有哪些產品呢?'
print 'message1 (distance): ' , Levenshtein.distance(keyword,message1)
print 'message2 (distance): ' , Levenshtein.distance(keyword,message2)
print 'message3 (distance): ' , Levenshtein.distance(keyword,message3)
print 'message1 (ratio): ' , Levenshtein.ratio(keyword,message1)
print 'message2 (ratio): ' , Levenshtein.ratio(keyword,message2)
print 'message3 (ratio): ' , Levenshtein.ratio(keyword,message3)

執行結果

1
2
3
4
5
6
7
$ python levenshtein_distance.py
message1 (distance): 10
message2 (distance): 17
message3 (distance): 24
message1 (ratio): 0.615384615385
message2 (ratio): 0.484848484848
message3 (ratio): 0.27027027027

最後我們根據上述程式範例,我們很難設定萊文斯坦距離的門檻值判斷使用者傳送文字內容是否與關鍵字非常相似,此我們就能夠透過設定萊文斯坦比的門檻值判斷使用者傳送文字內容是否與關鍵字非常相似,例如設定門檻值為 0.4 時,就能夠透過萊文斯坦距比判斷出「我想了解安裝的步驟」和「請問安裝到底有哪些步驟呢?」和關鍵字「安裝步驟」非常相似,此時就能夠回傳關鍵字「安裝步驟」所對應的回答內容。但是請注意當文字內容過長時僅透過萊文斯坦距比判斷門檻值將不適用,需要搭配其它方式提高準確度。

總結我們透過在 Python 中提供的「Python-Levenshtein」套件解決如何判斷兩個字串差別程度,以利針對傳送文字內容適當回答的問題,同時初步應用於聊天機器人的問答應用中。

相關資源