Tanl Linguistic Pipeline

search/ixe/Common/lexicon.cpp

/*
**      IXE
**      Common/lexicon.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/lexicon.h"

// standard

// local
#include "Common/util.h"
#include "Common/PostingList.h"

using namespace IXE::io;

namespace IXE {

void Lexicon::access(mappedFile& indexFile, off32_t& offset)
{
  bigrams.access(indexFile, offset);
  begin_ = indexFile.begin();
  off32_t const *p = reinterpret_cast<off32_t const *>(begin_ + offset);
  entries = p[0];               // FIXME: ENDIAN
  table = reinterpret_cast<LexEntry const *>(&p[1]);
  // Advance offset to next table
  offset = table[entries].word;
}

Size Lexicon::getWord(TermID termID, char* term, Size size) const
{
  if (bigrams.size() == 0) {
#   ifdef LEXLEN
    Size len;
    char const* word = getPostfix(termID, len);
#   else
    char const* word = getPostfix(termID);
    Size len = ::strlen(word);
#   endif
    len = MIN(len, size);
    ::memcpy(term, word, len);
    term[len] = '\0';
    return len;
  }
  Lexicon* lex = (Lexicon*)this; // hack to access the right version of BigramTable[]
  TermID* bigramTable = (TermID*)&lex->bigrams[0];
  // Find initial bigram for word
  // (it is the last one having a value smaller than termID)
  int bigram_index = 0;
  int first = 0;
  int last = num_bigrams - 1;
  int dist = last - first;
  while (dist > 0) {
    int half = dist / 2;
    int middle = first + half;
    TermID vmiddle = bigramTable[middle];
    if (vmiddle > termID) {
      last = middle;
      dist = half;
    } else if (termID < bigramTable[middle+1]) {
      bigram_index = middle;
      break;
    } else if (middle + 1== last) {
      // not present
      term[0] = '\0';
      return (Size)-1;
    } else {
      first = middle + 1;
      dist = last - first;
    }
  }
  term[0] = (char)(bigram_index >> 8);
  term[1] = (char)bigram_index;
# ifdef LEXLEN
  Size len;
  char const* word = getPostfix(termID, len);
# else
  char const* word = getPostfix(termID);
  Size len = ::strlen(word);
# endif
  len = MIN(len+2, size);
  ::memcpy(term+2, word, len-2);
  term[len] = '\0';     // ensure termination
  return len;
}

Lexicon::const_iterator Lexicon::find(char const* word)
{
  size_type begin, end;
  if (bigrams.size()) {
      //
      // Search the bigrams index first.
      unsigned short bigram = *(short *)(word);
#     ifndef WORDS_BIGENDIAN
      bigram = (bigram << 8) | (bigram >> 8);
#     endif
      begin = bigrams[bigram];
      end = bigrams[bigram + 1];
      if (begin == end)         // not present
        return this->end();
      // Chop off the first 2 characters from the string
      word = &word[2];
    } else {
      begin = 0;
      end = entries;
    }
  // specialized version of ::lower_bound
  const_iterator first = position_at(begin);
  const_iterator last = position_at(end);
  const_iterator middle;
  int len = last - first;
  unsigned char mchar, vchar;
  register const char *smiddle, *svalue;

  while (len > 0) {
    int half = len / 2;
    middle = first + half;
    // find where middle differs from value
    smiddle = getPostfix(*middle);
    svalue = word;
    while ((mchar = *smiddle++) == (vchar = *svalue++))
      if (mchar == '\0')
        return middle;
    if (mchar < vchar) {
      first = middle + 1;
      len = len - half - 1;
    }
    else
      len = half;
  }
  return this->end();                   // not found
}

#ifdef LEXLEN
Lexicon::const_iterator Lexicon::find(byte* word, Size len)
{
  size_type begin, end;
  Size bglen;
  if (bigrams.size()) {
    //
    // Search the bigrams index first.
    unsigned short bigram = *(short *)(word);
#   ifndef WORDS_BIGENDIAN
    bigram = (bigram << 8) | (bigram >> 8);
#   endif
    begin = bigrams[bigram];
    end = bigrams[bigram + 1];
    if (begin == end)           // not present
      return this->end();
    // Chop off the first 2 bytes from the string
    word = &word[2];
    bglen = 2;
  } else {
    begin = 0;
    end = entries;
    bglen = 0;
  }
  // specialized version of ::lower_bound
  const_iterator first = position_at(begin);
  const_iterator last = position_at(end);
  register Size lmiddle;
  unsigned char mchar, vchar;

  int dist = last - first;
  while (dist > 0) {
    int half = dist / 2;
    const_iterator middle = first + half;
    char const* smiddle = getPostfix(*middle, lmiddle);
    byte* svalue = word;
    Size lvalue = len;
    // find where middle differs from word
    while (lvalue > bglen && lmiddle > bglen) {
      if ((mchar = *smiddle++) != (vchar = *svalue++))
        break;
      lvalue--; lmiddle--;
    }
    if (lvalue == bglen && lmiddle == bglen)    // found
      return middle;  
    if (mchar < vchar || lmiddle == bglen) {
      first = middle + 1;
      dist = dist - half - 1;
    } else
      dist = half;
  }
  return this->end();           // not found
}
#endif // LEXLEN

#ifdef LEXLEN
struct EntryCompare :
 std::binary_function<LexEntry const*, char const*, bool>
{
  EntryCompare(Size len, Lexicon const& lex) : len(len), lex(lex) { }

  result_type
  operator ()(first_argument_type a, second_argument_type b) const {
    Size wl;
    char const* word = lex.getPostfix(a, wl);
    return ::memcmp(word, b, MIN(wl, len)) < 0;
  }
  result_type
  operator ()(second_argument_type a, first_argument_type b) const {
    Size wl;
    char const* word = lex.getPostfix(b, wl);
    return ::memcmp(a, word, MIN(len, wl)) < 0;
  }
private:
  Size const    len;
  Lexicon const& lex;
};
#else
struct EntryCompare :
 std::binary_function<LexEntry const*, char const*, bool>
{
  EntryCompare(int len, Lexicon const& lex) : len(len), lex(lex) { }

  result_type
  operator ()(first_argument_type a, second_argument_type b) const {
    return ::strncmp(lex.getPostfix(a), b, len) < 0;
  }
  result_type
  operator ()(second_argument_type a, first_argument_type b) const {
    return ::strncmp(a, lex.getPostfix(b), len) < 0;
  }
# ifdef _MSC_VER        // why does it need this? Beppe
  result_type
  operator ()(first_argument_type a, first_argument_type b) const {
    return ::strncmp(lex.getPostfix(a), lex.getPostfix(b), len) < 0;
  }
# endif
private:
  int const     len;
  Lexicon const& lex;
};
#endif // LEXLEN

Lexicon::Range Lexicon::findPrefix(char const * term, Size len)
{
  Range range;
  if (bigrams.size()) {
    size_type begin, end;
    if (len > 1) {
      // Determine range of initial bigram
      unsigned short bigram = *(short *)term;// SS
#     ifndef WORDS_BIGENDIAN
      bigram = (bigram << 8) | (bigram >> 8);
#     endif
      begin = bigrams[bigram];
      end = bigrams[bigram + 1];
      // restrict to rest of prefix
      EntryCompare const comparator(len - 2, *this);
      const char * rest = term + 2;

      range = std::equal_range(position_at(begin),
                               position_at(end),
                               rest, comparator);
    } else {
      char first = term[0];
      begin = bigrams[first << 8];
      end = bigrams[(first + 1) << 8];
      // fill the pair
      range.first = position_at(begin);
      range.second = position_at(end);
    }
  } else {
      EntryCompare const comparator(len, *this);
      range = std::equal_range(begin(), end(), term, comparator);
  }
  return range;
}

Count Lexicon::frequency(char const* word)
{
# ifdef LEXLEN
  const_iterator it = find(word, strlen(word));
# else
  const_iterator it = find(word);
# endif
  if (it == end())
    return 0;
  PostingList postlist(postingsFile, it);
  return postlist.size();
}

char const* Lexicon::Cursor::word()
{
  if (lexicon->bigrams.size() == 0)
#   ifdef LEXLEN
    {
      Size len;
      char const* word = lexicon->getPostfix(word_index, len);
      ::memcpy(term, word, len);
      term[len] = '\0';
      return term;
    }
#   else
    return lexicon->getPostfix(word_index);
#   endif
  Size const* bigramTable = (Size const*)&lexicon->bigrams[0];
  // Find initial bigram for word
  // (it is the last one having a value smaller than word_index)
  int first = bigram_index;
  int last = num_bigrams - 1;
  int dist = last - first;
  while (dist > 0) {
    int half = dist / 2;
    int middle = first + half;
    long vmiddle = (long)bigramTable[middle];
    if (vmiddle > word_index) {
      last = middle;
      dist = half;
    } else if (word_index < (long)bigramTable[middle+1]) {
      bigram_index = middle;
      break;
    } else if (middle + 1== last) {
      // not present
      return ""; // or 0?
    } else {
      first = middle + 1;
      dist = last - first;
    }
  }
  term[0] = (char)(bigram_index >> 8);
  term[1] = (char)bigram_index;
# ifdef LEXLEN
  Size len;
  char const* word = lexicon->getPostfix(word_index, len);
  len = MIN(len, 2*WordMaxSize);
  ::memcpy(term+2, word, len-2);
  term[len] = '\0';
# else
  ::strncpy(term+2, lexicon->getPostfix(word_index), 2*WordMaxSize-2);
  term[2*WordMaxSize] = '\0';   // ensure termination
# endif
  return term;
}

// FIXME: Make sure compiler performs suitable unnamed return value
// optimization which avoids calling destructor for local PostingList,
// which would close the MappedFileView
// This is true for GCC 2.96 20000731

PostingList Lexicon::Cursor::postingList()
{
  off64_t postingStart = operator *()->postingsOffset();
  return PostingList(lexicon->postingsFile,
                     postingStart,
                     (*this)[1]->postingsOffset() - postingStart);
}

void Lexicon::Cursor::postingList(PostingList& pl)
{
  off64_t postingStart = operator *()->postingsOffset();
  pl.open(lexicon->postingsFile,
          postingStart,
          (*this)[1]->postingsOffset() - postingStart);
}

} // namespace IXE

 

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