• Refine your search:
  • 
    Keyword
  • 
    Creator / Publisher:
    
    • Ganguly, Arnab (1)
    • Gibney, Daniel (1)
    • Hooshmand, Sahar (1)
    • Külekci, M. Oğuzhan (1)
    • Thankachan, Sharma V. (1)
  • 
    Year
  • 
    Medium:
    
    • Online (1)
  • 
    Type:
    
    • Article (1)
  • 
    BLLDB-Access

Search in the Catalogues and Directories

All fields Title Creator / Publisher Keyword Year AND OR AND NOT All fields Title Creator / Publisher Keyword Year AND OR AND NOT All fields Title Creator / Publisher Keyword Year AND OR AND NOT All fields Title Creator / Publisher Keyword Year AND OR AND NOT All fields Title Creator / Publisher Keyword Year Sort by creator [A → Z]' creator [Z → A]' publishing year ↑ (asc)' publishing year ↓ (desc)' title [A → Z]' title [Z → A]' Simple Search Hits 1 – 1 of 1 1 FM-Index Reveals the Reverse Suffix Array ... Ganguly, Arnab; Gibney, Daniel; Hooshmand, Sahar; Külekci, M. Oğuzhan; Thankachan, Sharma V.. - : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020 Abstract: Given a text T[1,n] over an alphabet Σ of size σ, the suffix array of T stores the lexicographic order of the suffixes of T. The suffix array needs Θ(nlog n) bits of space compared to the n log σ bits needed to store T itself. A major breakthrough [FM - Index, FOCS'00] in the last two decades has been encoding the suffix array in near-optimal number of bits (≈ log σ bits per character). One can decode a suffix array value using the FM-Index in log^{O(1)} n time. We study an extension of the problem in which we have to also decode the suffix array values of the reverse text. This problem has numerous applications such as in approximate pattern matching [Lam et al., BIBM' 09]. Known approaches maintain the FM - Index of both the forward and the reverse text which drives up the space occupancy to 2nlog σ bits (plus lower order terms). This brings in the natural question of whether we can decode the suffix array values of both the forward and the reverse text, but by using nlog σ bits (plus lower order terms). ... : LIPIcs, Vol. 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020), pages 13:1-13:14 ... Keyword: Burrows - Wheeler transform; Compression; Data Structures; FM-Index; String Algorithms; Suffix Trees URL: https://drops.dagstuhl.de/opus/volltexte/2020/12138/ https://dx.doi.org/10.4230/lipics.cpm.2020.13 BASE Hide details

Mobile view All Catalogues UB Frankfurt Linguistik 0 IDS Mannheim 0 OLC Linguistik 0 UB Frankfurt Retrokatalog 0 DNB Subject Category Language 0 Institut für Empirische Sprachwissenschaft 0 Leibniz-Centre General Linguistics (ZAS) 0 Bibliographies BLLDB 0 BDSL 0 IDS Bibliografie zur deutschen Grammatik 0 IDS Bibliografie zur Gesprächsforschung 0 IDS Konnektoren im Deutschen 0 IDS Präpositionen im Deutschen 0 IDS OBELEX meta 0 MPI-SHH Linguistics Collection 0 MPI for Psycholinguistics 0 Linked Open Data catalogues Annohub 0 Online resources Link directory 0 Journal directory 0 Database directory 0 Dictionary directory 0 Open access documents BASE 1 Linguistik-Repository 0 IDS Publikationsserver 0 Online dissertations 0 Language Description Heritage 0