Lipschitz Embeddings

One of the well known approximate string matching algorithms is Lipschitz Embeddings. Here it goes:

Input: A text file T containing N strings (O_1, O₂,…….O_N) and a query object q.

Output: Nearest string to q with corresponding edit distance.

Steps:

1. Construct a text file R of k strings (A₁,A₂,……..A_k) by choosing randomly from N string

2. Compute F(q),the array of edit distances of the query object q to k strings of R, that is, F(q) = (d(q,A₁ ),d(q,A₂ ),……,d(q,A_k ) ) where, d(q,A_j ) is the edit distance between q and A_j .Here,1≤j≤k.

3. Compute F(O_i ),the array of edit distances of each string O_i in T to k reference strings in R.

         that is, F(O_i) =( (d(O_i ,A₁),(d(O_i , A₂ ),…….d(O_i , A_k ) ).Here,1≤ i ≤ N.

4. Calculate ∂(F(O_j ),F(q)),the distance between each string O_j of T to query string q in embedding  space where,

        

          where 1≤ j ≤ N, 1≤ i ≤ k, p=2.

    5. Find the minimum value among ∂(F(O_i ),F(q)), if the minimum is ∂(F(O_m ),F(q)),

         then find d(O_m ,q). (1≤i≤N).

   6. For i=1 to N,

      if(∂(F(O_i ),F(q))  > d(O_m ,q) )

           then edit_distance= d(O_m ,q) and nearest_string= O_m.

      else if (d(O_i ,q) < d(O_m ,q))

           then edit_distance= d(O_i ,q) and nearest_string = O_i

7.      Show the edit_distance and nearest_string.

See ya next time.