A universal algorithm for sequential data compression
From MaRDI portal
Publication:4158937
DOI10.1109/TIT.1977.1055714zbMath0379.94010WikidataQ55921954 ScholiaQ55921954MaRDI QIDQ4158937
Publication date: 1977
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Related Items
Computing q-Gram Non-overlapping Frequencies on SLP Compressed Texts, A Heuristic For Computing Repeats With A Factor Oracle: Application To Biological Sequences, UNIVERSAL CODING AND PREDICTION ON ERGODIC RANDOM POINTS, Arithmetics on Suffix Arrays of Fibonacci Words, Congruence Closure of Compressed Terms in Polynomial Time, Diverse Palindromic Factorization Is NP-complete, Approximating LZ77 via Small-Space Multiple-Pattern Matching, Efficient algorithms for Lempel-Ziv encoding, Unnamed Item, FINDING CHARACTERISTIC SUBSTRINGS FROM COMPRESSED TEXTS, Self-indexed Text Compression Using Straight-Line Programs, An Efficient Scheme for Joint Compression and Encryption, Machine-learning iterative calculation of entropy for physical systems, R\'enyi entropy and pattern matching for run-length encoded sequences, ZIV-LEMPEL AND CROCHEMORE FACTORIZATIONS OF THE GENERALIZED PERIOD-DOUBLING WORD, Phenomenology of coupled nonlinear oscillators, Composite Repetition-Aware Data Structures, Lempel Ziv Computation in Small Space (LZ-CISS), Linear pattern matching of compressed terms and polynomial rewriting, An Opportunistic Text Indexing Structure Based on Run Length Encoding, A Faster Algorithm for Computing Maximal $$\alpha $$-gapped Repeats in a String, Pushdown and Lempel-Ziv depth, Inline vector compression for computational physics, Time series compression based on reinforcement learning, Engineering Practical Lempel-Ziv Tries, Semiconductor Emitters in Entropy Sources for Quantum Random Number Generation, Compression Using Lossless Decimation: Analysis and Application, String Indexing with Compressed Patterns, A circuit complexity formulation of algorithmic information theory, Hybrid indexes for repetitive datasets, Large-scale detection of repetitions, Data structures for computing unique palindromes in static and non-static strings, A new algorithm for compression of partially commutative alphabets, Haar-like wavelets on hierarchical trees, On Sensitivity of Compact Directed Acyclic Word Graphs, The “Runs” Theorem, Random access in persistent strings and segment selection, Unnamed Item, Unnamed Item, USING ALIGNMENT FOR MULTILINGUAL TEXT COMPRESSION, Deterministic compression with uncertain priors, Entropy estimate by a randomness criterion, Joint Source-Cryptographic-Channel Coding Based on Linear Block Codes, An Online Algorithm for Finding the Longest Previous Factors, WORD COMPLEXITY AND REPETITIONS IN WORDS, Minimal Unique Substrings and Minimal Absent Words in a Sliding Window, Relative entropy via non-sequential recursive pair substitution, De Novo NGS Data Compression, LZ78 Compression in Low Main Memory Space, On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation, Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries, A Self-index on Block Trees, Diverse Palindromic Factorization is NP-Complete, Compressed Membership in Automata with Compressed Labels, Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition, Self-indexing Based on LZ77, Faster Subsequence and Don’t-Care Pattern Matching on Compressed Texts, A FULLY COMPRESSED PATTERN MATCHING ALGORITHM FOR SIMPLE COLLAGE SYSTEMS, On-line construction of two-dimensional suffix trees, Estimating Entropy Rates with Bayesian Confidence Intervals, Shannon entropy: a rigorous notion at the crossroads between probability, information theory, dynamical systems and statistical physics, Structure-generating mechanisms in agent-based models, Adaptive arithmetic coding using fuzzy reasoning and grey prediction, Data compression with long repeated strings, Compression in the presence of shared data, Parallelism and dictionary based data compression, Optimal encoding of non-stationary sources, \(LZ\)-based image compression, Redundancy estimates for the Lempel–Ziv algorithm of data compression, Estimation of the Entropy Rate of a Countable Markov Chain, Unnamed Item, COMPRESSED MEMBERSHIP PROBLEMS FOR REGULAR EXPRESSIONS AND HIERARCHICAL AUTOMATA, Computing Longest Common Substring and All Palindromes from Compressed Strings, The Vcodex Platform for Data Compression, An example of mathematical authorship attribution, Statistical physics approach to categorize biologic signals: From heart rate dynamics to DNA sequences, Artificial sequences and complexity measures, Quasi-distinct Parsing and Optimal Compression Methods, On the Value of Multiple Read/Write Streams for Data Compression, CONVERGENCE OF C0 COMPLEXITY, On the size of overlapping Lempel-Ziv and Lyndon factorizations, Error Analysis of ZFP Compression for Floating-Point Data, Universal Data Compression Algorithm Based on Approximate String Matching, A Linear-Time Algorithm for Seeds Computation, Non-sequential recursive pair substitution: some rigorous results, Fast Exponentiation Using Data Compression, Bicriteria Data Compression, Mathematical Models of Textual Data: A Short Review, Small-space LCE data structure with constant-time queries, LZ-End Parsing in Linear Time, Unnamed Item, Information density, structure and entropy in equilibrium and non-equilibrium systems, Random Access to Grammar-Compressed Strings and Trees, Bridging Lossy and Lossless Compression by Motif Pattern Discovery, On the compression of locational and environmental data in multi-vehicle missions: a control systems approach, Almost linear time computation of maximal repetitions in run length encoded strings, Lazy Lempel-Ziv Factorization Algorithms, On Undetected Redundancy in the Burrows-Wheeler Transform, The Heaviest Induced Ancestors Problem Revisited, P-complete problems in data compression, Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach, Multivariate permutation entropy and its application for complexity analysis of chaotic systems, Phase transitions in tumor growth. III: Vascular and metastasis behavior, Bacterial DNA sequence compression models using artificial neural networks, Comparison of LZ77-type parsings, Speeding up HMM decoding and training by exploiting sequence repetitions, FM-index of alignment: a compressed index for similar strings, A novel block-based scheme for arithmetic coding, A separation between RLSLPs and LZ77, Faster subsequence recognition in compressed strings, Optimal partitioning of data chunks in deduplication systems, Solving a \(k\)-node minimum label spanning arborescence problem to compress fingerprint templates, A universal online caching algorithm based on pattern matching, A diffusion limit for a class of randomly-growing binary trees, Phase transition in a generalized Eden growth model on a tree, Approximate string matching with compressed indexes, Linear-time text compression by longest-first substitution, Concurrent vs. exclusive reading in parallel decoding of LZ-compressed files, An efficient algorithm for sequence comparison with block reversals, Replacing suffix trees with enhanced suffix arrays, Adaptive text mining: inferring structure from sequences, Dynamics characterization of modified Gross-Pitaevskii equation, Practical and flexible pattern matching over Ziv-Lempel compressed text., Straight-line programs: a practical test (extended abstract), A worst-case analysis of the LZ2 compression algorithm, Measuring the clustering effect of BWT via RLE, Analytical depoissonization and its applications, On updating suffix tree labels, On compressing and indexing repetitive sequences, Similarity in languages and programs, On parsing optimality for dictionary-based text compression -- the \texttt{Zip} case, Compact q-gram profiling of compressed strings, Convergence of recurrence of blocks for mixing processes, Compressed parameterized pattern matching, Application of Lempel-Ziv factorization to the approximation of grammar-based compression., Truncated suffix trees and their application to data compression., The three squares lemma revisited, Efficient algorithms for three variants of the LPF table, Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms., Time-space trade-offs for Lempel-Ziv compressed indexing, Scalability and communication in parallel low-complexity lossless compression, Computing maximal-exponent factors in an overlap-free word, Quasi-distinct parsing and optimal compression methods, A fast dynamic compression scheme for natural language texts, On optimal parsing for LZ78-like compressors, FM-index of alignment with gaps, Zipping thermal ratchets, Synergy, redundancy, and multivariate information measures: an experimentalist's perspective, Fast equality test for straight-line compressed strings, Personalized multi-user view and content synchronization and retrieval in real-time mobile social software applications, Parameterized longest previous factor, A faster implementation of online RLBWT and its application to LZ77 parsing, Impugning randomness, convincingly, Quantifying local randomness in human DNA and RNA sequences using Erdös motifs, Detecting life signatures with RNA sequence similarity measures, Similarity analysis of DNA sequences based on the generalized LZ complexity of (0,1)-sequences, Algorithmic folding complexity, An adaptive character wordlength algorithm for data compression, Efficient parallel algorithms to test square-freeness and factorize strings, A sensor-based framework for kinetic data compression, Randomized prediction of individual sequences, Lempel-Ziv data compression on parallel and distributed systems, The smallest grammar problem as constituents choice and minimal grammar parsing, The greedy approach to dictionary-based static text compression on a distributed system, On processes which cannot be distinguished by finite observation, Practical fixed length Lempel-Ziv coding, On-line versus off-line computation in dynamic text compression, Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees, A novel lossless data compression scheme based on the error correcting Hamming codes, Compressed subsequence matching and packed tree coloring, A universal statistical test for random bit generators, Is Huffmann coding dead?, Predictive analog-to-digital conversion for resistance to data outliers, Disjunctivity and other properties of sets of pseudo-bordered words, Computing longest previous factor in linear time and applications, Computing regularities in strings: a survey, Computing the longest previous factor, ODC: frame for definition of dense codes, Balancing and clustering of words in the Burrows-Wheeler transform, On the algorithmic complexity of static structures, Space-efficient construction of Lempel-Ziv compressed text indexes, Leaf languages and string compression, On bounded redundancy of universal codes, An extension of the Lyndon-Schützenberger result to pseudoperiodic words, Exploring the dynamics of dyadic interactions via hierarchical segmentation, Combinatorics on partial word correlations, An empirical study of the complexity and randomness of prediction error sequences, LZ77 computation based on the run-length encoded BWT, Lempel-Ziv factorization powered by space efficient suffix trees, Efficient algorithms to compute compressed longest common substrings and compressed palindromes, On the distribution function of the complexity of finite sequences, Hydrozip: how hydrological knowledge can be used to improve compression of hydrological data, XML compression techniques: A survey and comparison, Comparative construction of plug-in estimators of the entropy rate of two-state Markov chains, Phylogenetic inference from binary sequences reduced by primary DNA sequences, A complexity-based measure and its application to phylogenetic analysis, A compressed dynamic self-index for highly repetitive text collections, A review on the application of fuzzy transform in data and image compression, Text compression methods, An Introduction to Neural Data Compression, Greedy versus optimal analysis of bounded size dictionary compression and on-the-fly distributed computing, On the complexity of pattern matching for highly compressed two-dimensional texts., Collage system: A unifying framework for compressed pattern matching., Pass-efficient methods for compression of high-dimensional turbulent flow data, Complexity analysis to explore the structure of ancient stromatolites, Lossless compression and information hiding in images, Factorizing strings into repetitions, Closed Ziv-Lempel factorization of the \(m\)-bonacci words, Fast gapped variants for Lempel-Ziv-Welch compression, Contrasting stochasticity with chaos in a permutation Lempel-Ziv complexity -- Shannon entropy plane, Viral genome phylogeny based on Lempel-Ziv complexity and Hausdorff distance, Grammar index by induced suffix sorting, An LMS-based grammar self-index with local consistency properties, On the approximation ratio of LZ-end to LZ77, A separation of \(\gamma\) and \(b\) via Thue-Morse words, Phase transitions in tumor growth. V: What can be expected from cancer glycolytic oscillations?, The heaviest induced ancestors problem: better data structures and applications, Phase transitions in tumor growth. VI: Epithelial-mesenchymal transition, A parametrized family of Tversky metrics connecting the Jaccard distance to an analogue of the normalized information distance, Code-carrying theories, The fractional greedy algorithm for data compression, Sublinear algorithms for approximating string compressibility, Fingerprints in compressed strings, Grammar compressed sequences with rank/select support, Automatic Kolmogorov complexity, normality, and finite-state dimension revisited, Longest previous overlapping factor array, Shortest unique palindromic substring queries in semi-dynamic settings, Robust universal complete codes for transmission and compression, Adaptive learning of compressible strings, Progress, gaps and obstacles in the classification of cellular automata, c-trie++: a dynamic trie tailored for fast prefix searches, Variations of the parameterized longest previous factor, Predictability of players' actions as a mechanism to boost cooperation, Unified compression-based acceleration of edit-distance computation, Recurrence times, waiting times and universal entropy production estimators, Sensitivity of string compressors and repetitiveness measures, Computing longest previous non-overlapping factors, Complexity-compression tradeoffs in lossy compression via efficient random codebooks and databases, Dimension is compression, Lempel-Ziv-like parsing in small space, Generative complexity of Gray-Scott model, Parallel algorithms for Burrows-Wheeler compression and decompression, Generalized substring compression, Note on the greedy parsing optimality for dictionary-based text compression, Speeding up the detection of tandem repeats over the edit distance, Randomized probe selection algorithm for microarray design, Comparison of alignment free string distances for complete genome phylogeny, A combinatorial view on string attractors, Fast relative Lempel-Ziv self-index for similar sequences, Fast algorithms for finding a minimum repetition representation of strings and trees, Palindromic trees for a sliding window and its applications, Burrows-Wheeler compression: Principles and reflections, Compressing table data with column dependency, Fast string matching for multiple searches, Compact video content representation for video coding using low multi-linear tensor rank approximation with dynamic core tensor order, Binary image compression via monochromatic pattern substitution: sequential and parallel implementations, Time-universal data compression, Fuzzy relation equations for coding/decoding processes of images and videos, Parallel Lempel Ziv coding, Phylogenetic analysis of DNA sequences based on the generalized pseudo-amino acid composition, A fast and efficient nearly-optimal adaptive Fano coding scheme, Flexible indexing of repetitive collections, Convergence properties of functional estimates for discrete distributions, Size and path length of Patricia tries: Dynamical sources context, Completing prefix codes in submonoids., Partial words and the critical factorization theorem, Distance measures for biological sequences: some recent approaches, Second step algorithms in the Burrows-Wheeler compression algorithm, Estimation of muscle spindle information rate by pattern matching and the effect of gamma system activity on parallel spindles, On the non-randomness of maximum Lempel Ziv complexity sequences of finite size, Comparison of protein secondary structures based on backbone dihedral angles, A motion compression/reconstruction method based on max t-norm composite fuzzy relational equations, Data compression and genomes: a two-dimensional life domain map, On universal algorithms for classifying and predicting stationary processes, Dynamic determination of variable sizes of chunks in a deduplication system, A brief history of parameterized matching problems, Dynamic index and LZ factorization in compressed space, Direct merging of delta encoded files, Refining the \(r\)-index, Automatic proofs of memory deallocation for a Whiley-to-C compiler, Asymptotically most powerful tests for random number generators, Optimal data compression algorithm, Regular expression searching on compressed text, Two-pattern strings. I: A recognition algorithm, Approximate string matching on Ziv--Lempel compressed text, Finger search in grammar-compressed strings, Variable-length codes independent or closed with respect to edit relations, Orthogonal Range Searching for Text Indexing, On fungal automata, A fully linear-time approximation algorithm for grammar-based compression, Sampling automata and programs, Time-space trade-offs for compressed suffix arrays., Compror: On-line lossless data compression with a factor oracle., Reducing space for index implementation., Approximate pattern matching in LZ77-compressed texts, Compressed automata for dictionary matching, Faster online computation of the succinct longest previous factor array, Fast distance multiplication of unit-Monge matrices, Space-efficient representation of truncated suffix trees, with applications to Markov order estimation, Data compression and learning in time sequences analysis, Computing minimal unique substrings for a sliding window
