< ?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";
}