|
Abstract : |
1 Introduction Consider two persons, P and Q; assume that P knows a binary string x and Q knows a binary string y (that is assumed to be close to x, see below). The persons can send bits to each other (Figure 1). P wants to know the string y; the communication protocol should require as few bits as possible using the fact that P already knows the string x that y is close to. The distance between y and x is measured by the number of edit operations needed to transform x into y (see Definition 2.1); let us mention that distance in our sense is not symmetric. We present a probabilistic algorithm and estimate the number of transmitted bits and running time., |
