A Space-Economical Suffix Tree Construction Algorithm
From MaRDI portal
Publication:4095870
DOI10.1145/321941.321946zbMath0329.68042OpenAlexW2121252285WikidataQ56431602 ScholiaQ56431602MaRDI QIDQ4095870
Publication date: 1976
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321941.321946
Related Items
Algorithmic Framework for Approximate Matching Under Bounded Edits with Applications to Sequence Analysis, On the construction of classes of suffix trees for square matrices: Algorithms and applications, On representations of ternary order relations in numeric strings, A linear time lower bound on McCreight and general updating algorithms for suffix trees, Words over an ordered alphabet and suffix permutations, On position restricted substring searching in succinct space, Faster index for property matching, An index data structure for matrices, with applications to fast two-dimensional pattern matching, On-line construction of suffix trees, Space-Efficient Frameworks for Top- k String Retrieval, Indexing factors with gaps, Data structures and algorithms for the string statistics problem, Unnamed Item, Efficient computation of substring equivalence classes with suffix arrays, Space-time trade-offs for finding shortest unique substrings and maximal unique matches, Alphabet-Dependent String Searching with Wexponential Search Trees, Faster repetition-aware compressed suffix trees based on block trees, Optimal in-place suffix sorting, Two-dimensional pattern matching on a dynamic library of texts, On the relationship between histogram indexing and block-mass indexing, Indexing a sequence for mapping reads with a single mismatch, Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets, ABBA: adaptive Brownian bridge-based symbolic aggregation of time series, Linking indexing data structures to de Bruijn graphs: construction and update, Parallel suffix sorting for large string analytics, Quantum algorithm for lexicographically minimal string rotation, On-line construction of parameterized suffix trees for large alphabets, Time-Optimal Top-$k$ Document Retrieval, Sparse suffix trees, Compressed text indexing with wildcards, The longest common substring problem, Finding patterns and periods in Cartesian tree matching, Generalized substring compression, Wavelet trees for all, INDEXING GAPPED-FACTORS USING A TREE, REACHABILITY ON SUFFIX TREE GRAPHS, Towards a real time algorithm for parameterized longest common prefix computation, Partial words and the critical factorization theorem revisited, Algorithms for extracting motifs from biological weighted sequences, Linear time algorithm for the longest common repeat problem, Algorithms for Indexing Highly Similar DNA Sequences, Full-Text Indexes for High-Throughput Sequencing, DNA-Seq Error Correction Based on Substring Indices, String-Matching and Alignment Algorithms for Finding Motifs in NGS Data, Efficient enumeration of maximal induced bicliques, The affix array data structure and its applications to RNA secondary structure analysis, Fast compressed self-indexes with deterministic linear-time construction, Unnamed Item, Sparse and Truncated Suffix Trees on Variable-Length Codes, Quick Greedy Computation for Minimum Common String Partitions, THEORETICAL ISSUES OF SEARCHING AERIAL PHOTOGRAPHS: A BIRD'S EYE VIEW, An Evolutionary Distance Based on Maximal Unique Matches, On-line construction of two-dimensional suffix trees, Spaces, Trees, and Colors, Forty Years of Text Indexing, Optimal parallel suffix tree construction, Quick greedy computation for minimum common string partition, Data compression with long repeated strings, Optimal encoding of non-stationary sources, Unnamed Item, Simple and flexible detection of contiguous repeats using a suffix tree, Compressed indexes for approximate string matching, Construction of a de Bruijn Graph for Assembly from a Truncated Suffix Tree, Indexing Circular Patterns, Efficient pattern matching in elastic-degenerate strings, Unnamed Item, A brief history of parameterized matching problems, Fast prefix matching of bounded strings, Online Suffix Tree Construction for Streaming Sequences, Counter based suffix tree for DNA pattern repeats, Range LCP, Cartesian Tree Matching and Indexing, Locally Compressed Suffix Arrays, ALGORITHMS FOR POINT SET MATCHING WITH k-DIFFERENCES, Universal Data Compression Algorithm Based on Approximate String Matching, Detecting leftmost maximal periodicities, The suffix binary search tree and suffix AVL tree, Generalizations of suffix arrays to multi-dimensional matrices., IN-PLACE UPDATE OF SUFFIX ARRAY WHILE RECODING WORDS, THE VIRTUAL SUFFIX TREE, Seed-driven Learning of Position Probability Matrices from Large Sequence Sets., Detection of periodicities and string-matching in real time, Orthogonal Range Searching for Text Indexing, Sliding suffix tree, Constructing suffix arrays in linear time, Space efficient linear time construction of suffix arrays, Distributed suffix trees, A speed-up for the commute between subword trees and DAWGs., Reducing space for index implementation., Dictionary matching with a few gaps, Geometric BWT: compressed text indexing via sparse suffixes and range searching, Faster online computation of the succinct longest previous factor array, Faster Compressed Suffix Trees for Repetitive Collections, Locally Maximal Common Factors as a Tool for Efficient Dynamic String Algorithms., Suffix trays and suffix trists: structures for faster text indexing, Compressing dictionary matching index via sparsification technique, Space-efficient representation of truncated suffix trees, with applications to Markov order estimation, Approximate string matching using compressed suffix arrays, A metric index for approximate string matching, Structural properties of the string statistics problem, Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach, Dynamic dictionary matching with failure functions, Dynamic suffix tree and two-dimensional texts management, Sublinear approximate string matching and biological applications, Pattern matching in a digitized image, Dynamic dictionary matching, Online timestamped text indexing, The property suffix tree with dynamic properties, Linear-size suffix tries, Time optimal left to right construction of position trees, Construction of Aho Corasick automaton in linear time for integer alphabets, 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, Parallel string matching with k mismatches, An \(O(ND)\) difference algorithm and its variations, A new distance metric on strings computable in linear time, Data structures and algorithms for approximate string matching, Parallel construction of a suffix tree with applications, Efficient discovery of unusual patterns in time series, La reconnaissance des facteurs d'un langage fini dans un texte en temps linéaire. (Recognition of the factors of a finite language in a text in linear time), Compact directed acyclic word graphs for a sliding window, The suffix tree of a tree and minimizing sequential transducers, On updating suffix tree labels, Validating the Knuth-Morris-Pratt failure function, fast and online, Position-restricted substring searching over small alphabets, Efficient index for retrieving top-\(k\) most frequent documents, Generalized substring selectivity estimation, Reverse engineering of compact suffix trees and links: a novel algorithm, Generalizations of suffix arrays to multi-dimensional matrices., Truncated suffix trees and their application to data compression., On-line suffix tree construction with reduced branching, A new efficient indexing algorithm for one-dimensional real scaled patterns, Ultra-succinct representation of ordered trees with applications, Two-dimensional substring indexing., Scalability and communication in parallel low-complexity lossless compression, Linear-time construction of two-dimensional suffix trees, On demand string sorting over unbounded alphabets, Motif trie: an efficient text index for pattern discovery with don't cares, String matching with weighted errors, PSIST: a scalable approach to indexing protein structures using suffix trees, Parallel construction of minimal suffix and factor automata, Verifying and enumerating parameterized border arrays, Lyndon words, permutations and trees., Text indexing with errors, Optimal off-line detection of repetitions in a string, A linear size index for approximate pattern matching, Fast profile matching algorithms - A survey, Property matching and weighted matching, Lempel-Ziv data compression on parallel and distributed systems, Practical compressed suffix trees, Improved space-time tradeoffs for approximate full-text indexing with one edit error, Inferring strings from suffix trees and links on a binary alphabet, A new decomposition technique for maximal clique enumeration for sparse graphs, Multiple matching of parameterized patterns, On-line string matching with feedback, Succinct indexes for reporting discriminating and generic words, On the string matching with \(k\) mismatches, Comparing bacterial genomes from linear orders of patterns, Fast average-case pattern matching by multiplexing sparse tables, Approximate string-matching with \(q\)-grams and maximal matches, An efficient algorithm for the all pairs suffix-prefix problem, A grouping approach for succinct dynamic dictionary matching, On-line construction of compact suffix vectors and maximal repeats, Efficient detection of quasiperiodicities in strings, Computing regularities in strings: a survey, Computing the longest previous factor, Efficient CRCW-PRAM algorithms for universal substring searching, On finding common subtrees, Two-dimensional dictionary matching, On-line construction of compact directed acyclic word graphs, Linear time algorithms for finding and representing all the tandem repeats in a string, A quick tour on suffix arrays and compressed suffix arrays, Dynamic extended suffix arrays, Ternary directed acyclic word graphs, On average sequence complexity, Cache-oblivious index for approximate string matching, Optimal prefix and suffix queries on texts, Partial words and the critical factorization theorem, On suffix extensions in suffix trees, Improving on-line construction of two-dimensional suffix trees for square matrices, La reconnaissance des facteurs d'un mot dans un texte, Finding the longest common nonsuperstring in linear time, Indexing and querying character sets in one- and two-dimensional words, Suffix tree characterization of maximal motifs in biological sequences, Linearized suffix tree: An efficient index data structure with the capabilities of suffix trees and suffix arrays, Comparison and evaluation of code clone detection techniques and tools: A qualitative approach, Optimal data compression algorithm, Real two dimensional scaled matching, Discovering subword associations in strings in time linear in the output size, Transducers and repetitions, Dynamic dictionary matching in external memory, Average sizes of suffix trees and DAWGs, Approximation algorithms for the shortest common superstring problem, Efficient computation of shortest absent words in a genomic sequence, Parallel construction and query of index data structures for pattern matching on square matrices, The smallest automaton recognizing the subwords of a text
