基于trie数据字典的php中文分词 -- 算法 -- IT技术博客大学习 -- 共学习共进步！

您现在的位置：首页 --> 算法 --> 基于trie数据字典的php中文分词

基于trie数据字典的php中文分词

浏览:3031次出处信息

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 词:军队

―――――――――――――――――――――――

以前研究过分词的人，很容易发现这个分词还是不足的，但是对于想了解中文分词的基本原理的同学可以思考一下。