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