Branch data Line data Source code
1 : : /** @file flint_spelling.cc
2 : : * @brief Spelling correction data for a flint database.
3 : : */
4 : : /* Copyright (C) 2004,2005,2006,2007,2008,2009,2010 Olly Betts
5 : : *
6 : : * This program is free software; you can redistribute it and/or modify
7 : : * it under the terms of the GNU General Public License as published by
8 : : * the Free Software Foundation; either version 2 of the License, or
9 : : * (at your option) any later version.
10 : : *
11 : : * This program is distributed in the hope that it will be useful,
12 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : : * GNU General Public License for more details.
15 : : *
16 : : * You should have received a copy of the GNU General Public License
17 : : * along with this program; if not, write to the Free Software
18 : : * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 : : */
20 : :
21 : : #include <config.h>
22 : :
23 : : #include <xapian/error.h>
24 : : #include <xapian/types.h>
25 : :
26 : : #include "expandweight.h"
27 : : #include "flint_spelling.h"
28 : : #include "flint_utils.h"
29 : : #include "omassert.h"
30 : : #include "ortermlist.h"
31 : :
32 : : #include "../prefix_compressed_strings.h"
33 : :
34 : : #include <algorithm>
35 : : #include <map>
36 : : #include <queue>
37 : : #include <vector>
38 : : #include <set>
39 : : #include <string>
40 : :
41 : : using namespace std;
42 : :
43 : : void
44 : 476 : FlintSpellingTable::merge_changes()
45 : : {
46 : 476 : map<F_fragment, set<string> >::const_iterator i;
47 [ + + ]: 657 : for (i = termlist_deltas.begin(); i != termlist_deltas.end(); ++i) {
48 : 181 : string key = i->first;
49 : 181 : const set<string> & changes = i->second;
50 : :
51 : 181 : set<string>::const_iterator d = changes.begin();
52 [ - + ]: 181 : if (d == changes.end()) continue;
53 : :
54 : 181 : string updated;
55 : 181 : string current;
56 : 181 : PrefixCompressedStringWriter out(updated);
57 [ + + ]: 181 : if (get_exact_entry(key, current)) {
58 : 42 : PrefixCompressedStringItor in(current);
59 : 42 : updated.reserve(current.size()); // FIXME plus some?
60 [ + + ][ + + ]: 84 : while (!in.at_end() && d != changes.end()) {
[ + + ]
61 : 42 : const string & word = *in;
62 : : Assert(d != changes.end());
63 : 42 : int cmp = word.compare(*d);
64 [ - + ]: 42 : if (cmp < 0) {
65 : 0 : out.append(word);
66 : 0 : ++in;
67 [ + + ]: 42 : } else if (cmp > 0) {
68 : 2 : out.append(*d);
69 : 2 : ++d;
70 : : } else {
71 : : // If an existing entry is in the changes list, that means
72 : : // we should remove it.
73 : 40 : ++in;
74 : 40 : ++d;
75 : : }
76 : : }
77 [ + + ]: 42 : if (!in.at_end()) {
78 : : // FIXME : easy to optimise this to a fix-up and substring copy.
79 [ + + ]: 13 : while (!in.at_end()) {
80 : 7 : out.append(*in++);
81 : : }
82 : 42 : }
83 : : }
84 [ + + ]: 338 : while (d != changes.end()) {
85 : 157 : out.append(*d++);
86 : : }
87 [ + + ]: 181 : if (!updated.empty()) {
88 : 145 : add(key, updated);
89 : : } else {
90 : 36 : del(key);
91 : : }
92 : : }
93 : 476 : termlist_deltas.clear();
94 : :
95 : 476 : map<string, Xapian::termcount>::const_iterator j;
96 [ + + ]: 523 : for (j = wordfreq_changes.begin(); j != wordfreq_changes.end(); ++j) {
97 : 47 : string key = "W" + j->first;
98 [ + + ]: 47 : if (j->second) {
99 : 39 : add(key, F_pack_uint_last(j->second));
100 : : } else {
101 : 8 : del(key);
102 : : }
103 : : }
104 : 476 : wordfreq_changes.clear();
105 : 476 : }
106 : :
107 : : void
108 : 199 : FlintSpellingTable::toggle_fragment(F_fragment frag, const string & word)
109 : : {
110 : 199 : map<F_fragment, set<string> >::iterator i = termlist_deltas.find(frag);
111 [ + + ]: 199 : if (i == termlist_deltas.end()) {
112 : 181 : i = termlist_deltas.insert(make_pair(frag, set<string>())).first;
113 : : }
114 : : // The commonest case is that we're adding lots of words, so try insert
115 : : // first and if that reports that the word already exists, remove it.
116 : 199 : pair<set<string>::iterator, bool> res = i->second.insert(word);
117 [ - + ]: 199 : if (!res.second) {
118 : : // word is already in the set, so remove it.
119 : 0 : i->second.erase(res.first);
120 : : }
121 : 199 : }
122 : :
123 : : void
124 : 38 : FlintSpellingTable::add_word(const string & word, Xapian::termcount freqinc)
125 : : {
126 [ - + ]: 38 : if (word.size() <= 1) return;
127 : :
128 : 38 : map<string, Xapian::termcount>::iterator i = wordfreq_changes.find(word);
129 [ - + ]: 38 : if (i != wordfreq_changes.end()) {
130 : : // Word "word" already exists and has been modified.
131 [ # # ]: 0 : if (i->second) {
132 : 0 : i->second += freqinc;
133 : 0 : return;
134 : : }
135 : : // If "word" is currently modified such that it no longer exists, so
136 : : // we need to execute the code below to re-add trigrams for it.
137 : 0 : i->second = freqinc;
138 : : } else {
139 : 38 : string key = "W" + word;
140 : 38 : string data;
141 [ + + ]: 38 : if (get_exact_entry(key, data)) {
142 : : // Word "word" already exists, so increment its count.
143 : : Xapian::termcount freq;
144 : 4 : const char * p = data.data();
145 [ + - - + ]: 4 : if (!F_unpack_uint_last(&p, p + data.size(), &freq) || freq == 0) {
[ - + ]
146 : 0 : throw Xapian::DatabaseCorruptError("Bad spelling word freq");
147 : : }
148 : 4 : wordfreq_changes[word] = freq + freqinc;
149 : : return;
150 : : }
151 [ + + ][ + + ]: 38 : wordfreq_changes[word] = freqinc;
152 : : }
153 : :
154 : : // New word - need to create trigrams for it.
155 : :
156 : 34 : F_fragment buf;
157 : : // Head:
158 : 34 : buf[0] = 'H';
159 : 34 : buf[1] = word[0];
160 : 34 : buf[2] = word[1];
161 : 34 : buf[3] = '\0';
162 : 34 : toggle_fragment(buf, word);
163 : :
164 : : // Tail:
165 : 34 : buf[0] = 'T';
166 : 34 : buf[1] = word[word.size() - 2];
167 : 34 : buf[2] = word[word.size() - 1];
168 : 34 : buf[3] = '\0';
169 : 34 : toggle_fragment(buf, word);
170 : :
171 [ + + ]: 34 : if (word.size() <= 4) {
172 : : // We also generate 'bookends' for two, three, and four character
173 : : // terms so we can handle transposition of the middle two characters
174 : : // of a four character word, substitution or deletion of the middle
175 : : // character of a three character word, or insertion in the middle of a
176 : : // two character word.
177 : : // 'Bookends':
178 : 19 : buf[0] = 'B';
179 : 19 : buf[1] = word[0];
180 : 19 : buf[3] = '\0';
181 : 19 : toggle_fragment(buf, word);
182 : : }
183 [ + + ]: 34 : if (word.size() > 2) {
184 : : // Middles:
185 : 30 : buf[0] = 'M';
186 [ + + ]: 110 : for (size_t start = 0; start <= word.size() - 3; ++start) {
187 : 72 : memcpy(buf.data + 1, word.data() + start, 3);
188 : 72 : toggle_fragment(buf, word);
189 : : }
190 : : }
191 : : }
192 : :
193 : : void
194 : 32 : FlintSpellingTable::remove_word(const string & word, Xapian::termcount freqdec)
195 : : {
196 : 32 : map<string, Xapian::termcount>::iterator i = wordfreq_changes.find(word);
197 [ + + ]: 32 : if (i != wordfreq_changes.end()) {
198 [ + + ]: 6 : if (i->second == 0) {
199 : : // Word has already been deleted.
200 : 3 : return;
201 : : }
202 : : // Word "word" exists and has been modified.
203 [ + - ]: 3 : if (freqdec < i->second) {
204 : 3 : i->second -= freqdec;
205 : 3 : return;
206 : : }
207 : :
208 : : // Mark word as deleted.
209 : 0 : i->second = 0;
210 : : } else {
211 : 26 : string key = "W" + word;
212 : 26 : string data;
213 [ + + ]: 26 : if (!get_exact_entry(key, data)) {
214 : : // This word doesn't exist.
215 : : return;
216 : : }
217 : :
218 : : Xapian::termcount freq;
219 : 9 : const char *p = data.data();
220 [ - + ]: 9 : if (!F_unpack_uint_last(&p, p + data.size(), &freq)) {
221 : 0 : throw Xapian::DatabaseCorruptError("Bad spelling word freq");
222 : : }
223 [ + + ]: 9 : if (freqdec < freq) {
224 : 1 : wordfreq_changes[word] = freq - freqdec;
225 : : return;
226 : : }
227 : : // Mark word as deleted.
228 [ + + ][ + + ]: 26 : wordfreq_changes[word] = 0;
229 : : }
230 : :
231 : : // Remove fragment entries for word.
232 : :
233 : 8 : F_fragment buf;
234 : : // Head:
235 : 8 : buf[0] = 'H';
236 : 8 : buf[1] = word[0];
237 : 8 : buf[2] = word[1];
238 : 8 : buf[3] = '\0';
239 : 8 : toggle_fragment(buf, word);
240 : :
241 : : // Tail:
242 : 8 : buf[0] = 'T';
243 : 8 : buf[1] = word[word.size() - 2];
244 : 8 : buf[2] = word[word.size() - 1];
245 : 8 : buf[3] = '\0';
246 : 8 : toggle_fragment(buf, word);
247 : :
248 [ + + ]: 8 : if (word.size() <= 4) {
249 : : // 'Bookends':
250 : 4 : buf[0] = 'B';
251 : 4 : buf[1] = word[0];
252 : 4 : buf[3] = '\0';
253 : 4 : toggle_fragment(buf, word);
254 : : }
255 [ + - ]: 8 : if (word.size() > 2) {
256 : : // Middles:
257 : 8 : buf[0] = 'M';
258 [ + + ]: 52 : for (size_t start = 0; start <= word.size() - 3; ++start) {
259 : 20 : memcpy(buf.data + 1, word.data() + start, 3);
260 : 20 : toggle_fragment(buf, word);
261 : : }
262 : : }
263 : : }
264 : :
265 : : struct TermListGreaterApproxSize {
266 : 0 : bool operator()(const TermList *a, const TermList *b) {
267 : 0 : return a->get_approx_size() > b->get_approx_size();
268 : : }
269 : : };
270 : :
271 : : TermList *
272 : 72 : FlintSpellingTable::open_termlist(const string & word)
273 : : {
274 : : // This should have been handled by Database::get_spelling_suggestion().
275 : : AssertRel(word.size(),>,1);
276 : :
277 : : // Merge any pending changes to disk, but don't call commit() so they
278 : : // won't be switched live.
279 [ + + ]: 72 : if (!wordfreq_changes.empty()) merge_changes();
280 : :
281 : : // Build a priority queue of TermList objects which returns those of
282 : : // greatest approximate size first.
283 : 72 : priority_queue<TermList*, vector<TermList*>, TermListGreaterApproxSize> pq;
284 : : try {
285 : 72 : string data;
286 : 72 : F_fragment buf;
287 : :
288 : : // Head:
289 : 72 : buf[0] = 'H';
290 : 72 : buf[1] = word[0];
291 : 72 : buf[2] = word[1];
292 [ + + ]: 72 : if (get_exact_entry(string(buf), data))
293 : 35 : pq.push(new FlintSpellingTermList(data));
294 : :
295 : : // Tail:
296 : 72 : buf[0] = 'T';
297 : 72 : buf[1] = word[word.size() - 2];
298 : 72 : buf[2] = word[word.size() - 1];
299 [ + + ]: 72 : if (get_exact_entry(string(buf), data))
300 : 35 : pq.push(new FlintSpellingTermList(data));
301 : :
302 [ + + ]: 72 : if (word.size() <= 4) {
303 : : // We also generate 'bookends' for two, three, and four character
304 : : // terms so we can handle transposition of the middle two
305 : : // characters of a four character word, substitution or deletion of
306 : : // the middle character of a three character word, or insertion in
307 : : // the middle of a two character word.
308 : 45 : buf[0] = 'B';
309 : 45 : buf[1] = word[0];
310 : 45 : buf[3] = '\0';
311 [ + + ]: 45 : if (get_exact_entry(string(buf), data))
312 : 10 : pq.push(new FlintSpellingTermList(data));
313 : : }
314 [ + + ]: 72 : if (word.size() > 2) {
315 : : // Middles:
316 : 66 : buf[0] = 'M';
317 [ + + ]: 245 : for (size_t start = 0; start <= word.size() - 3; ++start) {
318 : 179 : memcpy(buf.data + 1, word.data() + start, 3);
319 [ + + ]: 179 : if (get_exact_entry(string(buf), data))
320 : 79 : pq.push(new FlintSpellingTermList(data));
321 : : }
322 : :
323 [ + + ]: 66 : if (word.size() == 3) {
324 : : // For three letter words, we generate the two "single
325 : : // transposition" forms too, so that we can produce good
326 : : // spelling suggestions.
327 : : // ABC -> BAC
328 : 11 : buf[1] = word[1];
329 : 11 : buf[2] = word[0];
330 [ + + ]: 11 : if (get_exact_entry(string(buf), data))
331 : 1 : pq.push(new FlintSpellingTermList(data));
332 : : // ABC -> ACB
333 : 11 : buf[1] = word[0];
334 : 11 : buf[2] = word[2];
335 : 11 : buf[3] = word[1];
336 [ + + ]: 11 : if (get_exact_entry(string(buf), data))
337 : 1 : pq.push(new FlintSpellingTermList(data));
338 : : }
339 : : } else {
340 : : Assert(word.size() == 2);
341 : : // For two letter words, we generate H and T terms for the
342 : : // transposed form so that we can produce good spelling
343 : : // suggestions.
344 : : // AB -> BA
345 : 6 : buf[0] = 'H';
346 : 6 : buf[1] = word[1];
347 : 6 : buf[2] = word[0];
348 [ + + ]: 6 : if (get_exact_entry(string(buf), data))
349 : 1 : pq.push(new FlintSpellingTermList(data));
350 : 6 : buf[0] = 'T';
351 [ + + ]: 6 : if (get_exact_entry(string(buf), data))
352 : 1 : pq.push(new FlintSpellingTermList(data));
353 : : }
354 : :
355 [ + + ]: 72 : if (pq.empty()) return NULL;
356 : :
357 : : // Build up an OrTermList tree by combine leaves and/or branches in
358 : : // pairs. The tree is balanced by the approximated sizes of the leaf
359 : : // FlintSpellingTermList objects - the way the tree is built are very
360 : : // similar to how an optimal Huffman code is often constructed.
361 : : //
362 : : // Balancing the tree like this should tend to minimise the amount of
363 : : // work done.
364 [ + + ]: 163 : while (pq.size() > 1) {
365 : : // Build the tree such that left is always >= right so that
366 : : // OrTermList can rely on this when trying to minimise work.
367 : 94 : TermList * termlist = pq.top();
368 : 94 : pq.pop();
369 : :
370 : 94 : termlist = new OrTermList(pq.top(), termlist);
371 : 94 : pq.pop();
372 : 94 : pq.push(termlist);
373 : : }
374 : :
375 : 72 : return pq.top();
376 : 0 : } catch (...) {
377 : : // Make sure we delete all the TermList objects to avoid leaking
378 : : // memory.
379 [ # # ]: 0 : while (!pq.empty()) {
380 [ # # ]: 0 : delete pq.top();
381 : 0 : pq.pop();
382 : : }
383 : 0 : throw;
384 : 72 : }
385 : : }
386 : :
387 : : Xapian::doccount
388 : 90 : FlintSpellingTable::get_word_frequency(const string & word) const
389 : : {
390 : 90 : map<string, Xapian::termcount>::const_iterator i;
391 : 90 : i = wordfreq_changes.find(word);
392 [ - + ]: 90 : if (i != wordfreq_changes.end()) {
393 : : // Modified frequency for word:
394 : 0 : return i->second;
395 : : }
396 : :
397 : 90 : string key = "W" + word;
398 : 90 : string data;
399 [ + + ]: 90 : if (get_exact_entry(key, data)) {
400 : : // Word "word" already exists.
401 : : Xapian::termcount freq;
402 : 88 : const char *p = data.data();
403 [ - + ]: 88 : if (!F_unpack_uint_last(&p, p + data.size(), &freq)) {
404 : 0 : throw Xapian::DatabaseCorruptError("Bad spelling word freq");
405 : : }
406 : 88 : return freq;
407 : : }
408 : :
409 : 90 : return 0;
410 : : }
411 : :
412 : : ///////////////////////////////////////////////////////////////////////////
413 : :
414 : : Xapian::termcount
415 : 656 : FlintSpellingTermList::get_approx_size() const
416 : : {
417 : : // This is only used to decide how to build a OR-tree of TermList objects
418 : : // so we just need to return "sizes" which are ordered roughly correctly.
419 : 656 : return data.size();
420 : : }
421 : :
422 : : std::string
423 : 220 : FlintSpellingTermList::get_termname() const
424 : : {
425 : 220 : return current_term;
426 : : }
427 : :
428 : : Xapian::termcount
429 : 210 : FlintSpellingTermList::get_wdf() const
430 : : {
431 : 210 : return 1;
432 : : }
433 : :
434 : : Xapian::doccount
435 : 0 : FlintSpellingTermList::get_termfreq() const
436 : : {
437 : 0 : return 1;
438 : : }
439 : :
440 : : Xapian::termcount
441 : 0 : FlintSpellingTermList::get_collection_freq() const
442 : : {
443 : 0 : return 1;
444 : : }
445 : :
446 : : TermList *
447 : 373 : FlintSpellingTermList::next()
448 : : {
449 [ + + ]: 373 : if (p == data.size()) {
450 : 163 : p = 0;
451 : 163 : data.resize(0);
452 : 163 : return NULL;
453 : : }
454 [ + + ]: 210 : if (!current_term.empty()) {
455 [ - + ]: 47 : if (p == data.size())
456 : 0 : throw Xapian::DatabaseCorruptError("Bad spelling termlist");
457 : 47 : current_term.resize(byte(data[p++]) ^ MAGIC_XOR_VALUE);
458 : : }
459 : : unsigned add;
460 [ + - ][ - + ]: 210 : if (p == data.size() ||
[ - + ]
461 : : (add = byte(data[p]) ^ MAGIC_XOR_VALUE) >= data.size() - p)
462 : 0 : throw Xapian::DatabaseCorruptError("Bad spelling termlist");
463 : 210 : current_term.append(data.data() + p + 1, add);
464 : 210 : p += add + 1;
465 : 373 : return NULL;
466 : : }
467 : :
468 : : TermList *
469 : 0 : FlintSpellingTermList::skip_to(const string & term)
470 : : {
471 [ # # ][ # # ]: 0 : while (!data.empty() && current_term < term) {
[ # # ]
472 : 0 : (void)FlintSpellingTermList::next();
473 : : }
474 : 0 : return NULL;
475 : : }
476 : :
477 : : bool
478 : 397 : FlintSpellingTermList::at_end() const
479 : : {
480 : 397 : return data.empty();
481 : : }
482 : :
483 : : Xapian::termcount
484 : 0 : FlintSpellingTermList::positionlist_count() const
485 : : {
486 : 0 : throw Xapian::UnimplementedError("FlintSpellingTermList::positionlist_count() not implemented");
487 : : }
488 : :
489 : : Xapian::PositionIterator
490 : 0 : FlintSpellingTermList::positionlist_begin() const
491 : : {
492 : 0 : throw Xapian::UnimplementedError("FlintSpellingTermList::positionlist_begin() not implemented");
493 : : }
|
