Flexible matching for noisy structural descriptions
Floriana Esposito, Donato Malerba, Giovanni Maria Semeraro · 1991
Uncertainty on data often makes the task of perfectly matching two descriptions quite ineffective. In this case, a flexible matching, measuring the similarity of two descriptions rather than their equality, is more useful. According to the convention of connecting similarity to the most common concept of distance, we present a definition of distance measure, based on a probabilistic interpretation of the matching predicate, which can cope with structural deformations. As the problem of matching two formulas of the FOPL is NP-complete, two methods arc presented in order to cope with complexity: firstly, a branch-and-bound algorithm, and secondly, a heuristic method. These ideas are applied to the problem of recognizing office documents in digital form according to their page layout. 1