技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 基于trie数据字典的php中文分词

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

浏览:3027次  出处信息

    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函数的代码

建议继续学习:

  1. 一个简单的中文分词程序    (阅读:4523)
  2. 漫话中文分词算法    (阅读:3980)
  3. 漫话中文自动分词和语义识别(下):句法结构和语义结构    (阅读:3438)
  4. 腾讯php程序员面试题目答案――编程任务    (阅读:3224)
  5. Levenshtein distance相似度算法    (阅读:3103)
  6. 排头兵PHP中文分词,纯PHP版实现    (阅读:2687)
  7. Mysql+sphinx+中文分词简介(ubuntu)    (阅读:2333)
  8. Mysql+sphinx+中文分词简介(ubuntu)    (阅读:1949)
  9. Trie树(字典树) 最热门的前N个搜索关键词    (阅读:1772)
  10. 利用新词统计特征进行中文分词    (阅读:1614)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1