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.
Flexible matching for noisy structural descriptions
ESPOSITO, Floriana;MALERBA, Donato;SEMERARO, Giovanni
1991-01-01
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
