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

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函数的代码,以优化分词结果

 

腾讯php程序员面试题目答案——编程任务

编程任务:
1、 我们碰到了大麻烦,一个新来的传教士惹恼了上帝,上帝很愤怒,要求我们把圣经(bbe.txt)背熟,直至他说哪个单词,我们就要飞快的回答出这个单词在 第几行第几个单词位置。听说你是个优秀的程序员,那么髟助我们完成这个不可能的任务吧。
要求如下:
1)/myworks /example/bbe.txt,98版本英文圣经一本
2)输入部分要求如下:php ./example.php [单词]
3)输出部分如下:[单词] 1,2 2,4 5,6 表示:此单词在1行2列(第二个单词),2行4列…
说明:
1)此文本 4MB之巨…
2)单词的含义:由英文字母(大小写),数字(0-9)组成的串
3)提供给你的机器OS为ubuntu 9.10,内存只有1G,而且,很不幸的,其中700M用来做了别的
4)上机考试不允许上网,但我装了man文档以及读取CHM以及PDF的 阅读器,在电脑的桌面的CHM文件夹中,有相应的PHP参考手册
5)算法复杂度要求不能大于O(N^2)(就是N的平方)
6)什 么?PHP低效且用起来不顺手,好的,你可以用别的语言来实现。但注意:提供给你的机器上只有python 2.4/perl 5.8/gcc[g++]

题目链接:http://www.xhttp.cn/2010/05/2

——————————————————————————————————————————————

分析问题:
典型的字典算法,或是分词算法,好在是英文圣经程序可以少些几行代码
1、建立字典,也就是要找的词,比如 fuck,baby,come,on -_- 估计BBE里少有这样的很黄很暴力的词汇
2、因为对内存有要求,其实这个时候可以分章节查找,就是载入内存允许的章节
3、算法时间度o(n)吧,可以一次查找多个词汇

贴我的代码:

< ?php
/**
 * @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('fuck');
$trie->setWord('you');
$trie->setWord('come');
$trie->setWord('on');
var_dump($trie->isWord('fuck'));
var_dump($trie->isWord('a'));
var_dump($trie->isWord('db'));
var_dump($trie->isWord('comeon'));
var_dump($trie->isWord('you'));
print_r($trie->search('hello,tencent,i tell you sonme about bbe,
fuck you come on baby,come on,baby,baby,come on,tellgyou fuckdkkdkflsjflsjf'));

写的比较乱,代码应该还有很大的优化余地,不过足以说明Trie树的基本思想了,我如果有时间的话,会写一个中文分词的例子.
欢迎拍砖

 

腾讯php程序员面试题目答案

在我鸦片师兄的博客看到他对腾讯面试题的解答,我心血来潮,在他的基础上面提出了自己的解法,主要是受他的启发,利用令牌算法优化了一下.

设计任务:
1、最近总有人骚扰我们的投票模块,需要你来设计一个投票限制的东东
要求如下:
1)要求每个QQ号码(假设此QQ号码在UNIT32 内可以表示)10分钟这内只能投5票。
2)我们的用户很踊跃,平均每天要有2000万人左右通过此程序投票。
说明:
1)无需写代码,只需要图跟文字即可。
2)对于关键逻辑,请用图加代码表示出来,这也是对你文字表达能力的一个考验。
3)对你能想到的所有的边界条件列出来,这是对你逻辑思维全面与敏捷性的考验。
4)存储部分,尽你所能吧。如果,你需要一个自己设计的存储层,那么把这个存储层的实现,用文字+图片方式描述清楚,要是设计合理,你会获得华丽的奖分.

解答:
核心问题:如何统计10分钟之内投了5票?

首先:以秒为键切分数据集,10*60=600个时间戳桶,并添加一个Forbid令牌桶
然后:每个数据集内,以qq号码为键,vote次数为值
OK,已经成功转换为key-value方式存储,2000万的日投票,除以86400秒,并发231.48rps,使用memcache能够轻松胜任。

数据集ID:201006072134
【QQ号码:Vote次数】

201006072134 | 201006072135 | 201006072136
【12345:3】 | 【12345:3】 | 【12345:3】
【88888:2】 | 【88888:3】 | 【88888:3】

把下一秒钟不能投票的同学 生成一个令牌桶Forbid。
—————-
Forbid令牌桶
【12345】
【55555】
【66666】
【77777】
【99999】
—————–
if(in_array($uid,$not_vote))
{
$flag = ‘不能投票’;
}
else
{
$flag = ‘可以投票’;
//insert 新时间戳桶
}

定时任务
1、unset(10分钟前的时间戳桶)
2、重新生成令牌桶

 

phpQuery-分析网页文本的新利器

phpQuery是一个服务器端jQuery开源项目。它可以让PHP开发人员采用与jQuery相同的语法来处理网页元素。
在这以前要抓取分析网页文本,不会写正则几乎不可能实现,现在好了,有了phpQuery.
phpQuery is a server-side, chainable, CSS3 selector driven Document Object Model (DOM) API based on jQuery JavaScript Library.

Library is written in PHP5 and provides additional Command Line Interface (CLI).

如果你使用过jQuery,你会发现操作网页文本dom如此简单。

  < ?php     
  include_once( './phpQuery.php' );     
  $html = new phpQueryDocumentFile('xxx.html');  
  $title = $html->find('title')->text();     
  echo $title;

以上内容是取得网页的 title。多方便啊。。。
更多信息..
http://code.google.com/p/phpquery/

 

Redis指令手册中文版

Redis指令手册中文版——–powered by shjuto@gmail.com

连接控制

QUIT :退出,关闭连接

代码实例:连接 退出

telnet localhost 6379
QUIT
  • AUTH : 密码验证
  • 举例说明

    1、首先需要在redis的配置文件redis.conf中requirepass注释掉的内容,设置需要密码连接,否则auth任何密码都通过
    2、重新启动redis
    3、验证 auth testpassword,testpassword是我在配置文件中设置的requirepass testpassword
    4、redis 服务器的速度众所周知,因此官方文件中 提醒设置比较复杂的密码,防止机器破解

    telnet localhost 6379
    Escape character is '^]'.
    auth dsddsd
    -ERR invalid password
    keys global*
    -ERR operation not premitted
    auth ddddd
    -ERR invalid password
    auth testpassword
    +OK

    管理数据操作

  • EXISTS :判断一个键是否存在;存在返回 1;否则返回0;
  • 举例:

    EXISTS burce
    :0
    SET bruce 10
    paitoubing
    +OK
    SET test 5
    paitoubing
    +OK
    -ERR unknown command 'ing'
    EXISTS bruce
    :1

    上面的程序
    EXISTS bruce是否存在,结果是不存在,然后set一个key为bruce 数据长度为10的数据,如果数据长度操作设置的值,多余的字节会当作redis命令来处理

    DEL :删除某个key,或是一系列key;DEL key1 key2 key3 key4

    TYPE: 返回某个key元素的数据类型 ( none:不存在,string:字符,list,set,zset,hash)

    KEYS: 返回匹配的key列表 (KEYS foo*:查找foo开头的keys)

    RANDOMKEY: 随机获得已经存在的key

    RENAME : 更改key的名字,如果名字存在则更改失败

    DBSIZE: 返回当前数据库的key的总数

    EXPIRE: 设置某个key的过期时间(秒),(EXPIRE bruce 1000:设置bruce这个key1000秒后系统自动删除)

    TTL: 查找某个key还有多长时间过期,返回时间秒

    SELECT: 选择数据库

    MOVE: 把key从一个数据库转移到另外一个库

    FLUSHDB: 清空当前数据库数据

    FLUSHALL:清空所有数据库数据

    字符串类型的数据操作

    SET 存一个数据到数据库 SET keyname datalength data (SET bruce 10 paitoubing:保存key为burce,字符串长度为10的一个字符串paitoubing到数据库)

    GET:获取某个key 的value值

    GETSET GETSET可以理解成获得的key的值然后SET这个值,更加方便的操作 (SET bruce 10 paitoubing,这个时候需要修改bruce变成1234567890并获取这个以前的数据paitoubing,GETSET bruce 10 1234567890)

    MGET 一次性获得多个key的数据 (MGET uid:1:name uid:1:email uid:1:ciy)

    SETNX SETNX与SET的区别是SET可以创建与更新key的value,而SETNX是如果key不存在,则创建key与value数据

    SETEX SETEX = SET + EXPIRE,貌似我的这个版本没有办法测试

    MSET 一次性设置多个参数的值(MSET uid:1:name shjuto uid:1:email shjuto@gmail.com uid:1:city 8 回车 nanchang)最后一个值需要回车输入,和SET一样,不知为啥。

    MSETNX 如果设置的key不存在的话,或是叫做新key的话;一次性设置多个参数的值(MSET uid:1:name shjuto uid:1:email shjuto@gmail.com uid:1:city 8 回车 nanchang)最后一个值需要回车输入,和SET一样,不知为啥。

    INCR 自增,有点类是mysql incr.(INCR global:uid)

    INCRBY 自增 +length ,(INCRBY uid 5)原来的基础+5=result

    DECR 自减

    * DECRBY 自减 -lenght

    APPEND 一个例子足以说明

    redis&gt; exists mykey
    (integer) 0
    redis&gt; append mykey "Hello "
    (integer) 6
    redis&gt; append mykey "World"
    (integer) 11
    redis&gt; get mykey
    "Hello World"

    SUBSTR 一个例子足以说明一切,LIKE PHP ‘S STYLE

    redis&gt; set s "This is a string"
    OK
    redis&gt; substr s 0 3
    "This"
    redis&gt; substr s -3 -1
    "ing"
    redis&gt; substr s 0 -1
    "This is a string"
    redis&gt; substr s 9 100000
    " string"

    LISTS (无索引序列,head位置是0,……)

    # RPUSH 追加数据到系列的尾部 (RPUSH listtest 10 \n 1111111122)
    # LPUSH 追加数据到序列的头部 (LPUSH listtest 10 \n 2222222222)
    # LLEN 一个序列的长度;(LLEN listtest)
    # LRANGE 从自定的范围内返回序列的元素 (LRANGE testlist 0 2;返回序列testlist前0 1 2元素)
    # LTRIM 修剪某个范围之外的数据 (LTRIM testlist 0 2;保留0 1 2元素,其余的删除)
    # LINDEX 返回某个位置的序列值(LINDEX testlist 0;返回序列testlist位置为零的元素)
    # LSET 更新某个位置元素的值 (LSET testlist 0 5 \n 55555;)
    # LPOP key Return and remove (atomically) the first element of the List at key
    # RPOP key Return and remove (atomically) the last element of the List at key
    # LREM 根据值删除序列元素 (LREM testlist 0 5 \n 33333;删除序列中所有的等于33333的元素,为何不是REMOVE BY KEY?不知道何故,可能对删除重复数据有用吧)
    # BLPOP key1 key2 … keyN timeout Blocking LPOP >1.31,后续更新
    # BRPOP key1 key2 … keyN timeout Blocking RPOP >1.31
    # RPOPLPUSH srckey dstkey Return and remove (atomically) the last element of the source List stored at _srckey_ and push the same element to the destination List stored at _dstkey_

    SETS (有索引无序序列)

    # SADD 增加元素到SETS序列,如果元素不存在则添加成功 1,否则失败 0;(SADD testlist 3 \n one)

    # SREM 删除SETS序列的某个元素,如果元素不存则失败0,否则成功 1(SREM testlist 3 \N one)

    # SPOP 随机删除某个元素 (SPOP testlist)

    # SMOVE 把一个SETS序列的某个元素 移动到 另外一个SETS序列 (SMOVE testlist test 3\n two;从序列testlist移动元素two到 test中,—testlist中将不存在two元素)

    # SCARD 统计某个SETS的序列的元素数量 (SCARD testlist)

    # SISMEMBER 产看某个数据是否在序列中,(SISMEMBER testlist 3 \n two)

    # SINTER 几个SETS序列的交集 SINTER key1 key2 … keyN (SINTER test testlist),牛B呀

    # SINTERSTORE 把计算出来的交集 记录到一个新的序列 SINTERSTORE dstkey key1 key2 … keyN (SINTERSTORE resultlist testlist test;把testlist test的交集记录到resultlist)

    # SUNION 几个SETS序列的并集 SUNION key1 key2 … keyN (SUNION test testlist)

    # SUNIONSTORE 把计算出来的并集 记录到一个新的序列 SUNIONSTORE dstkey key1 key2 … keyN (SUNIONSTORE resultlist testlist test;把testlist test的交集记录到resultlist)

    # SDIFF key1 key2 … keyN,求出某几个序列的并集 与 某个序列 求出差集 ,请看官方例子:
    key1 = x,a,b,c
    key2 = c
    key3 = a,d
    SDIFF key1,key2,key3 => x,b

    # SDIFFSTORE dstkey key1 key2 … keyN ,和前面的SINTERSTORE SUNIONSTORE差不多,对比
    # SMEMBERS KEY 返回某个序列的所有元素
    # SRANDMEMBER KEY 随机返回某个序列的元素

    Commands operating on sorted sets (zsets, Redis version >= 1.1)

    • ZADD key score member Add the specified member to the Sorted Set value at key or update the score if it already exist
    • ZREM key member Remove the specified member from the Sorted Set value at key
    • ZINCRBY key increment member If the member already exists increment its score by _increment_, otherwise add the member setting _increment_ as score
    • ZRANK key member Return the rank (or index) or _member_ in the sorted set at _key_, with scores being ordered from low to high
    • ZREVRANK key member Return the rank (or index) or _member_ in the sorted set at _key_, with scores being ordered from high to low
    • ZRANGE key start end Return a range of elements from the sorted set at key
    • ZREVRANGE key start end Return a range of elements from the sorted set at key, exactly like ZRANGE, but the sorted set is ordered in traversed in reverse order, from the greatest to the smallest score
    • ZRANGEBYSCORE key min max Return all the elements with score >= min and score <= max (a range query) from the sorted set
    • ZCARD key Return the cardinality (number of elements) of the sorted set at key
    • ZSCORE key element Return the score associated with the specified element of the sorted set at key
    • ZREMRANGEBYRANK key min max Remove all the elements with rank >= min and rank <= max from the sorted set
    • ZREMRANGEBYSCORE key min max Remove all the elements with score >= min and score <= max from the sorted set
    • ZUNIONSTORE / ZINTERSTORE dstkey N key1keyN WEIGHTS w1wN AGGREGATE SUM|MIN|MAX Perform a union or intersection over a number of sorted sets with optional weight and aggregate

    Commands operating on hashes

    • HSET key field value Set the hash field to the specified value. Creates the hash if needed.
    • HGET key field Retrieve the value of the specified hash field.
    • HMSET key field1 value1fieldN valueN Set the hash fields to their respective values.
    • HINCRBY key field integer Increment the integer value of the hash at _key_ on _field_ with _integer_.
    • HEXISTS key field Test for existence of a specified field in a hash
    • HDEL key field Remove the specified field from a hash
    • HLEN key Return the number of items in a hash.
    • HKEYS key Return all the fields in a hash.
    • HVALS key Return all the values in a hash.
    • HGETALL key Return all the fields and associated values in a hash.

    Sorting

    • SORT key BY pattern LIMIT start end GET pattern ASC|DESC ALPHA Sort a Set or a List accordingly to the specified parameters

    Transactions

    Publish/Subscribe

    Persistence control commands

    • SAVE Synchronously save the DB on disk
    • BGSAVE Asynchronously save the DB on disk
    • LASTSAVE Return the UNIX time stamp of the last successfully saving of the dataset on disk
    • SHUTDOWN Synchronously save the DB on disk, then shutdown the server
    • BGREWRITEAOF Rewrite the append only file in background when it gets too big

    Remote server control commands

    • INFO Provide information and statistics about the server
    • MONITOR Dump all the received requests in real time
    • SLAVEOF Change the replication settings
    • CONFIG Configure a Redis server at runtime

    update:2010-05-21,my redis version 1.26

     
     
    About This Website

    Lamp development & SEO & Plan of Website & Project Managment

    Learn more »
    Follow Us (SNS)
    Help & Support

    more about Bruce.xu»

    Get in touch

    QQ: +252339382
    Email: shjuto @ gmail.com

    Online contact form »