1

我试图在一组字段中找到几乎重复的值，以便管理员清理它们。

我符合两个条件

  1. 一个字符串完全包含在另一个字符串中，并且至少是其长度的 1/4
  2. 字符串的编辑距离小于两个字符串总长度的 5%

伪 PHP 代码：

foreach($values as $value){
$matches = array();
foreach($values as $match){
  if(
    (
      $value['length'] < $match['length']
      &&
      $value['length'] * 4 > $match['length']
      &&
      stripos($match['value'], $value['value']) !== false
    )
    ||
    (
      $match['length'] < $value['length']
      &&
      $match['length'] * 4 > $value['length']
      &&
      stripos($value['value'], $match['value']) !== false
    )
    ||
    (
      abs($value['length'] - $match['length']) * 20 < ($value['length'] + $match['length'])
      &&
      0 < ($match['changes'] = levenshtein($value['value'], $match['value']))
      &&
      $match['changes'] * 20 <= ($value['length'] + $match['length'])
      )
    ){
      $matches[] = &$match;
    }
}
// output matches for current outer loop value
}

我试图尽可能减少对相对昂贵的函数的调用stripos，levenshtein这大大减少了执行时间。然而，作为一个 O(n^2) 操作，这并不能扩展到更大的值集，而且似乎大量的处理时间都花在了简单地遍历数组上。

正在操作的几组值的一些属性

总计 | 弦乐 | # 每个字符串的匹配数 | |
弦乐 | 搭配火柴 | 平均 | 中位数 | 最大 | 时间（秒）|
--------+-------------+---------+--------+------+ ----------+
    第844章 413 | 1.8 | 1 | 58 | 140 |
    第593章 156 | 1.2 | 1 | 5 | 62 |
    272 | 168 | 3.2 | 2 | 26 | 10 |
    157 | 47 | 1.5 | 1 | 4 | 3.2 |
    106 | 48 | 1.8 | 1 | 8 | 1.3 |
     62 | 47 | 2.9 | 2 | 16 | 0.4 |

我可以做些什么来减少检查标准的时间，更重要的是，我有什么方法可以减少所需的标准检查次数（例如，通过预处理输入值），因为有这样的选择性低？

编辑：实施的解决方案

// $values is ordered from shortest to longest string length
$values_count = count($values); // saves a ton of time, especially on linux
for($vid = 0; $vid < $values_count; $vid++){
for($mid = $vid+1; $mid < $values_count; $mid++){ // only check against longer strings
  if(
    (
      $value['length'] * 4 > $match['length']
      &&
      stripos($match['value'], $value['value']) !== false
    )
    ||
    (
      ($match['length'] - $value['length']) * 20 < ($value['length'] + $match['length'])
      &&
      0 < ($changes = levenshtein($value['value'], $match['value']))
      &&
      $changes * 20 <= ($value['length'] + $match['length'])
      )
    ){
      // store match in both directions
      $matches[$vid][$mid] = true;
      $matches[$mid][$vid] = true;
    }

}
}
// Sort outer array of matches alphabetically with uksort()
foreach($matches as $vid => $mids){
  // sort inner array of matches by usage count with uksort()
  // output matches
}
4

2 回答 2

0

您可以首先按长度（ O(N) ）对字符串进行排序，然后仅将较小的字符串检查为子字符串或较大的字符串，并且仅在差异不太大的字符串对中使用 levenshtein 进行检查。

您已经执行了这些检查，但现在您对所有 N x N 对都执行此操作，而首先按长度预选将帮助您减少要首先检查的对。避免 N x N 循环，即使它只包含会失败的测试。

对于子字符串匹配，您可以通过为所有较小的项目创建索引来进一步改进，并在解析较大的项目时相应地更新它。索引应该可以形成一个在字母上分支的树结构，其中每个单词（字符串）形成从根到叶的路径。通过这种方式，您可以找到索引中的任何单词是否与要匹配的某个字符串进行比较。对于匹配字符串中的每个字符，尝试继续树索引中的任何指针，并在索引处创建一个新指针。如果指针不能指向索引中的下一个字符，则将其删除。如果任何指针到达叶注，则您已找到子字符串匹配。我认为实现这一点并不困难，但也不是微不足道的。

于 2010-05-20T23:03:41.620 回答
0

通过收紧内循环，您可以立即获得 100% 的改进。您的结果中没有重复匹配吗？

对于预处理步骤，我将完成并计算字符频率（假设您的字符集很小，例如 a-z0-9，鉴于您使用的是 stripos，我认为这很可能）。然后而不是比较序列（昂贵）比较频率（便宜）。这会给您带来误报，您可以忍受这些误报，也可以插入您目前必须淘汰的测试。

于 2010-05-20T23:27:31.500 回答