データベース内のすべての文字列と特定の編集距離の文字列を一致させたいという問題があります。指定された文字列と編集距離の正規表現を生成
私の考えは、編集距離がdからsまでのすべての文字列と一致する正規表現を生成することでした。その上r = 'abc|.abc|.bc|a.c|ab.|abc.'と：
だから例えば私はの形でd = 1とs = 'abc'のための正規表現rを生成したいです。しかし、これが非常に効率的であるかどうか、あるいはすでにその問題の良いアルゴリズムがあるのかどうかはわかりません。エディット・ディスタンスのキャラクタ・スワップを考慮したい。 'acb'もrの一部である必要があります。私はPHPでそれを実現し、SQLクエリを作成したい：SELECT * FROM table WHERE name RLIKE TheRegularExpression。
このようにするのは良い方法ですか？または何をお勧めしますか？
おそらく最も良いことは、すべての可能性のための反復プロセスを構築することです。言い換えれば、このような何か：あなたは、効率をしたい場合
function findall($startString) {
// create an array of all strings that are distance one away
// each element would be $returnArray["abc"] = "abc";
}
$d = 2; // distance
$myArray[$startString] = $startString;
for($i = 0; $i < $d; $i++) {
$newCombos = array_merge(array(), $myArray);
foreach($myArray as $element) {
$newCombos = array_merge($newCombos, findall($element));
}
$myArray = array_merge(array(), $newCombos);
}
$myRegex = implode("|", $myArray);
ありがとう！魅力のように働く！ –
私が解決策について気づいた唯一の事は、SQLクエリは非常に長く、長い単語と2より高い編集距離では遅いということです。 –
実際にはLevenshtein関数の解決策はおそらく私よりも優れていると思います（enrico.bacisによる） 、あなたはそれをチェックアウトする必要があります – durron597
Levenshtein Distance（またはそれに近いもの）の実装が必要です。ここでは、MySQLで使用するfunction definitionがあります。
不必要に正確な結果を計算するのではなく、決定された編集距離が必要なしきい値を超えると、そのアルゴリズムを修復する方が効率的です。 – millimoose
ありがとうございます。問題は、私はそれを使用するサーバー上で私はストアド関数とプロシージャを使用する権利がないので、私はPHPで実装する必要があります... –
Levenshtein functionをMysqlに格納できます。その後、次のような検索を簡単に行うことができます：
、まず第一に、あなたはそのテーブルがかなりある場合を除き、テーブル内のすべてのレコードにインデックスを使用して解決することはできませんWHERE条件を適用することは避けてください小さい。 – millimoose
また、結果のパターンの長さは 'O（nCd）'となり、 'n'は文字列の長さ、' d'は距離です。これは潜在的に非常に大きなパターンにつながる可能性があります。たとえば、 '80'文字列の場合、希望の距離が' 5 'の場合、約2ギガバイトのREをデータベースに送ります。ただし、文字列が短く、「d」が非常に小さいか、またはnに非常に近いことが確かであれば、それは実行可能かもしれません。 – millimoose
これは、文字列がユーザーによって入力された場合、長さが一定の限度内であるかどうかを確認する必要があります。そうでなければ、DoSホールを作成します。 （ユーザー入力の非常に非効率なアルゴリズムと同様に） – millimoose