The Prague Stringology Conference 2005

Ahmed Cheriat, Agata Savary, Béatrice Bouchou and Mírian Halfeld Ferrari

Incremental String Correction: Towards Correction of XML Documents

We define a problem of an incremental string-to-string correction with respect to a regular grammar. A user is given a valid word which may be updated through one or more editing operations. If the resulting word is invalid we propose correction candidates that take not only the incorrect word but also the initial valid word into account. The method is based on the error distance matrix calculation as proposed by [Oflazer96]. It has been developed in view of incremental XML document correction (as opposed to correction from scratch). Experimental results show a good performance of our algorithm despite its exponential theoretical complexity.

Download paper: Article in PostScript Article in PDF
 PostScript   PDF