Submitted by mam on January 19, 2007 - 10:00
Fri Jan 19
Juha Kärkkäinen
Faster Filters for Approximate String Matching
Abstract:
The approximate string matching problem is to find the occurrences of a pattern string in a text string while allowing some number of differences between the pattern and an occurrence. The indexed version of the problem uses a precomputed text index to speed up the matching. The best practical algorithms for indexed approximate string matching are heuristic algorithms that use a filter criterion to identify areas of text that might contain an occurrence and then check only those areas. Among the best filter criteria are factor filters. We introduce a new class of filters called suffix filters, which are stronger (i.e., produce fewer areas to check) than factor filters. Experiments demonstrate that algorithms based on suffix filters are faster and can handle a larger number of differences than those based on factor filters.
Please note the change of hall: B222 (was C222)
HIIT seminars in spring 2007 will be held in hall **B222** of Exactum, on Fridays starting at 10:15 a.m. Coffee available from 10.
Juha Kärkkäinen
Faster Filters for Approximate String Matching
Abstract:
The approximate string matching problem is to find the occurrences of a pattern string in a text string while allowing some number of differences between the pattern and an occurrence. The indexed version of the problem uses a precomputed text index to speed up the matching. The best practical algorithms for indexed approximate string matching are heuristic algorithms that use a filter criterion to identify areas of text that might contain an occurrence and then check only those areas. Among the best filter criteria are factor filters. We introduce a new class of filters called suffix filters, which are stronger (i.e., produce fewer areas to check) than factor filters. Experiments demonstrate that algorithms based on suffix filters are faster and can handle a larger number of differences than those based on factor filters.
Please note the change of hall: B222 (was C222)
HIIT seminars in spring 2007 will be held in hall **B222** of Exactum, on Fridays starting at 10:15 a.m. Coffee available from 10.
Events:
Last updated on 18 Jan 2007 by Martti Mäntylä - Page created on 19 Jan 2007 by Martti Mäntylä