But you could just pull it all into a database, don't reinvent the wheel, drink a $beverage_of_your_choice and be happy.

use Tree::Trie;

# read in all of dict - it's around 400K words
open(DICT, "<", "/usr/share/dict/words");
my $trie   = new Tree::Trie;
my $trie_r = new Tree::Trie;
while (<DICT>) {
    chomp;
    next if /[^-\w\d]/;
    $trie->add($_);
    $trie_r->add(join('',reverse split('', $_)));
}
close DICT;

use Time::HiRes qw(time);
my (@match, $start);
foreach my $lookup (@ARGV) {
    my @args;
    my $t;

    my $start = time;
    if ($lookup =~ /^([^\*]+)\*$/) {
        @match = $trie->lookup($1);
    } elsif ($lookup =~ /^\*([^\*]+)$/) {
        @match = map { join('',reverse split('', $_)) }
          $trie_r->lookup(join('',reverse split('', $1)));
    }

    print $lookup, 
      sprintf(" (%0.4fs) : ", time - $start), 
      join(',', @match),
      "\n";
}
[download]

On my system the searches are very fast once the database is loaded.

$ perl trie.pl 'oophoro*' '*otomy' '*botomy' 'sam*'
oophoro* (0.0011s) : oophoroepilepsy,oophoropexy,oophoron,oophorocyste
+ctomy,oophorocele,oophororrhaphy,oophoromalacia,oophoroma,oophoromani
+a,oophorosalpingectomy,oophorostomy,oophorotomy
*otomy (0.0209s) : sclerotomy,iridosclerotomy,viscerotomy,merotomy,ure
+terotomy,sphincterotomy,enterotomy,laparoenterotomy,gastroenterotomy,
+celioenterotomy,hernioenterotomy,uterotomy,abdomino-uterotomy,laparo-
+uterotomy,hysterotomy,colpohysterotomy,laparocolpohysterotomy,abdomin
+ohysterotomy,laparohysterotomy,gastrohysterotomy,celiohysterotomy,lap
+arotomy,splenolaparotomy,hysterolaparotomy,blepharotomy,Caesarotomy,h
+ydrotomy,angiohydrotomy,androtomy,chondrotomy,synchondrotomy,thyrotom
+y,pleurotomy,neurotomy,aponeurotomy,commissurotomy,necrotomy,sacrotom
+y,microtomy,nephrotomy,lithonephrotomy,laparonephrotomy,urethrotomy,o
+stearthrotomy,arthrotomy,osteoarthrotomy,cerebrotomy,corotomy,aeropor
+otomy,oophorotomy,metrotomy,elytrotomy,laparoelytrotomy,gastroelytrot
+omy,celioelytrotomy,ventrotomy,antrotomy,sequestrotomy,gastrotomy,lap
+arogastrotomy,gastrogastrotomy,celiogastrotomy,colopexotomy,loxotomy,
+tendotomy,pericardotomy,chordotomy,cleidotomy,orchidotomy,iridotomy,c
+litoridotomy,thyroidotomy,mastoidotomy,ichthyotomy,embryotomy,myotomy
+,tenomyotomy,fibromyotomy,ophthalmomyotomy,tenontomyotomy,leukotomy,l
+ymphotomy,nymphotomy,synechotomy,polychotomy,bronchotomy,thoracobronc
+hotomy,orchotomy,trichotomy,dichotomy,subdichotomy,choledochotomy,duo
+denocholedochotomy,canthotomy,lithotomy,cholelithotomy,pyelolithotomy
+,ureterolithotomy,nephrolithotomy,choledocholithotomy,pelviolithotomy
+,ornithotomy,coccygotomy,laryngotomy,tracheolaryngotomy,pharyngotomy,
+salpingotomy,laparosalpingotomy,celiosalpingotomy,myringotomy,syringo
+tomy,dacryocystosyringotomy,esophagotomy,vagotomy,herniotomy,cranioto
+my,arteriotomy,salpingo-ovariotomy,ovariotomy,parovariotomy,oariotomy
+,pelviotomy,cardiotomy,pericardiotomy,symphysiotomy,episiotomy,celiot
+omy,coeliotomy,ciliotomy,fasciotomy,kiotomy,orchiotomy,rachiotomy,bra
+chiotomy,angiotomy,lymphangiotomy,biotomy,pubiotomy,herpetotomy,oment
+otomy,tenontotomy,odontotomy,pancreatotomy,meatotomy,hepatotomy,lapar
+ohepatotomy,keratotomy,dermatotomy,stomatotomy,prostatotomy,aortotomy
+,cystotomy,cholecystotomy,laparocholecystotomy,epicystotomy,dacryocys
+totomy,hypocystotomy,lithocystotomy,uterocystotomy,laparocystotomy,re
+ctocystotomy,proctocystotomy,prostatocystotomy,mastotomy,histotomy,co
+stotomy,periostotomy,phytotomy,septotomy,rectotomy,proctotomy,autotom
+y,orbitotomy,ototomy,ileotomy,laparoileotomy,peritoneotomy,perineotom
+y,peotomy,tracheotomy,cricotracheotomy,laryngotracheotomy,stereotomy,
+thyreotomy,cricothyreotomy,edeotomy,symphyseotomy,osteotomy,hebeosteo
+tomy,periosteotomy,splenotomy,laparosplenotomy,hymenotomy,rumenotomy,
+adenotomy,duodenotomy,gastroduodenotomy,tenotomy,myotenotomy,myoenoto
+my,jejunotomy,splanchnotomy,tympanotomy,neuroanotomy,vaginotomy,turbi
+notomy,mediastinotomy,pogonotomy,pneumonotomy,cionotomy,kionotomy,val
+votomy,proctovalvotomy,ophthalmotomy,pneumotomy,thalamotomy,mammotomy
+,desmotomy,syndesmotomy,plasmotomy,myomotomy,laparomyomotomy,celiomyo
+motomy,entomotomy,symphysotomy,vasotomy,tarsotomy,cirsotomy,glossotom
+y,pyelotomy,celotomy,kelotomy,helotomy,trachelotomy,laparotrachelotom
+y,cystotrachelotomy,cephalotomy,encephalotomy,omphalotomy,amygdalotom
+y,staphylotomy,ankylotomy,xylotomy,spondylotomy,condylotomy,bdellotom
+y,fallotomy,tonsillotomy,cyclotomy,aplotomy,vesiculotomy,ossiculotomy
+,valvulotomy,uvulotomy,capsulotomy,typhlotomy,alveolotomy,colotomy,il
+eocolotomy,laparocolotomy,gastrocolotomy,lumbocolotomy,cholecystocolo
+tomy,cheilotomy,chilotomy,pulpotomy,colpotomy,laparocolpotomy,gastroc
+olpotomy,celiocolpotomy,hippotomy,anthropotomy,cecotomy,caecotomy,onc
+otomy,leucotomy,thoracotomy,scotomy,phrenicotomy,cricotomy,varicotomy
+,clavicotomy,vesicotomy,hepaticotomy,scleroticotomy,phlebotomy,ophtha
+lmophlebotomy,hepatophlebotomy,arteriophlebotomy,flebotomy,hebotomy,g
+astrotubotomy,strabotomy,lobotomy,rhizotomy,zootomy
*botomy (0.0008s) : phlebotomy,ophthalmophlebotomy,hepatophlebotomy,ar
+teriophlebotomy,flebotomy,hebotomy,gastrotubotomy,strabotomy,lobotomy
sam* (0.0052s) : sam,saman,samarra,samara,samaras,samarskite,samaroid,
+samarium,samariums,samaria,samariform,samaritan,samaritans,samadh,sam
+adhi,samaj,sam-sodden,samuel,samurai,samurais,samuin,samh,samhita,sam
+khya,samkara,samgha,samfoo,samiel,samiels,samiresite,samiri,samian,sa
+mizdat,samisen,samisens,samite,samites,samiti,samely,samel,sameliness
+,same-colored,same-minded,same-seeming,same-sounding,same-sized,same-
+featured,same,samenesses,sameness,samen,samech,samechs,samek,samekh,s
+amekhs,sameks,samesome,samnani,samnite,samvat,sammy,sammel,sammer,sam
+mier,samskara,samshu,samshus,samshoo,samsara,samsaras,samson,samsonia
+n,samsonite,samlet,samlets,sample,samplery,sampler,samplers,samplemen
+,sampleman,sampled,samples,sampling,samplings,samp,samphire,samphires
+,sampaloc,sampan,sampans,sampaguita,samps,sampi,sambel,sambul,sambuni
+grin,sambuca,sambucas,sambur,samburs,sambuke,sambukes,sambuk,sambhur,
+sambhurs,sambhar,sambhars,sambhogakaya,sambal,sambaed,samba,sambar,sa
+mbars,sambaqui,sambaquis,sambas,sambaing,sambo,sambouk,sambouse,sambo
+s,samoyed,samory,samohu,samoa,samoan,samoans,samogon,samogonka,samova
+r,samovars,samosa,samosas,samosatenian,samothere,samothracian
[download]

You'd need to do more work if you wanted fast "foo*bar" searches or other syntax. Also worth noting is that it uses quite a lot of memory, but hey, that's Perl for you!

Thanks for the question - that was fun!

-sam

I can understand that oophoroepilepsy matches against oophoro* (with the '*' wildcard at the end), but how does otomyces match against *otomy (with the '*' wildcard at the beginning)?

Shouldn't '*otomy' (and '*botomy', for that matter) match against something like 'phlebotomy'?

What is the significance of the position of the wildcard character in the search string?

Hey, reverse() on a scalar doesn't reverse it! I wonder why I thought it did. Fixed code will go in the original node in a moment. I'm sure there are other bugs though - this was just example code!

-sam

You can build an index IF you know the regexes to index in advance. You can't build an index that will work for any random regex that comes along.

If you want to do it, just look up information on building an inverted word index, but use regexes instead of words. (In short, you run every regex against every record and build a hash from regexes to a list of records that match them.) You could probably even adapt some of the text search tools on CPAN if you chose to.

A possible strategy could be to open the file(s) and upon reading each string immediately checking whether the string matches your query, discarding the string if not and keeping it if it does. This probably the fastest way, but will only work for one query. Each query would suffer again the cost of opening the file(s) and reading the strings.

If you need to run multiple queries, you must invent a data-structure to hold all the strings and timestamps (a hash of arrays or an array of arrays spring to mind). The set-up of these will also have a one-time cost and there is of course the memory issue to look into: too much memory needed and your machine will start swapping, which will degrade the performance of your queries. Fortunately memory if cheap, so adding another GigaByte of RAM will solve a lot of problems in that respect.

But you will still be re-inventing a lot of wheels and rather than playing at the "(re-)invent-a-database" game, why not dumping the data into a simple SQLite database and then running the usual SQL-queries against this database?

Try this. It uses ~300MB to store and index 1 million (randomly generated) words (14MB on disk). It allows full regex searching (with some adaptions) and never seems to take more than 2 seconds:

#! perl -slw
use strict;
use Time::HiRes qw[ time ];
use List::MoreUtils qw[ uniq ];

sub idx{
    my $idx = chr(0) x 4;
    vec( $idx, $_, 1 ) = 1 for map ord()-ord('a'), uniq sort split'', 
+$_[ 0 ];
    $idx;
}

my %idx;

open DICT, '<', 'junk.words' or die $!;
while( <DICT> ) {
    chomp;
    push @{ $idx{ idx( $_ ) } }, $_;
}
my @keys = keys %idx;
print scalar @keys;

while( <> ) {
    my $start = time;
    my @matches;
    my $n = 0;
    chomp;
    ( my $pat = $_ ) =~ tr[a-z][]cd;
    $pat = idx( $pat );
    for my $idx ( grep+(($_ & $pat) eq $pat), @keys ) {
        for my $poss ( @{ $idx{ $idx } } ) {
            $poss =~ $_ and $matches[ $n++ ] = $poss;
        }
    }
    printf "Found $n matches in  %.2f seconds; Display? ", time() - $s
+tart;
    if( <> =~ /y/i ) {
        print for @matches;
    }
}
[download]

A few examples:

c:\test>742277.pl
857720
z$
Found 38464 matches in  1.86 seconds; Display? n
zz$
Found 1481 matches in  1.80 seconds; Display? n
zzz$
Found 55 matches in  1.78 seconds; Display? n
^a.*zzz$
Found 3 matches in  1.00 seconds; Display? y
afyjhcukywpbzzz
azhmwxjxncbaozzz
atzzz
[aeiou]{6]
Found 0 matches in  0.39 seconds; Display? n
[aeiou]{6}
Found 99 matches in  0.43 seconds; Display? n
[aeiou]{7}
Found 23 matches in  0.45 seconds; Display? n
[aeiou]{8}
Found 2 matches in  0.43 seconds; Display? y
ouaueeie
acxftoeeoeuiofoj
^[aeiou]+$
Found 3 matches in  0.44 seconds; Display? y
ieouea
iuaoea
ouaueeie
^for
Found 54 matches in  0.67 seconds; Display? n
^for.*ness
Found 0 matches in  0.39 seconds; Display?
^for.*n
Found 14 matches in  0.50 seconds; Display? y
foromnfikqfarwgedn
fornsdlluobiqdmacjl
forhkzmalfewhaohknrl
fornfxdprljcckkh
fortgntqbpbnmmtpk
forkqvimulibcfxwyjnce
formslskcoazusn
fornywxhqt
forndbzjfm
forfnmhhvdcntt
forxhbcimsggnhhmbiqze
foruhvpekgtnialyifyi
forcnmamdsx
forcvxnb
[download]