Some follow-ups to Mike's comments. > Be sure to test this is really faster: you'll need to add a step to > resolve word -> id (eg via hashmap) which may net/net add cost because > the FST can incrementally (quickly) determine a word doesn't exist > with a given prefix. FST can also do better sharing (less RAM) of
This is a tradeoff that you need to make for your particular type of data. The number of unique words in your patterns and the fanout of initial letter prefixes will matter here. For me by-word ID was more effective because I had a relatively small (in-memory) term dictionary and wanted to limit the number of states tracked at once. With the letter-by-letter approach the number of states to track will grow. > However, there is a cool paper that Robert found: > http://www.cis.uni-muenchen.de/people/Schulz/Pub/dictle5.ps Yeah... If we had full fst library and lots of memory pattern matching (and rewriting) is essentially a finite, determinized regexp. So it can be definitely made very efficient using fsts, the question is how much processing needs to be done to construct an automaton for this. That paper looks cool but I didn't have time to look deeply into it -- the simple approach works way (orders of magnitude) below the set speed threshold required by the client. Again -- even with degenerate cases the processing time is bounded by the longest search pattern (there is no backtracking, only concurrent state tracking and possibly overlap resolution afterwards). > Still, I would first try the obvious approach (use FST the way > SynFilter does) and see if it's fast enough. +1. D. --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
