Fundamenta Informaticae - Volume 56, issue 1-2

Authors: Smyth, Bill

Article Type: Other

Citation: Fundamenta Informaticae, vol. 56, no. 1-2, pp. i-ii, 2003

Authors: Crochemore, Maxime | Iliopoulos, Costas S. | Lecroq, Thierry | Pinzon, Yoan J. | Plandowski, Wojciech | Rytter, Wojciech

Article Type: Research Article

Abstract: We consider a version of pattern matching useful in processing large musical data: δ-matching, which consists in finding matches which are δ-approximate in the sense of the distance measured as maximum difference between symbols. The alphabet is an interval of integers, and the distance between two symbols a, b is measured as |a-b|. We also consider (δ, γ)-matching, where γ is a bound on the total sum of the differences. We first consider "occurrence heuristics" by …adapting exact string matching algorithms to the two notions of approximate string matching. The resulting algorithms are efficient in practice. Then we consider "substring heuristics". We present δ-matching algorithms fast on the average providing that the pattern is "non-flat" and the alphabet interval is large. The pattern is "flat" if its structure does not vary substantially. The algorithms, named δ-BM1, δ-BM2 and δ-BM3 can be thought as members of the generalized Boyer-Moore family of algorithms. The algorithms are fast on average. This is the first paper on the subject, previously only "occurrence heuristics" have been considered. Our substring heuristics are much stronger and refer to larger parts of texts (not only to single positions). We use δ-versions of suffix tries and subword graphs. Surprisingly, in the context of δ-matching subword graphs appear to be superior compared with compact suffix trees. Show more

Keywords: String algorithms, approximate string matching, dynamic programming, computer-assisted music analysis

Citation: Fundamenta Informaticae, vol. 56, no. 1-2, pp. 1-21, 2003

Authors: Kuri, Josué | Navarro, Gonzalo | Mé, Ludovic

Article Type: Research Article

Abstract: We present new search algorithms to detect the occurrences of any pattern from a given pattern set in a text, allowing in the occurrences a limited number of spurious text characters among those of the pattern. This is a common requirement in intrusion detection applications. Our algorithms exploit the ability to represent the search state of one or more patterns in the bits of a single machine word and update all the search states in a single …operation. We show analytically and experimentally that the algorithms are able of fast searching for large sets of patterns allowing a wide number of spurious characters, yielding in our machine about a 75-fold improvement over the classical dynamic programming algorithm. Show more

Keywords: Approximate string matching, bit-parallelism, security, audit trails

Citation: Fundamenta Informaticae, vol. 56, no. 1-2, pp. 23-49, 2003

Authors: Burkhardt, Stefan | Kärkkäinen, Juha

Article Type: Research Article

Abstract: A popular and well-studied class of filters for approximate string matching compares substrings of length q, the q-grams, in the pattern and the text to identify text areas that contain potential matches. A generalization of the method that uses gapped q-grams instead of contiguous substrings is mentioned a few times in literature but has never been analyzed in any depth. In this paper, we report the first results of a study on gapped q-grams. We show …that gapped q-grams can provide orders of magnitude faster and/or more efficient filtering than contiguous q-grams. To achieve these results the arrangement of the gaps in the q-gram and a filter parameter called threshold have to be optimized. Both of these tasks are nontrivial combinatorial optimization problems for which we present efficient solutions. We concentrate on the k mismatches problem, i.e, approximate string matching with the Hamming distance. Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 56, no. 1-2, pp. 51-70, 2003

Authors: Nicodème, Pierre

Article Type: Research Article

Abstract: In previous work [10], we considered algorithms related to the statistics of matches with words and regular expressions in texts generated by Bernoulli or Markov sources. In this work these algorithms are extended for two purposes: to determine the statistics of simultaneous counting of different motifs, and to compute the waiting time for the first match with a motif in a model which may be constrained. This extension also handles matches with errors. The package is …fully implemented and gives access to high and low level commands. We also consider an example corresponding to a practical biological problem: getting the statistics for the number of matches of words of size 8 in a genome (a Markovian sequence), knowing that an (overrepresented DNA protecting) pattern named Chi occurs a given number of times. Show more

Keywords: Marked automata, generating functions, computer algebra

Citation: Fundamenta Informaticae, vol. 56, no. 1-2, pp. 71-88, 2003

Authors: Crochemore, Maxime | Iliopoulous, Costas S. | Pinzon, Yoan J.

Article Type: Research Article

Abstract: Two algorithms are presented that solve the problem of recovering the longest common subsequence of two strings. The first algorithm is an improvement of Hirschberg's divide-and-conquer algorithm. The second algorithm is an improvement of Hunt-Szymanski algorithm based on an efficient computation of all dominant match points. These two algorithms use bit-vector operations and are shown to work very efficiently in practice.

Keywords: Longest Common Subsequence, bit-parallelism

Citation: Fundamenta Informaticae, vol. 56, no. 1-2, pp. 89-103, 2003

Authors: Jansson, Jesper | Lingas, Andrzej

Article Type: Research Article

Abstract: We present a fast algorithm for optimal alignment between two similar ordered trees with node labels. Let S and T be two such trees with |S| and |T| nodes, respectively. If there exists an optimal alignment between S and T which uses at most d blank symbols and d is known in advance, it can be constructed in O(n log n·(maxdeg)^3·d^2) time, where n=max{|S|,|T|} and maxdeg is the maximum degree of all nodes in S and …T. If d is not known in advance, we can construct an optimal alignment in O(n log n·(maxdeg)^3·f^2) time, where f is the difference between the highest possible score for any alignment between two trees having a total of |S|+|T| nodes and the score of an optimal alignment between S and T, if the scoring scheme satisfies some natural assumptions. In particular, if the degrees of both input trees are bounded by a constant, the running times reduce to O(n log n·d^2) and O(n log n·f^2), respectively. Show more

Citation: Fundamenta Informaticae, vol. 56, no. 1-2, pp. 105-120, 2003

Authors: Béal, Marie-Pierre | Crochemore, Maxime | Mignosi, Filippo | Restivo, Antonio | Sciortino, Marinella

Article Type: Research Article

Abstract: We give a quadratic-time algorithm to compute the set of minimal forbidden words of a factorial regular language. We give a linear-time algorithm to compute the minimal forbidden words of a finite set of words. This extends a previous result given for the case of a single word only. We also give quadratic-time algorithms to check whether a regular language is factorial or anti-factorial.

Keywords: Anti-factorial language, factor automaton, factorial language, failure function, forbidden word, formal languages, sofic shift, symbolic dynamics

Citation: Fundamenta Informaticae, vol. 56, no. 1-2, pp. 121-135, 2003

Authors: Gasieniec, Leszek | Potapov, Igor

Article Type: Research Article

Abstract: An exact pattern matching problem is to find all occurrences of a pattern p in a text t. We say that the pattern matching algorithm is optimal if its running time is linear in the sizes of t and p, i.e., O(t+p). Perhaps one of the most interesting settings of the pattern matching problem is when one has to design an efficient algorithm with a help of a small extra space. In this paper we explore this setting to the extreme. We work under an assumption that the text t is available …only in a compressed form, represented by a straight-line program. The compression methods based on efficient construction of straight-line programs are as competitive as the compression standards, including the Lempel-Ziv compression scheme and recently intensively studied text compression via block sorting, due to Burrows and Wheeler. Our main result is an algorithm that solves the compressed string matching problem in an optimal linear time, with a help of a constant extra space. We also discuss an efficient implementation of a version our algorithm showing that the new concept may have also some interesting real applications. Our result is in contrast with many other compressed pattern matching algorithms where the goal is to find all pattern occurrences in time related to the size of the compressed text. However one must remember that all previous algorithms used at least a linear (in a compressed text, a dictionary, or a pattern) extra memory while our algorithm can be implemented in a constant size extra space. Also from the practical point of view, when the compression ratio is constant (very rarely smaller than 25%), there is no dramatic difference between the running time based on the size of the compressed text and the size of the original text, while an extra space resources might be strictly limited. Show more

Keywords: Compressed pattern matching, straight-line program, directed acyclic graph traversal, small extra space

Citation: Fundamenta Informaticae, vol. 56, no. 1-2, pp. 137-154, 2003

Authors: Afrati, Foto | Leiß, Hans | de Rougemont, Michel

Article Type: Research Article

Abstract: A compression algorithm takes a finite structure of a class K as input and produces a finite structure of a different class K' as output. Given a property P on the class K defined in a logic ℒ, we study the definability of property P on the class K'. We consider two compression schemes on unary ordered structures (strings), compression by run-length encoding and the classical Lempel-Ziv-78 scheme. First-order properties of strings are first-order on run-length compressed strings, but this …fails for images, i.e. 2-dimensional strings. We present simple first-order properties of strings which are not first-order definable on strings compressed with the Lempel-Ziv-78 compression scheme. We show that all properties of strings that are first-order definable on strings are definable on Lempel-Ziv compressed strings in FO(TC), the extension of first-order logic with the transitive closure operator. We define a subclass F of the first-order properties of strings such that if P is a property in F, it is also first-order definable on the Lempel-Ziv compressed strings. Monadic second-order properties of strings, i.e. regular languages, are dyadic second-order definable on Lempel-Ziv compressed strings. Show more

Keywords: Logic, definability, string compression, Lempel-Ziv-78

Citation: Fundamenta Informaticae, vol. 56, no. 1-2, pp. 155-180, 2003