在PHP中查找相似文本

Question

我有一个PHP数组，内容如下：

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

我想比较数组中的每个元素与其余元素。

例如：我想将"foo"与 "bar"，"hallo"，"world"，"fooo"，"bar1"，"hall_o"，"wor1ld"，"foo"，"bard"，"hzallo"和"w44orld"进行比较。 然后，我想将"bar"与"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%，那么我想打印出$var_1和所有相应的$var_2相似文本值，使匹配百分比> 90。

目前，我计划使用两个循环来实现这一点，外部循环用于$var_1，内部循环用于$var_2。 数组的每个元素的值可以高达5000个字符，并且数组中可以有1000个元素，因此我的当前逻辑非常昂贵。

有没有更好的处理方式？

- Pawan Mude

Answer 1

为了让索引正常工作，数组 $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>';
}

- Expedito

---

你很聪明。这个一维数组完美地运行了。我仍在努力理解它是如何完美地工作的。如果输入数组 $arr 是 array( key1 => value1, key2 => value2, key3 => value3, ... )，那么我们如何在 $out 中打印键和值？ - Pawan Mude

我在MySQL数据库中存储了“问题ID”和“问题”。我在PHP中获取“问题ID”和“问题”，然后应用所述的逻辑来获取重复的问题。现在，在识别重复问题之后，我想找出相应的“问题ID”。 - Pawan Mude

@pawanmude - 我修改了我的答案以保持索引值。 - Expedito

非常出色的解决方案。再次感谢您，先生。我成功获取了重复问题所需的“问题ID”。 - Pawan Mude

Answer 2

很遗憾，如果列表变得比微不足道的列表更大，您提出的方法会变得缓慢且效果不佳。以下是一种可能更好并且算法效率高的方法。

首先，创建一个字母双词语的倒排索引（http://en.wikipedia.org/wiki/Bigram）例如（假设不区分大小写）：

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

可以使用下划线代替伪字符^和$ 以便于结果排序。

现在，您可以使用典型的排名算法（请参阅tf * idf和简单的基于记号计数的算法）来查找相似的单词并对其进行排序。因此，给定“hallo”，

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

您将获得“hzallo”的良好匹配，因为^ h，al，ll，lo和o $都匹配。

您需要类似Solr或数据库的TEXT索引来完成这个任务，除非您想编写一个简单的倒排索引，但这是值得的。查找速度将比您目前考虑的快几个数量级，并且结果将按接近程度排序。

之后，您可以使用类似Levenshtein的算法，但我认为在许多情况下您并不需要这么做。

- Jaimie Sirovich

---

谢谢Jaimie提出新的逻辑。目前我正在使用"Pé de Leão"提供的解决方案，在大约2.5分钟内完美地生成所需的输出。 - Pawan Mude

2.5分钟速度相对较慢。相信我，除非我误解了，否则你会想要使用带有某种模糊性的倒排索引。在其核心，这仍然是Google的工作方式。 - Jaimie Sirovich