Experimental evaluation of algorithms for computing quasiperiods
From MaRDI portal
Publication:2220855
Abstract: Quasiperiodicity is a generalization of periodicity that was introduced in the early 1990s. Since then, dozens of algorithms for computing various types of quasiperiodicity were proposed. Our work is a step towards answering the question: "Which algorithm for computing quasiperiods to choose in practice?". The central notions of quasiperiodicity are covers and seeds. We implement algorithms for computing covers and seeds in the original and in new simplified versions and compare their efficiency on various types of data. We also discuss other known types of quasiperiodicity, distinguish partial covers as currently the most promising for large real-world data, and check their effectiveness using real-world data.
Recommendations
Cites work
- A simple mergeable dictionary
- Algorithms on Strings
- An on-line string superprimitivity test
- An optimal algorithm for computing the repetitions in a word
- An optimal algorithm to compute all the covers of a string
- An output-sensitive algorithm for the minimization of 2-dimensional string covers
- Approximate cover of strings
- Approximate seeds of strings
- Can we recover the cover?
- Computing covers using prefix tables
- Computing the \(\lambda \)-covers of a string
- Computing the cover array in linear time
- Computing the λ-Seeds of a String
- Counting palindromes in substrings
- Cover array string reconstruction
- Covering a string
- Data structures and algorithms for the string statistics problem
- Efficient algorithms for shortest partial seeds in words
- Efficient detection of quasiperiodicities in strings
- Efficient seed computation revisited
- Enhanced string covering
- Fast algorithm for partial covers in words
- Fast Pattern Matching in Strings
- scientific article; zbMATH DE number 1615296 (Why is no real title available?)
- scientific article; zbMATH DE number 1003282 (Why is no real title available?)
- scientific article; zbMATH DE number 2052918 (Why is no real title available?)
- scientific article; zbMATH DE number 2086666 (Why is no real title available?)
- scientific article; zbMATH DE number 1400047 (Why is no real title available?)
- Indexing weighted sequences: neat and efficient
- Jewels of Stringology
- New complexity results for the k-covers problem
- On approximate enhanced covers under Hamming distance
- On left and right seeds of a string
- On-line construction of suffix trees
- Optimal superprimitivity testing for strings
- Quasi-periodicity under mismatch errors
- Quasiperiodicities in Fibonacci strings.
- Quasiperiodicity and string covering
- Repetitive perhaps, but certainly not boring
- Testing string superprimitivity in parallel
- The complexity of the minimum k-cover problem
- The maximum number of squares in a tree
- The weighted suffix tree: an efficient data structure for handling molecular weighted sequences and its applications
- Two strings at Hamming distance 1 cannot be both quasiperiodic
- Two-dimensional prefix string matching and covering on square matrices
- Universal reconstruction of a string
Cited in
(10)- k-approximate quasiperiodicity under Hamming and edit distance
- scientific article; zbMATH DE number 1507240 (Why is no real title available?)
- String Covering: A Survey
- Subsequence covers of words
- Internal Quasiperiod Queries
- String covers of a tree revisited
- Internal quasiperiod queries
- Subsequence covers of words
- String 2-covers with no length restrictions
- Optimality of some algorithms to detect quasiperiodicities
This page was built for publication: Experimental evaluation of algorithms for computing quasiperiods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2220855)
