trie 的应用

WBOY
發布: 2016-06-23 14:38:41
原創
1016 人瀏覽過

本帖最后由 xuzuning 于 2013-04-14 19:02:03 编辑

应 CSDN 要求,收到 CSDN 月饼的应发散分贴
前贴已发,由于僧多粥少。故此结贴,比继续发帖散分

class TTrie {  protected $buffer = array();  protected $dict = array( array() );  protected $input = 0; //字符串当前偏移  protected $backtracking = 0; //字符串回溯位置  public $debug = 0;  public $savematch = 1;  function set($word, $action='') {	if(is_array($word)) {		foreach($word as $k=>$v) $this->set($k, $v);		return;	}	$p = count($this->dict);	$cur = 0; //当前节点号	foreach(str_split($word) as $c) {		if (isset($this->dict[$cur][$c])) { //已存在就下移			$cur = $this->dict[$cur][$c];			continue;		}		$this->dict[$p]= array(); //创建新节点		$this->dict[$cur][$c] = $p; //在父节点记录子节点号		$cur = $p; //把当前节点设为新插入的		$p++;	}	$this->dict[$cur]['acc'] = $action; //一个词结束,标记叶子节点  }  function match($s) {	$ret = array();	$cur = 0; //当前节点,初始为根节点	$i =& $this->input; //字符串当前偏移	$p =& $this->backtracking; //字符串回溯位置	$s .= "\0"; //附加结束符	$len = strlen($s);	$buf = '';	while($i < $len) {		$c = $s{$i};		if(isset($this->dict[$cur][$c])) { //如果存在			$cur = $this->dict[$cur][$c]; //转到对应的位置			if(isset($this->dict[$cur][$s[$i+1]])) {//检查下一个字符是否也能匹配,长度优先				$i++;				continue;			}			if(isset($this->dict[$cur]['acc'])) { //是叶子节点,单词匹配!				if($buf != '') {					$this->buffer[] = $buf;					$buf = '';				}				if($this->savematch) $this->buffer[] = substr($s, $p, $i - $p + 1); //取出匹配位置和匹配的词				$ar = explode(',', $this->dict[$cur]['acc']);				call_user_func_array( array($this, array_shift($ar)), $ar );				$p = $i + 1; //设置下一个回溯位置				$cur = 0; //重置当前节点为根节点			}		} else { //不匹配			$buf .= $s{$p}; //substr($s, $p, $i - $p + 1); //保存未匹配位置和未匹配的内容			$cur = 0; //重置当前节点为根节点			$i = $p; //把当前偏移设为回溯位置			$p = $i + 1; //设置下一个回溯位置		}		$i++; //下一个字符	}	if(trim($buf, "\0")) $this->buffer[] = trim($buf, "\0");	return $this->buffer;  }  function __call($method, $param) {	if($this->debug) printf("偏移:%d 回溯:%d\n", $this->input, $this->backtracking);  }}
登入後複製

回复讨论(解决方案)

这个是国庆中秋过节的福利么。。。 



老大在各应我没发散分帖啊?哈哈 ...话说我早发到水区去了.嘿嘿
继续接分

初学绝对很有用

接分~~~~
是哪家的月饼啊

我看不到懂样

这代码干什么用的?没看懂……
看维基的解释,居然还是不懂…… http://zh.wikipedia.org/wiki/Trie
大学白读了……

没学过算法,看到树就知道爬

文……

这代码干什么用的?没看懂……
看维基的解释,居然还是不懂…… http://zh.wikipedia.org/wiki/Trie
大学白读了……
字典树,先读入文本(多个字符串),然后查找一个串在文本中出现过几次等相关应用。。。
复杂度就等于这个串的长度。。。。。
优点: 速度快
缺点: 空间花销大

感谢谢

严重支持这种分享精神,有分享才会有进步

EWN 

收藏了嘿嘿

收藏!

接分,老大威武!

火钳刘明

谢谢徐哥

徐哥谢谢

很久没来了,以来就看到散分帖,果断接之

接月饼分, 学习, 收藏之

接分,mark下,慢慢看

果断回帖来接分!

初学绝对很有用

这代码干什么用的?没看懂……
看维基的解释,居然还是不懂…… http://zh.wikipedia.org/wiki/Trie
大学白读了……

我记得是离散或者编译原理的内容啊

果断接分 月饼拿来 

好东西呀

算法贴……感觉c++写的要好看呢……

我的沙发贴子为什么给删除了,而且也没通知?黑暗?

收到!接分

楼主好人啊,谢谢

字典树,先读入文本(多个字符串),然后查找一个串在文本中出现过几次等相关应用。。。
复杂度就等于这个串的长度。。。。。
优点: 速度快
缺点: 空间花销大
多谢了,现在有点明白了,做个模型,实战理解去了。

怎么用啊。看不懂。楼主能举几个例子看看吗 

持续接分ing

kan kan

中秋来接分了

恭喜,恭喜,来接接分啦!

weidejif zhihao huitiel

学习下

学习下ing。。。

学习ing

这是发月饼吗?

跟着大牛走

原来这里送分了

没看懂



真悲催

版主  想请教一下

$TTrie = new TTrie();
$TTrie->set('abc');
$TTrie->set('abd');
var_dump($TTrie->dict);

array(5) {
  [0]=>
  array(1) {
    ["a"]=>
    int(1)
  }
  [1]=>
  array(1) {
    ["b"]=>
    int(2)
  }
  [2]=>
  array(2) {
    ["c"]=>
    int(3)
    ["d"]=>
    int(4)
  }
  [3]=>
  array(1) {
    ["acc"]=>
    string(0) ""
  }
  [4]=>
  array(1) {
    ["acc"]=>
    string(0) ""
  }
}


那个acc有什么用的呢    是不是各自和c、d 同级才对的呢。

学习了,嘿嘿,挺好

相關標籤:
來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
最新問題
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板