Fast Pattern Matching in Compressed Text using Wavelet Tree

REFERENCES

• R. Baeza-Yates. “Efficient text searching,” Ph. D. thesis, Dept. of Comp. Sci., Univ. of Waterloo, 1989.
   Google Scholar
• B. S. Baker. “A theory of parameterized pattern matching: Algorithms and applications,” in Proc. of the 25th ACM Symposium on the Theory of Comput., ACM Press, New York, 1993, pp. 71–80.
   Google Scholar
• R. Boyer and J. Moore. (1977). A fast string searching algorithm,” Commun. ACM 20 (10), pp. 762–772.
   Web of Science ®Google Scholar
• A. Goel and R. Prasad. (2014). “Efficient indexing techniques for record matching and deduplication,” Int. J. Comput. Vision Robot. 4 (1/2), pp. 75–85.
   Google Scholar
• S. Tevatia and R. Prasad. (2014). “Multi-patterns parameterized matching with application to computational biology,” Int J. Inform. Commun. Technol. 7 (4/5), pp. 469–480.
   Google Scholar
• R. Beal and D.A. Adjeroh. “Compressed parameterized pattern matching,” in IEEE Data Compression Conf., Snowbird, UT, USA March 20–22, 2013, pp. 461–470.
   Google Scholar
• R. Garg, R. Prasad and S. Agarwal. “Fast parameterized word matching on compressed text,” IEEE Int Conf.on ICCCT, MNNIT, Allahabad, India, Sept 26–28, 2014, pp. 317–321.
   Google Scholar
• R. Prasad and R. Garg. Efficient multi-word parameterized matching on compressed text,” in Proc. of IEEE Int. Conf. on ICAST, Oct. 29-31, Ota, Nigeria, 2014, pp. 1–6.
   Google Scholar
• A. Amir, G. Benson and M. Farach. (1996). “Let sleeping files lie: Pattern matching in Z-compressed files,” J. Comput Sys Sci. 52, pp. 299–307.
   Web of Science ®Google Scholar
• L.G. Asieniec and W. Rytter. Almost optimal fully LZW-compressed pattern matching,” in Proc. of IEEE Data Compression Conf., Snowbird, UT, USA, March 29-31, 1999, pp. 316–325.
   Google Scholar
• M. Farach and M. Thorup. String matching in Lempel-Ziv compressed strings”, in Proc. of Annual ACM Symposium on the Theory of Comput., Las Vegas, Nevada, USA, May 29-June 1, 1995, pp. 703–712.
   Google Scholar
• D.A. Huffman. “A method for the construction of minimum-redundancy codes,” in Proc. of the IRE, 40 (9), 1952, pp. 1098–1101.
   Google Scholar
• M. Karpinski, W. Rytter and A. Shinohara. (1997). An efficient pattern-matching algorithm for strings with short descriptions,” Nordic J. Comput. 4 (2), pp. 172–186.
   Google Scholar
• Y. Lifshits. “Processing compressed texts: A tractability border,” in Proc. of Combinatorial Pattern Matching, LNCS, Springer, Heidelberg, vol. 4580, 2007, pp. 228–240.
   Google Scholar
• E.S. Moura, G. Navarro, N. Ziviani and R. Baeza-Yates. “Fast searching on compressed text allowing errors,” in Proc. 21st Annual Int. ACM SIGIR Conf. Res. Dev Information Retrieval, Melbourne, Australia, 1998, pp. 298–306.
   Google Scholar
• T. Eilam-Tzoreff and U. Vishkin. (1988). “Matching patterns in strings subject to multi-linear transformations,” Theoretical Comput Sci. 60 (3), pp. 231–254.
   Web of Science ®Google Scholar
• D. Knuth, J. Morris and V. Pratt. (1977). “Fast pattern matching in strings,” SIAM J. Comput. 6 (2), pp. 323–350.
   Google Scholar
• A. Mukherjee and T. Acharya, Compressed pattern-matching,” in Proc. IEEE Data Compression Conf., Snowbird, UT, Mar. 1994, pp. 468.
   Google Scholar
• E.S. Moura, G. Navarro, N. Ziviani and R. Baeza-Yates. (2000). “Fast and flexible word searching on compressed text,” ACM Trans. Inf. Syst. 18 (2), pp. 113–139 .
   Web of Science ®Google Scholar
• N. Ziviani, E.S. Moura, G. Navarro and R. Baeza-Yates. (2000). Compression: A key for next generation text retrieval systems,”IEEE Comput. 33 (11), pp. 37–44.
   Google Scholar
• E.S. Moura, G. Navarro, N. Ziviani and R. Baeza-Yates. Direct pattern matching on compressed text,” in Proc. of 5th Int.Symposium on String Processing and Information Retrieval (SPIRE’98), IEEE Computer Soc., Washington, 1998, pp. 90–95.
   Google Scholar
• E.S. Moura, G. Navarro and R. Baeza-Yates. (2000). Fast and flexible word searching on compressed text,” ACM Trans. Inf. Syst. 18 (2), pp. 113–139.
   Web of Science ®Google Scholar
• A. Gupta and S. Agarwal. (2008). A scheme that facilitates searching and partial decompression of textual documents,” Intl. J. Adv. Comp. Eng. 1 (2), pp. 99–109.
   Google Scholar
• A. Gupta and S. Agarwal. “A novel approach of data compression for dynamic data,” in Proc. of IEEE 3rd Int. Conf. on System of Systems Eng., California, USA, 2008, pp. 1–6.
   Google Scholar
• R. Grossi, A. Gupta, and J. Vitter. “High-order entropy compressed text indexes,” in Proc. of 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 03), Baltimore, MD, Jan. 2003, pp. 841–850.
   Google Scholar
• N.R. Brisaboa, Y. Cillero, A. Fariña, S. Ladra, and O. Pedreira. “A new approach for document indexing using wavelet trees,” in Proc. Database and Expert Systems Applications, DEXA '07, 18th Int. Workshop, Regensburg, Germany, Sept. 3–7, 2007, pp. 69–73.
   Google Scholar
• R. Khetan, S. Agarwal and R. Prasad. (2016). “An efficient approach towards compressed parameterized word matching using wavelet tree,” J. Inform. Optimization Sci. 37 (2), pp. 285–301.
   Web of Science ®Google Scholar
• N.R. Brisaboa, A. Fariña, S. Ladra, G. Navarro. “Implicit Indexing of Natural Language Text by Reorganizing Bytecodes,” in Information Retrieval, 15 (6), Springer Netherlands, Hingham, MA ( Estados Unidos), 2012, pp. 527–557.
   Google Scholar
• G. Navarro. (2014). “Wavelet trees for all.” J. Discrete Algorithms, vol. 25, Mar. 2014, pp. 2–10.
   Google Scholar
• F. Claude, and G. Navarro. “Practical rank/select queries over arbitrary sequences.” in Proc. of the 15th Int. Symp.on String Processing and Information Retrieval (SPIRE), LNCS 5280, Melbourne, Australia, Nov. 2008, pp.176–187.
   Google Scholar
• P. Ferragina, G. Manzini, V. Mäkinen, and G. Navarro. (2007). “Compressed representations of sequences and full-text indexes.” ACM Trans. Algorithms, 3 (2), pp. 20–24.
   Google Scholar
• G. Navarro, and V. Makinen. (2007). “Compressed full-text indexes,” ACM Comp. Survey, vol. 39, pp. 1–61.
   Web of Science ®Google Scholar
• A. Moffat. (1989). “Word-based text compression,” Softw: Pract. Exper. 19 (2), pp. 185–198.
   Web of Science ®Google Scholar
• E. S. Moura, G. Navarro, N. Ziviani, and R. Baeza-Yates, “Fast searching on compressed text allowing errors,” in Proc. of the 21^st Annual Int. ACM SIGIR Conf. on Res. and Dev. in Information Retrieval, Melbourne, Australia, 1998, pp. 298–306.
   Google Scholar
• T. Tao and A. Mukherjee. (2005). “Pattern matching in LZW compressed file,” IEEE Trans. Comput. 54 (8), pp. 929–938.
   Web of Science ®Google Scholar
• P. Gawrychowski. “Optimal pattern matching in LZW compressed strings, “in Proc. Symp. on Discrete Algorithms, SIAM, San Francisco, CA, Jan. 2011, pp. 362–372.
   Google Scholar
• P. Gawrychowski. “Pattern matching in Lempel-Ziv compressed strings: Fast, simple, and deterministic,” in Proc. Eur Symp. on Algorithms, Springer, Saarbrücken, Germany, Sept. 2011, pp. 421–432.
   Google Scholar
• P. Gawrychowski. “Tying up the loose ends in fully LZW-compressed pattern matching,” in Proc. Symposium on Theoretical Aspects of Computer Sciences, Paris, France, vol. 14, Mar. 2012, pp. 624–635.
   Google Scholar
• A. Je˙z. “Faster fully compressed pattern matching by recompression,” in Proc. of Int Colloquium on Automata, Languages and Programming, Springer, Warwick, UK, vol. 7391, Jul. 2012, pp. 533–544.
   Google Scholar
• M. Gu, M. Farach and R. Beigel. “An efficient algorithm for dynamic text indexing,” in Proc. of Symposium on Discrete Algorithms, ACM/SIAM, Arlington, VA, Jan. 1994, pp. 697–704.
   Google Scholar
• N. R. Brisaboa, A. Fariña, S. Ladra and G. Navarro. “Reorganizing compressed text”, in Proc. of the 31th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 2008), ACM Press, Singapore, pp. 139–146, 2008.
   Google Scholar
• S. Tevatia, R. Prasad, and D. Rai, “An offensive algorithm for multi-pattern parameterized string matching,” in Proc. of IEEE Int. Conf. (ICCCCM-13), Allahabad, India, August 3–4, 2013, pp.1–5.
   Google Scholar
• M.D. Araujo, G. Navarro and N. Ziviani. “Large text searching allowing errors”. in R. Baeza-Yates, Ed., Proc. of the Fourth South American Workshop on string Proc., Careton University Press, Chile, vol. 8, 1997, pp. 2–20.
   Google Scholar
• E.S. Moura, G. Navarro and N. Ziviani. “Indexing compressed text.” in R. Baeza-Yates, Ed., in Proc. of the Fourth South American Workshop on string Proc., Careton University Press, Chile, vol. 8, 1997, pp. 95–111.
   Google Scholar