source: trunk/gsdl/src/mgpp/text/stem_search.cpp@ 711

/**************************************************************************
 *
 * stem_search.c -- Functions for searching the blocked stemmed dictionary
 * Copyright (C) 1994  Neil Sharman
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program 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, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 * $Id: stem_search.cpp 711 1999-10-17 23:43:31Z cs025 $
 *
 **************************************************************************/

#include "sysfuncs.h"

#include "memlib.h"
#include "messages.h"
#include "filestats.h"
#include "timing.h"
#include "local_strings.h"
#include "netorder.h"  /* [RPAP - Jan 97: Endian Ordering] */

#include "mg.h"
#include "invf.h"
#include "text.h"
#include "lists.h"
#include "backend.h"
#include "words.h"
#include "locallib.h"
#include "stem_search.h"
#include "StemBlock.h"
#include "StemIdx.h"
#include "mg_errors.h"
#include "term_lists.h"
#include "stemmer.h"


/*
   $Log$
   Revision 1.2  1999/10/17 23:43:29  cs025
   Changes to eradicate Xmalloc

   Revision 1.1  1999/10/11 02:58:32  cs025
   Base install of MG-PP

   Revision 1.1  1999/08/10 21:18:22  sjboddie
   renamed mg-1.3d directory mg

   Revision 1.3  1999/07/02 00:18:55  rjmcnab
   Changed so FindWords could be used in new ways.

   Revision 1.2  1998/11/25 07:55:51  rjmcnab

   Modified mg to that you can specify the stemmer you want
   to use via a command line option. You specify it to
   mg_passes during the build process. The number of the
   stemmer that you used is stored within the inverted
   dictionary header and the stemmed dictionary header so
   the correct stemmer is used in later stages of building
   and querying.

   Revision 1.1  1998/11/17 09:35:39  rjmcnab
   *** empty log message ***

   * Revision 1.3  1994/10/20  03:57:04  tes
   * I have rewritten the boolean query optimiser and abstracted out the
   * components of the boolean query.
   *
   * Revision 1.2  1994/09/20  04:42:08  tes
   * For version 1.1
   *
 */

static char *RCSID = "$Id: stem_search.cpp 711 1999-10-17 23:43:31Z cs025 $";


size_t stemAbstractReader(void *ptr, size_t size, size_t nitems, void *file)
{ return Fread(ptr, size, nitems, (File *) file);
}

char stemAbstractGetc(void *file)
{ return Getc(((File *) file));
}

int stemAbstractSeeker(void *file, long offset, int ptrname)
{ return Fseek((File *) file, offset, ptrname);
}

/* [RPAP - Jan 97: Stem Index Change] */
stemmed_idx *
ReadStemIdxBlk (File * stem_idx_file)
{
  unsigned long i;
  stemmed_idx *si;
  u_char *buffer;

  si = StemIdx_header_read((void *) stem_idx_file, 1, stemAbstractReader, stemAbstractGetc);
  if (si == NULL)
    {
      mg_errno = MG_NOMEM;
      return (NULL);
    }
  mg_errno = MG_NOERROR;

  /*  fprintf (stderr, "mem for stem idx = %i\n", si->MemForStemIdx); */

  return si;
}

static int 
Word_BaseIndexNo(int num_indexes, u_char *base, unsigned short *index, u_char *word)
{
  register int lo, hi, mid, c;

  lo = 0;
  hi = num_indexes - 1;
  while (lo <= hi)
    {
      mid = (lo + hi) / 2;
      c = casecompare (word, base + index[mid] + 1);  /* [RPAP - Jan 97: Stem Index Change] */
      if (c < 0)
    hi = mid - 1;
      else if (c > 0)
    lo = mid + 1;
      else
    {
      hi = mid;
      break;
    }
    }
  if (hi < 0)
    hi = 0;

  return hi;
}


/* [RPAP - Jan 97: Stem Index Change] */
/* word should be appropriately stemed */
static int
Word_IdxBlockNo (stemmed_idx * si, u_char * word)
{
  register int lo = 0, hi = si->sih.num_blocks - 1;
  register int mid = 0, c = 0;

  while (lo <= hi)
    {
      mid = (lo + hi) / 2;
      c = casecompare (word, si->index[mid]);
      if (c < 0)
    hi = mid - 1;
      else if (c > 0)
    lo = mid + 1;
      else
    return mid;
    }
  return hi < 0 ? 0 : (c < 0 ? mid - 1 : mid);
}


static int 
Word_BlockNo (stemmed_dict * sd, u_char * word)
{
  register int lo = 0, hi = sd->sdh.num_blocks - 1;
  register int mid = 0, c = 0;
  while (lo <= hi)
    {
      mid = (lo + hi) / 2;
      c = casecompare (word, sd->index[mid]);  /* [RPAP - Jan 97: Stem Index Change] */
      if (c < 0)
    hi = mid - 1;
      else if (c > 0)
    lo = mid + 1;
      else
    return mid;
    }
  return hi < 0 ? 0 : (c < 0 ? mid - 1 : mid);
}

unsigned long Word_SkipToNextInvfPtr(u_char **base, unsigned long invfp)
{ 
  unsigned suff;
  unsigned long next_invfp;

  *base  = *base + 1;
  suff   = **base;
  *base  = *base + 1;
  *base += suff + sizeof (unsigned long) * 2;
  bcopy ((void *) *base, (void *) &next_invfp, sizeof (next_invfp));
  NTOHUL(next_invfp);  /* [RPAP - Jan 97: Endian Ordering] */
  return next_invfp - invfp;
}

/*
 * This function looks up a word in the stemmed dictionary, it returns -1
 * if the word cound not be found, and 0 if it successfully finds the word.
 * If count is non-null the ulong it is pointing to is set to the number of 
 * occurances of the stemmed word in the collection. i.e wcnt.
 * If doc_count is non-null the ulong it is pointing to is set to the number
 * of documents that the word occurs in. i.e fcnt
 * If invf_ptr is non-null the ulong it is pointing to is set to the position
 * of the inverted file where the entry for this word start.
 */
int 
FindWord (stemmed_dict * sd, u_char * Word, unsigned long *count,
      unsigned long *doc_count, unsigned long *invf_ptr,
      unsigned long *invf_len)
{
  register int lo, hi, mid, c;
  register unsigned int res;
  int block, num_indexes;
  unsigned long *first_word, *last_invf_len;
  unsigned short *num_words;
  u_char *base;
  unsigned short *index;
  u_char prev[MAXSTEMLEN + 1];

  /**
   * GRB : Get the index for the block of words in the stemmed dictionary;
   *       If the block required is not the current cached (active) block,
   *         then load that block in now. 
   */

  block = Word_BlockNo (sd, Word);
  /* [RPAP - Jan 97: Endian Ordering] */
  if (sd->active != sd->pos[block])
    {
      StemBlock_read(sd, block, &first_word, &last_invf_len, &num_words, 
             &index, &num_indexes);
    }
  else
    {
      first_word = (unsigned long *) (sd->buffer);
      last_invf_len = (unsigned long *) (first_word + 1);
      num_words = (unsigned short *) (last_invf_len + 1);
      index = num_words + 1;
      num_indexes = ((*num_words - 1) / sd->sdh.lookback) + 1;
    }
  base = (u_char *) (index + num_indexes);

  /* --
     -- GRB: search current block for the given word using binary chop
     --
  */
  hi = Word_BaseIndexNo(num_indexes, base, index, Word);

  res = hi * sd->sdh.lookback;
  base += index[hi];

  /** 
   *
   * GRB: stream over the words which come from the same stem, and 
   *      check for matches amongst them
   */
  while (res < *num_words)
    {
      unsigned long invfp;
      StemBlock_ReadWordString(&base, prev);

      c = casecompare (Word, prev);   /* [RPAP - Jan 97: Stem Index Change] */
      if (c < 0)
    return (-1);

      if (c == 0 && doc_count)
    {
      bcopy ((void *) base, (void *) doc_count, sizeof (*doc_count));
      NTOHUL(*doc_count);  /* [RPAP - Jan 97: Endian Ordering] */
    }
      base += sizeof (*doc_count);

      if (c == 0 && count)
    {
      bcopy ((void *) base, (void *) count, sizeof (*count));
      NTOHUL(*count);  /* [RPAP - Jan 97: Endian Ordering] */
    }
      base += sizeof (*count);

      if (c == 0 && invf_ptr)
    {
      bcopy ((void *) base, (void *) &invfp, sizeof (invf_ptr));
      NTOHUL(invfp);  /* [RPAP - Jan 97: Endian Ordering] */
      *invf_ptr = invfp;
    }
      base += sizeof (*invf_ptr);

      if (c == 0)
    {
      /* Calculate invf_len is necessary */
      if (!invf_len)
        return (*first_word + res);

      /* If the current word is the last word of the block then get the 
         length from last_invf_len */
      if (res == *num_words - 1)
        {
          *invf_len = *last_invf_len;
          return (*first_word + res);
        }

      /* Skip over most of the next word to get to the invf_ptr */
      *invf_len = Word_SkipToNextInvfPtr(&base, invfp);
      return (*first_word + res);
    }
      res++;
    }
  /* -- GRB return a negative response; word was not actually found after all */
  return (-1);
}


/* [RPAP - Jan 97: Stem Index Change] */
int 
FindWords (stemmed_dict * sd, u_char * sWord, int stem_method, TermList ** tl)
{
  register unsigned int res;
  unsigned int idx_res;
  unsigned copy, suff;
  int j, k;

  int block, num_indexes;
  unsigned long *first_word, *last_invf_len;
  unsigned short *num_words;
  u_char *base;
  unsigned short *index;
  u_char prev[MAXSTEMLEN + 1];

  int idx_block, idx_num_indexes;
  unsigned long *idx_first_word;
  unsigned short *idx_num_words;
  u_char *idx_base;
  unsigned short *idx_index;
  u_char idx_prev[MAXSTEMLEN + 1];

  unsigned int num_entries, num_cases;
  unsigned short blk_index, offset;
  stemmed_idx * si = NULL;

  /* handle stem_method 0 seperately */
  if (stem_method == 0) {
    TermEntry te;
    if ((te.WE.word_num = FindWord (sd, sWord, &te.WE.count, &te.WE.doc_count,
                   &te.WE.invf_ptr, &te.WE.invf_len)) != -1) {
      te.WE.max_doc_count = te.WE.doc_count;

      te.Count = 1;
      te.Word = copy_string (sWord);
      if (!te.Word)
    FatalError (1, "Could NOT create memory to add term");
      te.Stem = copy_string (sWord);
      if (!te.Stem)
    FatalError (1, "Could NOT create memory to add term");
      /*      te.query_mask = NULL;*/
      
      TermList_AddTermEntry (*tl, &te);
      return (*tl)->num;
      
    } else {
      /* didn't match */
      return 0;
    }
  }
  
  if (stem_method == 1)
    si = sd->stem1;
  else if (stem_method == 2)
    si = sd->stem2;
  else
    si = sd->stem3;

  /**
   * Locate block: If this block is not the active one, then make it active.
   */
  idx_block = Word_IdxBlockNo (si, sWord);

  /* [RPAP - Jan 97: Endian Ordering] */
  if (si->active != si->pos[idx_block])
    {
      StemIdx_block_readNext((void *) si->stem_idx_file, si, idx_block, &idx_first_word, &idx_num_words,
                 &idx_index, &idx_num_indexes, stemAbstractSeeker, stemAbstractReader);
    }
  else
    {
      idx_first_word = (unsigned long *) (si->buffer);
      idx_num_words = (unsigned short *) (idx_first_word + 1);
      idx_index = idx_num_words + 1;
      idx_num_indexes = ((*idx_num_words - 1) / si->sih.lookback) + 1;
    }
  idx_base = (u_char *) (idx_index + idx_num_indexes);

  /**
   * Search in this stem index for the word using binary chop
   */
  {
    /* Locate 3-in-4 block */
    //register int lo, hi, mid, c;
    int hi;

    hi = Word_BaseIndexNo(idx_num_indexes, idx_base, idx_index, sWord);
    idx_res = hi * si->sih.lookback;
    idx_base += idx_index[hi];
  }

  /* Locate word entry by streaming forwards through the index */
  for (;;)
    {
      int c;
      if (idx_res >= *idx_num_words)
    return (-1);
      StemIdx_ReadWordString(&idx_base, idx_prev);

      c = casecompare (sWord, idx_prev);
      if (c < 0)
    return (-1);
     
      bcopy ((void *) idx_base, (void *) &num_entries, sizeof (num_entries));
      NTOHUI(num_entries);  /* [RPAP - Jan 97: Endian Ordering] */
      idx_base += sizeof (num_entries);
      
      if (c > 0)
    idx_base += num_entries * (sizeof (num_cases) + sizeof (block) + 
                   sizeof (blk_index) + sizeof (offset));
      else
    break;

      idx_res++;
    }

  for (k = 0; k < num_entries; k++)
    {
      //unsigned copy, suff;
      unsigned long invfp;
      /**
       * GRB: Read next stem index pos, getting the details of the next word
       *      which is an extension of this stem (a wordform of this stem)
       */
      StemIdx_ReadPosEntry(&idx_base, &num_cases, (unsigned int *) &block, &blk_index, &offset);
      

      /**
       * GRB: Now look up the given word form, as per FindWord above.
       *      Firstly, we need to get to the right block; we read this
       *      above [rather than using Word_BlockIndex as in FindWord()]
       *      So we just need to make sure that it is the active block
       */

      /* [RPAP - Jan 97: Endian Ordering] */
      if (sd->active != sd->pos[block])
    {
      StemBlock_read(sd, block, &first_word, &last_invf_len, &num_words,
             &index, &num_indexes);
    }
      else
    {
      first_word = (unsigned long *) (sd->buffer);
      last_invf_len = (unsigned long *) (first_word + 1);
      num_words = (unsigned short *) (last_invf_len + 1);
      index = num_words + 1;
      num_indexes = ((*num_words - 1) / sd->sdh.lookback) + 1;
    }
      base = (u_char *) (index + num_indexes);
      
      res = blk_index * sd->sdh.lookback;
      base += index[blk_index];

      /**
       * GRB: We know how many words to offset by, so let's scramble
       *      past them
       */      
      for (j = 0; j < offset; j++)
    {
      StemBlock_ReadWordString(&base, prev);
      
      base += sizeof (unsigned long);   /* skip doc_count */
      base += sizeof (unsigned long);   /* skip count */
      base += sizeof (unsigned long);   /* skip invf_ptr */
      res++;
    }

      /**
       * GRB: Now take this wordform case by case
       */
      for (j = 0; j < num_cases; j++)
    {
      TermEntry te;
      
      if (res >= *num_words)
        return (-1);
      StemBlock_ReadWordString(&base, prev);
          
      te.Word = copy_string (prev);
      if (!te.Word)
        FatalError (1, "Could NOT create memory to add term");
      te.Stem = copy_string (prev);
      if (!te.Stem)
        FatalError (1, "Could NOT create memory to add term");
      stemmer (2, sd->sdh.stemmer_num, te.Stem);

      te.Count = 1;
      te.WE.word_num = *first_word + res;
      bcopy ((void *) base, (void *) &te.WE.doc_count, sizeof (te.WE.doc_count));
      NTOHUL(te.WE.doc_count);  /* [RPAP - Jan 97: Endian Ordering] */
      te.WE.max_doc_count = te.WE.doc_count;
      base += sizeof (te.WE.doc_count);
          
      bcopy ((void *) base, (void *) &te.WE.count, sizeof (te.WE.count));
      NTOHUL(te.WE.count);
      base += sizeof (te.WE.count);
          
      bcopy ((void *) base, (void *) &invfp, sizeof (te.WE.invf_ptr));
      NTOHUL(invfp);  /* [RPAP - Jan 97: Endian Ordering] */
      te.WE.invf_ptr = invfp;
      base += sizeof (te.WE.invf_ptr);
        
      /* If the current word is the last word of the block the get the 
         length from last_invf_len */
      if (res == *num_words - 1)
        te.WE.invf_len = *last_invf_len;
      else
        {
          u_char *oldbase = base;
          
          /* Skip over most of the next word to get to the invf_ptr */
          te.WE.invf_len = Word_SkipToNextInvfPtr(&base, invfp);
          base = oldbase;
        }
          
      /* Add term entry to term list */
      /*      te.query_mask = NULL;*/
      TermList_AddTermEntry (*tl, &te);

          /**
           * GRB: If this is the final case of this wordform in this block, 
           *      and we have one or more remaining blocks containing the wordform, 
           *      then read in next block
           */         
      if (res == *num_words - 1 && j + 1 < num_cases)
        {
          /* Read in next block */
          block++;
          StemBlock_read(sd, block, &first_word, &last_invf_len, &num_words, 
                 &index, &num_indexes);
          base = (u_char *) (index + num_indexes);
          base += index[0];
          res = 0;
          blk_index = 0;
        }
      else
        res++;
    } /* end for num_cases */
    } /* end for num_entries */
  return (*tl)->num;
}


void 
FreeStemDict (stemmed_dict * sd)
{
  /* [RPAP - Jan 97: Stem Index Change] */
  if (sd->stem1)
    FreeStemIdx (sd->stem1);
  if (sd->stem2)
    FreeStemIdx (sd->stem2);
  if (sd->stem3)
    FreeStemIdx (sd->stem3);

  delete (sd->index[0]);
  delete (sd->index);
  delete (sd->buffer);
  delete (sd->pos);
  delete sd;
}

/* [RPAP - Jan 97: Stem Index Change] */
void
FreeStemIdx (stemmed_idx * si)
{
  delete si->index[0];
  delete si->index;
  delete si->buffer;
  delete si->pos;
  delete si;
}