1 #!/usr/bin/env python 2 3 """ 4 Specific classes for storing term information. 5 6 Copyright (C) 2009, 2010, 2011 Paul Boddie <paul@boddie.org.uk> 7 8 This program is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free Software 10 Foundation; either version 3 of the License, or (at your option) any later 11 version. 12 13 This program is distributed in the hope that it will be useful, but WITHOUT ANY 14 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A 15 PARTICULAR PURPOSE. See the GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License along 18 with this program. If not, see <http://www.gnu.org/licenses/>. 19 """ 20 21 from iixr.data import * 22 from iixr.files import * 23 from itermerge import itermerge 24 from os.path import commonprefix # to find common string prefixes 25 from bisect import bisect_right, insort_right 26 import operator 27 28 class TermWriter(FileWriter): 29 30 "Writing term information to files." 31 32 def begin(self, docnum_size, position_size): 33 34 "Begin writing to the file." 35 36 self.write_numbers((docnum_size, position_size)) 37 self.end_record() 38 39 self.data_start = self.tell() 40 self.docnum_size = docnum_size 41 self.position_size = position_size 42 self.subtractor = get_subtractor(docnum_size) 43 self.last_term = "" 44 45 def write_terms(self, terms): 46 47 """ 48 Write the 'terms' to the term information file, with each term's details 49 stored in a separate record. 50 """ 51 52 if hasattr(terms, "items"): 53 terms = terms.items() 54 terms.sort() 55 56 for term, doc_positions in terms: 57 if not doc_positions: 58 continue 59 60 if hasattr(doc_positions, "items"): 61 doc_positions = doc_positions.items() 62 63 docnum, positions = doc_positions[0] 64 65 if not positions: 66 continue 67 68 # Start the writing, if appropriate. 69 70 if self.data_start is None: 71 self.begin(sizeof(docnum), sizeof(positions[0])) 72 73 # Write each term and document positions. 74 75 self.write_term(term, doc_positions) 76 self.end_record() 77 78 # Methods requiring an open record. 79 80 def write_term(self, term, doc_positions): 81 82 """ 83 Write the given 'term', its document frequency (number of documents in 84 which it appears), and 'doc_positions' to the term information file. 85 """ 86 87 self.write_term_only(term) 88 89 # Write the document frequency and the term positions. 90 91 self.write_positions(doc_positions) 92 93 def write_term_plus_remaining(self, term, data): 94 95 "Write the given 'term' and the document position 'data'." 96 97 self.write_term_only(term) 98 self.write_remaining(data) 99 100 def write_term_only(self, term): 101 102 "Write only the given 'term'." 103 104 if term <= self.last_term: 105 raise ValueError, "Term %r precedes the previous term %r." % (term, self.last_term) 106 107 # Write the prefix length and term suffix. 108 109 common = len(commonprefix([self.last_term, term])) 110 suffix = term[common:] 111 112 self.write_number(common) 113 self.write_string(suffix) 114 115 self.last_term = term 116 117 def write_positions(self, doc_positions): 118 119 "Write the given 'doc_positions' to the file." 120 121 # Make sure that the positions are sorted. 122 123 doc_positions.sort() 124 125 # Write the document frequency. 126 127 self.write_number(len(doc_positions)) 128 129 last_docnum = None 130 131 for docnum, positions in doc_positions: 132 133 # Store the first document number as it is. 134 135 if last_docnum is None: 136 docnum_seq = docnum 137 138 # Reject out-of-order documents. 139 140 elif docnum < last_docnum: 141 raise ValueError, "Document number %r is less than previous number %r." % (docnum, last_docnum) 142 143 # Calculate an ongoing delta. 144 145 else: 146 docnum_seq = self.subtractor(docnum, last_docnum) 147 148 # Write the document number and positions. 149 150 self.write_sequence_value(docnum_seq, self.docnum_size) 151 self.write_monotonic_sequence(positions, self.position_size) 152 153 last_docnum = docnum 154 155 # Write a terminating byte to indicate that no more document pages 156 # exist. 157 158 self.write_byte(0) 159 160 class TermReader(FileReader): 161 162 "Reading term information from files." 163 164 def begin(self): 165 166 "Begin reading from the file." 167 168 self.begin_record() 169 try: 170 self.docnum_size, self.position_size = self.read_numbers(2) 171 except EOFError: 172 self.docnum_size, self.position_size = 0, 0 # NOTE: No positions! 173 174 self.data_start = self.tell() 175 self.adder = get_adder(self.docnum_size) 176 self.last_term = "" 177 178 def get_sizes(self): 179 return self.docnum_size, self.position_size 180 181 # Methods requiring an open record. 182 183 def read_term(self): 184 185 "Read a term and its document positions from the term information file." 186 187 # Read the term. 188 189 self.read_term_only() 190 191 # Read the document frequency and the term positions. 192 193 positions = self.read_positions() 194 195 return self.last_term, positions 196 197 def read_term_plus_remaining(self): 198 199 """ 200 Read a term and the unprocessed document position data. 201 """ 202 203 self.read_term_only() 204 return self.last_term, self.read_remaining() 205 206 def read_term_only(self): 207 208 "Read a term only." 209 210 # Read the prefix length and term suffix. 211 212 common = self.read_number() 213 suffix = self.read_string() 214 215 self.last_term = self.last_term[:common] + suffix 216 return self.last_term 217 218 def read_positions(self): 219 220 "Read document positions from the term information file." 221 222 doc_positions = [] 223 224 while 1: 225 226 # Read the document frequency. 227 228 npositions = self.read_number() 229 230 last_docnum = None 231 i = 0 232 while i < npositions: 233 234 # Read the document number. 235 236 docnum = self.read_sequence_value(self.docnum_size) 237 if last_docnum is not None: 238 docnum = self.adder(docnum, last_docnum) 239 240 # Read the positions. 241 242 positions = self.read_monotonic_sequence(self.position_size) 243 doc_positions.append((docnum, positions)) 244 245 last_docnum = docnum 246 i += 1 247 248 # Read a terminating byte to discover whether more document pages 249 # exist. 250 251 if not self.read_byte(): 252 break 253 254 return doc_positions 255 256 # Indexes covering the information files. 257 258 class TermIndexWriter(FileWriter): 259 260 "Writing term index information to files." 261 262 def begin(self): 263 264 "Begin writing to the file." 265 266 self.data_start = self.tell() 267 self.last_term = "" 268 self.last_offset = 0 269 270 def write_term(self, term, offset): 271 272 "Write the given 'term' and 'offset'." 273 274 if term <= self.last_term: 275 raise ValueError, "Term %r precedes the previous term %r." % (term, self.last_term) 276 277 # Write the prefix length and term suffix. 278 279 common = len(commonprefix([self.last_term, term])) 280 suffix = term[common:] 281 282 self.write_number(common) 283 self.write_string(suffix) 284 285 # Write the offset delta. 286 287 self.write_number(offset - self.last_offset) 288 289 self.last_term = term 290 self.last_offset = offset 291 292 class TermIndexReader(FileReader): 293 294 "Reading term index information to files." 295 296 def begin(self): 297 298 "Begin reading from the file." 299 300 self.data_start = self.tell() 301 self.last_term = "" 302 self.last_offset = 0 303 304 def read_term(self): 305 306 "Read a term and an offset from the file." 307 308 # Read the prefix length and term suffix. 309 310 common = self.read_number() 311 suffix = self.read_string() 312 313 self.last_term = self.last_term[:common] + suffix 314 315 # Read the offset delta. 316 317 self.last_offset += self.read_number() 318 return self.last_term, self.last_offset 319 320 # External reading classes. 321 322 class TermIterator(TermReader): 323 324 "An iterator over terms and positions read from a file." 325 326 def __iter__(self): 327 return self 328 329 def next(self): 330 try: 331 self.begin_record() 332 return self.read_term() 333 except EOFError: 334 raise StopIteration 335 336 class TermDataIterator(TermReader): 337 338 "An iterator over terms and unprocessed document positions data." 339 340 def __iter__(self): 341 return self 342 343 def next(self): 344 try: 345 self.begin_record() 346 return self.read_term_plus_remaining() 347 except EOFError: 348 raise StopIteration 349 350 class TermIndexIterator(TermIndexReader): 351 352 "An iterator over terms and offsets read from a file." 353 354 def __iter__(self): 355 return self 356 357 def next(self): 358 try: 359 self.begin_record() 360 return self.read_term() 361 except EOFError: 362 raise StopIteration 363 364 class CombinedIterator: 365 366 "An iterator providing index and information file access." 367 368 def __init__(self, reader, index_reader): 369 self.reader = reader 370 self.index_reader = index_reader 371 self.records = list(index_reader) 372 self.terms = [t for t, dp in self.records] 373 374 # Cache the last term and positions. 375 376 self.last_term_returned = None 377 self.last_positions_returned = None 378 379 def go_to_term(self, term): 380 381 """ 382 Return the 'term' and positions or nearest following term and positions. 383 """ 384 385 if self.last_term_returned is not None and self.last_term_returned == term: 386 return self.last_term_returned, self.last_positions_returned 387 388 # Get the record providing a term less than or equal to the requested 389 # term, getting the first entry if no such records exist. 390 391 after = bisect_right(self.terms, term) 392 before = max(0, after - 1) 393 394 t, offset = self.records[before] 395 terms_after = self.terms[after:] 396 397 # Seek to the corresponding record in the information file. 398 # Only do this if the term is more quickly reached by seeking. 399 400 if term <= t or ( 401 self.last_term_returned is None or term < self.last_term_returned or 402 self.last_term_returned < t or terms_after and terms_after[0] <= self.last_term_returned 403 ): 404 405 self.reader.seek(offset) 406 407 # Skip the term information, overwrite the reader's state. 408 409 self.reader.begin_record() 410 self.reader.read_term_only() 411 self.reader.last_term = t 412 413 # Where the found term is equal or greater, just read the positions for 414 # the index entry. 415 416 if t >= term: 417 418 # Get the positions. 419 420 self.last_term_returned, self.last_positions_returned = t, self.reader.read_positions() 421 return self.last_term_returned, self.last_positions_returned 422 423 # Where the found term is less, use the information file to find the 424 # term or the one after. 425 426 else: 427 428 # Scan for the term. 429 430 while t < term: 431 t, dp = self.next() # remembers the term and positions 432 433 return t, dp 434 435 def __iter__(self): 436 return self 437 438 def next(self): 439 self.last_term_returned, self.last_positions_returned = record = self.reader.next() 440 return record 441 442 def close(self): 443 if self.reader is not None: 444 self.reader.close() 445 self.reader = None 446 if self.index_reader is not None: 447 self.index_reader.close() 448 self.index_reader = None 449 450 class MultipleReader(itermerge): 451 452 """ 453 Accessing many term readers at once. 454 NOTE: This does not currently work with CombinedIterator instances because 455 NOTE: iteration causes the next method to be called in advance, and this 456 NOTE: obstructs interleaving of go_to_term and next invocations. 457 """ 458 459 def __init__(self, readers, combine=None): 460 461 """ 462 Initialise a master index reader using underlying 'readers' and a 463 'combine' function which knows how to combine position information from 464 different sources. 465 """ 466 467 self.readers = readers 468 self.combine = combine or operator.add 469 470 # Initialise this object as an iterator over the readers. 471 472 itermerge.__init__(self, self.readers) 473 self.next_value = None 474 475 def get_sizes(self): 476 477 # Readers must have compatible sizes. 478 479 if self.readers: 480 return self.readers[0].get_sizes() 481 else: 482 return 0, 0 483 484 def go_to_term(self, term): 485 486 # Refresh the iterators to provide sought values. 487 488 self.iters = [] 489 for reader in self.readers: 490 try: 491 insort_right(self.iters, (reader.go_to_term(term), reader.next)) 492 except StopIteration: 493 pass 494 495 self.next_value = None 496 return self.next() 497 498 def next(self): 499 500 # Return any prematurely read value. 501 502 if self.next_value is not None: 503 term, positions = self.next_value 504 505 # Otherwise, get the next value. 506 507 else: 508 term, positions = itermerge.next(self) 509 510 # Look at the next item to see if it has positions for the current term. 511 512 try: 513 t, p = itermerge.next(self) 514 while t == term: 515 positions = self.combine(positions, p) 516 t, p = itermerge.next(self) 517 self.next_value = t, p 518 519 # Where an item could not be fetched, cause future requests to fail. 520 521 except StopIteration: 522 self.next_value = None 523 524 return term, positions 525 526 def close(self): 527 for reader in self.readers: 528 reader.close() 529 self.readers = [] 530 531 # vim: tabstop=4 expandtab shiftwidth=4