在酒店名称输入时实施建议

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