trie 的应用

WBOY
Freigeben: 2016-06-23 14:38:41
Original
1014 Leute haben es durchsucht

本帖最后由 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);  }}
Nach dem Login kopieren

回复讨论(解决方案)

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



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

初学绝对很有用

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

我看不到懂样

这代码干什么用的?没看懂……
看维基的解释,居然还是不懂…… 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 同级才对的呢。

学习了,嘿嘿,挺好

Verwandte Etiketten:
Quelle:php.cn
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage