A Bipartite Matching Approach to Approximate String Comparison and Search

Abstract: Approximate string comparison and search is an important part of applications that range from natural language to the interpretation of DNA. This paper presents a bipartite weighted graph matching approach to these problems, based on the authors' linear time matching algorithms (SODA94 pp. 65-76). Our approach's tolerance to permutation of symbols or blocks, distinguishes it from the widely used edit distance and finite state machine methods. A close relationship with the earlier related proximity comparison method is established.

Under the linear cost model, a simple O(1) time per position online algorithm is presented for comparing two strings given a fixed alignment. Heuristics are given for optimal alignment. In the approximate string search problem, one string advances in a fixed direction relative to the other with each time step. We introduce a new online algorithm for this setting which dynamically maintains an optimal bipartite weighted matching.

We discuss the application of our algorithms to natural language text search, including prefilters to improve efficiency, and the use of polygraphic symbols to improve search quality. Our approach is used in the LikeIt text search utility now under development. Its overall design and objectives are summarized.

Keywords: Approximate String Comparison, Approximate String Search, Text Search, Sequence Comparison, Bipartite Quasi-Convex Matching, Distance Metric, Natural Language Processing.

• View the complete paper (converted to HTML)

• The complete paper (PDF)

• The complete paper (PostScript)

• BibTex entry

• My homepage ( Peter N. Yianilos )

• See also:
  • Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-convex Tours
  • The LikeIt Intelligent String Comparison Facility
  • Netrics Corporation: The commercial source of the world's most advanced intelligent data quality solutions -- industrial-strength machine intelligence and learning technology for the international medical information processing industry, and others for whom database quality and robust operation is critical.
  • The LikeIt Intelligent String Comparison Facility (Software)
  • Solving the Minimum-Cost Matching Problem for Quasi-Convex Tours: An Efficient ANSI C Implementation
  • Quasi-Convex Matching (software)
  • Mulistage Intelligent String Comparison Method (patent pending)
  • Quasiconvex Bipartite Matching (patent pending)
  • The PF474 VLSI Chip
  • The Friendly Finder database utility
  • String comparator device system circuit and method (patent)
  • A dedicated compartor matches symbol strings fast and intelligently
  • String Comparator - A new tool for speech recognition
  • The application of a pattern matching algorithm to searching medical record text
  • The definition, computation, and application of symbol string similarity functions
  • PF474 Product Data Book

• Coauthors:
  • Sam Buss