Approximate String Matching Algorithm

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):
  • Smith-Waterman Sequence Alignment Algorithm.
  • Needleman-Wunsch Sequence Alignment Algorithm.
  • improved levenshtein http://www.perlmonks.org/?node_id=333616
  • http://search.cpan.org/dist/Text-Levenshtein/
• Counter-Example(s):
  • any Exact String Matching Algorithm, such as the Knuth-Morris-Pratt String Matching Algorithm.
  • any Approximate Tuple Matching Algorithm.
  • any Approximate Graph Matching Algorithm.
• 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).

---