A reasonable distance measure reflects the number of changes that must be made t

Question

A reasonable distance measure reflects the number of changes that must be made to convert one string to another. There are three natural types of changes:

Substitution – Replace a single character from pattern P with a different character in text T, such as changing “shot” to “spot.”

Insertion – Insert a single character into pattern P to help it match text T, such as changing “ago” to “agog.”

Deletion – Delete a single character from pattern P to help it match text T , such as changing “hour” to “our.”

In the transponsition operation previously it was taking two operations with the cost of 2, which is one inerstion and one deletion.

But I want to make it just to have a cost of 1, like others. Explain how to modify the simple edit distance algorithm to make the cost of transposition equal to 1 instead of 2. Please explian.

Here is someone's explaination but I don't understand, can someone explain to me more detailed "we can copy a value in a variable named temp, and then insert it on the other one anf then the other value will be inserted on the other."

}

}

}

}

}

}

Explanation / Answer

The explaination you provided is just a swap operation. let you want to transpose/replace S[i] with T[j]. we can get it done with the help of following operation.

1) declare a character variable. let say : temp

2) store S[i] in temp;

3) store T[j] in S[i]

4) store temp in T[j]

concretly

char temp;

temp=S[i];

S[i]=T[j];

T[j]=temp;

this the the explaination of the statement given above.

and if you are working with Substitution operation then a better way to substitute S[i] with T[j] is

write S[i]=T[j]

This will be done on the cost of 1.

let me know if you are still in doubt, :)

hit thumbs up if you like the answer

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.