Levenshtein Mesafesi

Giriş
Önce Edit Distance kavramını anlamak gerekir. 

Edit Distance Nedir?

Açıklaması şöyle

Edit distance is the minimum number of operations required to transform one string into the other.

Different definitions of an edit distance use different sets of string operations.

Örneğin Hamming Distance algoritması, Levenshtein Distance algoritması gibi algoritmalar iki string'in birbirlerine ne kadar benzediğini döner.

Edit Distance küçük ise imla hatası olması ihtimali yüksektir.

Bazı Yöntemler 1

Edit Distance hesaplama için kullanılan diğer bazı yöntemler şöyle

- Levenshtein distance. This provides a similarity measure between two strings.
- Needleman-Wunch. This is the edit distance based similarity measure between two strings.
- Smith-Waterman. This is a similarity measure between two string.
- Smith-Waterman-Gotoh. This is a similarity measure between two strings.
- Smith-Waterman Gotoh Affine Window. This is a windowed affine gap providing a similarity measure between two strings.

Bazı Yöntemler 2

Açıklaması şöyle.  Hamming Distance substitution yapar.  Levenshtein Distance ilave olarak silme ve ekleme de yapar.

There are many string metrics to choose from. The following is a list of some of the most frequently used string metrics:

- Hamming Distance: This method counts the number of substitutions that are required to turn one string into another.

- Levenshtein Distance: This string metrics expands on the Hamming Distance by allowing operations such as deletion and insertion in addition to substitution

- Jaro-Winkler Distance: a string metric measuring an edit distance between two sequences

- Learnable Distance: This one takes into consideration that different edit operations have varying significance in different domains.

- Sørensen–Dice coefficient: This one measures how similar two strings are in terms of the number of common bigrams (a bigram is a pair of adjacent letters in the string). 

Hamming Mesafesi Nedir?

- İki tane eşit uzunluktaki string'in kaç tane harfinin farklı olduğunu bulmak için kullanılır

- İki tane sayının kaç tane bitinin farklı olduğunu bulmak için kullanılır

Levenshtein Mesafesi Nedir?

Levenshtein yöntemi Edit Distance hesaplamak için kullanılan yöntemlerden birisi. Açıklaması şöyle

Levenshtein distance operations (in wiki) are the removal, insertion, or substitution of a character in the string. sometimes, the term Levenshtein distance is often used interchangeably with edit distance.

Levenshtein Mesafesi recursive ve dynamic olarak çözülebilir. 

Örnek

Dynamic çözüm için şöyle yaparız. Bu çözüm aslında bir spell autocorrect için kullanılıyor ve  4 tane şeyi deniyor. Bunlar Deletion Distance, Transposition Distance, Alteration Distance, Insertion Distance.

//Time O(n*m), Space O(n*m), n is word1 length, m is word2 length
private int editDistance(String word1, String word2) {
  int n = word1.length();
  int m = word2.length();
  int dp[][] = new int[n+1][m+1];

  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      if (i == 0)
        dp[i][j] = j;      
      else if (j == 0)
        dp[i][j] = i; 
      else if (word1.charAt(i-1) == word2.charAt(j-1))
        dp[i][j] = dp[i-1][j-1];                
      else if (i>1 && j>1  && word1.charAt(i-1) == word2.charAt(j-2) 
          && word1.charAt(i-2) == word2.charAt(j-1))
        dp[i][j] = 1 + Math.min(Math.min(dp[i-2][j-2], dp[i-1][j]),
          Math.min(dp[i][j-1], dp[i-1][j-1]));
      else
        dp[i][j] = 1 + Math.min(dp[i][j-1], Math.min(dp[i-1][j], dp[i-1][j-1])); 
    }
  } 
  return dp[n][m];
}

Dictionary içinde arama kodu şöyle. Burada yukarıda tanımlı editDistance() metodu çağrılıyor

//Time O(S*n*m) ~ O(S), Space(K*N), S is number of words in dictionary 
//K is number of edit distance, N is the max number of similar words
private String suggestSimilarWord(String inputWord) {
  if (inputWord.length()==0 || inputWord==null ||
    invalid.contains(inputWord.toLowerCase()) )
    return null;
  String s = inputWord.toLowerCase();
  String res=null;

  TreeMap<Integer, TreeMap<Integer, TreeSet<String>>> map = new TreeMap<>();      
  TrieNode node = trie.find(s);           
  if(node == null) {
    for (String w: dict.keySet()) {
      int dist = editDistance(w, s);              
      TreeMap<Integer, TreeSet<String>> similarWords = map.getOrDefault(dist,
        new TreeMap<>());
      int freq = dict.get(w);
      TreeSet<String> set = similarWords.getOrDefault(freq, new TreeSet<>());
      set.add(w);         
      similarWords.put(freq, set);
      map.put(dist, similarWords);        
    }       
    res = map.firstEntry().getValue().lastEntry().getValue().first();
  } else if (node !=null) {
    res = s;
  }
  return res;
}

Örnek
Problem şöyle olsun.

One away : There are three types of edits that can be performed on strings: insert a character, remove a character and replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away.

C ile çözüm için şöyle yaparız. one_away() metodu uzun olan string'i bulur ve ilk parametre olarak helper_one_away() metoduna geçer. Üçüncü parametre ise silme işlemine izin verilip verilmediğidir. İki string aynı uzunlukta ise silme işlemine izin verilmez. String'ler farklı uzunlukta ise silme işlemine izin verilir.

helper_one_away() metodu iki string üzerinde dolaşır. Aynı konumdaki iki karakter birbirinden farklı ise bir sayacı artırır. Eğer sayaç 1'den büyükse iki karakter farklı demektir ve false döner. Eğer sayaç henüz 0 veya 1 ise uzun string'deki karakteri silmiş gibi kabul eder.

Elimizde şöyle iki string olsun. a karakterine gelince l karakterinden farklı olacaktır. İlk string ilerlemeye devam eder. İkinci string bir geri gider.

("pale", "ple")

static bool helper_one_away(const char *a, const char *b,
                           bool allow_deletion)
{
  size_t nchars = 0;
  while (*a) {
    if (*a++ != *b++) {
      if (++nchars > 1) return false;
      if (allow_deletion) --b;
    }
  }
  return true;
}

/* Return true if a can be obtained from string2 by adding,
   deleting, or removing at most one character */
bool one_away(const char *a, const char *b)
{
  switch (strlen(a) - strlen(b)) {
    case (size_t)-1: return helper_one_away(b, a, true);
    case 0:          return helper_one_away(a, b, false);
    case 1:          return helper_one_away(a, b, true);
    default:         return false;
  }
}