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