-1

私はPHPを使用しています。

5 つの文字列があるとします。

"The quick brown fox"
"The sly brown fox"
"The sly brown chicken"
"Totally different text here"
"Not like the others"

そして、残りと最も「異なる」2つを見つけたいと思います。それを 1000 個のテキスト文字列に拡張して、たとえば 300 個の最も「異なる」文字列を取得できるようにしたいと考えています。

どこから始めればよいですか？

編集

「異なる」をどのように定義するかは議論の余地があります！

*編集2 *

similar_textPHPの機能に応じて、「異なる」を異なると定義しました。しかし、他の定義があるかもしれません。本当の問題は、すべてのテキスト文字列を比較する方法です。Jean は、合計を数えることを提案しました。これは、そうする Phillipe のコードのハッキングされたバージョンです。

$strings = array(
    "The quick brown fox",
    "The sly brown fox",
    "The sly brown chicken",
    "Totally different text here",
    "Not like the others"
);

$n = 3;
$sim = array();

for ($i = 0; $i < count($strings); $i++) {

    $total = 0;

    for ($j = 0; $j < count($strings); $j++) {

        if($strings[$i] != $strings[$j]) {

            $sim_val = similar_text($strings[$i], $strings[$j]);
            $total += $sim_val;
            $sim[$strings[$i]][] = array(
                "sim" => $sim_val,
                "w1" => $strings[$i],
                "w2" => $strings[$j]
            );

        }
    }

    $sim[$strings[$i]]['total'] = $total;

}

uasort($sim, function($w1, $w2) {
    return $w1["total"] > $w2["total"];
});

$sim = array_keys($sim);
$sim = array_slice($sim,0,$n);

それが返ってくる

Array
(
    [0] => Not like the others
    [1] => Totally different text here
    [2] => The quick brown fox
)

これは正しい答えのようです。すべてに感謝します（質問に反対票を投じた人は別として。あなたにブーイングします;-)

編集 3 *

わかりましたので、これを 1000 個の文字列でテストしてきました。それぞれに約 500 の一意の単語があり、strlen約 14000 の単語があります。したがって、... これをすばやく実行するにはsimilar_text、指摘したように遅いので、すぐに忘れることができます。簡単な「compare_words」関数を書きました。

function same_words($text1,$text2) {

    $words_1 = array_unique(explode(" ",$text1));
    $words_2 = array_flip(array_unique(explode(" ",$text2)));       

    foreach($words_1 AS $word) {
        if($words_2[$word]) {
            $count++;   
        }
    }

    return $count;

}

しかし、それも遅すぎます。

4

3 に答える 3

2

関数を使用してsimilar_text()、最低パーセンテージを取得します。

http://php.net/manual/en/function.similar-text.php

于 2013-03-05T12:52:17.943 に答える
2

あなたがしなければならないことは、少し力ずくで、すべての単語を他の単語でテストし、類似性を保存し（つまり、similar_text に基づいて）、類似性によって結果を並べ替えることです。

$strings = array(
    "The quick brown fox",
    "The sly brown fox",
    "The sly brown chicken",
    "Totally different text here",
    "Not like the others"
);

$n = 5;
$sim = array();
$sum = 0;

for ($i = 0; $i < count($strings); $i++) {
    $t = 0;
    for ($j = 0; $j < count($strings); $j++) {
        if ($j != $i) {
            $t += similar_text($strings[$i], $strings[$j]);
        }
    }

    $avg = $t / (count($strings) - 1);
    $sim[] = array(
        "sim" => $avg,
        "word" => $strings[$i]
    );

    $sum += $avg;
}

$avg = $sum / count($strings);
usort($sim, function($w1, $w2) use ($avg) {
    return abs($w1["sim"] - $avg) < abs($w2["sim"] - $avg);
});

for ($i = 0; $i < $n && $i < count($sim); $i++) {
    echo $sim[$i]['word'] . "<br />";
}

ただし、このアプローチはそれほど高速ではなく、O(n^2 * m^3 + n log n)

代わりにsimilar_textlevenshtein を使用することもできます。これは非常に優れたパフォーマンスを発揮し、次のような結果になりますO(n^2*m^2 + n log n)(ここで、m は入力文字列の最大長です)。

于 2013-03-05T13:03:50.303 に答える
0

さて、ここに考えがあります：あなたが違うと呼ぶものを定義してください。さまざまな種類の違いを特定し、それらをスコアに結び付けます。例えば ​​：

  • 同一文字列: 0
  • 同じ順序でのいくつかの一般的な単語: スコアは、順序の範囲と一般的な単語の数によって異なります。
  • いくつかの一般的な単語ですが、同じ順序ではありません
  • 同じ順序で共通の文字セットを持ついくつかの単語 (例: virtual と virtual) など...

スコアが高いほど、調査された基準の文字列間の差が大きくなります。

次に、2 つの文字列の「差」スコアを計算します。スコアが高いほど、それらは最も異なります。

この種のアプローチは、複数の異なるパラメーターに基づいて決定を下す必要がある場合によく使用されます。これは、一部のスパム対策ソフトウェアがスパムを識別する方法です。ただし、スコアを計算して、電子メールがスパムにどの程度似ているかを判断します。

問題は次のとおりです。それは常に比較に関するものです。したがって、2 つの文字列を一緒に比較することはできますが、1 つの文字列を残りの文字列と比較することはできません。そのため、最も異なる 2 つの文字列を特定するには、何らかの平均システムに頼る必要があります…そして、スコアが平均から離れているものを選択します。

于 2013-03-05T12:59:49.510 に答える