summaryrefslogtreecommitdiffstatshomepage
path: root/src/lib/util/corestr.cpp
diff options
context:
space:
mode:
author Vas Crabb <vas@vastheman.com>2019-03-26 11:13:37 +1100
committer Vas Crabb <vas@vastheman.com>2019-03-26 11:13:37 +1100
commit97b67170277437131adf6ed4d60139c172529e4f (patch)
tree7a5cbf608f191075f1612b1af15832c206a3fe2d /src/lib/util/corestr.cpp
parentb380514764cf857469bae61c11143a19f79a74c5 (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.cpp95
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