Tanl Linguistic Pipeline

search/ixe/Common/PostingList.cpp

/*
**      IXE
**      Common/PostingList.cpp
** ----------------------------------------------------------------------
**      Copyright (c) 2000  Ideare SpA. All rights reserved.
**      Copyright (c) 2000  Giuseppe Attardi (attardi@di.unipi.it).
** ----------------------------------------------------------------------
**
**  This file is part of IXE.
**
**  IXE is free software; you can redistribute it and/or modify it
**  under the terms of the GNU General Public License, version 3,
**  as published by the Free Software Foundation.
**
**  IXE is distributed in the hope that it will be useful,
**  but WITHOUT ANY WARRANTY; without even the implied warranty of
**  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
**  GNU General Public License for more details.
**
**  You should have received a copy of the GNU General Public License
**  along with this program.  If not, see <http://www.gnu.org/licenses/>.
**  ----------------------------------------------------------------------
*/

// Settings
#include "Common/PostingList.h"

namespace IXE {

//=============================================================================
//=============================================================================

PostingList::const_iterator&
PostingList::const_iterator::operator ++()
{
  // rest_ contains the number of remaining elements, including
  // the current one, already read into posting (cannot be 0, which means end)
  assert(rest_ > 0);
  if (--rest_ == 0)             // decrement count
    return *this;

  posting.index = parseEptacode(c_); // document ID

  if (!posting.colors.empty())
    posting.colors.erase(posting.colors.begin(), posting.colors.end());
  if (*c_ == 0x80)              // = 0 in base-128 coding
    {                           // META ID list follows
      ++c_;                     // skip past 0x80
      while (*c_ != 0x80)
        posting.colors.insert(parseEptacode(c_) - 1); // distinguish from 0x80
      ++c_;                     // skip past 0x80
    }

  posting.termFrequency = parseEptacode(c_);
  hitlen = parseEptacode(c_) + posting.termFrequency; // L is just the delta
  hitsCursor = PostingList::HitsCursor(posting.termFrequency, c_);
  c_ += hitlen;
  return *this;
}

PostingList::const_iterator&
PostingList::const_iterator::next(DocID min)
{
  if (min <= posting.index)
    return *this;

# ifndef noSKIP_LIST
  if (table_ &&                 // there is a table
      min >= table_[0].id) {    // looking for PL beyond first block
    // Perform a binary search on the portion of the table
    // corrisponding to postings beyond the current one
    // rest_ - 1 = remaining elements (initially rest_ == size_)
    int current = size_ - rest_;// current posting (already read into posting)
    int start = MAX(0, current / Postings_Segment_Size - 1);
    int end = tablesz_;
    int mid = (start + end) / 2;

    while (min > table_[start].id && mid > start) {
      if (min < table_[mid].id)
        end = mid;              // not -1 otherwise mid-1 would be excluded
      else
        start = mid;
      mid = (start + end) / 2;
    }
    // (start+1) since first block (up to Posting_Segment_Size) has no entry
    int block_first = (start + 1) * (Postings_Segment_Size);
    if (block_first > current) {
      c_ = (const byte*)table_ + table_[start].offset;
      // +1 since it gets decremented by ++()
      rest_ = size_ - block_first + 1;
      ++(*this); // read the posting
    }
  }
# endif // SKIP_LIST

# if 1                          // Optimize by inlining ++()
  while (rest_ && min > posting.index) {
    // ++() expanded inline
    if (--rest_ == 0)
      break;
    posting.index = parseEptacode(c_); // document ID

    if (!posting.colors.empty())
      posting.colors.erase(posting.colors.begin(), posting.colors.end());
    if (*c_ == 0x80)            // = 0 in base-128 coding
      {                         // META ID list follows
        ++c_;                   // skip past 0x80
        while (*c_ != 0x80)
          posting.colors.insert(parseEptacode(c_) - 1); // distinguish from 0x80
        ++c_;                   // skip past 0x80
      }

    posting.termFrequency = parseEptacode(c_);
    hitlen = parseEptacode(c_) + posting.termFrequency; // L is just the delta
    c_ += hitlen;
  }
  hitsCursor = PostingList::HitsCursor(posting.termFrequency, c_ - hitlen);
# else
  while (rest_ && min > posting.index)
    operator ++();
# endif

  return *this;
}

PostingList::remap_iterator &
PostingList::remap_iterator::operator ++()
{
# ifndef oldMerge
  assert(rest_ > 0);

  const_iterator::operator++();
  if (rest_ == 0) 
    return *this;

  while (remap->find(posting.index) != remapEnd) {
    const_iterator::operator++();
    if (rest_ == 0)
      return *this;
  }

  Remap::const_iterator remf = remap->lower_bound(posting.index);
  if (remf != remapEnd) {
    posting.index -= remf->second;
    if (remf->first>posting.index)
      posting.index -= 1;
  }
  else
    posting.index -= remap->size();

  posting.index += displace;

  return *this;

# else //oldMerge
  // We look for the minimum remapped ID.
  // Examine the next ID, check whether it is smaller the the first (smallest)
  // remapped. If not, return.
  // Ex:
  //  List: (3, 6, 7, 8)
  //  Remap: (2 -> 7), (4 -> 9), (5 -> 6)
  //  Displace: 10
  //  Result: 2, 5, 13, 18

  // Snapshots
  // After constructor
  // rest_: 4, c_: 3, 6, 7, 8   posting: 7 (remapped to 2)
  // ++()
  // rest_: 3, c_: 3, 6, 7, 8   posting: 6 (remapped to 5)
  // ++()
  // rest_: 2, c_: 8            posting: 3 (remapped to 13)
  // ++()
  // rest_: 1, c_:              posting: 8 (remapped to 18)


  // The code must maintain the following invariants:
  // a. posting contains the current posting
  // b. c_ points to where to start scanning for next posting
  // c. rest_ counts the remaining postings, including the current,
  //    but excluding already remapped.
  //

  assert(rest_ > 0);

  // rest_: 4, c_: 3, 6, 7, 8   posting: 7 (remapped to 2)

  Count restSave = rest_;
  byte const* cSave = c_;
  // advance skipping those already returned
  while (rest_) {
    cSave = c_;                 // save last non skipped, so we can reread it
    const_iterator::operator++();
    if (!remapped.contains(posting.index))
      break;
  }

  // rest_: 4, c_: 6, 7, 8      posting: 3

  DocID index = posting.index;  // save, since next() will overwrite

  // look for a remapped ID smaller than current.
  // map is sorted by first.
  while (remapIt != remapEnd) {
    if (remapIt->second < index) {
      displace--;               // one document was skipped
      ++remapIt;
      continue;
    }
    if (remapIt->first >= displace + index)
      // does not remap to a smaller index
      break;

    // (5 -> 6)
    DocID postindex = remapIt->first;
    DocID indexRemapped = remapIt->second;
    ++remapIt;
    // skip to it
    bool found = next(indexRemapped) != const_iterator();

    // rest_: 3, c_: 7, 8       posting: 6

    // move back. Next step will start from there.
    rest_ = restSave;
    c_ = cSave;

    // rest_: 4, c_: 3, 6, 7, 8 posting: 6

    if (found && posting.index == indexRemapped) {
      remapped.insert(indexRemapped); // so it will be skipped later
      // the id is remapped
      posting.index = postindex;
      --rest_;
      // rest_: 3, c_: 3, 6, 7, 8       posting: 6 (remapped to 5)
      return *this;
    }
  }
  // no remapped id smaller than current
  // move back to current.
  rest_ = restSave;
  c_ = cSave;
  // reread posting
  const_iterator::operator++();
  posting.index += displace;
  return *this;
# endif //oldMerge
}

} // namespace IXE

 

Copyright © 2005-2011 G. Attardi. Generated on 3 Mar 2011 by doxygen 1.6.1.