Approximate String Matching Algorithm: Difference between revisions
Jump to navigation
Jump to search
m (Text replacement - "]]↵*" to "]]. *") |
m (Text replacement - "> ↵" to "> ") |
||
| Line 5: | Line 5: | ||
** It can be applied by an [[Approximate String Matching System]]. | ** It can be applied by an [[Approximate String Matching System]]. | ||
** … | ** … | ||
* <B>Example(s):</B> | * <B>Example(s):</B> | ||
** [[Smith-Waterman Sequence Alignment Algorithm]]. | ** [[Smith-Waterman Sequence Alignment Algorithm]]. | ||
** [[Needleman-Wunsch Sequence Alignment Algorithm]]. | ** [[Needleman-Wunsch Sequence Alignment Algorithm]]. | ||
** improved levenshtein http://www.perlmonks.org/?node_id=333616 | ** improved levenshtein http://www.perlmonks.org/?node_id=333616 | ||
** http://search.cpan.org/dist/Text-Levenshtein/ | ** http://search.cpan.org/dist/Text-Levenshtein/ | ||
* <B>Counter-Example(s):</B> | * <B>Counter-Example(s):</B> | ||
** any [[Exact String Matching Algorithm]], such as the [[Knuth-Morris-Pratt String Matching Algorithm]]. | ** any [[Exact String Matching Algorithm]], such as the [[Knuth-Morris-Pratt String Matching Algorithm]]. | ||
** any [[Approximate Tuple Matching Algorithm]]. | ** any [[Approximate Tuple Matching Algorithm]]. | ||
Revision as of 02:40, 27 March 2024
An Approximate String Matching Algorithm is a String Matching Algorithm that can solve an Approximate String Matching Task.
- Context:
- It can be a Sequence Alignment Algorithm.
- It can use a String Distance Function.
- It can be applied by an Approximate String Matching System.
- …
- Example(s):
- Counter-Example(s):
- See: Levenshtein Distance Function.
References
2002
- (Navarro & Raffinot, 2002) ⇒ Gonzalo Navarro, and Mathieu Raffinot. (2002). “Flexible Pattern Matching in Strings." Cambridge University Press.
2001
- Gonzalo Navarro, Ricardo Baeza-Yates, E. Sutinen, and J. Tarhio. (2001). “Indexing Methods for Approximate String Matching.” In: IEEE Data Engineering Bulletin, 24(4).
- (Navarro, 2001) ⇒ Gonzalo Navarro. (2001). “A Guided Tour to Approximate String Matching.” In: ACM Computing Surveys (CSUR), 33(1). doi:10.1145/375360.375365
1995
- J. Zobel, P. Dart. (1995). “Finding Approximate Matches in Large Lexicons.” In: Software-Practice & Experience 25(3), pp 331–345.
1991
- P. Jokinen and E. Ukkonen. (1991). “Two Algorithms for Approximate String Matching in Static Texts.” In: A. Tarlecki, editor, Mathematical Foundations of Computer Science.
1985
- E. Ukkonen. (1985). “Algorithms for Approximate String Matching.” In: Information and Control, 64.
1974
- (Wagner & Fischer, 1974) ⇒ Robert A. Wagner, and Michael J. Fischer. (1974). “The String to String Correction Problem.” In: Journal of the ACM (JACM), 21(1).