Matching strings in encoded sequences
From MaRDI portal
Abstract: We investigate the longest common substring problem for encoded sequences and its asymptotic behaviour. The main result is a strong law of large numbers for a re-scaled version of this quantity, which presents an explicit relation with the R'enyi entropy of the source. We apply this result to the zero-inflated contamination model and the stochastic scrabble. In the case of dynamical systems, this problem is equivalent to the shortest distance between two observed orbits and its limiting relationship with the correlation dimension of the pushforward measure. An extension to the shortest distance between orbits for random dynamical systems is also provided.
Let \(\chi, \tilde\chi \) be alphabets. An encoder is a measurable function on strings \(f\colon \chi ^{\mathrm{N}} \to \tilde\chi^{\mathrm{N}}\). For any \(x,y \in \chi^{\mathrm{N}}\) the longest common substring between encoded strings is \[ M_n^f(x,y) = \max \{ k:f(x)_i^{i + k - 1} = f(y)_j^{j + k - 1},\ 0 \le i,j \le n - k\}. \] Here it is proved an almost sure convergence of \(M_n^f\). The result is applied to generalize some earlier results for stochastic scrabble, stochastic noise and for analysis of the behaviour of the shortest distance between observed orbits of a dynamical system.
Recommendations
- Rényi entropy and pattern matching for run-length encoded sequences
- Longest common substring for random subshifts of finite type
- On the shortest distance between orbits and the longest common substring problem
- Critical phenomena in sequence matching
- Maximal length of common words among random letter sequences
Cites work
- A Phase Transition for the Distribution of Matching Blocks
- A suboptimal lossy data compression based on approximate pattern matching
- An Erdős-Rényi law with shifts
- AN INTRODUCTION TO QUANTITATIVE POINCARÉ RECURRENCE IN DYNAMICAL SYSTEMS
- Critical phenomena for sequence matching with scoring
- Entropy and data compression schemes
- Entry and return times distribution
- Exponential decay of correlations for randomly chosen hyperbolic toral automorphisms
- From the divergence between two measures to the shortest path between two observables
- Hitting time statistics for observations of dynamical systems
- scientific article; zbMATH DE number 1516956 (Why is no real title available?)
- scientific article; zbMATH DE number 918233 (Why is no real title available?)
- Inequalities for the occurrence times of rare events in mixing processes. The state of the art
- Information theory and coding by example
- Large deviations for short recurrence
- Laws of rare events for deterministic and random dynamical systems
- Limit distribution of maximal non-aligned two-sequence segmental score
- Longest common substring for random subshifts of finite type
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- More on recurrence and waiting times
- Nonparametric entropy estimation for stationary processes and random fields, with applications to English text
- On compound Poisson approximation for sequence matching
- On the shortest distance between orbits and the longest common substring problem
- On the spectra of randomly perturbed expanding maps
- Poincaré recurrence for observations
- Pointwise dimensions for Poincaré recurrences associated with maps and special flows
- Quantitative recurrence results
- Random perturbations of stochastic processes with unbounded variable length memory
- Recurrence for random dynamical systems
- Recurrence rate in rapidly mixing dynamical systems
- Recurrence, dimensions, and Lyapunov exponents.
- Return times in a process generated by a typical partition
- Rényi Entropies and Large Deviations for the First Match Function
- Some asymptotic properties of the entropy of a stationary ergodic data source with applications to data compression
- Stochastic scrabble: large deviations for sequences with scores
- Stochastically perturbed chains of variable memory
- The asymptotics of waiting times between stationary processes, allowing distortion
- The distribution of the short-return function
- The Rényi entropy function and the large deviation of short return times
- The Shortest Possible Return Time of <inline-formula> <tex-math notation="LaTeX">$\beta$ </tex-math> </inline-formula>-Mixing Processes
Cited in
(10)- On the shortest distance between orbits and the longest common substring problem
- Shortest distance between multiple orbits and generalized fractal dimensions
- Longest common substring for random subshifts of finite type
- Matching of observations of dynamical systems, with applications to sequence matching
- Rényi entropy and pattern matching for run-length encoded sequences
- Minimal distance between random orbits
- Common substring with shifts in \(b\)-ary expansions
- On the shortest distance between orbits in conformal iterated function systems
- Shortest distance between partial orbits
- Sequence matching with binary codes
This page was built for publication: Matching strings in encoded sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2174991)
