The Likeit Intelligent String Comparison Facility

Abstract: A highly-efficient ANSI-C facility is described for intelligently comparing a query string with a series of database strings. The bipartite weighted matching approach taken tolerates ordering violations that are problematic for simple automaton or string edit distance methods---yet common in practice. The method is character and polygraph based and does not require that words are properly formed in a query. Database characters are processed at a rate of approximately 2.5 million per second using a 200MHz Pentium Pro processor. A subroutine-level API is described along with an simple executable utility supporting both command-line and Web interfaces. An optimized Web interface is also reported consisting of a daemon that preloads multiple databases, and a corresponding CGI stub. The daemon may be initiated manually or via inetd.

Keywords: String Comparison/Similarity, Text/Database Search/Retrieval, Bipartite Matching/Assignment, Edit Distance.

• 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
  • 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)
  • A Bipartite Matching Approach to Approximate String Comparison and Search
  • 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:
  • Kirk Kanzelberger