php 版简单 Trie 树

用 php 写了一个简单的 Trie 树,可以用来做字符串匹配。


<?php

$words = array(
'123','145','43'  
);

class Trie {
    /**
     *
     * 节点数组。每个节点为二元组,依次为是否叶子节点,子节点.
     * @var array $nodes
     */
    protected $nodes;
    
    /**
     * 
     * @var array $words 关键词数组
     */
    function __construct($words) {
        $this->nodes = array( array(false, array()) ); //初始化,添加根节点
        $p = 1; //下一个要插入的节点号
        foreach ($words as $word) {
            $cur = 0; //当前节点号
            for ($len = strlen($word), $i = 0; $i < $len; $i++) {
                $c = ord($word[$i]);
                if (isset($this->nodes[$cur][1][$c])) { //已存在就下移
                    $cur = $this->nodes[$cur][1][$c];
                    continue;
                }
                $this->nodes[$p]= array(false, array()); //创建新节点
                $this->nodes[$cur][1][$c] = $p; //在父节点记录子节点号
                $cur = $p; //把当前节点设为新插入的
                $p++; //
            }
            $this->nodes[$cur][0] = true; //一个词结束,标记叶子节点
        }
    }
    
    function match($s) {
        $ret = array();
        $cur = 0; //当前节点,初始为根节点
        $i = 0; //字符串当前偏移
        $p = 0; //字符串回溯位置
        $len = strlen($s);
        while($i < $len) {
            $c = ord($s[$i]);
            if (isset($this->nodes[$cur][1][$c])) { //如果存在
                $cur = $this->nodes[$cur][1][$c]; //下移当前节点
                if ($this->nodes[$cur][0]) { //是叶子节点,单词匹配!
                    $ret[$p] = substr($s, $p, $i - $p + 1); //取出匹配位置和匹配的词
                    $p = $i + 1; //设置下一个回溯位置
                    $cur = 0; //重置当前节点为根节点
                }
            } else { //不匹配
                $cur = 0; //重置当前节点为根节点
                $i = $p; //把当前偏移设为回溯位置
                $p = $i + 1; //设置下一个回溯位置
            }
            $i++; //下一个字符
        }
        return $ret;
    }
}

$trie = new Trie($words);
$s = '123456787654321';
$found = $trie->match($s, $trie);
print_r($found);

结果:

Array
(
    [0] => 123
    [11] => 43
)

不知道有没有 bug 。

7 thoughts on “php 版简单 Trie 树

  1. muxi

    发现一个bug,假设有个词叫做aaa,当第一次构建树的时候,这三个或更多个a是平级的,array(4) {
    [0]=>
    array(2) {
    [0]=>
    bool(false)
    [1]=>
    array(1) {
    [97]=>
    int(1)
    }
    }
    [1]=>
    array(2) {
    [0]=>
    bool(false)
    [1]=>
    array(1) {
    [97]=>
    int(2)
    }
    }
    [2]=>
    array(2) {
    [0]=>
    bool(false)
    [1]=>
    array(1) {
    [97]=>
    int(3)
    }
    }
    [3]=>
    array(2) {
    [0]=>
    bool(false)
    [1]=>
    array(0) {
    }
    }
    }
    按理说,第二个a应该在第一个a的里面,最后一个才是叶子

    Reply
  2. muxi

    其实吧,我觉得吧,应该考虑一下编码问题,不然遇到中文就不准了,比如把strlen换成 iconv_strlen

    Reply
  3. Sunnyo

    神仙哥 测试了下你这套算法
    如果 $words = array(‘php’, ‘python’, ‘java’, ‘javascript’); 加入到字典里
    查找 $s = ‘php java javascript pythonhello www’;
    找不到 javascript 只能找到两个 java

    Reply
    1. 神仙 Post author

      因为这里是最短匹配,javascript 的前缀也是 java。所以碰到 java 就匹配掉了。
      要按最长匹配,或者重叠匹配,就不在第一次匹配时就跳出,而是继续走到叶子节点。

      Reply
  4. Sunnyo

    array(4) {
    [0]=>
    string(3) “php”
    [4]=>
    string(4) “java”
    [9]=>
    string(4) “java”
    [20]=>
    string(6) “python”
    }

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.