diff options
author | 2019-03-25 22:44:58 +0100 | |
---|---|---|
committer | 2019-03-25 22:44:58 +0100 | |
commit | c24473ddff715ecec2e258a6eb38960cf8c8e98e (patch) | |
tree | 8ea44b6396a6129913c0aac13859b5de9965e972 /src/lib/util/corestr.cpp | |
parent | 009cba4fb8102102168ef32870892438327f3705 (diff) | |
parent | 598cd5227223c3b04ca31f0dbc1981256d9ea3ff (diff) |
conflict resolution (nw)
Diffstat (limited to 'src/lib/util/corestr.cpp')
-rw-r--r-- | src/lib/util/corestr.cpp | 95 |
1 files changed, 95 insertions, 0 deletions
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 <algorithm> +#include <memory> + #include <ctype.h> #include <stdlib.h> @@ -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<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 |