diff options
Diffstat (limited to 'src/lib/util/corestr.cpp')
-rw-r--r-- | src/lib/util/corestr.cpp | 95 |
1 files changed, 0 insertions, 95 deletions
diff --git a/src/lib/util/corestr.cpp b/src/lib/util/corestr.cpp index 5add3ed302f..a2fef33a87a 100644 --- a/src/lib/util/corestr.cpp +++ b/src/lib/util/corestr.cpp @@ -10,10 +10,6 @@ #include "corestr.h" #include "osdcore.h" - -#include <algorithm> -#include <memory> - #include <ctype.h> #include <stdlib.h> @@ -240,94 +236,3 @@ int strreplace(std::string &str, const std::string& search, const std::string& r } return matches; } - -namespace util { - -/** - * @fn double edit_distance(std::u32string const &lhs, std::u32string const &rhs) - * - * @brief Compares strings and returns prefix-weighted similarity score (smaller is more similar). - * - * @param lhs First input. - * @param rhs Second input. - * - * @return Similarity score ranging from 0.0 (totally dissimilar) to 1.0 (identical). - */ - -double edit_distance(std::u32string const &lhs, std::u32string const &rhs) -{ - // based on Jaro-Winkler distance - // TODO: this breaks if the lengths don't fit in a long int, but that's not a big limitation - constexpr long MAX_PREFIX(4); - constexpr double PREFIX_WEIGHT(0.1); - constexpr double PREFIX_THRESHOLD(0.7); - - std::u32string const &longer((lhs.length() >= rhs.length()) ? lhs : rhs); - std::u32string const &shorter((lhs.length() < rhs.length()) ? lhs : rhs); - - // find matches - long const range((std::max)(long(longer.length() / 2) - 1, 0L)); - std::unique_ptr<long []> match_idx(std::make_unique<long []>(shorter.length())); - std::unique_ptr<bool []> match_flg(std::make_unique<bool []>(longer.length())); - std::fill_n(match_idx.get(), shorter.length(), -1); - std::fill_n(match_flg.get(), longer.length(), false); - long match_cnt(0); - for (long i = 0; shorter.length() > i; ++i) - { - char32_t const ch(shorter[i]); - long const n((std::min)(i + range + 1L, long(longer.length()))); - for (long j = (std::max)(i - range, 0L); n > j; ++j) - { - if (!match_flg[j] && (ch == longer[j])) - { - match_idx[i] = j; - match_flg[j] = true; - ++match_cnt; - break; - } - } - } - - // early exit if strings are very dissimilar - if (!match_cnt) - return 1.0; - - // now find transpositions - std::unique_ptr<char32_t []> ms(std::make_unique<char32_t []>(2 * match_cnt)); - std::fill_n(ms.get(), 2 * match_cnt, char32_t(0)); - char32_t *const ms1(&ms[0]); - char32_t *const ms2(&ms[match_cnt]); - for (long i = 0, j = 0; shorter.length() > i; ++i) - { - if (0 <= match_idx[i]) - ms1[j++] = shorter[i]; - } - match_idx.reset(); - for (long i = 0, j = 0; longer.length() > i; ++i) - { - if (match_flg[i]) - ms2[j++] = longer[i]; - } - match_flg.reset(); - long halftrans_cnt(0); - for (long i = 0; match_cnt > i; ++i) - { - if (ms1[i] != ms2[i]) - ++halftrans_cnt; - } - ms.reset(); - - // simple prefix detection - long prefix_len(0); - for (long i = 0; ((std::min)(long(shorter.length()), MAX_PREFIX) > i) && (lhs[i] == rhs[i]); ++i) - ++prefix_len; - - // do the weighting - double const m(match_cnt); - double const t(double(halftrans_cnt) / 2); - double const jaro(((m / lhs.length()) + (m / rhs.length()) + ((m - t) / m)) / 3); - double const jaro_winkler((PREFIX_THRESHOLD > jaro) ? jaro : (jaro + (PREFIX_WEIGHT * prefix_len * (1.0 - jaro)))); - return 1.0 - jaro_winkler; -} - -} // namespace util |