如何在 PHP 中高效计算字符元组

Question

我需要在 PHP 项目（文件分类器）中快速计算巨大文件/字符串（从 10MB+ 到 1GB+）中的字符元组（或 N-gram）。

当前的实现是针对单个字符计数（N=1），并且在 0.x 秒内运行得非常快。对于非常大的字符串（最多 10 亿个字符/字节）

function frequencies($txt) {
  $index = count_chars($txt, 1);
  foreach ($index as $code => $nb) {
    $count[chr($code)] = $nb;
  }
  return $count;
}

我想修改它以使用二元组（N = 2或更多）运行，所以我写了这个

function frequencies($txt, $n) {
    $length = strlen($txt) - $n+1;
    for ($i = 0; $i < $length; $i++) {
        @$count [ substr($txt, $i, $n) ] ++;
    }
    return $count;
}
// NB: '@' is ugly but seems faster than if isset()

但是这段代码真的很慢：45 秒。对于 N = 1，在同一个文件上（大约慢 100 倍），对于 N=2，则需要超过一分钟。

我尝试过直接访问+串联替代方案：

function twograms($txt) {
    $length = strlen($txt) - $n;
    for ($i = 0; $i < $length; $i++) {
        @$count [ $txt[$i] . $txt[$i+1] ] ++;
    }
    return $count;
}

而且运行速度稍快一些，需要 42 秒。 （+/- 误差范围）

它仍然很慢并且与内置功能

count_char()

效率不匹配。

这里有一个在线 PHP 测试/基准测试链接。

还有其他选择吗？有没有一种方法可以更有效地计算字符元组？

Answer 1

我不确定性能，但是当您对替代方案进行基准测试时可以包括这种方法。它使用

str_split

 和 

array_count_values

 的组合来计算源字符串中的字符序列：

$str = 'The quick brown fox jumps over the lazy dog';

$len = 2;
$counts = [];
for ($n = 0; $n < $len; $n++) {
    $ngramCounts = array_count_values(str_split(substr($str, $n), $len));
    foreach ($ngramCounts as $ngram => $count) {
        $counts[$ngram] = ($counts[$ngram] ?? 0) + $count;
    }
}
print_r($counts);