输入酒店名称时执行建议

Question

我正在开发酒店预订系统。我的任务是实现一种算法，当输入错误的酒店名称时，它会给出正确的建议。例如，如果用户将酒店名称键入 "MOFENBICK" 而不是真实名称 "MOVENPICK"，那么我的算法应该建议 "did you mean MOVENPICK"。我计划使用 Machine Learning Ideas 来实现它。对于这个问题，最好的特征选择是什么？

Answer 1

您无需深入实施神经网络。这对于这个特定任务来说太过分了。

按照建议，使用编辑距离。 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. 遍历 database/set 中的所有酒店名称 2. 计算给定输入与酒店名称之间的编辑距离 3. 选择产生最小编辑距离的名称

虽然这对小集来说效果很好，但您可以使用 BK-Tree 进一步优化它。

阅读material:

输入酒店名称时执行建议

Implementing suggestions when a hotel name is typed in

matlab

machine-learning

octave