Suffix Arrays: A New Method for On-Line String Searches
From MaRDI portal
Publication:3142586
DOI10.1137/0222058zbMath0784.68027OpenAlexW2158874082WikidataQ55934558 ScholiaQ55934558MaRDI QIDQ3142586
Publication date: 27 March 1994
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0222058
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Information storage and retrieval of data (68P20) Computing methodologies for text processing; mathematical typography (68U15)
Related Items
Approximate string matching using compressed suffix arrays, A metric index for approximate string matching, Extended suffix array construction using Lyndon factors, A linear time lower bound on McCreight and general updating algorithms for suffix trees, Document retrieval with one wildcard, The property suffix tree with dynamic properties, Efficient computation of sequence mappability, Less space: indexing for queries with wildcards, Lyndon array construction during Burrows-Wheeler inversion, Construction of Aho Corasick automaton in linear time for integer alphabets, Efficient parameterized string matching, Closed factorization, Sequence binary decision diagram: minimization, relationship to acyclic automata, and complexities of Boolean set operations, Computing suffix links for suffix trees and arrays, A time and space efficient data structure for string searching on large texts, r-indexing the eBWT, Grammar index by induced suffix sorting, Computing the original eBWT faster, simpler, and with less memory, Extracting the sparse longest common prefix array from the suffix binary search tree, Optimal suffix sorting and LCP array construction for constant alphabets, Combinatorics of minimal absent words for a sliding window, Approximate string matching with compressed indexes, Suffix-sorting via Shannon-Fano-Elias codes, All-pairs suffix/prefix in optimal time using Aho-Corasick space, Replacing suffix trees with enhanced suffix arrays, Indexing text using the Ziv--Lempel trie, Compressed directed acyclic word graph with application in local alignment, A fast algorithm for the all-pairs suffix-prefix problem, Compressed property suffix trees, A framework for space-efficient string kernels, Position-restricted substring searching over small alphabets, Colored range queries and document retrieval, On compressing and indexing repetitive sequences, Variations of the parameterized longest previous factor, \(p\)-suffix sorting as arithmetic coding, The longest common extension problem revisited and applications to approximate string searching, Generalizations of suffix arrays to multi-dimensional matrices., Text sparsification via local maxima., String matching with alphabet sampling, Efficient algorithms for three variants of the LPF table, A new efficient indexing algorithm for one-dimensional real scaled patterns, Two-dimensional substring indexing., Bidirectional search in a string with wavelet trees and bidirectional matching statistics, Approximate all-pairs suffix/prefix overlaps, New algorithms on wavelet trees and applications to information retrieval, On demand string sorting over unbounded alphabets, Period recovery of strings over the Hamming and edit distances, The indexing for one-dimensional proportionally-scaled strings, On the possible patterns of inputs for block sorting in the Burrows-Wheeler transformation, Using compressed suffix-arrays for a compact representation of temporal-graphs, Efficient online string matching based on characters distance text sampling, Parameterized longest previous factor, A linearly computable measure of string complexity, Dictionary matching with a bounded gap in pattern or in text, Worst-case efficient single and multiple string matching on packed texts in the word-RAM model, Verifying and enumerating parameterized border arrays, Succinct data structures for flexible text retrieval systems, Text indexing with errors, A linear size index for approximate pattern matching, Universal compressed text indexing, Counting suffix arrays and strings, Practical compressed suffix trees, Improved space-time tradeoffs for approximate full-text indexing with one edit error, Efficient pattern matching for RNA secondary structures, Fast compressed self-indexes with deterministic linear-time construction, Tighter bounds for the sum of irreducible LCP values, Burrows-Wheeler transform and LCP array construction in constant space, Inducing enhanced suffix arrays for string collections, A practical semi-external memory method for approximate pattern matching, Computing longest previous factor in linear time and applications, Position heaps: a simple and dynamic text indexing data structure, Permuted pattern matching algorithms on multi-track strings, Computing regularities in strings: a survey, Computing the longest previous factor, On-line construction of compact directed acyclic word graphs, A quick tour on suffix arrays and compressed suffix arrays, Space-efficient construction of Lempel-Ziv compressed text indexes, A simple algorithm for computing the document array, Cache-oblivious index for approximate string matching, New space/time tradeoffs for top-\(k\) document retrieval on sequences, On suffix extensions in suffix trees, Errata for ``Faster index for property matching, Alignment-free sequence comparison using absent words, Wee LCP, Lempel-Ziv factorization powered by space efficient suffix trees, Rank/select on dynamic compressed sequences and applications, Linearized suffix tree: An efficient index data structure with the capabilities of suffix trees and suffix arrays, The exact multiple pattern matching problem solved by a reference tree approach, Wheeler languages, Lossless filter for multiple repetitions with Hamming distance, Optimal data compression algorithm, Real two dimensional scaled matching, Dynamic dictionary matching in external memory, Fast pattern matching in indexed texts, The suffix binary search tree and suffix AVL tree, Parallel construction and query of index data structures for pattern matching on square matrices, Time-space trade-offs for compressed suffix arrays., Reducing space for index implementation., Faster online computation of the succinct longest previous factor array, String inference from longest-common-prefix array, Top-\(k\) term-proximity in succinct space, On the construction of classes of suffix trees for square matrices: Algorithms and applications, Engineering a lightweight external memory suffix array construction algorithm, Faster average case low memory semi-external construction of the Burrows-Wheeler transform, Lightweight LCP construction for very large collections of strings, An improved algorithm for the all-pairs suffix-prefix problem, On position restricted substring searching in succinct space, Faster index for property matching, CROCHEMORE'S REPETITIONS ALGORITHM REVISITED: COMPUTING RUNS, Space-Efficient Frameworks for Top- k String Retrieval, Indexing factors with gaps, Parallel lightweight wavelet tree, suffix array and FM-index construction, Efficient computation of substring equivalence classes with suffix arrays, Space-time trade-offs for finding shortest unique substrings and maximal unique matches, Kings, Name Days, Lazy Servants and Magic, Alphabet-Dependent String Searching with Wexponential Search Trees, Lempel Ziv Computation in Small Space (LZ-CISS), Succinct Non-overlapping Indexing, Dictionary Matching with Uneven Gaps, Tighter Bounds for the Sum of Irreducible LCP Values, Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree, A Probabilistic Analysis of the Reduction Ratio in the Suffix-Array IS-Algorithm, Faster repetition-aware compressed suffix trees based on block trees, An Opportunistic Text Indexing Structure Based on Run Length Encoding, LZRR: LZ77 parsing with right reference, A Faster Algorithm for Computing Maximal $$\alpha $$-gapped Repeats in a String, Longest Common Prefix with Mismatches, Algorithms to compute the Burrows-Wheeler similarity distribution, Large-scale detection of repetitions, Indexing a sequence for mapping reads with a single mismatch, Improved characters distance sampling for online and offline text searching, Linking indexing data structures to de Bruijn graphs: construction and update, Stronger Lempel-Ziv based compressed text indexing, The parameterized suffix tray, Unnamed Item, Compressed text indexing with wildcards, Fast circular dictionary-matching algorithm, The longest common substring problem, Computing Longest Single-arm-gapped Palindromes in a String, Space-efficient algorithms for computing minimal/shortest unique substrings, Wavelet trees for all, On the combinatorics of suffix arrays, Space-efficient construction of compressed suffix trees, An Online Algorithm for Finding the Longest Previous Factors, Better External Memory LCP Array Construction, Computing longest palindromic substring after single-character or block-wise edits, Alphabet-independent linear-time construction of compressed suffix arrays using \(o(n \log n)\)-bit working space, Worst Case Efficient Single and Multiple String Matching in the RAM Model, PSAEC: An Improved Algorithm for Short Read Error Correction Using Partial Suffix Arrays, Algorithms for Indexing Highly Similar DNA Sequences, Full-Text Indexes for High-Throughput Sequencing, Searching and Indexing Circular Patterns, Fast BWT in small space by blockwise suffix sorting, Faster suffix sorting, Rank and select revisited and extended, HPRD: a high performance RDF database, Freeness of partial words, The affix array data structure and its applications to RNA secondary structure analysis, Unnamed Item, An artificial neural network based approach for online string matching/filtering of large databases, WEIGHTED AUTOMATA FOR FULL-TEXT INDEXING, Forty Years of Text Indexing, Lempel-Ziv compressed structures for document retrieval, GAME: A simple and efficient whole genome alignment method using maximal exact match filtering, Unnamed Item, Unnamed Item, Succinct non-overlapping indexing, Popping Superbubbles and Discovering Clumps: Recent Developments in Biological Sequence Analysis, Counting Parameterized Border Arrays for a Binary Alphabet, Bidirectional Text Compression in External Memory, A brief history of parameterized matching problems, Refining the \(r\)-index, Parallel computation of the Burrows Wheeler transform in compact space, Efficient computation of longest single-arm-gapped palindromes in a string, Online Suffix Tree Construction for Streaming Sequences, Online algorithms for constructing linear-size suffix trie, Contracted Suffix Trees: A Simple and Dynamic Text Indexing Data Structure, Permuted Longest-Common-Prefix Array, Dichotomic Selection on Words: A Probabilistic Analysis, A Succinct Solution to Rmap Alignment, Faster queries for longest substring palindrome after block edit, Indexing the bijective BWT, Quasi-Linear-Time Algorithm for Longest Common Circular Factor, Locally Compressed Suffix Arrays, General Document Retrieval in Compact Space, THE VIRTUAL SUFFIX TREE, On the size of the smallest alphabet for Lyndon trees, Orthogonal Range Searching for Text Indexing, Constructing suffix arrays in linear time, Space efficient linear time construction of suffix arrays, Indexing text with approximate \(q\)-grams, RECONSTRUCTING A SUFFIX ARRAY, A SIMPLE ALPHABET-INDEPENDENT FM-INDEX, Computing the Burrows-Wheeler transform in place and in small space, Improved and extended locating functionality on compressed suffix arrays, Bottom-\(k\) document retrieval, A Fast Suffix-Sorting Algorithm, Geometric BWT: compressed text indexing via sparse suffixes and range searching, Suffix trays and suffix trists: structures for faster text indexing, Compressing dictionary matching index via sparsification technique, Circular Sequence Comparison with q-grams, Bidirectional Variable-Order de Bruijn Graphs, On the Structure of Consistent Partitions of Substring Set of a Word, Property Suffix Array with Applications in Indexing Weighted Sequences, Practical Wavelet Tree Construction, Fast detection of specific fragments against a set of sequences, Efficient construction of the BWT for repetitive text using string compression, Inferring strings from position heaps in linear time, Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets, Algorithms and complexity on indexing founder graphs, Computing all-vs-all MEMs in run-length-encoded collections of HiFi reads, Parallel suffix sorting for large string analytics, String Covering: A Survey, Computational graph pangenomics: a tutorial on data structures and their applications, The “Runs” Theorem, Online algorithms for finding distinct substrings with length and multiple prefix and suffix conditions, Accessing the suffix array via \(\phi^{-1}\)-forest, Sparse suffix trees, Elastic founder graphs improved and enhanced, Constructing and indexing the bijective and extended Burrows-Wheeler transform, SpliceTAPyR — An Efficient Method for Transcriptome Alignment, SORTING SUFFIXES OF TWO-PATTERN STRINGS, Spaces, Trees, and Colors, An experimental study of a compressed index, Simple and flexible detection of contiguous repeats using a suffix tree, Faster algorithms for 1-mappability of a sequence, Compressed indexes for approximate string matching, Space efficient algorithms for the Burrows-Wheeler backtransformation, Indexing Circular Patterns, Unnamed Item, Universal Data Compression Algorithm Based on Approximate String Matching, Generalizations of suffix arrays to multi-dimensional matrices., Small-space LCE data structure with constant-time queries, Inducing Suffix and LCP Arrays in External Memory, LCP Array Construction in External Memory, Faster Compressed Suffix Trees for Repetitive Collections, Fast Compressed Self-Indexes with Deterministic Linear-Time Construction, On Undetected Redundancy in the Burrows-Wheeler Transform, Practical Compact Indexes for Top-kDocument Retrieval, Non-Overlapping Indexing - Cache Obliviously
