next up previous contents
Next: La recuperación incremental Up: El análisis incremental en Previous: El análisis incremental en

Descripción del problema

Consideremos el caso de una única modificación en la cadena de entrada. Sea la cadena original y , con , la cadena modificada. La entrada x tendrá la forma con

donde

Por tanto, la modificación ha consistido en sustituir por . Concretamente, en el caso de una inserción tenemos que con k > 0, en el caso del borrado y k < 0 y en el caso de una sustitución k=0.

A se le denomina punto de modificación relativa a w y x. Según esto podemos distinguir tres clases de items según su participación en el nuevo proceso de análisis:



Miguel A. Alonso Pardo
Thu Nov 20 15:31:06 CET 1997