-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 *

我们根据 PHPsimilar_text函数将“不同”定义为不同。但可能还有其他定义。真正的问题是如何比较所有的文本字符串。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 个独特的单词，astrlen大约有 14000 个。所以......为了快速运行，我们可以立即忘记similar_text'cos 所指出的那样，它很慢。我写了一个快速的`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_text你也可以使用 levenshtein 它表现得更好，并产生类似的结果O(n^2*m^2 + n log n)（其中 m 是输入字符串的最大长度）

于 2013-03-05T13:03:50.303 回答
0

好吧，这里有一个想法：定义你所说的与众不同。识别多种差异并为它们打分。例如 ：

  • 相同的字符串：0
  • 一些常用词，排序相同：分数取决于排序的程度和常用词的个数。
  • 一些常用词，但顺序不同
  • 一些单词具有相同顺序的一组共同字母（例如虚拟和虚拟），等等......

分数越高，所调查标准的字符串之间的差异就越大。

然后计算两个字符串的“差异”分数。分数越高，他们的差异就越大。

当需要根据多个不同的参数做出决定时，通常会使用这种方法。这就是一些反垃圾邮件软件识别垃圾邮件的方式。除了他们计算一个分数来确定电子邮件与垃圾邮件的相似程度。

问题是：它总是关于比较。因此，您可以将两个字符串一起比较，但不能将一个字符串与其他字符串进行比较。因此，要识别两个最不同的字符串，您需要使用一些平均系统……并选择那些得分离平均值较远的字符串。

于 2013-03-05T12:59:49.510 回答