-----Original Message----- From: Ronald J Kimball Sent: Thursday, July 09, 2009 10:18 AM Subject: Re: [Boston.pm] binary search on a list of sorted strings in memory
> Another option would be a dictionary tree, in which each node is a single > letter, so each word is represented by a path through the tree. I don't > know how suitable it would be for this purpose. It is a cool structure > though. :) Back from CS algorithm class, the Boyer-Moore algorithm seems ideally suited for a fast pattern matching scheme that you are looking for. Because it searches in reverse order and can quickly find & abandon target strings that do *not* match, it seems its worth a look. Plenty of Google hits to describe it. Apparently, Perl's RE optimizer uses this for simple string searches (http://mkweb.bcgsc.ca/intranet/perlbook/prog/ch24_02.htm). -Nilanjan _______________________________________________ Boston-pm mailing list [email protected] http://mail.pm.org/mailman/listinfo/boston-pm
