对一段话做 字典匹配,把匹配到关键词以数组型式输出。例如:开国大典之前,第一届全国政协选出毛泽东为中央人民政府主席,朱德、刘少奇、宋庆龄、李济深、张澜、高岗为副主席。字典是个文本文件,每个关键词一行,一共有一百万的关键词。
最初使用笨办法:$string='开国大典之前,第一届全国政协选出毛泽东为中央人民政府主席,朱德、刘少奇、宋庆龄、李济深、张澜、高岗为副主席。';
$keywords=file("dict.txt");
$find=array();
foreach($keywords as $word)
{
$pos=strpos($string,$word);
if($pos!== false)
{
$find[]=$word;
}
}这个办法笨 一百万次循环下来 需要好几秒;加载字典到内存也需要0.5秒;后来我想了办法,改进了一下字典把字典从一维数组 改造 二维数组。类似这样$keyword=array('中'=>array('中华','中国','中央'),
'创'=>array('创业','创伤','创世'),
);以每个关键词第一个汉字为key ,转换为一个二维数组;再把提取需要匹配的语句中的每个汉字。$keywords=array('中'=>array('中华','中国','中央'),
'创'=>array('创业','创伤','创世'),
......
);$string='开国大典之前,第一届全国政协选出毛泽东为中央人民政府主席,朱德、刘少奇、宋庆龄、李济深、张澜、高岗为副主席。';$hanzi=array_unique(str2_split($string));  //str2_split 提取每个汉字为数组的函数
$new_keywords=array();
foreach($hanzi as $h)
{

if(isset($keywords[$h]))
{
$new_keywords=$new_keywords+$keywords[$t];
}
}
//经过上面这一步骤,原来一百万的数组,已经大大减少了。经过一步骤的处理,整体性能能提高十倍。//下面的还是使用笨办法
$find=array();
foreach($new_keywords as $word)
{
$pos=strpos($string,$word);
if($pos!== false)
{
$find[]=$word;
}
}经过优化之后 性能提高了十倍,一个不太长的段落,基本1秒以内都能个算出来。但还是满足不了我的要求,我希望能提高到0.00秒这种级别。有哪位大神能帮助我另外每次请求把字典载入内存都比较耗时,这部分性能有什么办法可以节约下来。

解决方案 »

  1.   


    $keyword=array('中'=> array(
       '中' => array(
          '华',
          '国',
          '央'),
        ),
        '创' => array(
           '业',
           '伤',
           '世'),
         ),
    );
      

  2.   

    本帖最后由 xuzuning 于 2011-12-30 09:25:33 编辑
      

  3.   

    第二次 改进的方法,我是借鉴了这篇文章http://www.paitoubing.cn/blog/php-trie-mmseg
      

  4.   

    虽然你参考了人家的算法,但你并没有理解 Trie 的核心