Реализации алгоритмов/Расстояние Левенштейна: различия между версиями

Содержимое удалено Содержимое добавлено
Строка 541:
 
template<typename T>
typename T::size_typevalue_type LevensteinDistance(const T &sourcesrc, const T &dst)
}{
const T &target) {
using TSizeType =const typename T::size_type m = src.size;
if (source.size() > target.size()) {
const typename T::size_type n = dst.size;
return LevensteinDistance(target, source);
if (m==0){
}
return n;}
if (n==0){
return m;}
std::vector < std::vector< typename T::value_type>>matrix(m+1,n+1);
for (typename T::size_type i=0; i<=m; ++i){
matrix [i].resize(n+1);
matrix [i][0] = i;
for (typename T::size_type j=0; j<=n; ++j){
matrix[0][j] =j;}
typename T::valuetype above_cell, left_cell, diagonal_cell, cost);
for (typename T::size_type i=1; i<=m; ++i){
for (typename T::size_type j=1; j<=n; ++j){
cost = src[i-1]==dst[j-1]?0 1;
above_cell = matrix[i-1][j];
left_cell = matrix[i][j-1];
diagonal_cell = matrix[i-1][j-1];
matrix[i][j] = std::min(std::min(above_cell+1, left_cell+1),diagonal_cell+cost);
}
}
return matrix[m][n];
 
using TSizeType = typename T::size_type;
const TSizeType min_size = source.size(), max_size = target.size();
std::vector<TSizeType> lev_dist(min_size + 1);
 
for (TSizeType i = 0; i <= min_size; ++i) {
lev_dist[i] = i;
}
 
for (TSizeType j = 1; j <= max_size; ++j) {
TSizeType previous_diagonal = lev_dist[0], previous_diagonal_save;
++lev_dist[0];
 
for (TSizeType i = 1; i <= min_size; ++i) {
previous_diagonal_save = lev_dist[i];
if (source[i - 1] == target[j - 1]) {
lev_dist[i] = previous_diagonal;
} else {
lev_dist[i] = std::min(std::min(lev_dist[i - 1], lev_dist[i]), previous_diagonal) + 1;
}
previous_diagonal = previous_diagonal_save;
}
}
 
return lev_dist[min_size];
</source>
 
}
Пример использования:
<source lang="CPP">