Реализации алгоритмов/Расстояние Левенштейна: различия между версиями
Содержимое удалено Содержимое добавлено
→C++: Это логически неверно использовать typename T::value_type, т.к. для строки он равен char, из-за чего могут спокойно происходить переполнения. Тест: 1000 букв a, 1000 букв b. |
→C++: Изменён код C++. Теперь он использует min(m, n) памяти вместо m * n памяти. Добавлено код на обобщённое расстояние Левенштейна |
||
Строка 530:
== [[w:C++|C++]] ==
Имплементация использует <math>\sim~ min(m, n)</math> памяти:
<!--
Зависимости: Нет. Стандартный Си++.
Автор:
▲Дата: 16 сентября 2007 г.
-->
<source lang="CPP">
template<typename T>
#include <vector>▼
#include <algorithm>▼
const T &t) {
if (s.size() > t.size()) {
return LevensteinDistance(t, s);
}▼
const T_size_t min_size = s.size(), max_size = t.size();
▲typename T::size_type levenshtein_distance(const T & src, const T & dst) {
std::vector<T_size_t> lev_dist(min_size + 1);
const typename T::size_type m = src.size();▼
▲ }
}▼
▲ }
for (
T_size_t previous_diagonal = lev_dist[0], previous_diagonal_save;
}▼
▲ for (typename T::size_type i = 0; i <= n; ++i) {
▲ matrix[0][i] = i;
}▼
previous_diagonal_save = lev_dist[i];
lev_dist[i] = previous_diagonal;
▲ for(typename T::size_type j = 1; j <= n; ++j) {
lev_dist[i] = std::min(std::min(lev_dist[i - 1], lev_dist[i]), previous_diagonal) + 1;
previous_diagonal = previous_diagonal_save;
diagonal_cell = matrix[i - 1][j - 1];▼
}
}
}▼
return
}
</source>
Строка 584 ⟶ 578 :
const std::string src = "125";
const std::string dst = "521";
const std::string::size_type distance =
...
</source>
Имплементация обобщённого расстояния Левенштейна с произвольными стоимостями вставки, удаления и замены символа:
<!--
Зависимости: Нет. Стандартный Си++.
Автор: Николай Королев, korolevns98@gmail.com, Москва, Россия.
Дата: 05 января 2019 г.
-->
<source lang="CPP">
▲#include <algorithm>
▲#include <vector>
template<typename T>
typename T::size_type GeneralizedLevensteinDistance(const T &s,
const T &t,
typename T::size_type insert_cost = 1,
typename T::size_type delete_cost = 1,
typename T::size_type replace_cost = 1) {
if (s.size() > t.size()) {
return GeneralizedLevensteinDistance(t, s, delete_cost, insert_cost, replace_cost);
▲ }
const T_size_t min_size = s.size(), max_size = t.size();
std::vector<T_size_t> lev_dist(min_size + 1);
lev_dist[0] = 0;
for (T_size_t i = 1; i <= min_size; ++i) {
lev_dist[i] = lev_dist[i - 1] + delete_cost;
▲ }
for (T_size_t j = 1; j <= max_size; ++j) {
T_size_t previous_diagonal = lev_dist[0], previous_diagonal_save;
lev_dist[0] += insert_cost;
for (T_size_t i = 1; i <= min_size; ++i) {
previous_diagonal_save = lev_dist[i];
lev_dist[i] = previous_diagonal;
} else {
lev_dist[i] = std::min(std::min(lev_dist[i - 1] + delete_cost, lev_dist[i] + insert_cost), previous_diagonal + replace_cost);
}
previous_diagonal = previous_diagonal_save;
}
▲ }
return lev_dist[min_size];
}
</source>
| |||