RapidFuzz
Loading...
Searching...
No Matches
LCSseq.hpp
1/* SPDX-License-Identifier: MIT */
2/* Copyright © 2022-present Max Bachmann */
3
4#pragma once
5#include <rapidfuzz/distance/LCSseq_impl.hpp>
6
7#include <algorithm>
8#include <limits>
9
10namespace rapidfuzz {
11
17template <typename InputIt1, typename InputIt2>
18size_t lcs_seq_distance(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2,
19 size_t score_cutoff = std::numeric_limits<size_t>::max())
20{
21 return detail::LCSseq::distance(first1, last1, first2, last2, score_cutoff, score_cutoff);
22}
23
24template <typename Sentence1, typename Sentence2>
25size_t lcs_seq_distance(const Sentence1& s1, const Sentence2& s2,
26 size_t score_cutoff = std::numeric_limits<size_t>::max())
27{
28 return detail::LCSseq::distance(s1, s2, score_cutoff, score_cutoff);
29}
30
31template <typename InputIt1, typename InputIt2>
32size_t lcs_seq_similarity(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2,
33 size_t score_cutoff = 0)
34{
35 return detail::LCSseq::similarity(first1, last1, first2, last2, score_cutoff, score_cutoff);
36}
37
38template <typename Sentence1, typename Sentence2>
39size_t lcs_seq_similarity(const Sentence1& s1, const Sentence2& s2, size_t score_cutoff = 0)
40{
41 return detail::LCSseq::similarity(s1, s2, score_cutoff, score_cutoff);
42}
43
44template <typename InputIt1, typename InputIt2>
45double lcs_seq_normalized_distance(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2,
46 double score_cutoff = 1.0)
47{
48 return detail::LCSseq::normalized_distance(first1, last1, first2, last2, score_cutoff, score_cutoff);
49}
50
51template <typename Sentence1, typename Sentence2>
52double lcs_seq_normalized_distance(const Sentence1& s1, const Sentence2& s2, double score_cutoff = 1.0)
53{
54 return detail::LCSseq::normalized_distance(s1, s2, score_cutoff, score_cutoff);
55}
56
57template <typename InputIt1, typename InputIt2>
58double lcs_seq_normalized_similarity(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2,
59 double score_cutoff = 0.0)
60{
61 return detail::LCSseq::normalized_similarity(first1, last1, first2, last2, score_cutoff, score_cutoff);
62}
63
64template <typename Sentence1, typename Sentence2>
65double lcs_seq_normalized_similarity(const Sentence1& s1, const Sentence2& s2, double score_cutoff = 0.0)
66{
67 return detail::LCSseq::normalized_similarity(s1, s2, score_cutoff, score_cutoff);
68}
69
70template <typename InputIt1, typename InputIt2>
71Editops lcs_seq_editops(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2)
72{
73 return detail::lcs_seq_editops(detail::make_range(first1, last1), detail::make_range(first2, last2));
74}
75
76template <typename Sentence1, typename Sentence2>
77Editops lcs_seq_editops(const Sentence1& s1, const Sentence2& s2)
78{
79 return detail::lcs_seq_editops(detail::make_range(s1), detail::make_range(s2));
80}
81
82#ifdef RAPIDFUZZ_SIMD
83namespace experimental {
84template <int MaxLen>
85struct MultiLCSseq : public detail::MultiSimilarityBase<MultiLCSseq<MaxLen>, size_t, 0,
86 std::numeric_limits<int64_t>::max()> {
87private:
88 friend detail::MultiSimilarityBase<MultiLCSseq<MaxLen>, size_t, 0, std::numeric_limits<int64_t>::max()>;
89 friend detail::MultiNormalizedMetricBase<MultiLCSseq<MaxLen>, size_t>;
90
91 RAPIDFUZZ_CONSTEXPR_CXX14 static size_t get_vec_size()
92 {
93# ifdef RAPIDFUZZ_AVX2
94 using namespace detail::simd_avx2;
95# else
96 using namespace detail::simd_sse2;
97# endif
98 RAPIDFUZZ_IF_CONSTEXPR (MaxLen <= 8)
99 return native_simd<uint8_t>::size;
100 else RAPIDFUZZ_IF_CONSTEXPR (MaxLen <= 16)
101 return native_simd<uint16_t>::size;
102 else RAPIDFUZZ_IF_CONSTEXPR (MaxLen <= 32)
103 return native_simd<uint32_t>::size;
104 else RAPIDFUZZ_IF_CONSTEXPR (MaxLen <= 64)
105 return native_simd<uint64_t>::size;
106
107 static_assert(MaxLen <= 64, "expected MaxLen <= 64");
108 }
109
110 static size_t find_block_count(size_t count)
111 {
112 size_t vec_size = get_vec_size();
113 size_t simd_vec_count = detail::ceil_div(count, vec_size);
114 return detail::ceil_div(simd_vec_count * vec_size * MaxLen, 64);
115 }
116
117public:
118 MultiLCSseq(size_t count) : input_count(count), pos(0), PM(find_block_count(count) * 64)
119 {
120 str_lens.resize(result_count());
121 }
122
132 size_t result_count() const
133 {
134 size_t vec_size = get_vec_size();
135 size_t simd_vec_count = detail::ceil_div(input_count, vec_size);
136 return simd_vec_count * vec_size;
137 }
138
139 template <typename Sentence1>
140 void insert(const Sentence1& s1_)
141 {
142 insert(detail::to_begin(s1_), detail::to_end(s1_));
143 }
144
145 template <typename InputIt1>
146 void insert(InputIt1 first1, InputIt1 last1)
147 {
148 auto len = std::distance(first1, last1);
149 int block_pos = static_cast<int>((pos * MaxLen) % 64);
150 auto block = (pos * MaxLen) / 64;
151 assert(len <= MaxLen);
152
153 if (pos >= input_count) throw std::invalid_argument("out of bounds insert");
154
155 str_lens[pos] = static_cast<size_t>(len);
156
157 for (; first1 != last1; ++first1) {
158 PM.insert(block, *first1, block_pos);
159 block_pos++;
160 }
161 pos++;
162 }
163
164private:
165 template <typename InputIt2>
166 void _similarity(size_t* scores, size_t score_count, const detail::Range<InputIt2>& s2,
167 size_t score_cutoff = 0) const
168 {
169 if (score_count < result_count())
170 throw std::invalid_argument("scores has to have >= result_count() elements");
171
172 auto scores_ = detail::make_range(scores, scores + score_count);
173 RAPIDFUZZ_IF_CONSTEXPR (MaxLen == 8)
174 detail::lcs_simd<uint8_t>(scores_, PM, s2, score_cutoff);
175 else RAPIDFUZZ_IF_CONSTEXPR (MaxLen == 16)
176 detail::lcs_simd<uint16_t>(scores_, PM, s2, score_cutoff);
177 else RAPIDFUZZ_IF_CONSTEXPR (MaxLen == 32)
178 detail::lcs_simd<uint32_t>(scores_, PM, s2, score_cutoff);
179 else RAPIDFUZZ_IF_CONSTEXPR (MaxLen == 64)
180 detail::lcs_simd<uint64_t>(scores_, PM, s2, score_cutoff);
181 }
182
183 template <typename InputIt2>
184 size_t maximum(size_t s1_idx, const detail::Range<InputIt2>& s2) const
185 {
186 return std::max(str_lens[s1_idx], s2.size());
187 }
188
189 size_t get_input_count() const noexcept
190 {
191 return input_count;
192 }
193
194 size_t input_count;
195 size_t pos;
196 detail::BlockPatternMatchVector PM;
197 std::vector<size_t> str_lens;
198};
199} /* namespace experimental */
200#endif
201
202template <typename CharT1>
203struct CachedLCSseq
204 : detail::CachedSimilarityBase<CachedLCSseq<CharT1>, size_t, 0, std::numeric_limits<int64_t>::max()> {
205 template <typename Sentence1>
206 explicit CachedLCSseq(const Sentence1& s1_) : CachedLCSseq(detail::to_begin(s1_), detail::to_end(s1_))
207 {}
208
209 template <typename InputIt1>
210 CachedLCSseq(InputIt1 first1, InputIt1 last1) : s1(first1, last1), PM(detail::make_range(first1, last1))
211 {}
212
213private:
214 friend detail::CachedSimilarityBase<CachedLCSseq<CharT1>, size_t, 0, std::numeric_limits<int64_t>::max()>;
215 friend detail::CachedNormalizedMetricBase<CachedLCSseq<CharT1>>;
216
217 template <typename InputIt2>
218 size_t maximum(const detail::Range<InputIt2>& s2) const
219 {
220 return std::max(s1.size(), s2.size());
221 }
222
223 template <typename InputIt2>
224 size_t _similarity(const detail::Range<InputIt2>& s2, size_t score_cutoff, size_t) const
225 {
226 return detail::lcs_seq_similarity(PM, detail::make_range(s1), s2, score_cutoff);
227 }
228
229 std::vector<CharT1> s1;
230 detail::BlockPatternMatchVector PM;
231};
232
233#ifdef RAPIDFUZZ_DEDUCTION_GUIDES
234template <typename Sentence1>
235explicit CachedLCSseq(const Sentence1& s1_) -> CachedLCSseq<char_type<Sentence1>>;
236
237template <typename InputIt1>
238CachedLCSseq(InputIt1 first1, InputIt1 last1) -> CachedLCSseq<iter_value_t<InputIt1>>;
239#endif
240
243} // namespace rapidfuzz
Generated by doxygen 1.9.8