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);返回$percent value > 90%，那么我想打印 匹配百分比 > 90$var_1的所有相应的相似文本值$var_2

目前我计划使用两个循环来实现这一点，外部循环 for$var_1和内部循环 for $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$) 反对 index_of_words

& 你会很好地匹配“hzallo”，因为 ^h,al,ll,lo,o$ 都匹配。

除非您想编写一个简单的倒排索引，否则您将需要 Solr 或数据库的 TEXT 索引之类的东西，但这是值得的。查找将比您正在娱乐的速度快几个数量级，并且结果将按接近度排名。

之后，您可以使用 levenshtein 之类的东西，但我认为您在很多情况下都不需要。

于 2013-07-13T06:58:41.507 回答