Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Creating an index on a string-collection

by morgon (Priest)
on Feb 08, 2009 at 18:47 UTC ( #742277=perlquestion: print w/replies, xml ) Need Help??

morgon has asked for the wisdom of the Perl Monks concerning the following question:

Monks,

assume I have a large collection of strings (let's say a million of them) each associated with a timestamp.

I now want to be able to query this collection for all strings matching a given regex, possibly constrained by upper and/or lower limits on the associated timestamp, so e.g. a query would be "find all strings matching /abc.*/", another one would be "find all strings matching /x*y/ where the associated timestamps are of last week".

Evidently I could put all the data into a database and use SQL for the queries but I wonder if there is a good algorithm to build a suitable index for such queries and do all the querying in pure perl - in such a way of course that answering a query should not take more than a few seconds.

If building an index that supports arbirary regexes is too difficult I could make do with shell-style globbing.

Any ideas?

  • Comment on Creating an index on a string-collection

Replies are listed 'Best First'.
Re: Creating an index on a string-collection
by moritz (Cardinal) on Feb 08, 2009 at 19:01 UTC
    Since databases can build an index over the strings that works for simple regexes and shell-like glob patterns, of course such an algorithm exists. And since many databases are open source, you can just look at their implementation (for example mysql supports fulltext indexes and patterns that contain simple wildcards).

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

Re: Creating an index on a string-collection
by samtregar (Abbot) on Feb 08, 2009 at 21:35 UTC
    A few seconds is a long time to search a set of 1 million strings on a modern machine, so I don't think you'll need to try very hard. If your searches always have a fixed start or a fixed end you could use Tree::Trie. Here's an example that handles 'foo*' and '*foo' searches:

    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"; }

    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

    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

Re: Creating an index on a string-collection
by perrin (Chancellor) on Feb 08, 2009 at 21:38 UTC

    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.

Re: Creating an index on a string-collection
by CountZero (Bishop) on Feb 08, 2009 at 22:51 UTC
    One thing to consider is the cost to transform these strings into a format suitable for your regex to work with them. Presumably these strings live on your filesystem. They could all be in one huge file or each string can have its own file or anything in between these extremes.

    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?

    CountZero

    A program should be light and agile, its subroutines connected like a string of pearls. The spirit and intent of the program should be retained throughout. There should be neither too little or too much, neither needless loops nor useless variables, neither lack of structure nor overwhelming rigidity." - The Tao of Programming, 4.1 - Geoffrey James

Re: Creating an index on a string-collection
by BrowserUk (Pope) on Feb 09, 2009 at 04:13 UTC

    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; } }

    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

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (6)
As of 2020-08-07 14:06 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Which rocket would you take to Mars?










    Results (45 votes). Check out past polls.

    Notices?