Levenshtein расстояние, где мне только волнуют слова

Question

Я хочу проверить расстояние между двумя строками с точки зрения вставки/удаления/редактирования слов. Это похоже на расстояние levenshtein, но я забочусь только о словах, а не о персонажах. Например:

«Кот сидел на коврике» & «Собака осторожно сидел на коврике»

будет иметь слово расстояние 3.

Я работаю с Rosetta кода C++ скрипт для levenshtein distance, но я не вижу, как это сделать.

#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

Ну, так как в выходные дни, это один на дом :)

#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; 
} 

Это выводит «3», как должно ....