Scribd
Upload
7 views11 pages

Minimum Cost String Editing Algorithm

The document discusses the string editing problem, which involves transforming one string (X) into another (Y) using a minimum cost sequence of edit operations: insert, delete, and change. It outlines the cost values associated with each operation and presents a dynamic programming solution to compute the minimum cost for transforming the strings. The document also includes transformation rules and an example of converting the string 'HAND' into 'POND' with specified costs.

Uploaded by

abe.72007
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views11 pages

Minimum Cost String Editing Algorithm

The document discusses the string editing problem, which involves transforming one string (X) into another (Y) using a minimum cost sequence of edit operations: insert, delete, and change. It outlines the cost values associated with each operation and presents a dynamic programming solution to compute the minimum cost for transforming the strings. The document also includes transformation rules and an example of converting the string 'HAND' into 'POND' with specified costs.

Uploaded by

abe.72007
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

CS19341

Design and Analysis of Algorithms

DYNAMIC PROGRAMMING
STRING EDITING
PROBLEM STATEMENT:STRING
EDITING

Given two strings X and Y, the problem is to


transform String X to String Y using a minimum
cost sequence of edit operation.
PROBLEM STATEMENT:STRING
EDITING

Consider two Strings, Insert


X = x1x2x3x4x5.....xn ; Y = y1y2y3y4y5.....ym
Delete
where xi and yi are the members of alphabet Change
set
Transforming String X to String Y is made
Objective : Identify
using a sequence of edit operations on X minimum – cost
sequence of edit
Cost Value is associated with each operation operations
COST VALUE REPRESENTATION
FOR EACH OPERATION

Insert I(yj) – Cost of Inserting the


alphabet yj into string Y at jth
position
Delete D(xi) – Cost of Deleting the
alphabet xi from the string X at ith
position
Change C(xi,yj) – Cost of Changing the
alphabet xi of string X to yj of
String Y
DYNAMIC PROGRAMMING
SOLUTION
Define a Table Cost (i,j) - Table gives the minimum
cost for any edit sequence for transforming
x1x2x3.....xi to y1y2.....yj. for values 0<=i<=n and
0<=j<=m
Compute Cost(i,j) for each i and j,
0<=i<=n and 0<=j<=m

Cost(n,m) – Cost of Optimal Edit Sequence


Eye

DYNAMIC PROGRAMMING
SOLUTION
TRANSFORMATION- RULES

i j Action Done Cost (i,j)


i=0 j=0 Nothing Cost(0,0) = 0

i>0 j=0 Delete Cost(i,0) = Cost(i-1,0) + D(xi)

i=0 j>0 Insert Cost(0,j) = Cost(0,j-1) + I(yj)

i≠0 j≠0 3 Scenarios


STRING EDITING Eye

DYNAMIC PROGRAMMING
SOLUTION - PROCEDURE
STRING EDITING
DYNAMIC PROGRAMMING
SOLUTION - PROCEDURE
Construct a table
Each row in the table corresponds to
each character of String X
Each column in the table corresponds to
each character of String Y
Table is filled row by row [each cell
C(xi,yj)=0 if xi=yj Cost(i,j) is found]
Finally Cost(n,m) is found
Edit Sequence: change- STRING EDITING
change PROBLEM - 1
Cost=2
j=0 1 2 3 4
Convert the following String X = “HAND” NULL P O N D
into String Y = “POND” with the Minimum
Edit Operations. Consider, the Cost of i = 0 NULL 0 1 2 3 4
Insert, Delete and Change as 1 H 1 1 2 3 4
1
2 A 2 2 2 3 4

H N 3 3 3 2 3
A N D 3
4 D 4 4 4 3 2

P O N D Two Transformations :
H -> P
A -> O

You might also like