Longest Common Subsequence distance metric. More...
#include <bktree.hpp>
Inheritance diagram for bk_tree::metrics::LCSubseqDistance:
Public Member Functions | |
| LCSubseqDistance (size_t initial_size=BK_LCS_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< LCSubseqDistance > | |
| integer_type | operator() (std::string_view s, std::string_view t) const |
Detailed Description
Longest Common Subsequence distance metric.
\(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} 0, & \text{if } i = 0 \text{ or } j = 0 \\ d(x_{i-1}, y_{j-1}) + 1, & \text{if } x_i = y_j \\ \max\{d(x_{i-1}, y_j), d(x_i, y_{j-1})\}, & \text{if } x_i \neq y_j \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
