Approximate string matching in sublinear expected time

@inproceedings{citeulike:1587111, abstract = {The <e1>k</e1> differences approximate string matching problem specifies a text string of length <e1>n</e1>, a pattern string of length <e1>m</e1>, and the number <e1>k</e1> of differences (insertions, deletions, substitutions) allowed in a match, and asks for every location in the text where a match occurs. Previous algorithms required at least <e1>O</e1>(<e1>nk</e1>) time. When <e1>k</e1> is as large as a fraction of <e1>m</e1>, no substantial progress has been made over <e1>O </e1>(<e1>nm</e1>) dynamic programming. The authors have investigated much faster algorithms for restricted cases of the problem, such as when the text string is random and errors are not too frequent. They have devised an algorithm that, for <e1>k</e1>\&lt;<e1>m</e1>/log <e1>n</e1>+ <e1>O</e1>(1), runs in time <e1>O</e1>((<e1>n</e1>/<e1>m</e1>)<e1>k</e1> log <e1>n</e1>) on the average. In the worst case their algorithm is <e1>O</e1>(<e1>nk</e1>), but it is still an improvement in that it is very practical and uses only <e1>O</e1>(<e1>n</e1>) space compared with <e1>O</e1>(<e1>n</e1>) or <e1>O</e1>(<e1>n</e1>²). The authors define an approximate substring matching problem and give efficient algorithms based on their techniques. Special cases include several applications to genetics and molecular biology}, author = {Chang, W. I. and Lawler, E. L. }, booktitle = {Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on}, citeulike-article-id = {1587111}, journal = {Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on}, keywords = {approximate\_string\_matching, edit\_distance}, pages = {116--124 vol.1}, posted-at = {2007-08-24 03:27:53}, priority = {2}, title = {Approximate string matching in sublinear expected time}, url = {http://ieeexplore.ieee.org/xpls/abs\_all.jsp?arnumber=89530}, year = {1990} }

TY - CONF ID - citeulike:1587111 L3 - citeulike-article-id:1587111 TI - Approximate string matching in sublinear expected time T2 - Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on JF - Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on SP - 116 EP - 124 vol.1 N2 - The <e1>k</e1> differences approximate string matching problem specifies a text string of length <e1>n</e1>, a pattern string of length <e1>m</e1>, and the number <e1>k</e1> of differences (insertions, deletions, substitutions) allowed in a match, and asks for every location in the text where a match occurs. Previous algorithms required at least <e1>O</e1>(<e1>nk</e1>) time. When <e1>k</e1> is as large as a fraction of <e1>m</e1>, no substantial progress has been made over <e1>O </e1>(<e1>nm</e1>) dynamic programming. The authors have investigated much faster algorithms for restricted cases of the problem, such as when the text string is random and errors are not too frequent. They have devised an algorithm that, for <e1>k</e1>&lt;<e1>m</e1>/log <e1>n</e1>+ <e1>O</e1>(1), runs in time <e1>O</e1>((<e1>n</e1>/<e1>m</e1>)<e1>k</e1> log <e1>n</e1>) on the average. In the worst case their algorithm is <e1>O</e1>(<e1>nk</e1>), but it is still an improvement in that it is very practical and uses only <e1>O</e1>(<e1>n</e1>) space compared with <e1>O</e1>(<e1>n</e1>) or <e1>O</e1>(<e1>n</e1>²). The authors define an approximate substring matching problem and give efficient algorithms based on their techniques. Special cases include several applications to genetics and molecular biology KW - approximate_string_matching KW - edit_distance AU - Chang, WI AU - Lawler, EL PY - 1990/// UR - http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=89530 ER -