基于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函数的代码
建议继续学习:
- 一个简单的中文分词程序 (阅读:4523)
- 漫话中文分词算法 (阅读:3980)
- 漫话中文自动分词和语义识别(下):句法结构和语义结构 (阅读:3438)
- 腾讯php程序员面试题目答案――编程任务 (阅读:3224)
- Levenshtein distance相似度算法 (阅读:3103)
- 排头兵PHP中文分词,纯PHP版实现 (阅读:2687)
- Mysql+sphinx+中文分词简介(ubuntu) (阅读:2333)
- Mysql+sphinx+中文分词简介(ubuntu) (阅读:1949)
- Trie树(字典树) 最热门的前N个搜索关键词 (阅读:1772)
- 利用新词统计特征进行中文分词 (阅读:1614)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
扫一扫订阅我的微信号:IT技术博客大学习
<< 前一篇:腾讯-1亿个数据取前1万大的整数-题解答
后一篇:腾讯php程序员面试题目答案 >>
文章信息
- 作者:排头兵 来源: 排头兵 @ Talk
- 标签: trie 分词
- 发布时间:2010-07-21 09:52:25
建议继续学习
近3天十大热文
- [66] Oracle MTS模式下 进程地址与会话信
- [65] 如何拿下简短的域名
- [65] Go Reflect 性能
- [59] 【社会化设计】自我(self)部分――欢迎区
- [59] IOS安全–浅谈关于IOS加固的几种方法
- [59] 图书馆的世界纪录
- [59] android 开发入门
- [53] 视觉调整-设计师 vs. 逻辑
- [47] 界面设计速成
- [47] 读书笔记-壹百度:百度十年千倍的29条法则