在PHP

Question

我有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%然后我想打印 $var_1和$var_2所有相应的类似的文本值，其匹配率> 90

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

任何方向可以更好地处理它？

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>'; 
} 

Answer 2

不幸的是，如果列表变得比琐碎更大并且不能很好地工作，那么你提出的建议很慢。这是可能的，并且在算法上也是有效的。

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

1. “富”=>^F，FO，OO，邻$
2. “hzallo”=>^h时，赫兹，ZA，人，LL，邻$

您可以使用下划线而不是^和$，它们是假冒字符。我认为他们会帮助你排名的结果。

现在可以使用典型的排名算法（请参阅tf * idf和更简单的基于标记计数的算法）来排名最佳匹配。因此，鉴于 “喂，”

QUERY（^ h时，哈，人，LL，卤味，邻$）AGAINST index_of_words

&你会得到一个很好的匹配 “hzallo”，因为^ h时，人，ll，lo，o $全部匹配。

除非你想写一个简单的倒排索引，否则你需要类似Solr或数据库的TEXT索引来做这件事，但它是值得的。查找的速度将比您所喜欢的要快几个数量级，并且结果将按照接近的顺序排列。

之后，你可以使用像levenshtein这样的东西，但我认为你不需要在很多情况下。