在酒店名稱輸入時實施建議

Question

我正在開發酒店預訂系統。我的任務是實現一個算法，當酒店的名稱輸入錯誤時，它會給出正確的建議。例如，如果用戶輸入酒店名稱爲「MOFENBICK」而不是真名「MOVENPICK」，那麼我的算法應該顯示「您的意思是MOVENPICK」。我計劃使用機器學習理念來實現它。這個問題有什麼好的功能選擇？

Answer 1

你不需要去執行一個神經網絡。這對於這個特殊的任務來說太過分了。

建議使用Levenshtein距離。 Levenshtein距離背後的想法是它定義了一個字符串度量。簡單來說，它允許計算機算法說「mofenbick」和「movenpick」在距離2（因爲2個字母被改變）。

一些僞代碼來計算Levennshtein：

function LevenshteinDistance(char s[1..m], char t[1..n]): 

    // create two work vectors of integer distances 
    declare int v0[n + 1] 
    declare int v1[n + 1] 

    // initialize v0 (the previous row of distances) 
    // this row is A[0][i]: edit distance for an empty s 
    // the distance is just the number of characters to delete from t 
    for i from 0 to n: 
     v0[i] = i 

    for i from 0 to m-1: 
     // calculate v1 (current row distances) from the previous row v0 

     // first element of v1 is A[i+1][0] 
     // edit distance is delete (i+1) chars from s to match empty t 
     v1[0] = i + 1 

     // use formula to fill in the rest of the row 
     for j from 0 to n-1: 
      if s[i] = t[j]: 
       substitutionCost := 0 
      else: 
       substitutionCost := 1 
      v1[j + 1] := minimum(v1[j] + 1, v0[j + 1] + 1, v0[j] + substitutionCost) 

     // copy v1 (current row) to v0 (previous row) for next iteration 
     swap v0 with v1 

    // after the last swap, the results of v1 are now in v0 
    return v0[n] 

一旦你有超過字符串定義的指標，你需要一個快速的方法來查詢課程的酒店名單。 天真的實施將 1.疊代數據庫中的所有酒店名稱/設定 2.計算給定的輸入和酒店名稱 3之間的Levenshtein距離挑選產生最小編輯距離

名稱雖然這對小集合來說工作得很好，但您可以使用BK-Tree進一步優化它。

閱讀材料：

• https://en.wikipedia.org/wiki/Levenshtein_distance
• https://en.wikipedia.org/wiki/BK-tree