Document Open Access Logo

Indexing the Bijective BWT

Authors Hideo Bannai , Juha Kärkkäinen, Dominik Köppl , Marcin Pia̧tkowski

PDF
Thumbnail PDF

File

LIPIcs.CPM.2019.17.pdf
  • Filesize: 0.83 MB
  • 14 pages

Document Identifiers

Author Details

Hideo Bannai
  • Department of Informatics, Kyushu University, Fukuoka, Japan
Juha Kärkkäinen
  • Helsinki Institute of Information Technology (HIIT), Finland
Dominik Köppl
  • Department of Informatics, Kyushu University, Japan Society for Promotion of Science (JSPS)
Marcin Pia̧tkowski
  • Nicolaus Copernicus University, Toruń, Poland

Funding

This research received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 690941.
  • Köppl, Dominik: JSPS KAKENHI Grant Number JP18F18120.

Cite As Get BibTex

Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, and Marcin Pia̧tkowski. Indexing the Bijective BWT. In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 128, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.CPM.2019.17

Abstract

The Burrows-Wheeler transform (BWT) is a permutation whose applications are prevalent in data compression and text indexing. The bijective BWT is a bijective variant of it that has not yet been studied for text indexing applications. We fill this gap by proposing a self-index built on the bijective BWT . The self-index applies the backward search technique of the FM-index to find a pattern P with O(|P| lg|P|) backward search steps.

Subject Classification

ACM Subject Classification
  • Theory of computation
  • Mathematics of computing → Combinatorics on words
Keywords
  • Burrows-Wheeler Transform
  • Lyndon words
  • Text Indexing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Donald Adjeroh, Timothy Bell, and Amar Mukherjee. The Burrows-Wheeler Transform:: Data Compression, Suffix Arrays, and Pattern Matching. Springer, 2008. Google Scholar
  2. Uwe Baier. On Undetected Redundancy in the Burrows-Wheeler Transform. In Proc. CPM, volume 105 of LIPIcs, pages 3:1-3:15, 2018. Google Scholar
  3. Silvia Bonomo, Sabrina Mantaci, Antonio Restivo, Giovanna Rosone, and Marinella Sciortino. Sorting conjugates and Suffixes of Words in a Multiset. Int. J. Found. Comput. Sci., 25(8):1161, 2014. Google Scholar
  4. Stefan Böttcher, Alexander Bültmann, Rita Hartel, and Jonathan Schlüßler. Fast Insertion and Deletion in Compressed Texts. In Proc. DCC, page 393, 2012. Google Scholar
  5. Stefan Böttcher, Alexander Bültmann, Rita Hartel, and Jonathan Schlüßler. Implementing Efficient Updates in Compressed Big Text Databases. In Proc. DEXA, volume 8056 of LNCS, pages 189-202, 2013. Google Scholar
  6. M. Burrows and D. J. Wheeler. A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation, Palo Alto, California, 1994. Google Scholar
  7. Kuo Tsai Chen, Ralph H. Fox, and Roger C. Lyndon. Free differential calculus, IV. The quotient groups of the lower central series. Annals of Mathematics, pages 81-95, 1958. Google Scholar
  8. Jean-Pierre Duval. Factorizing Words over an Ordered Alphabet. J. Algorithms, 4(4):363-381, 1983. Google Scholar
  9. Paolo Ferragina and Giovanni Manzini. Opportunistic Data Structures with Applications. In Proc. FOCS, pages 390-398, 2000. Google Scholar
  10. Paolo Ferragina and Giovanni Manzini. Indexing compressed text. J. ACM, 52(4):552-581, 2005. Google Scholar
  11. Travis Gagie, Gonzalo Navarro, and Nicola Prezza. Optimal-Time Text Indexing in BWT-runs Bounded Space. In Proc. SODA, pages 1459-1477, 2018. Google Scholar
  12. Joseph Yossi Gil and David Allen Scott. A Bijective String Sorting Transform. ArXiv 1201.3077, 2012. URL: http://arxiv.org/abs/1201.3077.
  13. Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Faster Lyndon factorization algorithms for SLP and LZ78 compressed text. Theor. Comput. Sci., 656:215-224, 2016. Google Scholar
  14. Masaru Ito, Hiroshi Inoue, and Kenjiro Taura. Fragmented BWT: An Extended BWT for Full-Text Indexing. In Proc. SPIRE, volume 9954 of LNCS, pages 97-109, 2016. Google Scholar
  15. Manfred Kufleitner. On Bijective Variants of the Burrows-Wheeler Transform. In Proc. PSC, pages 65-79, 2009. Google Scholar
  16. R. C. Lyndon. On Burnside’s Problem. Transactions of the American Mathematical Society, 77(2):202-215, 1954. Google Scholar
  17. Veli Mäkinen and Gonzalo Navarro. Succinct Suffix Arrays based on Run-Length Encoding. Nord. J. Comput., 12(1):40-66, 2005. Google Scholar
  18. Udi Manber and Eugene W. Myers. Suffix Arrays: A New Method for On-Line String Searches. SIAM J. Comput., 22(5):935-948, 1993. Google Scholar
  19. Sabrina Mantaci, Antonio Restivo, Giovanna Rosone, and Marinella Sciortino. An extension of the Burrows-Wheeler Transform. Theor. Comput. Sci., 387(3):298-312, 2007. Google Scholar
  20. Gonzalo Navarro and Veli Mäkinen. Compressed full-text indexes. ACM Comput. Surv., 39(1):2, 2007. Google Scholar
  21. Gonzalo Navarro and Yakov Nekrich. Optimal Dynamic Sequence Representations. SIAM J. Comput., 43(5):1781-1806, 2014. Google Scholar
  22. Tatsuya Ohno, Yoshimasa Takabatake, Tomohiro I, and Hiroshi Sakamoto. A Faster Implementation of Online Run-Length Burrows-Wheeler Transform. In Proc. IWOCA, volume 10765 of LNCS, pages 409-419, 2017. Google Scholar
  23. Alberto Policriti and Nicola Prezza. Computing LZ77 in Run-Compressed Space. In Proc. DCC, pages 23-32, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact