Registered 2008-12-19 by Vamsi Kundeti

Given two strings S1 and S2 and three operations (Insert, delete, change) each with different costs, the sequence of operations to convert S1 to S2 is well known as the string editing problem. The minimum cost of transforming S1 to S2 is known as the the 'Edit Distance' between the strings S1 and S2. Computing the edit distance between strings has immense applications, in fact we use edit distance in our day to day life , edit distance is what gets computed when we 'diff' two files. Computing edit script is more general than just computing the edit distance, Hirschberg's algorithm gives a space efficient dynamic programming formulation for computing the edit script, the algorithm is recursive in nature. In this work we implement a non recursive version of the Hirschberg's algorithm. Our context of this problem is to build a highly area efficient VLSI hardware.

Computing the Edit script (minimum cost sequence of INSERT, DELETE and CHANGE) between two strings is a fundamental problem and occurs very frequently. Common UNIX utilities such as 'diff' are based on computing the edit script between tow strings. operations to transform string S1 to S2. I have the following idea to build a non-recursive version of the Hirschberg's algorithm, since the algorithm is non-recursive we can build an efficient digital circuit with this idea. We use a simple circular queue and apply DFS (Depth First Search) and we can prove that the capacity of this queue at any stage of the algorithm is θ(log(min(n1,n2)). The proof is simple we choose the geometrically decreasing string which has smaller length from the given strings(min(n1,n2)). Since we do a depth first search and the depth of subproblem tree is θ(log(min(n1,n2)), so we will have atmost θ(log(min(n1,n2)) subproblems in the circular queue at any stage of the algorithm.

Project information

Vamsi Kundeti
Not yet selected

RDF metadata

View full history Series and milestones

trunk series is the current focus of development.

All code Code

Version control system:

All packages Packages in Distributions

Get Involved

  • warning
    Report a bug
  • warning
    Ask a question
  • warning
    Help translate


Latest version is v0.9
released on 2008-12-19

All downloads