header
Edit distance algorithm

Tag:
Edit edit   Starstar

Program Information

Name: Edit distance algorithm
Domain: Algorithm
Functionality: It calculates the total minimum number of edit operations that transforms one given string $x$ into another one $y$.
Input: The given strings $x$ and $y$
Output: The total minimum number of edit operations

Reference

Generating Source Inputs for Metamorphic Testing Using Dynamic Symbolic Execution https://doi.org/10.1145/2896971.2896980 

MR Information

MR1------Limit case

Description:
Property: $O(X,'\ ')=O('\ ',X)=|X|$
Source input: $(X,'\ ')$
Source output: $O(X,'\ ')$
Follow-up input: $('\ ',X)$
Follow-up output: $O('\ ',X)$
Input relation: $(X,'\ ') \Rightarrow ('\ ',X)$
Output relation: $O(X,'\ ')=O('\ ',X)=|X|$
Pattern:

MR2------Concatenation

Description:
Property: $X'=X++R \wedge Y' = Y++S \Rightarrow O(X',Y')=min(O(X,Y),O(X',Y)+1,O(X,Y')+1)$  where $R$ and $S$ are random strings of length 1.
Source input: $(X,Y)$
Source output: $O(X,Y)$
Follow-up input: $(X',Y'),(X',Y),(X,Y')$
Follow-up output: $O(X',Y'),O(X',Y),O(X,Y')$
Input relation: $X'=X++R \wedge Y' = Y++S$ where $R$ and $S$ are random strings of length 1.
Output relation: $O(X',Y')=min(O(X,Y),O(X',Y)+1,O(X,Y')+1)$
Pattern:
Insert title here