summaryrefslogtreecommitdiffstatshomepage
path: root/src/lib/util/corestr.cpp
diff options
context:
space:
mode:
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