3

我有一个大小约为 5.8 MB的“单词”文件，其中包含 560,000 个单词。我正在使用它从连接在一起的字符串中获取真实的单词。

例如greenbananatruck可能是这样的字符串。

我编写了这个函数，以便以非常快的速度使用。但我不能让它比0.5 sec更快。我正在使用具有 8 核处理器、8GB RAM 的服务器。实际上cpu不是问题，问题是RAM。我需要能够在多个实例中快速有效地完成这个过程。

public function wordSplitReal( $str ){

  $words = array_filter( $this->dict, function($word) use(&$str) {
      $pos = strpos( $str, $word );
      if ( $pos !== false ){
          $str = substr_replace($str, "", $pos, strlen($word));
          return true;
      }
      return false;
  } );

  return $words;

}

这很简单，我实际上正在做的是将数组“dict” “过滤”为仅给定字符串中的单词。（我对多个单词不感兴趣。） Dict 从最长到最短的单词进行预排序。全部只有小写字母。这个函数是使用单例的更大类的一部分。

任何帮助，将不胜感激。

4

1 回答 1

1

数组对于这项工作来说是一个错误的工具，因为它们以线性时间访问（正如您所发现的，这对于字典来说太慢了）。您可能想要尝试一下；如果您搜索它们，有几个 PHP 实现。（我对任何 PHP trie 库都没有任何经验，所以我不能向你推荐一个。）

算法的大纲可能是：

While string is non-empty
  For all prefixes of str in decreasing order:
    If it is in trie:
      Drop the prefix
      Add it to the result array
      Next iteration of outer loop
  Return failure
Return result array

（该算法不是很复杂，因为它没有实现回溯；留给读者作为练习：p）

于 2013-06-05T01:45:35.720 回答