Расстояние Левенштейна, где я забочусь только о словах
Я хочу проверить расстояние между двумя строками с точки зрения вставки / удаления / редактирования слов. Это похоже на расстояние Левенштейна, но мне важны только слова, а не символы. Например:
«Кот сидел на коврике»&
«Собака аккуратно села на коврик»
будет иметь слово расстояние 3.
Я работаю со скриптом Rosetta Code C ++ для расстояния Левенштейна, но я не понимаю, как это сделать.
#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;
}
Решение
Ну, так как это выходные, этот на дому 🙂
#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», как и должно быть ….
Другие решения