Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

(trie exploration) Re: Re:x2 A Regexp Assembler/Compiler (Whats a 'trie'?)

by crazyinsomniac (Prior)
on Jun 20, 2002 at 12:11 UTC ( #175973=note: print w/ replies, xml ) Need Help??


in reply to Re:x2 A Regexp Assembler/Compiler (Whats a 'trie'?)
in thread A Regexp Assembler/Compiler

Interesting. I explored the idea a little. The browser didn't like \0 too much, so i typed \\NULL. Thanks.

#!/usr/bin/perl -w #file://letrie.pl use strict; $\="\n"; my %T=(); for my $word( qw/ aba abba abbda abbaracadabra bam bamara barbara / ) +{ print $word; my $R = \%T; my $C = -1; my( @word ) = $word =~ m{.}g; my $p = ""; while(++$C < @word) { $p = $word[$C]; if(exists $R->{$p}) { if(ref $R->{$p}) { $R = $R->{$p}; } else { $R = $R->{$p} = {}; } }else{ $R = $R->{$p} = {}; } } $R->{"\\NULL"}=1; # for exact match testing }#endof for use Data::Dumper; $Data::Dumper::Indent=1; $Data::Dumper::Purity=1; $Data::Dumper::Quotekeys=1; print Dumper \%T; print "Is 'abba' in a trie? ",in_a_trie(\%T,'abba'); print "Is 'abbda' in a trie? ",in_a_trie(\%T,'abbda'); print "Is 'abbdr' in a trie? ",in_a_trie(\%T,'abbdr'); print "Is 'a' in a trie? ",in_a_trie(\%T,'a'); print "Is 'b' in a trie? ",in_a_trie(\%T,'b'); print "Is 'ba' in a trie? ",in_a_trie(\%T,'ba'); print "Is 'bam' in a trie? ",in_a_trie(\%T,'bam'); print "Is 'fsck' in a trie? ",in_a_trie(\%T,'fsck'); exit; sub in_a_trie { my( $T, $W ) = @_; my $R = 0; my $SH = ""; for $SH ($W =~ m{.}g) { if(exists $T->{$SH} ) { $T = $T->{$SH}; $R++; } else { return 'no'; } } return ($R ? 'yes' : 'no').' ' .(ref $T and $T->{"\\NULL"} ? 'exact' : 'partial' ); } __DATA__ aba abba abbda abbaracadabra bam bamara barbara $VAR1 = { 'a' => { 'b' => { 'a' => { '\\NULL' => 1 }, 'b' => { 'a' => { '\\NULL' => 1, 'r' => { 'a' => { 'c' => { 'a' => { 'd' => { 'a' => { 'b' => { 'r' => { 'a' => { '\\NULL' => 1 } } } } } } } } } }, 'd' => { 'a' => { '\\NULL' => 1 } } } } }, 'b' => { 'a' => { 'm' => { '\\NULL' => 1, 'a' => { 'r' => { 'a' => { '\\NULL' => 1 } } } }, 'r' => { 'b' => { 'a' => { 'r' => { 'a' => { '\\NULL' => 1 } } } } } } } }; Is 'abba' in a trie? yes exact Is 'abbda' in a trie? yes exact Is 'abbdr' in a trie? no Is 'a' in a trie? yes partial Is 'b' in a trie? yes partial Is 'ba' in a trie? yes partial Is 'bam' in a trie? yes exact Is 'fsck' in a trie? no

 
______crazyinsomniac_____________________________
Of all the things I've lost, I miss my mind the most.
perl -e "$q=$_;map({chr unpack qq;H*;,$_}split(q;;,q*H*));print;$q/$q;"


Comment on (trie exploration) Re: Re:x2 A Regexp Assembler/Compiler (Whats a 'trie'?)
Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://175973]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (15)
As of 2015-07-06 18:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (80 votes), past polls