A Metric Index for Approximate String Matching

@misc{citeulike:158396, abstract = {We present a radically new indexing approach for approximate string matching. The scheme uses the metric properties of the edit distance and can be applied to any other metric between strings. We build a metric space where the sites are the nodes of the suffix tree of the text, and the approximate query is seen as a proximity query on that metric space. This permits us finding the R occurrences of a pattern of length m in a text of length n in average time O(m log n+m +R), using...}, author = {Avez, E. and Navarro, G. }, citeulike-article-id = {158396}, keywords = {approximate, indexing, matching, string}, posted-at = {2005-04-11 15:32:26}, priority = {3}, title = {A Metric Index for Approximate String Matching}, url = {http://citeseer.ist.psu.edu/avez02metric.html}, year = {2002} }

TY - GEN ID - citeulike:158396 L3 - citeulike-article-id:158396 TI - A Metric Index for Approximate String Matching N2 - We present a radically new indexing approach for approximate string matching. The scheme uses the metric properties of the edit distance and can be applied to any other metric between strings. We build a metric space where the sites are the nodes of the suffix tree of the text, and the approximate query is seen as a proximity query on that metric space. This permits us finding the R occurrences of a pattern of length m in a text of length n in average time O(m log n+m +R), using... KW - approximate KW - indexing KW - matching KW - string AU - Avez, E AU - Navarro, G PY - 2002/// UR - http://citeseer.ist.psu.edu/avez02metric.html ER -