2

クイズを作成したいのですが、ユーザーは正しい答えを入力する必要があります。答えが 90% 一致する場合、答えは正しいとしましょう。たとえば、ユーザーが次のように入力した場合

Britney Spersの代わりにBritney Spears、答えは正しいはずです。

答えがどれほど正確かを判断するためにJavascript関数を検索しました。PHP、Rubyなどの興味深い関数を見つけましたが、JavaScriptで必要です。

この種のアルゴリズムを経験した人はいますか? 答えてくれたらありがとう:)

4

2 に答える 2

3

編集距離アルゴリズムを探しています。基本的に、ある文字列から別の文字列に移動するのに何回の文字変更 (追加/削除/置換) が必要かを確認します。もちろん、距離を見つけるには、ターゲット文字列の辞書が必要です。

http://en.wikipedia.org/wiki/Edit_distance

具体的には: http://en.wikipedia.org/wiki/Levenshtein_distance

Britney Spersとの間の編集距離はBritney Spears1: insert になり'a'ます。

于 2012-04-22T18:39:48.840 に答える
3

編集距離(別名レーベンシュタイン距離)を探しています。このスキームでは、2 つの文字列間の距離は、文字列を一致させるために必要な挿入、削除、または置換の数です。たとえば、正解が「オレンジ」の場合:

  • "oranges" の距離は 0 (同じ単語です)
  • 「オレンジ」の距離は 1 (削除s)
  • 「ロレンジャー」の距離は 2 です (挿入r、置換s -> r)
  • 「スポンジ」の距離は 3 (代用o -> s、代用r -> p、代用o -> a)
  • "" の距離は 7 (すべての文字を に挿入oranges)

Javascript での単純なアルゴリズムは次のようになります (この gistから適応および変更されています)。

function(a, b){
  // Return the number of characters in the other
  // string if either string is blank.
  if(a.length == 0) return b.length; 
  if(b.length == 0) return a.length; 

  // Otherwise, let's make a matrix to represent the possible choices
  // we can take.
  var matrix = [];


  var i;
  for(i = 0; i <= b.length; i++){
    matrix[i] = [i];
  }

  var j;
  for(j = 0; j <= a.length; j++){
    matrix[0][j] = j;
  }

  for(i = 1; i <= b.length; i++){
    for(j = 1; j <= a.length; j++){
      if(b.charAt(i-1) == a.charAt(j-1)){
        matrix[i][j] = matrix[i-1][j-1];
      } else {
        matrix[i][j] = Math.min(matrix[i-1][j-1] + 1, // substitution
                                Math.min(matrix[i][j-1] + 1, // insertion
                                         matrix[i-1][j] + 1)); // deletion
      }
    }
  }

  return matrix[b.length][a.length];
};

あなたの質問の問題点の 1 つは、あなたが探しているものについて書いた例 (「一致 90%」や「回答の精度」など) が明確に定義された指標ではないことです。

答えが間違っている可能性はたくさんあります。たとえば、正解が「りんご」だとしましょう。これらのうちどれを受け入れるべきですか？

  • "APPLE" (間違った大文字)
  • 「ppple」（スペルミス）
  • "apples" (複数形ですが、単数形が欲しかった)
  • 「ふじりんご」（具体的すぎる）
  • 「果物」（広すぎる）

等々。これらのうちどれを受け入れるかを決定することは、単純な編集距離アルゴリズムの力を超えており、NLP のようなより重い作業が必要になります。

于 2012-04-22T18:43:23.723 に答える