Implementing suggestions when a hotel name is typed in

Question

I am working on a hotel reservation system. My task is to implement an algorithm that will give right suggestions when the name of a hotel is typed wrong. For example if the user types the name of the hotel as "MOFENBICK" instead of it's real name "MOVENPICK" then my algorithm should suggest "did you mean MOVENPICK". I plan to implement it using Machine Learning Ideas. What would a good choice of features be for this problem ?

Answer 1

You don't need to go as far as implementing a neural network. That's overkill for this particular task.

As suggested, use Levenshtein-distance. The idea behind Levenshtein distance is that it defines a metric over strings. In simpler terms, it allows a computer-algorithm to say "mofenbick" and "movenpick" are at distance 2 (because 2 letters were changed).

Some pseudo-code to calculate 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]

Once you have a metric defined over Strings, you need a fast way to query a list of hotels of course. The naïve implementation would be 1. iterate over all hotel names in the database/set 2. calculate the Levenshtein distance between the given input and the hotel name 3. pick the name that yields the smallest edit distance

Although this works fine for small sets, you can optimize this even further, using a BK-Tree.

reading material:

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