8

配列には 5000 個、場合によってはそれ以上の番地の文字列があります。それらすべてをレーベンシュタインと比較して、同様の一致を見つけたいと思います。すべての 5000 をループして、他のすべての 4999 と直接比較せずに、どうすればこれを行うことができますか?

編集:誰かに提案があれば、別の方法にも興味があります。全体的な目標は、ユーザーが送信した住所に基づいて類似のエントリを見つける (および重複を排除する) ことです。

4

8 に答える 8

7

同様のアドレスをグループ化するより良い方法は、次のようになると思います。

  1. 2 つのテーブルを持つデータベースを作成します。1 つはアドレス (および ID) 用、もう 1 つはアドレス内の単語またはリテラル番号のサウンドエックス (アドレス テーブルの外部キーを使用) 用です。

  2. アドレスを大文字にし、[AZ] または [0-9] 以外はスペースに置き換えます

  3. アドレスをスペースで分割し、各「単語」のsoundexを計算し、数字だけをそのまま残して、開始したアドレスの外部キーを使用してsoundexesテーブルに保存します

  4. 各アドレス (id $target を持つ) について、最も類似したアドレスを見つけます。

    SELECT similar.id, similar.address, count(*) 
FROM adress similar, word cmp, word src
WHERE src.address_id=$target
AND src.soundex=cmp.soundex
AND cmp.address_id=similar.id
ORDER BY count(*)
LIMIT $some_value;

  5. 送信元アドレスと、クエリによって返された上位数個の値とのレーベンシュタイン差を計算します。

(大規模な配列に対してあらゆる種類の操作を実行すると、多くの場合、データベースの方が高速になります)

于 2009-12-24T12:04:10.097 に答える
3

levenstein() 関数は入力として配列ではなく文字列のみを受け取るため、配列をループすることは避けられないと思います。

次のようなことができます：

for($i=0;$i<count($array)-1;$i++)
{
    for($j=$i+1;$j<count($array);$j++)
    {
        $lev = levenshtein($array[$i],$array[$j]);
        if($lev == 0)
        {
            // exact match
        }
        else if($lev <= THRESHOLD)
        {
            // similar
        }
    }
}
于 2009-12-24T11:41:56.007 に答える
3

bk-treeを使用して、検索/比較を高速化できます。

http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Treesによると:

ここで、レーベンシュタイン距離について特に有用な観察を行うことができます。距離空間を形成します。
[...]
検索で使用する文字列であるクエリと、文字列がクエリから離れて返される最大距離 n という 2 つのパラメータがあるとします。任意の文字列を取得し、それをテストしてクエリと比較するとします。得られた距離を d とします。三角形の不等式が成り立つことがわかっているため、すべての結果は最大で d+n の距離、少なくとも test からの距離は dn でなければなりません。
[...]
テストによると、距離が 1 の検索ではツリーの 5 ～ 8% を超えず、2 つのエラーで検索してもツリーの 17 ～ 25% を超えないことが示されています。すべてのノードをチェックするよりも大幅に改善されています。 !

編集：しかし、それはあなたの（「12 Bird Road、Apt 6」および「12 Bird Rd. #6」）の問題には役立ちません。力ずくの m*n 比較のみ。

于 2009-12-24T11:51:31.300 に答える
2

レーベンシュタイン アルゴリズムの性質 (具体的には 2 つの文字列の比較であるという事実) により、これがどのように可能であるかはわかりません。

もちろん、最初にいくつかの基本的なマッチング要件を実行することで比較の数を減らすことができますが、これはあなたが求めている範囲外です。

（おそらく無関係な）オプションとしてsoundex、文字列値を事前に計算できるようなものをいつでも使用できます。（MySQLで直接使用することもできます。）

于 2009-12-24T11:42:19.313 に答える
2

あなたはsoundexesに基づいてそれらをグループ化し、比較を最も近いNケースに制限することができます...

 $mashed=array();
 foreach ($address as $key=>$val) {
      $mashed[$key]=soundex($val);
 }
 sort($mashed);

次に、$mashed のキーを反復処理します。

C.

于 2009-12-24T11:42:25.493 に答える
1

あなたの問題を考えると、レーベンシュタイン距離を使用したい場合は、すべての住所を他のすべての住所と比較する以外に方法がありません。

まず、アドレスを正規化し、略語などを取り除く必要があります。

  • アベニュー -> アベニュー
  • 通り。-> 道路

同様の住所に対して、一定の最大レーベンシュタイン距離 ( N ) を設定できます。

その場合、現在のアドレス ペアの編集距離が N より大きいことが確実な場合は、レーベンシュタイン アルゴリズムを中止できます。このためには、レーベンシュタイン アルゴリズムのカスタム バージョンを作成する必要があります。これにより、アルゴリズムが少し速くなります。

関連する簡単な最適化もいくつかあります。例: アドレス A が 10 文字の長さで、アドレス B が 20 文字の長さで、レーベンシュタイン距離が 8 未満のアドレスを類似していると見なす場合。アドレスの長さを調べて、類似していないことをすぐに判断できます。

于 2009-12-24T11:43:21.840 に答える
1

類似した値をすべて見つけたい場合は、すべてのアイテムを他のすべてのアイテムと比較する必要があります。しかし、適切な配列関数を選択すると、作業が大幅に高速化されます。簡単な例を次に示します (結果配列の方が優れている可能性があります)。

$results = array();
$count = count($entries);
while ($count != 0) {
    # The entry to process
    $entry = array_shift($entries);
    # Get levenshtein distances to all others
    $result = array_map(
        'levenshtein',
        # array_map() needs two arrays, this one is an array consisting of
        # multiple entries of the value that we are processing
        array_fill($entry, 0, $count),
        $toCompare
    );
    $results[] = array($entry => $result);
    $count--;
}
于 2009-12-24T11:48:09.417 に答える
1 
$stringA = "this is php programming language";
$stringB = "this is complete programming script in which java php and  all other minor languages include";

echo "string 1---->".$stringA."<br />";
echo "string 2---->".$stringB."<br />";
// changing string to arrays
$array1 = explode(' ', $stringA);
$array2 = explode(' ', $stringB);

// getting same element from two strings
$c = array_intersect($array1, $array2);
// changing array to the string
$d=implode(' ',$c);

echo "string same elements---> ".$d."<br />";


// getting difrent  element from two arrays
$result = array_diff($array2, $array1);
// changing array to the string
$zem = implode(' ',$result);

if (!empty($zem)) {
  echo "string diffrence---> ".$zem."<br />";
} else {
  echo "string diffrence--->both strings are same <br />";
}

similar_text($stringA, $d, $p);
echo " similarity between the string is ".$p."% <br />";
于 2011-06-18T07:26:17.357 に答える