Levenshtein distance where I only care about words

Question

I want to check the distance between two strings in terms of inserting/deleting/editing words. This is similar to the levenshtein distance, but I only care about words, rather than characters. For example:

"The cat sat on the mat" & "Dog sat carefully on the mat"

would have a word distance of 3.

I am working from the Rosetta Code C++ script for levenshtein distance, but I can't see how to do it.

#include <string>
#include <iostream>
using namespace std;

// Compute Levenshtein Distance
// Martin Ettl, 2012-10-05

size_t uiLevenshteinDistance(const std::string &s1, const std::string &s2)
{
  const size_t m(s1.size());
  const size_t n(s2.size());

  if( m==0 ) return n;
  if( n==0 ) return m;

  size_t *costs = new size_t[n + 1];

  for( size_t k=0; k<=n; k++ ) costs[k] = k;

  size_t i = 0;
  for ( std::string::const_iterator it1 = s1.begin(); it1 != s1.end(); ++it1, ++i )
  {
    costs[0] = i+1;
    size_t corner = i;

    size_t j = 0;
    for ( std::string::const_iterator it2 = s2.begin(); it2 != s2.end(); ++it2, ++j )
    {
      size_t upper = costs[j+1];
      if( *it1 == *it2 )
      {
          costs[j+1] = corner;
      }
      else
      {
        size_t t(upper<corner?upper:corner);
        costs[j+1] = (costs[j]<t?costs[j]:t)+1;
      }

      corner = upper;
    }
  }

  size_t result = costs[n];
  delete [] costs;

  return result;
}

int main()
{
    string s0 = "rosettacode";
        string s1 = "raisethysword";
    cout << "distance between " << s0 << " and " << s1 << " : " 
         << uiLevenshteinDistance(s0,s1) << std::endl;

        return 0;
}

Answer 1

Well, since it is the weekend, this one is on the house :)

#include <iostream>
#include <sstream>
#include <string>
#include <vector>

typedef std::vector<std::string> Sentence;

Sentence &split(const std::string &s, char delim, Sentence &elems) {
  std::stringstream ss(s);
  std::string item;
  while (std::getline(ss, item, delim)) {
    elems.push_back(item);
  }
  return elems;
}

Sentence split(const std::string &s, char delim) {
  Sentence elems;
  split(s, delim, elems);
  return elems;
}

unsigned int edit_distance(const Sentence& s1, const Sentence& s2)
{
  const std::size_t len1 = s1.size(), len2 = s2.size();
  std::vector<std::vector<unsigned int>> d(len1 + 1, std::vector<unsigned int>(len2 + 1));

  d[0][0] = 0;
  for(unsigned int i = 1; i <= len1; ++i) d[i][0] = i;
  for(unsigned int i = 1; i <= len2; ++i) d[0][i] = i;

  for(unsigned int i = 1; i <= len1; ++i)
    for(unsigned int j = 1; j <= len2; ++j)
    {
      d[i][j] = std::min(d[i - 1][j] + 1, d[i][j - 1] + 1);
      d[i][j] = std::min(d[i][j], d[i - 1][j - 1] + (s1[i - 1] == s2[j - 1] ? 0 : 1));
    }
  return d[len1][len2];
}

int main(int argc, char *argv[])
{
  Sentence s1 = split("The cat sat on the mat", ' ');
  Sentence s2 = split("Dog sat carefully on the mat", ' ');

  std::cout << "Distance between sentences: " << edit_distance(s1, s2) << std::endl;

  return 0;
}

This outputs "3" as it should....