Real-time indexing over fixed finite alphabets

ABSTRACT

The quest for a real-time indexing algorithm is ove three decades old. To date there is no convincing understandable solution to this problem. This paper provides a real-time indexing algorithm over a constant sized alphabet. Assuming the text is arriving at a constant rate, the algorithm spends O(1) time on every text symbol. Whenever a length m pattern is given, the algorithm decides in time O(m) whether there is an occurrence of the pattern in the text thus far.

REFERENCES

• 1: A. Amir, T. Kopelowitz, M. Lewenstein, and N. Lewenstein. Towards real-time suffix tree construction. In Proc. 12th Symposium on String Processing and Information Retrieval (SPIRE), volume 3772 of LNCS, pages 67--78. Springer, 2005.
• 2: M. Farach, Optimal suffix tree construction with large alphabets, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.137, October 19-22, 1997
• 3: Zvi Galil, On converting on-line algorithms into real-time and on real-time algorithms for string-matching and palindrome recognition, ACM SIGACT News, v.7 n.4, p.26-30, November-Decmeber 1975 [doi>10.1145/990502.990505]
• 4: Roberto Grossi , Giuseppe F. Italiano, Efficient Techniques for Maintaining Multidimensional Keys in Linked Data Structures, Proceedings of the 26th International Colloquium on Automata, Languages and Programming, p.372-381, July 11-15, 1999
• 5: Juha Kärkkäinen and Peter Sanders. Simple linear work suffix array construction. In Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP 03), pages 943--955, 2003. LNCS 2719.
• 6: S. Rao Kosaraju, Real-time pattern matching and quasi-real-time construction of suffix trees (preliminary version), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.310-316, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195170]
• 7: Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.319-327, January 22-24, 1990, San Francisco, California, United States
• 8: Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
• 9: A. O. Slisenko. Recognition of palindromes by multi-head turing machines. In Proc. of the Steklov Math. Inst., volume 129, pages 30--202. Acad. of Sciences of the USSR, 1973.
• 10: E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14:249--260, 1995.
• 11: P. Weiner. Linear pattern matching algorithm. Proc. 14 IEEE Symposium on Switching and Automata Theory, pages 1--11, 1973.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching; Computations on discrete structures

General Terms:
Algorithms, Design, Management, Theory

Keywords:
pattern matching, quasi real time, real time, suffix tree