RapidFuzz
Loading...
Searching...
No Matches
JaroWinkler.hpp
1/* SPDX-License-Identifier: MIT */
2/* Copyright © 2022-present Max Bachmann */
3
4#pragma once
5
6#include <rapidfuzz/details/Range.hpp>
7#include <rapidfuzz/distance/JaroWinkler_impl.hpp>
8
9namespace rapidfuzz {
10
16template <typename InputIt1, typename InputIt2,
17 typename = rapidfuzz::rf_enable_if_t<!std::is_same<InputIt2, double>::value>>
18double jaro_winkler_distance(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2,
19 double prefix_weight = 0.1, double score_cutoff = 1.0)
20{
21 return detail::JaroWinkler::distance(first1, last1, first2, last2, prefix_weight, score_cutoff,
22 score_cutoff);
23}
24
25template <typename Sentence1, typename Sentence2>
26double jaro_winkler_distance(const Sentence1& s1, const Sentence2& s2, double prefix_weight = 0.1,
27 double score_cutoff = 1.0)
28{
29 return detail::JaroWinkler::distance(s1, s2, prefix_weight, score_cutoff, score_cutoff);
30}
31
32template <typename InputIt1, typename InputIt2,
33 typename = rapidfuzz::rf_enable_if_t<!std::is_same<InputIt2, double>::value>>
34double jaro_winkler_similarity(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2,
35 double prefix_weight = 0.1, double score_cutoff = 0.0)
36{
37 return detail::JaroWinkler::similarity(first1, last1, first2, last2, prefix_weight, score_cutoff,
38 score_cutoff);
39}
40
41template <typename Sentence1, typename Sentence2>
42double jaro_winkler_similarity(const Sentence1& s1, const Sentence2& s2, double prefix_weight = 0.1,
43 double score_cutoff = 0.0)
44{
45 return detail::JaroWinkler::similarity(s1, s2, prefix_weight, score_cutoff, score_cutoff);
46}
47
48template <typename InputIt1, typename InputIt2,
49 typename = rapidfuzz::rf_enable_if_t<!std::is_same<InputIt2, double>::value>>
50double jaro_winkler_normalized_distance(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2,
51 double prefix_weight = 0.1, double score_cutoff = 1.0)
52{
53 return detail::JaroWinkler::normalized_distance(first1, last1, first2, last2, prefix_weight, score_cutoff,
54 score_cutoff);
55}
56
57template <typename Sentence1, typename Sentence2>
58double jaro_winkler_normalized_distance(const Sentence1& s1, const Sentence2& s2, double prefix_weight = 0.1,
59 double score_cutoff = 1.0)
60{
61 return detail::JaroWinkler::normalized_distance(s1, s2, prefix_weight, score_cutoff, score_cutoff);
62}
63
64template <typename InputIt1, typename InputIt2,
65 typename = rapidfuzz::rf_enable_if_t<!std::is_same<InputIt2, double>::value>>
66double jaro_winkler_normalized_similarity(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2,
67 double prefix_weight = 0.1, double score_cutoff = 0.0)
68{
69 return detail::JaroWinkler::normalized_similarity(first1, last1, first2, last2, prefix_weight,
70 score_cutoff, score_cutoff);
71}
72
73template <typename Sentence1, typename Sentence2>
74double jaro_winkler_normalized_similarity(const Sentence1& s1, const Sentence2& s2,
75 double prefix_weight = 0.1, double score_cutoff = 0.0)
76{
77 return detail::JaroWinkler::normalized_similarity(s1, s2, prefix_weight, score_cutoff, score_cutoff);
78}
79
80#ifdef RAPIDFUZZ_SIMD
81namespace experimental {
82template <int MaxLen>
83struct MultiJaroWinkler : public detail::MultiSimilarityBase<MultiJaroWinkler<MaxLen>, double, 0, 1> {
84
85private:
86 friend detail::MultiSimilarityBase<MultiJaroWinkler<MaxLen>, double, 0, 1>;
87 friend detail::MultiNormalizedMetricBase<MultiJaroWinkler<MaxLen>, double>;
88
89public:
90 MultiJaroWinkler(size_t count, double prefix_weight_ = 0.1) : scorer(count), prefix_weight(prefix_weight_)
91 {}
92
102 size_t result_count() const
103 {
104 return scorer.result_count();
105 }
106
107 template <typename Sentence1>
108 void insert(const Sentence1& s1_)
109 {
110 insert(detail::to_begin(s1_), detail::to_end(s1_));
111 }
112
113 template <typename InputIt1>
114 void insert(InputIt1 first1, InputIt1 last1)
115 {
116 scorer.insert(first1, last1);
117 size_t len = static_cast<size_t>(std::distance(first1, last1));
118 std::array<uint64_t, 4> prefix;
119 for (size_t i = 0; i < std::min(len, size_t(4)); ++i)
120 prefix[i] = static_cast<uint64_t>(first1[static_cast<ptrdiff_t>(i)]);
121
122 str_lens.push_back(len);
123 prefixes.push_back(prefix);
124 }
125
126private:
127 template <typename InputIt2>
128 void _similarity(double* scores, size_t score_count, const detail::Range<InputIt2>& s2,
129 double score_cutoff = 0.0) const
130 {
131 if (score_count < result_count())
132 throw std::invalid_argument("scores has to have >= result_count() elements");
133
134 scorer.similarity(scores, score_count, s2, std::min(0.7, score_cutoff));
135
136 for (size_t i = 0; i < get_input_count(); ++i) {
137 if (scores[i] > 0.7) {
138 size_t min_len = std::min(s2.size(), str_lens[i]);
139 size_t max_prefix = std::min(min_len, size_t(4));
140 size_t prefix = 0;
141 for (; prefix < max_prefix; ++prefix)
142 if (static_cast<uint64_t>(s2[prefix]) != prefixes[i][prefix]) break;
143
144 scores[i] += static_cast<double>(prefix) * prefix_weight * (1.0 - scores[i]);
145 scores[i] = std::min(scores[i], 1.0);
146 }
147
148 if (scores[i] < score_cutoff) scores[i] = 0.0;
149 }
150 }
151
152 template <typename InputIt2>
153 double maximum(size_t, const detail::Range<InputIt2>&) const
154 {
155 return 1.0;
156 }
157
158 size_t get_input_count() const noexcept
159 {
160 return str_lens.size();
161 }
162
163 std::vector<size_t> str_lens;
164 // todo this could lead to incorrect results when comparing uint64_t with int64_t
165 std::vector<std::array<uint64_t, 4>> prefixes;
166 MultiJaro<MaxLen> scorer;
167 double prefix_weight;
168};
169
170} /* namespace experimental */
171#endif /* RAPIDFUZZ_SIMD */
172
173template <typename CharT1>
174struct CachedJaroWinkler : public detail::CachedSimilarityBase<CachedJaroWinkler<CharT1>, double, 0, 1> {
175 template <typename Sentence1>
176 explicit CachedJaroWinkler(const Sentence1& s1_, double _prefix_weight = 0.1)
177 : CachedJaroWinkler(detail::to_begin(s1_), detail::to_end(s1_), _prefix_weight)
178 {}
179
180 template <typename InputIt1>
181 CachedJaroWinkler(InputIt1 first1, InputIt1 last1, double _prefix_weight = 0.1)
182 : prefix_weight(_prefix_weight), s1(first1, last1), PM(detail::make_range(first1, last1))
183 {}
184
185private:
186 friend detail::CachedSimilarityBase<CachedJaroWinkler<CharT1>, double, 0, 1>;
187 friend detail::CachedNormalizedMetricBase<CachedJaroWinkler<CharT1>>;
188
189 template <typename InputIt2>
190 double maximum(const detail::Range<InputIt2>&) const
191 {
192 return 1.0;
193 }
194
195 template <typename InputIt2>
196 double _similarity(const detail::Range<InputIt2>& s2, double score_cutoff, double) const
197 {
198 return detail::jaro_winkler_similarity(PM, detail::make_range(s1), s2, prefix_weight, score_cutoff);
199 }
200
201 double prefix_weight;
202 std::vector<CharT1> s1;
203 detail::BlockPatternMatchVector PM;
204};
205
206#ifdef RAPIDFUZZ_DEDUCTION_GUIDES
207template <typename Sentence1>
208explicit CachedJaroWinkler(const Sentence1& s1_,
209 double _prefix_weight = 0.1) -> CachedJaroWinkler<char_type<Sentence1>>;
210
211template <typename InputIt1>
212CachedJaroWinkler(InputIt1 first1, InputIt1 last1,
213 double _prefix_weight = 0.1) -> CachedJaroWinkler<iter_value_t<InputIt1>>;
214#endif
215
218} // namespace rapidfuzz
Generated by doxygen 1.9.8