Abstract
Locally consistent parsing (LCP) is a context sensitive partitioning method which achieves partition consistency in (almost) linear time. When iteratively applied, LCP followed by consistent block labeling provides a powerful tool for processing strings for a multitude of problems. In this paper we summarize applications of LCP in approximating well known distance measures between pairs of strings in (almost) linear time.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alstrup, S., Stølting Brodal, G., Rauhe, T.: Pattern matching in dynamic texts. In: SODA 2000: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, pp. 819–828 (2000)
Bar-Yossef, Z., Jayram, T.S., Krauthgamer, R., Kumar, R.: Approximating edit distance efficiently. In: IEEE Symposium on Foundations of Computer Science, FOCS (2004)
Batu, T., Ergun, F., Cenk Sahinalp, S.: Oblivious string embeddings and edit distance approximations. Technical Report TR2005-11, School of Computing Science, Simon Fraser University (2005)
Cole, R., Hariharan, R.: Approximate string matching: A simpler faster algorithm. In: SODA, pp. 463–472 (1998)
Cole, R., Vishkin, U.: Deterministic coin tossing and accelerating cascades: Micro and macro techniques for designing parallel algorithms. In: ACM Symposium on Theory of Computing, STOC (1986)
Cormode, G., Muthukrishnan, S.: The string edit distance matching problem with moves. In: SODA, pp. 667–676 (2002)
Cormode, G., Muthukrishnan, S.: Substring compression problems. SODA (2005)
Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing 13(2), 338–355 (1984)
Indyk, P., Motwani, R.: Approximate nearest neighbors: Towards removing the curse of dimensionality. In: STOC, pp. 604–613 (1998)
Kushilevitz, E., Ostrovsky, R., Rabani, Y.: Efficient search for approximate nearest neighbor in high dimensional spaces. In: STOC, pp. 614–623 (1998)
Masek, W.J., Paterson, M.S.: A faster algorithm computing string edit distances. Journal of Computer and System Sciences 20(1), 18–31 (1980)
McCreight, E.M.: A space-economical suffix tree construction algorithm. J. ACM 23(2), 262–272 (1976)
Mehlhorn, K., Sundar, R., Uhrig, C.: Maintaining dynamic sequences under equality-tests in polylogarithmic time. In: SODA, pp. 213–222 (1994)
Muthukrishnan, S., Cenk Sahinalp, S.: Approximate nearest neighbors and sequence comparison with block operations. In: STOC, pp. 416–424 (2000)
Cenk Sahinalp, S., Vishkin, U.: On a parallel-algorithms method for string matching problems. In: Bonuccelli, M.A., Crescenzi, P., Petreschi, R. (eds.) CIAC 1994. LNCS, vol. 778, pp. 22–32. Springer, Heidelberg (1994)
Cenk Sahinalp, S., Vishkin, U.: Symmetry breaking for suffix tree construction. In: STOC, pp. 300–309 (1994)
Cenk Sahinalp, S., Vishkin, U.: Data compression using locally consistent parsing. UMIACS Technical Report (1995)
Cenk Sahinalp, S., Vishkin, U.: Efficient approximate and dynamic matching of patterns using a labeling paradigm. In: IEEE Symposium on Foundations of Computer Science, FOCS (1996)
Schieber, B., Vishkin, U.: On finding lowest common ancestors: Simplification and parallelization. SIAM Journal on Computing 17(6), 1253–1262 (1988)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Batu, T., Sahinalp, S.C. (2005). Locally Consistent Parsing and Applications to Approximate String Comparisons. In: De Felice, C., Restivo, A. (eds) Developments in Language Theory. DLT 2005. Lecture Notes in Computer Science, vol 3572. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11505877_3
Download citation
DOI: https://doi.org/10.1007/11505877_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26546-7
Online ISBN: 978-3-540-31682-4
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.