From 3d84943f72df5d69db5e5cff1d71887fcc23c422 Mon Sep 17 00:00:00 2001 From: Vas Crabb Date: Mon, 14 Jan 2019 00:44:46 +1100 Subject: Make search not suck as badly (use algorithm derived from Jaro-Winkler similarity to match search strings, match on more useful stuff) --- src/lib/util/corestr.cpp | 95 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 95 insertions(+) (limited to 'src/lib/util/corestr.cpp') diff --git a/src/lib/util/corestr.cpp b/src/lib/util/corestr.cpp index a2fef33a87a..5add3ed302f 100644 --- a/src/lib/util/corestr.cpp +++ b/src/lib/util/corestr.cpp @@ -10,6 +10,10 @@ #include "corestr.h" #include "osdcore.h" + +#include +#include + #include #include @@ -236,3 +240,94 @@ 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 match_idx(std::make_unique(shorter.length())); + std::unique_ptr match_flg(std::make_unique(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 ms(std::make_unique(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 -- cgit v1.2.3-70-g09d2