20 Result(s)
within
Chapter
Conference Paper
Amihood Amir
Algorithm Analysis and Problem Complexity
Pattern Recognition
-
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
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
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
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
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
Approximate Matching in the L 1 Metric
Approximate matching is one of the fundamental problems in pattern matching, and a ubiquitous problem in real applications. The Hamming distance is a simple and well studied example of appro...
-
Chapter and Conference Paper
Asynchronous Pattern Matching
This paper introduces a new pattern matching model that has been gaining importance recently, that of Asynchronous Pattern Matching. Traditional pattern matching has assumed the possibility of errors in the data
-
Chapter and Conference Paper
Faster Two Dimensional 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 matching, ...
-
Chapter and Conference Paper
Approximate Matching in Weighted Sequences
Weighted sequences have been recently introduced as a tool to handle a set of sequences that are not identical but have many local similarities. The weighted sequence is a “statistical image” of this set, wher...
-
Chapter and Conference Paper
Property Matching and Weighted Matching
Pattern Matching with Properties (Property Matching, for short), involves a string matching between the pattern and the text, and the requirement that the text part satisfies some property.
-
Chapter and Conference Paper
Two-Dimensional Range Minimum Queries
We consider the two-dimensional Range Minimum Query problem: for a static (m ×n)-matrix of size N = mn which may be preprocessed, answer on-line queries of the form “where is the position of a minimum element in ...
-
Chapter and Conference Paper
Deterministic Length Reduction: Fast Convolution in Sparse Data and Applications
In this paper a deterministic algorithm for the length reduction problem is presented. This algorithm enables a new tool for performing fast convolution in sparse data. The proposed algorithm performs the conv...
-
Chapter and Conference Paper
Approximate String Matching with Address Bit Errors
A string S ∈ Σ m can be viewed as a set of pairs S = { (σ i , i) : i ∈ { 0,..., m − 1} }. We consider approx...
-
Chapter and Conference Paper
Quasi-distinct Parsing and Optimal Compression Methods
In this paper, the optimality proof of Lempel-Ziv coding is re-studied, and a much more general compression optimality theorem is derived. In particular, the property of quasi-distinct parsing is defined. This pr...
-
Chapter and Conference Paper
Dictionary Matching with One Gap
The dictionary matching with gaps problem is to preprocess a dictionary D of d gapped patterns P 1,…,P d over alphabet Σ, where each gapped pattern P ...
-
Chapter and Conference Paper
Algorithms for Jumbled Indexing, Jumbled Border and Jumbled Square on Run-Length Encoded Strings
Jumbled Indexing, the problem of indexing a text for histogram queries, has been of much interest lately. In this paper we consider jumbled indexing for run-length encoded texts. We refute a form...
-
Chapter and Conference Paper
On the Efficiency of the Hamming C-Centerstring Problems
The Consensus String Problem is that of finding a string, such that the maximum Hamming distance from it to a given set of strings of the same length is minimized. However, a generalization is necessary for clust...
-
Chapter and Conference Paper
Approximate On-line Palindrome Recognition, and Applications
Palindrome recognition is a classic problem in computer science. It is an example of a language that can not be recognized by a deterministic finite automaton and is often brought as an example of a problem wh...
-
Chapter and Conference Paper
Range LCP Queries Revisited
The Range LCP problem is to preprocess a string \(S[1\dots n]\) , to enable efficient solutions of the following query: given a ...
-
Chapter and Conference Paper
On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling
Vertex Relabeling is a variant of the graph relabeling problem. In this problem, the input is a graph and two vertex labelings, and the question is to determine how close are the labelings. The distance measur...
