A Real-Time Algorithm for Searching for Substrings of a Pattern in Online Text Stream: An Alternative to Suffix Trees and Finite Automaton

Authors

  • Vinod Prasad UTAS Sur, Sultanate of Oman

DOI:

https://doi.org/10.14738/tecs.114.15065

Keywords:

Approximate String Matching, Similarity Search, Substring Search

Abstract

In the field of similarity search, very little effort has been made to process the text without using suffix trees or automata. Most of the algorithms developed in the past use data structures and methods outlined above to accelerate the search process. However, their costly maintenance has always been a cause of concern. Let, T be a text of size N, and P be a pattern of size M. We present highly practical algorithms to process a real-time stream of text characters. The algorithm reports all substrings of pattern P in the text stream T as they appear in the stream. This is highly useful in detecting patterns in the data stream in real-time, for example, viruses and malware can be detected as they appear in the data stream. Additionally, the algorithm can be used to find the longest common substring(s) between two given strings. We achieved the stated goals without using any sophisticated data structure such as a suffix tree or finite automaton. For an alphabet size σ the algorithm runs in O(M) space, and O (MN/σ) expected time, which simplifies to O(N) for M ≤ σ. We also provide experimental results to support our claim.

References

Morris J., and Pratt V. A linear pattern matching algorithm. Technical Report 40, Computing Center, University of California, Berkeley, 1970

Aho A., and Corasick M. Efficient string searching: An aid to bibliographic search. Communications of the ACM, 18, pp. 333-40, 1975

Knuth D., Morris J., and Pratt V. Fast pattern matching in strings. SIAM Journal on Computing, 6, pp. 323-50, 1977.

Boyer R., and Moore S. A fast string searching algorithm. Communications of the ACM, 20, pp. 762–772, 1977.

Horspool N. Practical fast searching in strings. Software Practice and Experience, 10, pp. 501–506. 1980

Karp R., and Rabin M. Efficient randomized pattern-matching algorithms. IBM Journal Research and Development, 31, pp. 249-60. 1987.

Levenshtein I. Binary codes capable of correcting deletions, insertions, and reversals, Soviet Physics Doklady, 10 (8), pp. 707–710. 1966

Hamming R. Error detecting and error correcting codes, Bell System Technical Journal, 29 (2), pp. 147–160, 1950

Lowrance R., and Wagner A. An extension of the string-to-string correction problem, Journal of the ACM

Sellers P. The theory and computation of evolutionary distances. Journal of Algorithms, 1, pp. 359–373,

Masek W., and Paterson M. A faster algorithm for computing string edit distances. Journal of Computer System Sciences, 20, pp. 18–31, 1980

Ukkonen E. Finding approximate patterns in strings. Journal of Algorithms, 6, pp. 132–137, 1985.

Landau G., and Vishkin U. Fast string matching with k differences. Journal of Computer System Sciences,

Galil Z., and Giancarlo R. Data structures and algorithms for approximate string matching. Journal of Complexity, 4, pp. 33–72, 1988

Landau G., and Vishkin U. Fast parallel and serial approximate string matching. Journal of Algorithms, 10, pp. 157–169, 1989

Galil Z., and Park K. An improved algorithm for approximate string matching. SIAM Journal on Computing, 19, pp. 989–999, 1990. URL: http://dx.doi.org/10.14738/tecs.114.15065 169

Ukkonen E., and Wood D. Approximate string matching with suffix automata. Algorithmica, 10, pp. 353–364, 1993.

Cole R., and Hariharan R. Approximate string matching: a simpler faster algorithm. Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, pp. 463–472, 1998.

Myers G. A fast bit-vector algorithm for approximate string matching based on dynamic programming. Journal of the ACM, 46(3), pp. 395–415, 1999.

Wu S., and Manber,U. Agrep—a fast approximate pattern-matching tool. Proceedings of the USENIX Technical Conference. USENIX Association, Berkeley, CA, USA. pp. 153–162. 1992.

Wu S., Manber U., and Myers E. A subquadratic algorithm for approximate limited expression matching. Algorithmica 15(1), pp. 50–67, 1996

Melichar B. String matching with k differences by finite automata. Proceedings of the International Congress on Pattern Recognition (ICPR ’96), pp. 256–260, 1996.

Tarhio J., and Ukkonen E. Approximate Boyer–Moore string matching. SIAM Journal of Computing, 2, pp. 243–260, 1993

Chang W., and Lawler E. Sublinear approximate string matching and biological applications. Algorithmica,

Takaoka T. Approximate pattern matching with samples. Proceedings of the ISAAC 1994, L.N.C.S Springer Verlag, pp. 234–242, 1994.

Baeza-Yates R., and Navarro G. Faster approximate string matching. Algorithmica, 23(2), pp. 127-158, 1999.

Landau G., and Vishkin, U. Efficient string with k mismatches. Theoretical Computer Science, 43, 239-249,

Weiner P. In the proceedings of the 14th Annual IEEE Symposium on Switching and Automata Theory, pp. 1–11, 1973.

McCreight E. A space-economical suffix tree construction algorithm, Journal of ACM 23, pp. 262-272, 1976.

Ukkonen E. On-line construction of suffix trees, Algorithmica 41. pp. 249-260, 1995.

Farach M. Optimal suffix tree construction with large alphabets. 38th IEEE Symposium on Foundations of Computer Science, pp. 137–143, 1997.

Gusfield D. Algorithms on strings, trees and sequences. Computer Science and Computational Biology, Cambridge University Press, ISBN 0-521-58519-8, 1999.

Galil Z., Giancarlo R. Improved string matching with k mismatches, SIGACT News 17 (4) pp. 52–54, 1986.

Amir A., Lewenstein M., and Porat E. A Faster algorithms for string matching with k mismatches. Journal of Algorithms, pp. 257-275, 2004.

Abrahamson K. Generalized string matching, SIAM Journal of Computing, 16 (6), pp. 1039–1051, 1987.

Baeza-Yates, R., Perleberg C.H. Fast and practical string matching. Information Processing Letters, 59, pp. Prasad, V. (2023). A Real-Time Algorithm for Searching for Substrings of a Pattern in Online Text Stream: An Alternative to Suffix Trees and Finite

Kurtz S. Reducing the space requirement of suffix trees, Software—Practice & Experience, 29(13),pp.1149-1171, 1999.

Amir A., Kopelowitz T., Lewenstein M., and Lewenstein N. Towards real-time suffix tree construction string processing and information retrieval. 12th International conference SPIRE 2005, Lecture Notes in Computer Science, pp 67-78, 2005.

Breslauer D., Giuseppe F. Near real-time suffix tree construction via the fringe marked ancestor problem. Journal of Discrete Algorithms, 18, pp. 32-48, 2013

Manber U., and Myers E. Sufix arrays: A new method for on-line string searches, SIAM Journal on Computing, 22(5), pp. 935–948, 1993.

Grossi R., and Vitter J. Compressed suffix arrays and suffix trees, with applications to text indexing and string matching, SIAM Journal on Computing, 35(2), pp. 378-407, 2005.

Sadakane K. Compressed suffix trees with full functionality. Theory of Computer Systems, 41(4) pp. 589-607, 2007.

Russo L., Navarro G., and Oliveira A. Proceedings of the 8th Latin American conference on Theoretical informatics, Springer-Verlag, pp. 362-373, 2008.

Alimaki V., Gerlach W., Dixit K., and Makinen V. Engineering a compressed suffix tree implementation. In the Proceedings of the 6th WEA, pp. 217-228, 2007.

Crochemore M., Hancart C., and Lecroq T. Algorithms on Strings, Cambridge University Press, 2007.

Navarro G. A guided tour to approximate string matching. ACM Computing Surveys, 33 (1), pp. 31–88, 2001.

Boytsov L. 2011. Indexing methods for approximate dictionary searching: Comparative analysis, ACM JEA 16 (1), pp. 1–9, 2011.

http://www.ncbi.nlm.nih.gov/protein/

Vinod Prasad. A Character Frequency based Approach to Search for Substrings of a Circular Pattern and its Conjugates in an Online Text, Computer Science Journal AGH University of Science and Technology, Poland, April 2021

Vinod Prasad. A Novel Mathematical Model for Similarity Search in Pattern Matching Algorithms, Journal of Computer and Communications, Sept. 2020.

Vinod Prasad. A Novel Algorithm for String Matching with Mismatches, 5th International Conference on Pattern Recognition Applications and Methods, Rome, ISBN 978-989-758-173-1, Feb 24-26, 2016.

Downloads

Published

2023-09-02

How to Cite

Prasad, V. (2023). A Real-Time Algorithm for Searching for Substrings of a Pattern in Online Text Stream: An Alternative to Suffix Trees and Finite Automaton. Transactions on Engineering and Computing Sciences, 11(4), 158–171. https://doi.org/10.14738/tecs.114.15065