Wyniki wyszukiwania - BazTech

1

Finding Patterns In Given Intervals

Crochemore M., Iliopoulos C.S., Kubica M., Rahman M.S., Waleń T.

Fundamenta Informaticae

|

2010

|

Vol. 101, nr 3

173-186

EN

In this paper, we study the pattern matching problem in given intervals. Depending on whether the intervals are given a priori for pre-processing, or during the query along with the pattern or, even in both the cases, we develop efficient solutions for different variants of this problem. In particular, we present efficient indexing schemes for each of the above variants of the problem.

2

External Memory Algorithms for String Problems

Roh K., Crochemore M., Iliopoulos C.S., Park K.

Fundamenta Informaticae

|

2008

|

Vol. 84, nr 1

17-32

EN

In this paper we present external memory algorithms for some string problems. External memory algorithms have been developed in many research areas, as the speed gap between fast internal memory and slow external memory continues to grow. The goal of external memory algorithms is to minimize the number of input/output operations between internal memory and external memory. These years the sizes of strings such as DNA sequences are rapidly increasing. However, external memory algorithms have been developed for only a few string problems. In this paper we consider five string problems and present external memory algorithms for them. They are the problems of finding the maximum suffix, string matching, period finding, Lyndon decomposition, and finding the minimum of a circular string. Every algorithm that we present here runs in a linear number of I/Os in the external memory model with one disk, and they run in an optimal number of disk I/Os in the external memory model with multiple disks.

3

Speeding-up Hirschberg and Hunt-Szymanski LCS Algorithms

Crochemore M., Iliopoulos C.S., Pinzon Y.J.

Fundamenta Informaticae

|

2003

|

Vol. 56, nr 1,2

89-103

EN

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.

4

Occurrence and Substring Heuristics for [ro]-Matching

Crochemore M., Iliopoulos C.S., Lecroq T., Pinzon Y.J., Plandowski W., Rytter W.

Fundamenta Informaticae

|

2003

|

Vol. 56, nr 1,2

1-21

EN

We consider a version of pattern matching useful in processing large musical data: d-matching, which consists in finding matches which are d-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 (d,g)-matching, where g 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 d-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 d-BM1, d-BM2 and d-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 d-versions of suffix tries and subword graphs. Surprisingly, in the context of d-matching subword graphs appear to be superior compared with compact suffix trees.

5

Computing forbidden words of regular languages

Béal M-P., Crochemore M., Mignosi F., Restivo A., Sciortino M.

Fundamenta Informaticae

|

2003

|

Vol. 56, nr 1,2

121-135

EN

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.