Perl 前缀树实现(2)
发布时间:2020-12-16 00:20:41 所属栏目:大数据 来源:网络整理
导读:在前一篇?Perl 前缀树实现?中用hash table的方法实现了前缀树,算法导论中用数组来实现,方法基本相同,下边用链表的方法来实现,遍历算法可以用到其他树结构遍历。 代码: use Data::Dumper;# 默认只支持字符串的输入sub trie_tree{ my $root = { char=unde
在前一篇?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},};
$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},};
$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 ' => ',"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); } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |