Edit distance metric. More...
#include <bktree.hpp>
Inheritance diagram for bk_tree::metrics::EditDistance:
Public Member Functions | |
| EditDistance (size_t initial_size=BK_ED_MATRIX_INITIAL_SIZE) | |
| integer_type | compute_distance (std::string_view s, std::string_view t) const |
 Public Member Functions inherited from bk_tree::metrics::Distance< EditDistance > | |
| integer_type | operator() (std::string_view s, std::string_view t) const |
Detailed Description
Edit distance metric.
Related to DamerauLevenshteinDistance.
\(d(x_m, y_n),\) where \(m\) is the length of \(x\), \(n\) is the length of \(y\),
\[\begin{equation} d(x_i, y_j)= \begin{cases} i, & \text{if } j = 0 \\ j, & \text{if } i = 0 \\ \min\left\{ d(x_i, y_{j-1}) + 1, d(x_{i-1}, y_j) + 1, \begin{cases} d(x_{i-1}, y_{j-1}) + 1, & x_i \neq y_j \\ d(x_{i-1}, y_{j-1}), & \text{otherwise} \end{cases} \right\} \end{cases} \end{equation}\]
for any \(0\le i < m\) and \(0\le j < n.\)
The documentation for this class was generated from the following file:
- /home/runner/work/bk-tree/bk-tree/bktree/bktree.hpp
