6

特定の編集距離を持つデータベース内のすべての文字列を特定の文字列に一致させたいという問題があります。

d私のアイデアは、文字列までの編集距離を持つすべての文字列に一致する正規表現を生成することでしたs。

たとえば、次の形式で正規表現を生成したいとしrます。しかし、これが非常に効率的であるかどうか、またはその問題に対するいくつかの優れたアルゴリズムがすでにあるかどうかはわかりません。編集距離での文字交換も検討したい。したがって、の一部でもある必要があります。PHPでそれを実現してから、SQLクエリを作成したいと思います。d = 1s = 'abc'r = 'abc|.abc|.bc|a.c|ab.|abc.''acb'rSELECT * FROM table WHERE name RLIKE TheRegularExpression

そのようにするのは良い方法ですか？または、何をお勧めしますか？

4

3 に答える 3

5

レーベンシュタイン関数をMysqlに保存できます。その後、次のように検索できます。

mysql_qery("SELECT `term` FROM `words` WHERE levenshtein('$word', `term`) BETWEEN 0 AND '$d'");
于 2012-11-02T17:38:29.460 に答える
1

Levenshtein Distance（または非常によく似たもの）の実装が必要です。これは、MySQLで使用するための関数定義です。

于 2012-11-02T17:37:05.560 に答える
1

おそらく最善の方法は、すべての可能性に対して反復プロセスを構築することです。言い換えれば、このようなもの：

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);
于 2012-11-02T17:38:53.670 に答える