Vorschläge implementieren, wenn ein Hotelname eingegeben wird

Question

Ich arbeite an einem Hotel Reservierungssystem. Meine Aufgabe ist es, einen Algorithmus zu implementieren, der richtige Vorschläge macht, wenn der Name eines Hotels falsch eingegeben wird. Zum Beispiel, wenn der Benutzer den Namen des Hotels als "MOFENBICK" eingibt, anstatt seinen wirklichen Namen "MOVENPICK", dann sollte mein Algorithmus vorschlagen, "meintest du MOVENPICK". Ich plane, es mit Machine Learning-Ideen umzusetzen. Was wäre eine gute Auswahl an Funktionen für dieses Problem?

Answer 1

Sie müssen nicht so weit gehen, ein neurales Netzwerk zu implementieren. Das ist Overkill für diese spezielle Aufgabe.

Wie vorgeschlagen, Levenshtein-Abstand verwenden. Die Idee hinter Levenshtein Abstand ist, dass es eine Metrik über Strings definiert. Einfacher gesagt, erlaubt es ein Computeralgorithmus zu sagen, dass "mofenbick" und "movenpick" sich in Entfernung 2 befinden (weil 2 Buchstaben geändert wurden).

Einige Pseudo-Code Levennshtein zu berechnen:

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] 

Sobald Sie eine Metrik definiert über Strings haben Sie eine schnelle Weise benötigen eine Liste der Hotels natürlich abzufragen. Der naive Umsetzung 1. Iterierte über alle Hotelnamen in der Datenbank würde/set 2. Berechnen Sie den Levenshtein Abstand zwischen dem gegebenen Eingang und dem Hotelname 3. den Namen auswählen, die die kleinste Editierdistanz

ergibt Obwohl dies für kleine Sets gut funktioniert, können Sie dies mit einem BK-Tree noch weiter optimieren.

Lesestoff:

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