Role of Suffix Array in String Matching: A Comparative Analysis
Keywords:
Suffix sorting, Suffix array, fm index, trie structureAbstract
Text search is a classical problem in Computer Science, which reside in many data-intensive applications. For this problem, suffix arrays are the most widely known and used data structures, which enabling fast searches for phrases, terms, substrings and regular expressions in large texts. Potential application domains of this method includes large-scale search services, such as Web search engines, plagiarism checker where it is necessary to efficiently process intensive traffic streams of on-line queries. Suffix array is an effective way to construct the index of the full text i.e. sorted array of all suffix of string which is important for different kind of applications, perhaps most notably string matching, string discovery and block-sorting data compression. This paper elucidates intensive research toward efficient construction of suffix arrays with algorithms striving not only to be fast, but also “lightweight” (in the idea that they use small working memory).
References
Member, Ubi;Myers, Geene. “Suffix arrays:a new method for online string search” First annual ACM-SIAM Journel on Computing 22, (1993).
Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno "Replacing suffix trees with enhanced suffix arrays". Journal of Discrete Algorithms 2: 53, (2004).
Gog, Simon, Alistair Moffat, J. Culpepper, Andrew Turpin, and Anthony Wirth. "Large-scale pattern search using reduced-space on-disk suffix arrays." IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 26, NO. 8, AUGUST 2014.
Ahmed Abdelhadi, A. H. Kandil1 and Mohamed Abouelhoda. “Cloud-based Parallel Suffix Array Construction based on MPI ” Middle East Conference on Biomedical Engineering (MECBME) ,(2014).
Stefan Burkhardt, Andreas Crauser, Eric Rivals, Hans, martin. “q-gram based database searching using suffix array (quasar)” ,2006.
Diego Arroyuelo, Carolina Bonacic, Veronica Gil-Costa, Mauricio Marin Gonzalo Navarro. “Distributed text search using suffix arrays” Elsevier Journal ,28 june 2014.
Maan Haj Rachid, Qutaibah Malluhi, and Mohamed Abouelhoda. “A space-efficient solution to find the maximum overlap using a compressed suffix array .” Middle East Conference on Biomedical Engineering (MECBME) , 2014.
Shunlai Bai, Wenhao Zhu, Bofeng Zhang , Jianhua Ma. “Search Results Clustering Based on Suffix Array and VSM .” IEEE/ACM International Conference on Green Computing and Communications & 2010 IEEE/ACM International Conference on Cyber, Physical and Social Computing , 2010.
Juha Ka ̈rkka ̈inen , Peter Sanders , Stefan Burkhardt. “Linear Work Suffix Array Construction .” ACM Journal, Volume 53 Issue 6, (2006).
Mohammadreza Ghodsi . “Approximate String Matching using Backtracking over Suffix Arrays .” Computer Science Department of University of Maryland at College Park , 2009.
Nataliya Timoshevskaya, Wu-chun. “SAIS-OPT: On the Characterization and Optimization of the SA-IS Algorithm for Suffix array construction” IEEE Transaction, 2014.
Hongwei Huo, Longgang Chen, Jeffrey Scott Vitter and Yakov Nekrich. “A Practical Implementation of Compressed Suffix Arrays with Applications to Self-Indexing.” IEEE Journel DOI 1109.2014.49, 2014.
Ricardo Baeza-Yates . “Modern information retrieval.” ACM press, 1999.
Esko Ukkonen , “On–line construction of suffix trees.”Algorithmatica , Volume 14, Issue 3, 1995, pp 249-260.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.
