145 lines
5 KiB
C++
145 lines
5 KiB
C++
#include <algorithm>
|
|
#include <catch2/catch_test_macros.hpp>
|
|
#include <cmath>
|
|
#include <cstddef>
|
|
#include <random>
|
|
#include <string>
|
|
#include <vector>
|
|
|
|
#include "fold/detect/detail/edit_distance.hpp"
|
|
|
|
namespace {
|
|
|
|
std::size_t scalarDistance(const std::string& a, const std::string& b) {
|
|
if (a.empty())
|
|
return b.size();
|
|
if (b.empty())
|
|
return a.size();
|
|
|
|
std::vector<std::size_t> prev(b.size() + 1), cur(b.size() + 1);
|
|
for (std::size_t j = 0; j <= b.size(); ++j)
|
|
prev[j] = j;
|
|
for (std::size_t i = 1; i <= a.size(); ++i) {
|
|
cur[0] = i;
|
|
for (std::size_t j = 1; j <= b.size(); ++j) {
|
|
const std::size_t cost = (a[i - 1] == b[j - 1]) ? 0 : 1;
|
|
cur[j] = std::min({prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + cost});
|
|
}
|
|
std::swap(prev, cur);
|
|
}
|
|
return prev[b.size()];
|
|
}
|
|
|
|
double scalarSimilarity(const std::string& a, const std::string& b) {
|
|
const std::size_t len = std::max(a.size(), b.size());
|
|
if (len == 0)
|
|
return 1.0;
|
|
return 1.0 - static_cast<double>(scalarDistance(a, b)) / static_cast<double>(len);
|
|
}
|
|
|
|
std::string randomString(std::mt19937& rng, std::size_t len) {
|
|
static constexpr char alphabet[] = "abcd{}$#0123";
|
|
std::uniform_int_distribution<std::size_t> pick(0, sizeof(alphabet) - 2);
|
|
std::string out;
|
|
out.reserve(len);
|
|
for (std::size_t i = 0; i < len; ++i)
|
|
out.push_back(alphabet[pick(rng)]);
|
|
return out;
|
|
}
|
|
|
|
bool nearlyEqual(double a, double b) { return std::abs(a - b) < 1e-12; }
|
|
|
|
} // namespace
|
|
|
|
TEST_CASE("rapidfuzz edit distance adapter matches scalar Levenshtein") {
|
|
using fold::detect::detail::editDistance;
|
|
|
|
const std::vector<std::pair<std::string, std::string>> fixed = {
|
|
{"", ""},
|
|
{"", "abc"},
|
|
{"abc", ""},
|
|
{"abc", "abc"},
|
|
{"kitten", "sitting"},
|
|
{std::string(63, 'a'), std::string(62, 'a') + 'b'},
|
|
{std::string(64, 'a'), std::string(63, 'a') + 'b'},
|
|
{std::string(65, 'a'), std::string(64, 'a') + 'b'},
|
|
{std::string(900, 'a'), std::string(899, 'a') + 'b'},
|
|
};
|
|
for (const auto& [a, b] : fixed)
|
|
REQUIRE(editDistance(a, b) == scalarDistance(a, b));
|
|
|
|
std::mt19937 rng(0xF01D);
|
|
for (std::size_t len_a : {0U, 1U, 7U, 31U, 64U, 65U, 127U, 160U}) {
|
|
for (std::size_t len_b : {0U, 2U, 9U, 33U, 63U, 66U, 128U}) {
|
|
const auto a = randomString(rng, len_a);
|
|
const auto b = randomString(rng, len_b);
|
|
REQUIRE(editDistance(a, b) == scalarDistance(a, b));
|
|
}
|
|
}
|
|
}
|
|
|
|
TEST_CASE("cutoff distance returns exact distance inside the band and cutoff+1 outside") {
|
|
using fold::detect::detail::editDistanceCutoff;
|
|
|
|
const std::string a = "aaaaaaaaaabbbbbbbbbb";
|
|
const std::string b = "aaaaaaaaaacccccccccc";
|
|
const auto exact = scalarDistance(a, b);
|
|
REQUIRE(exact == 10);
|
|
|
|
for (std::size_t cutoff = 0; cutoff <= 12; ++cutoff) {
|
|
const auto got = editDistanceCutoff(a, b, cutoff);
|
|
if (exact <= cutoff)
|
|
REQUIRE(got == exact);
|
|
else
|
|
REQUIRE(got == cutoff + 1);
|
|
}
|
|
}
|
|
|
|
TEST_CASE("thresholded normalized similarity preserves exact scores for passing pairs") {
|
|
using fold::detect::detail::normalizedSimilarity;
|
|
using fold::detect::detail::normalizedSimilarityAtLeast;
|
|
|
|
const std::vector<std::pair<std::string, std::string>> pairs = {
|
|
{"", ""},
|
|
{"aaaaaaaaaa", "aaaaaaaabb"},
|
|
{"aaaaaaaaaa", "bbbbbbbbbb"},
|
|
{std::string(65, 'a'), std::string(64, 'a') + 'b'},
|
|
{std::string(900, 'a'), std::string(899, 'a') + 'b'},
|
|
};
|
|
const std::vector<double> thresholds = {0.0, 0.5, 0.7, 0.8, 0.95, 1.0};
|
|
|
|
for (const auto& [a, b] : pairs) {
|
|
const double exact = scalarSimilarity(a, b);
|
|
REQUIRE(nearlyEqual(normalizedSimilarity(a, b), exact));
|
|
for (double threshold : thresholds) {
|
|
const double got = normalizedSimilarityAtLeast(a, b, threshold);
|
|
if (exact + 1e-12 >= threshold)
|
|
REQUIRE(nearlyEqual(got, exact));
|
|
else
|
|
REQUIRE(got == 0.0);
|
|
}
|
|
}
|
|
}
|
|
|
|
TEST_CASE("q-gram filter is conservative relative to exact similarity") {
|
|
using fold::detect::detail::canMeetSimilarityByQGram;
|
|
|
|
std::mt19937 rng(0xC10A);
|
|
const std::vector<double> thresholds = {0.5, 0.7, 0.85, 0.95, 1.0};
|
|
for (std::size_t len_a : {3U, 7U, 31U, 64U, 127U}) {
|
|
for (std::size_t len_b : {3U, 8U, 29U, 66U, 128U}) {
|
|
for (int repeat = 0; repeat < 20; ++repeat) {
|
|
const auto a = randomString(rng, len_a);
|
|
const auto b = randomString(rng, len_b);
|
|
const double exact = scalarSimilarity(a, b);
|
|
for (double threshold : thresholds) {
|
|
if (exact + 1e-12 >= threshold) {
|
|
REQUIRE(canMeetSimilarityByQGram(a, b, threshold));
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
REQUIRE(!canMeetSimilarityByQGram(std::string(120, 'a'), std::string(120, 'b'), 0.90));
|
|
}
|