Search results for "Algorithm"

showing 10 items of 4887 documents

Sorting suffixes of a text via its Lyndon Factorization

2013

The process of sorting the suffixes of a text plays a fundamental role in Text Algorithms. They are used for instance in the constructions of the Burrows-Wheeler transform and the suffix array, widely used in several fields of Computer Science. For this reason, several recent researches have been devoted to finding new strategies to obtain effective methods for such a sorting. In this paper we introduce a new methodology in which an important role is played by the Lyndon factorization, so that the local suffixes inside factors detected by this factorization keep their mutual order when extended to the suffixes of the whole word. This property suggests a versatile technique that easily can b…

FOS: Computer and information sciencesBWTLyndon FactorizationSettore INF/01 - InformaticaSorting Suffixes; Lyndon Factorization; Lyndon WordsSuffix arrayComputer Science - Data Structures and AlgorithmsData_FILESData Structures and Algorithms (cs.DS)Lyndon wordSorting suffixeSorting SuffixesLyndon Words
researchProduct

Novel Results on the Number of Runs of the Burrows-Wheeler-Transform

2021

The Burrows-Wheeler-Transform (BWT), a reversible string transformation, is one of the fundamental components of many current data structures in string processing. It is central in data compression, as well as in efficient query algorithms for sequence data, such as webpages, genomic and other biological sequences, or indeed any textual data. The BWT lends itself well to compression because its number of equal-letter-runs (usually referred to as $r$) is often considerably lower than that of the original string; in particular, it is well suited for strings with many repeated factors. In fact, much attention has been paid to the $r$ parameter as measure of repetitiveness, especially to evalua…

FOS: Computer and information sciencesBurrows–Wheeler transformSettore INF/01 - InformaticaCombinatorics on wordsFormal Languages and Automata Theory (cs.FL)Computer scienceString (computer science)Search engine indexingCompressed data structuresComputer Science - Formal Languages and Automata TheoryString indexingData structureMeasure (mathematics)Burrows-Wheeler-TransformRepetitivenessCombinatorics on wordsBurrows-Wheeler-Transform Compressed data structures String indexing Repetitiveness Combinatorics on wordsTransformation (function)Computer Science - Data Structures and AlgorithmsData Structures and Algorithms (cs.DS)AlgorithmData compression
researchProduct

Adaptive learning of compressible strings

2020

Suppose an oracle knows a string $S$ that is unknown to us and that we want to determine. The oracle can answer queries of the form "Is $s$ a substring of $S$?". In 1995, Skiena and Sundaram showed that, in the worst case, any algorithm needs to ask the oracle $\sigma n/4 -O(n)$ queries in order to be able to reconstruct the hidden string, where $\sigma$ is the size of the alphabet of $S$ and $n$ its length, and gave an algorithm that spends $(\sigma-1)n+O(\sigma \sqrt{n})$ queries to reconstruct $S$. The main contribution of our paper is to improve the above upper-bound in the context where the string is compressible. We first present a universal algorithm that, given a (computable) compre…

FOS: Computer and information sciencesCentroid decompositionGeneral Computer ScienceString compressionAdaptive learningKolmogorov complexityContext (language use)Data_CODINGANDINFORMATIONTHEORYString reconstructionTheoretical Computer ScienceCombinatoricsString reconstruction; String learning; Adaptive learning; Kolmogorov complexity; String compression; Lempel-Ziv; Centroid decomposition; Suffix treeSuffix treeIntegerComputer Science - Data Structures and AlgorithmsOrder (group theory)Data Structures and Algorithms (cs.DS)Adaptive learning; Centroid decomposition; Kolmogorov complexity; Lempel-Ziv; String compression; String learning; String reconstruction; Suffix treeTime complexityComputer Science::DatabasesMathematicsLempel-ZivSettore INF/01 - InformaticaLinear spaceString (computer science)SubstringBounded functionString learningTheoretical Computer Science
researchProduct

Nonlinearities and Adaptation of Color Vision from Sequential Principal Curves Analysis

2016

Mechanisms of human color vision are characterized by two phenomenological aspects: the system is nonlinear and adaptive to changing environments. Conventional attempts to derive these features from statistics use separate arguments for each aspect. The few statistical explanations that do consider both phenomena simultaneously follow parametric formulations based on empirical models. Therefore, it may be argued that the behavior does not come directly from the color statistics but from the convenient functional form adopted. In addition, many times the whole statistical analysis is based on simplified databases that disregard relevant physical effects in the input signal, as, for instance…

FOS: Computer and information sciencesColor visionComputer scienceCognitive NeuroscienceComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISIONStandard illuminantMachine Learning (stat.ML)Models BiologicalArts and Humanities (miscellaneous)Statistics - Machine LearningPsychophysicsHumansLearningComputer SimulationChromatic scaleParametric statisticsPrincipal Component AnalysisColor VisionNonlinear dimensionality reductionAdaptation PhysiologicalNonlinear systemNonlinear DynamicsFOS: Biological sciencesQuantitative Biology - Neurons and CognitionMetric (mathematics)A priori and a posterioriNeurons and Cognition (q-bio.NC)AlgorithmColor PerceptionPhotic Stimulation
researchProduct

Uncommon Suffix Tries

2011

Common assumptions on the source producing the words inserted in a suffix trie with $n$ leaves lead to a $\log n$ height and saturation level. We provide an example of a suffix trie whose height increases faster than a power of $n$ and another one whose saturation level is negligible with respect to $\log n$. Both are built from VLMC (Variable Length Markov Chain) probabilistic sources; they are easily extended to families of sources having the same properties. The first example corresponds to a ''logarithmic infinite comb'' and enjoys a non uniform polynomial mixing. The second one corresponds to a ''factorial infinite comb'' for which mixing is uniform and exponential.

FOS: Computer and information sciencesCompressed suffix arrayPolynomialLogarithmGeneral MathematicsSuffix treevariable length Markov chain[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Generalized suffix treeprobabilistic source0102 computer and information sciences02 engineering and technologysuffix trie01 natural scienceslaw.inventionCombinatoricslawComputer Science - Data Structures and AlgorithmsTrieFOS: Mathematics0202 electrical engineering electronic engineering information engineeringData Structures and Algorithms (cs.DS)Mixing (physics)[ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS]MathematicsDiscrete mathematicsApplied MathematicsProbability (math.PR)020206 networking & telecommunicationssuffix trie.Computer Graphics and Computer-Aided Design[MATH.MATH-PR]Mathematics [math]/Probability [math.PR]010201 computation theory & mathematicsmixing properties60J05 37E05Suffix[ MATH.MATH-PR ] Mathematics [math]/Probability [math.PR]Mathematics - ProbabilitySoftware
researchProduct

Adaptive Lower Bound for Testing Monotonicity on the Line

2018

In the property testing model, the task is to distinguish objects possessing some property from the objects that are far from it. One of such properties is monotonicity, when the objects are functions from one poset to another. This is an active area of research. In this paper we study query complexity of $\epsilon$-testing monotonicity of a function $f\colon [n]\to[r]$. All our lower bounds are for adaptive two-sided testers. * We prove a nearly tight lower bound for this problem in terms of $r$. The bound is $\Omega(\frac{\log r}{\log \log r})$ when $\epsilon = 1/2$. No previous satisfactory lower bound in terms of $r$ was known. * We completely characterise query complexity of this probl…

FOS: Computer and information sciencesComputer Science - Computational Complexity000 Computer science knowledge general worksComputer Science - Data Structures and AlgorithmsComputer ScienceData Structures and Algorithms (cs.DS)Computational Complexity (cs.CC)
researchProduct

Fast Matrix Multiplication: Limitations of the Laser Method

2014

Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time $O(n^{2.3755})$. Recently, a surge of activity by Stothers, Vassilevska-Williams, and Le Gall has led to an improved algorithm running in time $O(n^{2.3729})$. These algorithms are obtained by analyzing higher and higher tensor powers of a certain identity of Coppersmith and Winograd. We show that this exact approach cannot result in an algorithm with running time $O(n^{2.3725})$, and identify a wide class of variants of this approach which cannot result in an algorithm with running time $O(n^{2.3078})$; in particular, this approach cannot prove the conjecture that f…

FOS: Computer and information sciencesComputer Science - Computational ComplexityComputer Science - Data Structures and AlgorithmsData Structures and Algorithms (cs.DS)Computational Complexity (cs.CC)
researchProduct

Quantum versus Classical Online Streaming Algorithms with Advice

2018

We consider online algorithms with respect to the competitive ratio. Here, we investigate quantum and classical one-way automata with non-constant size of memory (streaming algorithms) as a model for online algorithms. We construct problems that can be solved by quantum online streaming algorithms better than by classical ones in a case of logarithmic or sublogarithmic size of memory, even if classical online algorithms get advice bits. Furthermore, we show that a quantum online algorithm with a constant number of qubits can be better than any deterministic online algorithm with a constant number of advice bits and unlimited computational power.

FOS: Computer and information sciencesComputer Science - Computational ComplexityQuantum PhysicsComputer Science - Data Structures and AlgorithmsFOS: Physical sciencesData Structures and Algorithms (cs.DS)Computational Complexity (cs.CC)Quantum Physics (quant-ph)
researchProduct

Quantum versus Classical Online Streaming Algorithms with Logarithmic Size of Memory

2023

We consider online algorithms with respect to the competitive ratio. Here, we investigate quantum and classical one-way automata with non-constant size of memory (streaming algorithms) as a model for online algorithms. We construct problems that can be solved by quantum online streaming algorithms better than by classical ones in a case of logarithmic or sublogarithmic size of memory.

FOS: Computer and information sciencesComputer Science - Computational ComplexityQuantum PhysicsFormal Languages and Automata Theory (cs.FL)General MathematicsComputer Science - Data Structures and AlgorithmsFOS: Physical sciencesData Structures and Algorithms (cs.DS)Computer Science - Formal Languages and Automata TheoryComputational Complexity (cs.CC)Quantum Physics (quant-ph)
researchProduct

Hybrid blind robust image watermarking technique based on DFT-DCT and Arnold transform

2018

In this paper, a robust blind image watermarking method is proposed for copyright protection of digital images. This hybrid method relies on combining two well-known transforms that are the discrete Fourier transform (DFT) and the discrete cosine transform (DCT). The motivation behind this combination is to enhance the imperceptibility and the robustness. The imperceptibility requirement is achieved by using magnitudes of DFT coefficients while the robustness improvement is ensured by applying DCT to the DFT coefficients magnitude. The watermark is embedded by modifying the coefficients of the middle band of the DCT using a secret key. The security of the proposed method is enhanced by appl…

FOS: Computer and information sciencesComputer Science - Cryptography and SecurityComputer Networks and CommunicationsComputer scienceMultiple Watermarking02 engineering and technologyDiscrete Fourier transformImage (mathematics)Digital imageDiscrete Fourier transform (DFT)SchemeRobustness (computer science)Quantization0202 electrical engineering electronic engineering information engineeringMedia TechnologyDiscrete cosine transformHybrid method[INFO]Computer Science [cs]Digital watermarkingDiscrete cosine transform (DCT)DistanceImage watermarking020207 software engineeringWatermarkMultimedia (cs.MM)Hardware and ArchitectureMedical ImagesEmbedding020201 artificial intelligence & image processingArnold transformWavelet DomainSvdCryptography and Security (cs.CR)AlgorithmCopyright protectionSoftwareComputer Science - Multimedia
researchProduct