Perl 前缀树兑现(2)

Perl 前缀树实现(2)

在前一篇 Perl 前缀树实现中用hash table的方法实现了前缀树，算法导论中用数组来实现，方法基本相同，下边用链表的方法来实现，遍历算法可以用到其他树结构遍历。

代码：

use Data::Dumper;

# 默认只支持字符串的输入
sub trie_tree{
    my $root = {
        char=>undef,
        next=>undef,
        child=>undef,
        count=>0,
    };

    for(@_){
        insert($root, $_);
    }
    return $root;
}

# 方便起见，每次只处理一个连续字符串
sub insert{
    my ($tree,$str) = @_;
    # 不包含字符串情况下返回
    if($str !~ /^[a-zA-Z]+$/){
        return;
    }
    else{
        # 所有节点都存小写字符
        my @tmp = split //,lc $str;

        my $root = $tree;
        for(@tmp){
            # 子节点为空或者第一个子节点字符大于插入字符
            if(! $root->{child} || $root->{child}->{char} gt $_){
                $root->{child} = {
                    char=>$_,
                    next=>$root->{child},
                    child=>undef,
                    count=>0,
                };
                $root = $root->{child};
            }
            else{
                $root = $root->{child};

                while($root->{char} ne $_){
                    if($root->{next} && $root->{next}->{char} le $_){
                        $root = $root->{next};
                    }
                    else{ last; }
                }

                if($root->{char} ne $_){
                    $root->{next} = {
                        char=>$_,
                        next=>$root->{next},
                        child=>undef,
                        count=>0,
                    };
                    $root = $root->{next};
                }                   
            }
        }
        $root->{count}++;
    }
}

# 返回值
# undef 完整字符串未出现
# 0 查找字符串作为前缀字符串出现
# N 字符串出现N次
sub search{
    my ($tree,$str) = @_;

    if($str !~ /^[a-zA-Z]+$/){
        return;
    }
    else{
        my @tmp = split //,lc $str;

        my $root = $tree;
        for(@tmp){
            if(! $root->{child}){
                return;
            }
            else{
                $root = $root->{child};

                while($root->{char} ne $_){
                    if($root->{next}){
                        $root = $root->{next};
                    }
                    else{ last; }
                }

                if($root->{char} ne $_){
                    return
                }                   
            }
        }
        return $root->{count};
    }
}

sub travel{
    my ($tree) = @_;

    if(!$tree->{child}){
        return
    }
    else{
        my @node = ($tree->{child});

        while(@node){
            if($node[-1]->{count} > 0){
                print join '', map {$_->{char}} @node;
                print ' => ',$node[-1]->{count},"\n";
            }
            while($node[-1]->{child}){                   
                push @node, $node[-1]->{child};
                if($node[-1]->{count} > 0){
                    print join '', map {$_->{char}} @node;
                    print ' => ',$node[-1]->{count},"\n";
                }
            }

            while(@node){
                my $t = pop @node;
                if($t->{next}){
                    push @node, $t->{next};
                    last;
                }
            }
        }
    }
}

my $tree = trie_tree(qw(this is just a testing));
insert($tree,'and');
insert($tree,'testing');
travel($tree);

做如下测试，插入40W长度为10的字串，观察所用内存及时间，明显可以看到这个版本所占用的内存更多而且时间更长。当然，由于使用了更多的hash table来表示每个单独的节点，会占用更多的内存，如果使用C来实现的话，相信内存使用不到Perl的1/10。

my $tree = trie_tree(qw(this is just a testing));
for(0..400000){
    my $tmp = join '', map { chr ((int rand(26)) + ord('a')) } 1..rand(10);
    insert($tree, $tmp);
}

Perl 前缀树兑现(2)

相关推荐