ホテル名の入力時に提案を実装

Question

私はホテルの予約システムに取り組んでいます。私の仕事は、ホテルの名前が間違って入力されたときに適切な提案をするアルゴリズムを実装することです。たとえば、ユーザーが実際のホテル名 "MOVENPICK"ではなく "MOFENBICK"としてホテルの名前を入力した場合、私のアルゴリズムは "MOVENPICKを意味しました"と提案する必要があります。私はMachine Learning Ideasを使ってそれを実装するつもりです。この問題のために機能の良い選択は何でしょうか？

Answer 1

ニューラルネットワークを実装する必要はありません。それはこの特定の仕事のために残忍です。

推奨されるように、Levenshtein-distanceを使用します。 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.反復処理になります/与えられた入力とホテル名 3間のレーベンシュタイン距離が最小編集距離

を生成する名前を選んで計算 2を設定しますこれは小さなセットではうまく動作しますが、BKツリーを使用してこれをさらに最適化することができます。

読み物：の

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