Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.
About 708 papers for “Approximate string matching”
Brad Harris · 2013
The problem of string matching is very simply stated. Given a body of text T[1…n] we try to find a pattern P[1…m] where m ≤ n. This can be used to search bodies of text for specific patterns, or in biology, can be used to search strands of DNA for specific sequences of genes. The problem of exact string matching has
Cited by 0
Gonzalo Navarro · Encyclopedia of Algorithms · 2014
Cited by 6
Wing‐Kin Sung · Encyclopedia of Algorithms · 2016
Cited by 0
Esko Ukkonen · Lecture notes in computer science · 1983
Cited by 139
Ricardo Baeza-Yates, Gonzalo Navarro · 1999
We present a new algorithm for on-line approximate string matching. The algorithm is based on the simulation of a non-deterministic finite automaton built from the pattern and using the text as input. This simulation uses bit operations on a RAM machine with word length w = \\Omega\\Gamma137 n) bits, where n is the text size. This is essentially similar to the model used in Wu and Manber's work, although we improve the search time by packing the automaton states differently. The running time achieved is O(n) for small patterns (i.e. whenever mk = O(log n)), where m is the pattern length and k ! m the number of allowed errors. This is in contrast with the result of Wu and Manber, which is O(kn) for m = O(log n). Longer patterns can be processed by partitioning the automaton into many machine words, at O(mk=w n) search cost. We allow generalizations in the pattern, such as classes of characters, gaps and others, at essentially the same search cost. We then explore other novel techniques t...
Cited by 0
Esko Ukkonen · Information and Control · 1985
Cited by 616
Jong Yong Kim, John Shawe‐Taylor · Theoretical Computer Science · 1992
Cited by 27
Maxime Crochemore, Costas S. Iliopoulos, C. Makris et al. · 2002
In this paper we consider several new versions of approximate string matching with gaps. The main characteristic of these new versions is the existence of gaps in the matching of a given pattern in a text. Algorithms are sketched for each version and their time and space complexity is stated. The specific versions of approximate string matching have various applications in computerized music analysis.
Cited by 1
Heping Shang, T.H. Merrettal · IEEE Transactions on Knowledge and Data Engineering · 1996
Tries offer text searches with costs which are independent of the size of the document being searched, and so are important for large documents requiring spelling checkers, case insensitivity, and limited approximate regular secondary storage. Approximate searches, in which the search pattern differs from the document by k substitutions, transpositions, insertions or deletions, have hitherto been carried out only at costs linear in the size of the document. We present a trie based method whose cost is independent of document size. Our experiments show that this new method significantly outperforms the nearest competitor for k=0 and k=1, which are arguably the most important cases. The linear cost (in k) of the other methods begins to catch up, for our small files, only at k=2. For larger files, complexity arguments indicate that tries will outperform the linear methods for larger values of k. The indexes combine suffixes and so are compact in storage. When the text itself does not need to be stored, as in a spelling checker, we even obtain negative overhead: 50% compression. We discuss a variety of applications and extensions, including best match (for spelling checkers), case insensitivity, and limited approximate regular expression matching.
Cited by 58
Daniel Lopresti, Gordon Wilfong · 1999
Approximate string matching is an important paradigm in domains ranging from speech recognition to information retrieval and molecular biology. In this paper, we introduce a new formalism for a class of applications that takes two strings as input, each specified in terms of a particular domain, and performs a comparison motivated by constraints derived from a third, possibly different domain. This issue arises, for example, when searching multimedia databases built using imperfect recognition technologies (e.g., speech, optical character, and handwriting recognition). We present a polynomial time algorithm for solving the problem, and describe several variations that can also be solved efficiently.
Cited by 0
Dimitris Papamichail, Georgios Papamichail · 2009
Cited by 0
Maxime Crochemore, Costas S. Iliopoulos, Thierry Lecroq et al. · HAL (Le Centre pour la Communication Scientifique Directe) · 2001
Abstract. Here we consider computational problems on ffi-approximate and(ffi; fl)-approximate string matching. These are two new notions of approximate matching that arise naturally in applications of computer assisted music analy-sis. We present fast, efficient and practical algorithms for these two notions of approximate string matching.
Cited by 17Open access
Lok-lam Cheng · 2003
Approximate string matching on large DNA sequences data is very important in bioinformatics. Some studies have shown that suffix tree is an efficient data structure for approximate string matching. It performs better than suffix array if the data structure can be stored entirely in the memory. However, our study find that suffix array is much better than suffix tree for indexing the DNA sequences since the data structure has to be created and stored on the disk due to its size. We propose a novel auxiliary data structure which greatly improves the efficiency of suffix array in the approximate string matching problem in the external memory model. The second problem we have tackled is the parallel approximate matching in DNA sequence. We propose 2 novel parallel algorithms for this problem and implement them on a PC cluster. The result shows that when the error allowed is small, a direct partitioning of the array over the machines in the cluster is a more efficient approach. On the other hand, when the error allowed is large, partitioning the data over the machines is a better approach.
Cited by 7Open access
Juha Kärkkäinen, Joong Chae Na · Society for Industrial and Applied Mathematics eBooks · 2007
We introduce a new filtering method for approximate string matching called the suffix filter. It has some similarity with well-known filtration algorithms, which we call factor filters, and which are among the best practical algorithms for approximate string matching using a text index. Suffix filters are stronger, i.e., produce fewer false matches than factor filters. We demonstrate experimentally that suffix filters are faster in practice, too.
Cited by 27
Alfonso Alba, Margarita Rodríguez‐Kessler, Edgar Arce-Santana et al. · 2012
A 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. The resulting algorithm provides a finer control over the false positive rate, allowing users to pick out relevant matchings in less time, and can be applied for both offline and online processing.
Cited by 3
Heikki Hyyrö, Gonzalo Navarro · 2002
We present a new bit-parallel technique for approximate string matching. We build on two previous techniques. The first one [Myers, J. of the ACM, 1999], searches for a pattern of length m in a text of length n permitting k differences in O(mn=w) time, where w is the width of the computer word. The second one [Navarro and Raffinot, ACM JEA, 2000], extends a sublinear-time exact algorithm to approximate searching. The latter technique makes use of an O(kmn=w) time algorithm [Wu and Manber, Comm. ACM, 1992] for its internal workings. This algorithm is slow but flexible enough to support all the required operations. In this paper we show that the faster algorithm of Myers can be adapted to support all those operations. This involves extending it to compute edit distance, to search for any pattern suffix, and to detect in advance the impossibility of a later match. The result is an algorithm that performs better than the original version of Navarro and Raffinot and that is the fastest for several combinations of m, k and alphabet sizes that are useful, for example, in natural language searching and computational biology.
Cited by 0
Chan, H.-L., Lam, T.-W., Sung, W.-K. et al. · National University of Singapore · 2006
Abstract. We revisit the problem of indexing a string S[1..n] to support searching all substrings in S that match a given pattern P [1..m] with at most k errors. Previous solutions either require an index of size exponential in k or need Ω(m k) time for searching. Motivated by the indexing of DNA sequences, we investigate space efficient indexes that occupy only O(n) space. For k = 1, we give an index to support matching in O(m + occ + log n log log n) time. The previously best solution achieving this time complexity requires an index of size O(n log n). This new index can be used to improve existing indexes for k ≥ 2 errors. Among others, it can support matching with k = 2 errors in O(m log n log log n + occ) time. 1
Cited by 0
Gonzalo Navarro · 1997
. We present a very simple and efficient algorithm for online multiple approximate string matching. It uses a previously known counting-based filter [9] that searches for a single pattern by quickly discarding uninteresting parts of the text. Our multi-pattern algorithm is based on the simulation of many parallel filters using bits of the computer word. Our average complexity to search r patterns of length m is O(rn log m= log n), being n is the text size. We can search patterns of different length, each one with a different number of errors. We show experimentally that our algorithm is competitive with the fastest known algorithms, being the fastest for a wide range of intermediate error ratios. We give the first average-case analysis of the filtering efficiency of the counting method, applicable also to [9]. 1 Introduction A number of important problems related to string processing lead to algorithms for approximate string matching: text searching, pattern recognition, computationa...
Cited by 0
Simon Gene Gottlieb, Knut Reinert · NAR Genomics and Bioinformatics · 2025
Finding approximate occurrences of a query in a text using a full-text index is a central problem in stringology with many applications, especially in bioinformatics. The recent work has shown significant speed-ups by combining bidirectional indices and employing variations of <i>search schemes</i>. Search schemes partition a query and describe how to search the resulting parts with a given error bound. The performance of search schemes can be approximated by the <i>node count</i>, which represents an upper bound of the number of search steps. Finding <i>optimum search schemes</i> is a difficult combinatorial optimization problem that becomes hard to solve for four and more errors. This paper improves on a few topics important to search scheme based searches: First, we show how search schemes can be used to model previously published approximate search strategies such as suffix filters, 01*0-seeds, or the pigeonhole principle. This unifies these strategies in the search scheme framework, makes them easily comparable and results in novel search schemes that allow for any number of errors. Second, we present a search scheme construction heuristic, which is on par with optimum search schemes and has a better node count than any known search scheme for equal or above four errors. Finally, using the different search schemes, we show that the node count measure is not an ideal performance metric and therefore propose an improved performance metric called the <i>weighted node count</i>, which approximates a search algorithm's run time much more accurately.
Cited by 1Open access
Toth, Róbert · Brno University of Technology Digital Library (Brno University of Technology) · 2014
Tato práce se zabývá problémem přibližného vyhledávání řetězců, označovaným též jako vyhledávání s chybami. Práce se zaměřuje na oblast offline algoritmů, které umožňují po jednorazovém předspracování textu velmi rychlé vyhledávaní díky indexu, který si nad textem vytvoří. Nejprve bude definován problém samotný a demonstrována rozmanitost jeho využití, následována krátkým shrnutím rozdílných přístupů k této problematice. Poté budou detailně probrány některé algoritmy založené na použití suffixových stromů a představen nový hybridní algoritmus. Algoritmy budou implementovány v jazyce C a jejich výkonnost detailně otestována v sérii experimentů se zaměřením na určení reálného přínosu nového algoritmu do této oblasti.
Cited by 0