/home/mhx/git/github/libmoost/include/moost/string/levenshtein.hpp

Go to the documentation of this file.

/* vim:set ts=3 sw=3 sts=3 et: */
#ifndef MOOST_STRING_LEVENSHTEIN_HPP__
#define MOOST_STRING_LEVENSHTEIN_HPP__

#include <vector>
#include <string>
#include <stdexcept>
#include <climits>

namespace moost { namespace string {

template <class RandomAccessIterator>
int levenshtein(RandomAccessIterator first1,
                RandomAccessIterator last1,
                RandomAccessIterator first2,
                RandomAccessIterator last2,
                std::vector< std::vector<int> > & d)
{
  const int m = last1 - first1; // length of 1
  const int n = last2 - first2; // length of 2
  int i, j, cost; // cost, iteration

  d.resize(m + 1);
  for (std::vector< std::vector< int> >::iterator it = d.begin(); it != d.end(); ++it)
    it->resize(n + 1);

  for (i = 0; i <= m; ++i)
    d[i][0] = i;
  for (j = 0; j <= n; ++j)
    d[0][j] = j;

  for (i = 1; i <= m; ++i)
  {
    for (j = 1; j <= n; ++j)
    {
      cost = (*(first1 + i - 1) == *(first2 + j - 1) ? 0 : 1);
      d[i][j] = std::min(d[i - 1][j] + 1, // deletion
                std::min(d[i][j - 1] + 1, // insertion
                d[i - 1][j - 1] +   cost)); // substitution

      if (   i > 1
          && j > 1
          && *(first1 + i - 1) == *(first2 + j - 2)
          && *(first1 + i - 2) == *(first2 + j - 1))
        d[i][j] = std::min(d[i][j], d[i - 2][j - 2] + cost); // transposition
    }
  }

  return d[m][n];
}

template <class RandomAccessIterator>
int levenshtein(RandomAccessIterator first1,
                RandomAccessIterator last1,
                RandomAccessIterator first2,
                RandomAccessIterator last2)
{
  std::vector< std::vector<int> > d;

  return levenshtein(first1, last1, first2, last2, d);
}

int levenshtein(const std::string & first,
                const std::string & second,
                std::vector< std::vector<int> > & d)
{
  return levenshtein(first.begin(), first.end(), second.begin(), second.end(), d);
}

int levenshtein(const std::string & first,
                const std::string & second)
{
  std::vector< std::vector<int> > d;
  return levenshtein(first.begin(), first.end(), second.begin(), second.end(), d);
}

template <class RandomAccessIterator>
int fast_levenshtein(RandomAccessIterator first1,
                RandomAccessIterator last1,
                RandomAccessIterator first2,
                RandomAccessIterator last2,
                int thresh = INT_MAX)
{
   const int n = last1 - first1; // length of 1
   const int m = last2 - first2; // length of 2

   // check precondition not violated
   if (n > m)
      throw std::runtime_error("fast_levenshtein called with first string longer than second!");

   if ((m - n) > thresh)    // abort, edit dist has to be more than thresh
      return m - n;

   std::vector<int> current(n + 1);
   std::vector<int> previous(n + 1);
   for (int i = 0; i <= n; ++i)
      current[i] = i;

   for (int i = 1; i <= m; ++i)
   {
      std::copy(current.begin(), current.end(), previous.begin());
      std::fill(current.begin(), current.end(), 0);
      current[0] = i;

      for (int j = 1; j <= n; ++j)
      {
         int substitute = previous[j - 1];
         if (*(first1 + j - 1) != *(first2 + i - 1))
            ++substitute;

         // Get minimum of insert, delete and substitute
         current[j] = std::min(std::min(previous[j] + 1, current[j - 1] + 1) , substitute);
      }

      // bail out if already over thresh
      int min_current = current[0];
      for (int j = 1; j <= n; ++j)
         if (current[j] < min_current)
            min_current = current[j];
      if (min_current > thresh)
         return min_current;
   }

   return current[n];
}

int fast_levenshtein(const std::string & first,
                const std::string & second,
                int thresh = INT_MAX)
{
  if (first.length() <= second.length())
     return fast_levenshtein(first.begin(), first.end(), second.begin(), second.end(), thresh);
  else
     return fast_levenshtein(second.begin(), second.end(), first.begin(), first.end(), thresh);
}

}} // moost::string

#endif // MOOST_STRING_LEVENSHTEIN_HPP__