Editing Final Report/Thesis 2016 (section)

=== Hamming Distance and Levenshtein Distance ===
The two concepts were introduced from Information Theory. Both of them describe the amount of differences between two strings. The Levenshtein Distance is applied to calculate the difference between two strings that consist of letters, while the Hamming Distance is used to compare two binary strings with same length.
The Hamming distance measures the minimum time of calculations (substitutions, precisely) required to transform string A into string B. For example, the Hamming distance between “1010” and “0010” is 1 as it requires substituting the first bit '1' in the first string with '0'. In this case the calculations of Hamming distance are based on pure binary strings so the Hamming distance can be easily expressed as H(a, b) = a XOR b. 
The Levenshtein Distance, also known as edit distance, is an enhanced version of the Hamming Distance. It not only counts substitution, also it considers insertions and deletions.  The Levenshtein distance between two words is the smallest calculation times of substitutions, insertions, and deletions of symbols that are used to transform one string into another.
Here is an example demonstrating the calculation of the Levenshtein distance, substitution is marked as s and d stands for deletion, i for insertion.  String1: INTENSION, string2: EXECUSION. 

            ＩＮＴＥ＃ＮＳＩＯＮ
            ｜｜｜｜｜｜｜｜｜｜
            ＃ＥＸＥＣＵＳＩＯＮ
            ｜｜｜｜｜｜｜｜｜｜
            ｄｓｓ－ｉｓ－－－－
        Table1. Levenshtein distance
According to Table1, the minimum cost to turn string1 into string2 is 5: 3 substitutions, 1 deletion and 1 insertion. As the Levenshtein Distance considers three kinds of calculations, the complexity is inherently higher than the Hamming Distance.