Combinatorial Pattern Matching
12th Annual Symposium, CPM 2001 Jerusalem, Israel, July 1–4, 2001 Proceedings
Page
%P
-
Chapter and Conference Paper
Fast Parallel and Serial Multidimensional Approximate Array Matching
Consider the multidimensional array matching problem, where differences between characters of the pattern and characters of the text are permitted. A difference may be due to a mismatch between a text and patt...
-
Article
Efficient matching of nonrectangular shapes
Most known two-dimensional matching algorithms have a rectangular text (image) and rectangular pattern (template) as their input. These matching algorithms perform a row by row analysis followed by some column...
-
Chapter and Conference Paper
Efficient randomized dictionary matching algorithms
The standard string matching problem involves finding all occurrences of a single pattern in a single text. While this approach works well in many application areas, there are some domains in which it is more ...
-
Chapter and Conference Paper
Optimal two-dimensional compressed matching
Recent proliferation of digitized data and the expected unprecedented growth in the volume of stored and transmitted data motivated the definition of the compressed matching paradigm. This is the problem of ef...
-
Chapter and Conference Paper
Alphabet independent and dictionary scaled matching
The rapidly growing need for analysis of digitized images in multimedia systems has lead to a variety of interesting problems in multidimensional pattern matching. One of the problems is that of scaled matchin...
-
Chapter and Conference Paper
An improved deterministic algorithm for generalized random sampling
We consider the problem of deterministically selecting s uniformly random different m-element subsets of {1,..., k}. The only known lower bound for the time to solve this problem is the trivial Ω(sm). The best tw...
-
Chapter and Conference Paper
Pattern matching in hypertext
A myriad of textual problems have been considered in the pattern matching field with many non-trivial results. Nevertheless, surprisingly little work has been done on the natural combination of pattern matchin...
-
Chapter and Conference Paper
A new and versatile method for association generation
Current algorithms for finding associations among the attributes describing data in a database have a number of shortcomings:
-
Applicati...
-
-
Chapter and Conference Paper
Efficient special cases of pattern matching with swaps
Let a text string of n symbols and a pattern string P of m symbols from alphabet Σ be given. A swapped version T′ of T is a length n string derived from T by a series of local swaps, (i.e. t ℓ ...
-
Chapter and Conference Paper
Indexing and Dictionary Matching with One Error (Extended Abstract)
The indexing problem is the one where a text is preprocessed and subsequent queries of the form: “Find all occurrences of pattern P in the text” are answered in time proportional to the length of the query and th...
-
Chapter and Conference Paper
Approximate Swapped Matching
Let a text string T of n symbols and a pattern string P of m symbols from alphabet ∑ be given. A swapped version P′ of P is a length m string derived from P by a series of local swaps, (i.e. p′ ...
-
Book and Conference Proceedings
-
Chapter and Conference Paper
Dynamic Text and Static Pattern Matching
In this paper, we address a new version of dynamic pattern matching. The dynamic text and static pattern matching problem is the problem of finding a static pattern in a text that is continuously being updated. T...
-
Chapter and Conference Paper
Two-Dimensional Pattern Matching with Rotations
The problem of pattern matching with rotation is that of finding all occurrences of a two-dimensional pattern in a text, in all possible rotations. We prove an upper and lower bound on the number of such diffe...
-
Chapter and Conference Paper
Real Two Dimensional Scaled Matching
Scaled Matching refers to the problem of finding all locations in the text where the pattern, proportionally enlarged according to an arbitrary real-sized scale, appears. Scaled matching is ...
-
Chapter and Conference Paper
Function Matching: Algorithms, Applications, and a Lower Bound
We introduce a new matching criterion — function matching — that captures several different applications. The function matching. problem has as its input a text T of length n over alphabet Σ ...
-
Chapter and Conference Paper
Faster Two Dimensional Pattern Matching with Rotations
The most efficient currently known algorithms for two dimensional matching with rotation have a worst case time complexity of O(n 2 m 3), where the s...
-
Chapter and Conference Paper
Efficient One Dimensional Real Scaled Matching
Real Scaled Matching refers to the problem of finding all locations in the text where the pattern, proportionally enlarged according to an arbitrary real-sized scale, appears. Real scaled ma...
-
Chapter and Conference Paper
Swap and Mismatch Edit Distance
There is no known algorithm that solves the general case of approximate string matching problem with the extended edit distance, where the edit operations are: insertion, deletion, mismatch, and swap, in time o(n...
-
Chapter and Conference Paper
Speaker Indexing in Audio Archives Using Gaussian Mixture Scoring Simulation
Speaker indexing has recently emerged as an important task due to the rapidly growing volume of audio archives. Current filtration techniques still suffer from problems both in accuracy and efficiency. In this...
