Results 141 to 150 of about 83,132 (184)
Some of the next articles are maybe not open access.
Approximate Boyer–Moore String Matching
SIAM Journal on Computing, 1993Summary: The Boyer-Moore idea applied in exact string matching is generalized to approximate string matching. Two versions of the problem are considered. The \(k\) mismatches problem is to find all approximate occurrences of a pattern string (length \(m\)) in a text string (length \(n\)) with at most \(k\) mismatches.
Tarhio, Jorma, Ukkonen, Esko
openaire +2 more sources
Spatial Approximate String Matching
2009 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, 2009In this investigation, we propose an algorithm for Spatial Approximate String Matching where k times of mismatch are allowed. There have been several algorithms proposed so far, but most of them examine the longest text strings, i.e., the longest one dimensional sequence of characters.
Akifumi Katsumata, Takao Miura
openaire +1 more source
Fast approximate string matching
Software: Practice and Experience, 1988AbstractApproximate string matching is an important operation in information systems because an input string is often an inexact match to the strings already stored. Commonly known accurate methods are computationally expensive as they compare the input string to every entry in the stored dictionary. This paper describes a two‐stage process.
O. Owolabi, D. R. McGregor
openaire +1 more source
VECTOR ALGORITHMS FOR APPROXIMATE STRING MATCHING
International Journal of Foundations of Computer Science, 2002Vector algorithms allow the computation of an output vector r = r1 r2 ⋯ rm given an input vector e = e1 e2 ⋯ em in a bounded number of operations, independent of m the length of the vectors. The allowable operations are usually restricted to bit-wise operations available in processors, including shifts and binary addition with carry.
Bergeron, Anne, Hamel, Sylvie
openaire +1 more source
Approximate string matching using phase correlation
2012 Annual International Conference of the IEEE Engineering in Medicine and Biology Society, 2012A novel method for approximate string matching with applications to bioinformatics is presented in this paper. Unlike most methods in the literature, the proposed method does not depend on the computation of the edit distance between two sequences, but uses instead a similarity index obtained by applying the phase correlation method.
Alfonso, Alba +3 more
openaire +2 more sources
Multiple approximate string matching
1997We present two new algorithms for on-line multiple approximate string matching. These are extensions of previous algorithms that search for a single pattern. The single-pattern version of the first one is based on the simulation with bits of a non-deterministic finite automaton built from the pattern and using the text as input.
Ricardo Baeza-Yates, Gonzalo Navarro
openaire +1 more source
On Approximate Jumbled Pattern Matching in Strings
Theory of Computing Systems, 2011zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Péter Burcsi +3 more
openaire +6 more sources
On approximate string matching
[Proceedings] DCC `93: Data Compression Conference, 2002Two practical universal source coding schemes are proposed. One is an approximate fixed length string matching data compression, and the other is LZ-type quasi parsing by approximate string matching. It is shown that in the former algorithm the compression rate converges to the theoretical bound of R(D) for a large class of processes as the database ...
openaire +1 more source
Approximate String Matching Techniques
Proceedings of the 16th International Conference on Enterprise Information Systems, 2014Data quality is a key to success for all kinds of businesses that have information applications involved, such as data integration for data warehouses, text and web mining, information retrieval, search engine for web applications, etc. In such applications, matching strings is one of the popular tasks. There are a number of approximate string matching
openaire +1 more source
Indexing Structures for Approximate String Matching
2003In this paper we give the first, to our knowledge, structures and corresponding algorithms for approximate indexing, by considering the Hamming distance, having the following properties. i) Their size is linear times a polylog of the size of the text on average. ii) For each pattern x, the time spent by our algorithms for finding the list occ(x) of all
A. GABRIELE +3 more
openaire +1 more source