A simple algorithm for computing the document array

DOI10.1016/J.IPL.2019.105887zbMATH Open1478.68461arXiv1812.09094OpenAlexW2905758257WikidataQ126833510 ScholiaQ126833510MaRDI QIDQ2011038FDOQ2011038

Authors: Felipe A. Louza 

Publication date: 28 November 2019

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: We present a simple algorithm for computing the document array given a string collection and its suffix array as input. Our algorithm runs in linear time using constant additional space for strings from constant alphabets.

Full work available at URL: https://arxiv.org/abs/1812.09094

Recommendations

• scientific article; zbMATH DE number 2038766
• Space-Efficient Algorithms for Document Retrieval
• Computing suffix links for suffix trees and arrays
• Suffix Arrays: A New Method for On-Line String Searches
• Linear work suffix array construction

zbMATH Keywords

text indexingdocument array

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Cites Work

• Improved compressed indexes for full-text document retrieval
• Title not available (Why is that?)
• Suffix Arrays: A New Method for On-Line String Searches
• Succinct data structures for flexible text retrieval systems
• Space-Efficient Algorithms for Document Retrieval
• Cross-document pattern matching
• Title not available (Why is that?)
• Bioinformatics algorithms. Sequence analysis, genome rearrangements, and phylogenetic reconstruction
• A constant-space comparison-based algorithm for computing the Burrows-Wheeler transform
• Efficient algorithms for the all-pairs suffix-prefix problem and the all-pairs substring-prefix problem
• Space-efficient construction of compressed indexes in deterministic linear time
• An improved algorithm for the all-pairs suffix-prefix problem
• Inducing enhanced suffix arrays for string collections
• Linear time algorithms for generalizations of the longest common substring problem
• Lightweight metagenomic classification via eBWT
• Algorithms to compute the Burrows-Wheeler similarity distribution
• Haplotype-aware graph indexes
• External memory BWT and LCP computation for sequence collections with applications

This page was built for publication: A simple algorithm for computing the document array

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2011038)