diff options
author | 2019-03-26 11:13:37 +1100 | |
---|---|---|
committer | 2019-03-26 11:13:37 +1100 | |
commit | 97b67170277437131adf6ed4d60139c172529e4f (patch) | |
tree | 7a5cbf608f191075f1612b1af15832c206a3fe2d /src/lib/util/corestr.cpp | |
parent | b380514764cf857469bae61c11143a19f79a74c5 (diff) |
(nw) Clean up the mess on master
This effectively reverts b380514764cf857469bae61c11143a19f79a74c5 and
c24473ddff715ecec2e258a6eb38960cf8c8e98e, restoring the state at
598cd5227223c3b04ca31f0dbc1981256d9ea3ff.
Before pushing, please check that what you're about to push is sane.
Check your local commit log and ensure there isn't anything out-of-place
before pushing to mainline. When things like this happen, it wastes
everyone's time. I really don't need this in a week when real work⢠is
busting my balls and I'm behind where I want to be with preparing for
MAME release.
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 |