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, 0 insertions, 95 deletions
diff --git a/src/lib/util/corestr.cpp b/src/lib/util/corestr.cpp
index 5add3ed302f..a2fef33a87a 100644
--- a/src/lib/util/corestr.cpp
+++ b/src/lib/util/corestr.cpp
@@ -10,10 +10,6 @@
#include "corestr.h"
#include "osdcore.h"
-
-#include <algorithm>
-#include <memory>
-
#include <ctype.h>
#include <stdlib.h>
@@ -240,94 +236,3 @@ 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