On approximate string matching

Two practical universal source coding schemes are proposed. One is an approximate fixed length string matching data compression, and the other is LZ-type quasi parsing by approximate string matching. It is shown that in the former algorithm the compression rate converges to the theoretical bound of R(D) for a large class of processes as the database size and the string length tend to infinity. A similar result holds for the latter algorithm in the limit of infinite data base size. The performance of the two algorithms is evaluated where data base size is finite and string length finite. The duality between the two algorithms is proved with some asymptotic properties concerning the workings of an approximate string matching algorithm for ergodic stationary sources