3

私はこのようなPHP配列を持っています

$array = array("foo", "bar", "hallo", "world", "fooo", "bar1", "hall_o", "wor1ld", "foo", "bard", "hzallo", "w44orld");

配列の各要素を残りの要素と比較したい。

例：私はコンプリートしたい"foo" with "bar", "hallo", "world", "fooo", "bar1", "hall_o", "wor1ld", "foo", "bard", "hzallo" and "w44orld"。

"bar" with "foo", "hallo", "world", "fooo", "bar1", "hall_o", "wor1ld", "foo", "bard", "hzallo", "w44orld" 次に、最後の要素まで比較したいと思います。

$var_1$var_2; として比較している要素と、残りの要素の変数を考えてみましょう。similar_text($var_1, $var_2, $percent);返された場合、一致率> 90の対応するすべての同様のテキスト値$percent value > 90%を印刷したい $var_1$var_2

現在、これを実現するために、外部ループ for$var_1と内部ループ for の2 つのループを使用する予定です$var_2。の各要素はarray最大 5000 文字の値を持つことができ、配列には 1000 個の要素を含めることができるため、現在のロジックは非常に高価です。

より良い方法でそれを処理する方向はありますか?

4

2 に答える 2

3

インデックス付けが機能するためには、配列$arrに一意の値が必要です。

$arr = array("foo", "bar", "hallo", "world", "fooo", "bar1", "hall_o", "wor1ld", "bard", "hzallo", "w44orld");
$dexed = array();
foreach ($arr as $key => $value){
    $dexed[$key]['val'] = $value;
    $dexed[$key]['key'] = $key;
}
$out = array();//output
$rev = array();//reverse lookup array
$t = 80;//threshold value
$cnt = count($dexed);
$k = 0;
for ($i=0; $i<$cnt-1; $i++){
    for ($j=$i+1; $j<$cnt; $j++){
        //similar_text calculates differently depending on order of arguments
        similar_text($dexed[$i]['val'], $dexed[$j]['val'], $percent1);
        similar_text($dexed[$j]['val'], $dexed[$i]['val'], $percent2);
        if (($percent1 >= $t) || ($percent2 >= $t)){
            //check if value already exists under different key
            if (in_array($dexed[$i]['val'], array_keys($rev))){
                if ( ! in_array($dexed[$j]['val'], array_keys($rev))){
                    $fkey = $rev[$dexed[$i]['val']];//key found
                    $next = count($out[$fkey]);
                    $out[$fkey][$next]['val'] = $dexed[$j]['val'];
                    $out[$fkey][$next]['key'] = $dexed[$j]['key'];
                    $rev[$dexed[$j]['val']] = $fkey;
                }
            } else {
                $out[$k][0]['val'] = $dexed[$i]['val'];
                $out[$k][0]['key'] = $dexed[$i]['key'];
                $out[$k][1]['val'] = $dexed[$j]['val'];
                $out[$k][1]['key'] = $dexed[$j]['key'];
                $rev[$dexed[$i]['val']] = $k;
                $rev[$dexed[$j]['val']] = $k;
                $k++;
            }
        }
    }
}

$outが生成されたら、次を使用してインデックス配列を生成します。

$index = array();
foreach ($out as $key => $group){
    $cnt = count($group);
    foreach ($group as $key2 => $word){
        for ($i=0; $i<$cnt; $i++){
            if ($i != $key2){
                $index[$word['key']][] = $key.':'.$i;
            }
        }
    }
}

特定のキー (元の配列内の単語のキー値) のすべての類似単語にアクセスします$arr。

$key = 2;
foreach ($index[$key] as $value){
    $parts = explode(':', $value);
    echo '<p>'.$out[$parts[0]][$parts[1]]['val'].'</p>';
}
于 2013-07-13T08:59:22.380 に答える
2

残念ながら、リストが些細なものよりも大きくなり、うまく機能しない場合、あなたが提案していることは遅くなります。これは、アルゴリズム的に効率的である可能性があり、またそうなるものです。

まず、文字バイグラムの逆索引を作成します ( http://en.wikipedia.org/wiki/Bigram )。例（大文字と小文字を区別しないと仮定）：

  1. "foo" => ^f,fo,oo,o$
  2. "hzallo" => ^h,hz,za,al,ll,o$

疑似文字である ^ と $ の代わりにアンダースコアを使用できます。結果をランク付けするのに役立つと思います。

類似した単語を見つけるために、典型的なランキング アルゴリズム (tf*idf およびより単純なトークン カウント ベースのアルゴリズムを参照) を使用して、最も一致する単語をランク付けできます。したがって、「ハロー」が与えられた場合、

QUERY(^h,ha,al,ll,lo,o$) AGAINST index_of_words

& ^h,al,ll,lo,o$ がすべて一致するため、"hzallo" に適切に一致します。

単純な逆インデックスを作成する場合を除き、これを行うには Solr またはデータベースの TEXT インデックスのようなものが必要になりますが、それだけの価値はあります。検索は、あなたが楽しませているものよりも桁違いに速くなり、結果は近さによってランク付けされます.

その後、レーベンシュタインのようなものを使用できますが、多くの場合、その必要はないと思います。

于 2013-07-13T06:58:41.507 に答える