Algorithms

320 KiB

Open AccessArticle

A Catalog of Self-Affine Hierarchical Entropy Functions

by John Kieffer

Algorithms 2011, 4(4), 307-333; https://0-doi-org.brum.beds.ac.uk/10.3390/a4040307 - 01 Nov 2011

Viewed by 6732

For fixed k ≥ 2 and fixed data alphabet of cardinality m, the hierarchical type class of a data string of length n = k^j for some j ≥ 1 is formed by permuting the string in all possible ways under permutations [...] Read more.

For fixed k ≥ 2 and fixed data alphabet of cardinality m, the hierarchical type class of a data string of length n = k^j for some j ≥ 1 is formed by permuting the string in all possible ways under permutations arising from the isomorphisms of the unique finite rooted tree of depth j which has n leaves and k children for each non-leaf vertex. Suppose the data strings in a hierarchical type class are losslessly encoded via binary codewords of minimal length. A hierarchical entropy function is a function on the set of m-dimensional probability distributions which describes the asymptotic compression rate performance of this lossless encoding scheme as the data length n is allowed to grow without bound. We determine infinitely many hierarchical entropy functions which are each self-affine. For each such function, an explicit iterated function system is found such that the graph of the function is the attractor of the system. Full article

(This article belongs to the Special Issue Data Compression, Communication and Processing)

► Show Figures

521 KiB

Open AccessArticle

An Algorithm to Compute the Character Access Count Distribution for Pattern Matching Algorithms

by Tobias Marschall and Sven Rahmann

Algorithms 2011, 4(4), 285-306; https://0-doi-org.brum.beds.ac.uk/10.3390/a4040285 - 31 Oct 2011

Cited by 3 | Viewed by 8709

Abstract

We propose a framework for the exact probabilistic analysis of window-based pattern matching algorithms, such as Boyer–Moore, Horspool, Backward DAWG Matching, Backward Oracle Matching, and more. In particular, we develop an algorithm that efficiently computes the distribution of a pattern matching algorithm’s running [...] Read more.

We propose a framework for the exact probabilistic analysis of window-based pattern matching algorithms, such as Boyer–Moore, Horspool, Backward DAWG Matching, Backward Oracle Matching, and more. In particular, we develop an algorithm that efficiently computes the distribution of a pattern matching algorithm’s running time cost (such as the number of text character accesses) for any given pattern in a random text model. Text models range from simple uniform models to higher-order Markov models or hidden Markov models (HMMs). Furthermore, we provide an algorithm to compute the exact distribution of differences in running time cost of two pattern matching algorithms. Methodologically, we use extensions of finite automata which we call deterministic arithmetic automata (DAAs) and probabilistic arithmetic automata (PAAs) [1]. Given an algorithm, a pattern, and a text model, a PAA is constructed from which the sought distributions can be derived using dynamic programming. To our knowledge, this is the first time that substring- or suffix-based pattern matching algorithms are analyzed exactly by computing the whole distribution of running time cost. Experimentally, we compare Horspool’s algorithm, Backward DAWG Matching, and Backward Oracle Matching on prototypical patterns of short length and provide statistics on the size of minimal DAAs for these computations. Full article

(This article belongs to the Special Issue Selected Papers from LATA 2010)

► Show Figures

536 KiB

Open AccessArticle

The Smallest Grammar Problem as Constituents Choice and Minimal Grammar Parsing

by Rafael Carrascosa, François Coste, Matthias Gallé and Gabriel Infante-Lopez

Algorithms 2011, 4(4), 262-284; https://0-doi-org.brum.beds.ac.uk/10.3390/a4040262 - 26 Oct 2011

Cited by 8 | Viewed by 8359

Abstract

The smallest grammar problem—namely, finding a smallest context-free grammar that generates exactly one sequence—is of practical and theoretical importance in fields such as Kolmogorov complexity, data compression and pattern discovery. We propose a new perspective on this problem by splitting it into two [...] Read more.

The smallest grammar problem—namely, finding a smallest context-free grammar that generates exactly one sequence—is of practical and theoretical importance in fields such as Kolmogorov complexity, data compression and pattern discovery. We propose a new perspective on this problem by splitting it into two tasks: (1) choosing which words will be the constituents of the grammar and (2) searching for the smallest grammar given this set of constituents. We show how to solve the second task in polynomial time parsing longer constituent with smaller ones. We propose new algorithms based on classical practical algorithms that use this optimization to find small grammars. Our algorithms consistently find smaller grammars on a classical benchmark reducing the size in 10% in some cases. Moreover, our formulation allows us to define interesting bounds on the number of small grammars and to empirically compare different grammars of small size. Full article

(This article belongs to the Special Issue Selected Papers from LATA 2010)

► Show Figures

1428 KiB

Open AccessArticle

Radio Frequency Interference Detection and Mitigation Algorithms Based on Spectrogram Analysis

by Jose Miguel Tarongi and Adriano Camps

Algorithms 2011, 4(4), 239-261; https://0-doi-org.brum.beds.ac.uk/10.3390/a4040239 - 25 Oct 2011

Cited by 30 | Viewed by 9369

Abstract

Radio Frequency Interference (RFI) detection and mitigation algorithms based on a signal’s spectrogram (frequency and time domain representation) are presented. The radiometric signal’s spectrogram is treated as an image, and therefore image processing techniques are applied to detect and mitigate RFI by two-dimensional [...] Read more.

Radio Frequency Interference (RFI) detection and mitigation algorithms based on a signal’s spectrogram (frequency and time domain representation) are presented. The radiometric signal’s spectrogram is treated as an image, and therefore image processing techniques are applied to detect and mitigate RFI by two-dimensional filtering. A series of Monte-Carlo simulations have been performed to evaluate the performance of a simple thresholding algorithm and a modified two-dimensional Wiener filter. Full article

► Show Figures

493 KiB

Open AccessArticle

Applying Length-Dependent Stochastic Context-Free Grammars to RNA Secondary Structure Prediction

by Frank Weinberg and Markus E. Nebel

Algorithms 2011, 4(4), 223-238; https://0-doi-org.brum.beds.ac.uk/10.3390/a4040223 - 21 Oct 2011

Cited by 3 | Viewed by 7234

Abstract

In order to be able to capture effects from co-transcriptional folding, we extend stochastic context-free grammars such that the probability of applying a rule can depend on the length of the subword that is eventually generated from the symbols introduced by the rule, [...] Read more.

In order to be able to capture effects from co-transcriptional folding, we extend stochastic context-free grammars such that the probability of applying a rule can depend on the length of the subword that is eventually generated from the symbols introduced by the rule, and we show that existing algorithms for training and for determining the most probable parse tree can easily be adapted to the extended model without losses in performance. Furthermore, we show that the extended model is suited to improve the quality of predictions of RNA secondary structures. The extended model may also be applied to other fields where stochastic context-free grammars are used like natural language processing. Additionally some interesting questions in the field of formal languages arise from it. Full article

(This article belongs to the Special Issue Selected Papers from LATA 2010)

► Show Figures

Journal Menu

Journal Browser

Algorithms, Volume 4, Issue 4 (December 2011) – 5 articles , Pages 223-333

Further Information

Guidelines

MDPI Initiatives

Follow MDPI