keywords:中文分词、PHP中文分词、trie数据结构、Doubule Array Trie Datastruct
原理：
Trie数据结构的名词介绍我就不介绍了，大家google,百度可以搜索一大堆的文章来.
Tire索引树法
结构：首字散列表、Trie索引树结点
优点：分词中，不需预知待查询词的长度，沿树链逐字匹配。
缺点：构造和维护比较复杂，单词树枝多，浪费了一定的空间。
有时间我会写一个双数组trie的中文分词小程序来，下面来最简单的trie,
代码：
| 以下是代码片段： < ?php /** * @version 0.1 * @todo 构造通用的字典算法，并写了一个简易的分词 * @author shjuto@gmail.com * Trie字典树 * */ class Trie { private $trie; function __construct() { $trie = array(’children’ => array(),’isword’=>false); } /** * 把词加入词典 * * @param String $key */ function &setWord($word=’’) { $trienode = &$this->trie; for($i = 0;$i < strlen($word);$i++) { $character = $word[$i]; if(!isset($trienode[’children’][$character])) { $trienode[’children’][$character] = array(’isword’=>false); } if($i == strlen($word)-1) { $trienode[’children’][$character] = array(’isword’=>true); } $trienode = &$trienode[’children’][$character]; } } /** * 判断是否为词典词 * * @param String $word * @return bool true/false */ function & isWord($word) { $trienode = &$this->trie; for($i = 0;$i < strlen($word);$i++) { $character = $word[$i]; if(!isset($trienode[’children’][$character])) { return false; } else { //判断词结束 if($i == (strlen($word)-1) && $trienode[’children’][$character][’isword’] == true) { return true; } elseif($i == (strlen($word)-1) && $trienode[’children’][$character][’isword’] == false) { return false; } $trienode = &$trienode[’children’][$character]; } } } /** * 在文本$text找词出现的位置 * * @param String $text * @return array array(’position’=>$position,’word’ =>$word); */ function search($text="") { $textlen = strlen($text); $trienode = $tree = $this->trie; $find = array(); $wordrootposition = 0;//词根位置 $prenode = false;//回溯参数,当词典ab,在字符串aab中，需要把$i向前回溯一次 $word = ’’; for ($i = 0; $i < $textlen;$i++) { if(isset($trienode[’children’][$text[$i]])) { $word = $word .$text[$i]; $trienode = $trienode[’children’][$text[$i]]; if($prenode == false) { $wordrootposition = $i; } $prenode = true; if($trienode[’isword’]) { $find[] = array(’position’=>$wordrootposition,’word’ =>$word); } } else { $trienode = $tree; $word = ’’; if($prenode) { $i = $i -1; $prenode = false; } } } return $find; } } $trie = new Trie(); $trie->setWord(’中国’); $trie->setWord(’中国人’); $trie->setWord(’伟大’); $trie->setWord(’军队’); $trie->setWord(’中国人民’); $trie->setWord(’中国人民解放军’); $trie->setWord(’解放军’); $trie->setWord(’解放’); $words = $trie->search(’伟大的中国人民解放军解放了全中国,是很伟大的军队’); foreach ($words as $word) { echo ’位置:’.$word[’position’].’-’.(strlen($word[’word’])+$word[’position’]); echo ’ 词:’.$word[’word’]."\n"; } |
运行结果：
位置:0-6 词:伟大
位置:9-15 词:中国
位置:9-18 词:中国人
位置:9-21 词:中国人民
位置:9-30 词:中国人民解放军
位置:30-36 词:解放
位置:42-48 词:中国
位置:55-61 词:伟大
位置:64-70 词:军队
―――――――――――――――――――――――
以前研究过分词的人，很容易发现这个分词还是不足的，但是对于想了解中文分词的基本原理的同学可以思考一下。
分词结果不够准确，解放军都没有分出来，原因嘛，是最大匹配中国人民解放军以后，我直接把$word轻松了，你可以修改search函数的代码