Cross-Domain Approximate String Matching

Overview

Approximate string matching is an important paradigm in domains ranging from speech recognition to information retrieval and molecular biology. This paper introduces 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). The paper presents a polynomial time algorithm for solving the problem, and describes several variations that can also be solved efficiently.