QueryNode.hpp

Go to the documentation of this file.

/*==========================================================================
 * Copyright (c) 2002-2003 University of Massachusetts.  All Rights Reserved.
 *
 * Use of the Lemur Toolkit for Language Modeling and Information Retrieval
 * is subject to the terms of the software license set forth in the LICENSE
 * file included with this software, and also available at
 * http://www.lemurproject.org/license.html
 *
 *==========================================================================
 */
/*
  author: fff, dmf
  * 03/31/2003 -- Split QueryNode out of StructQueryRep, refactor some 
  * code out of rep into node classes (more OOP that way).
  */

#ifndef _QUERYNODE_HPP
#define _QUERYNODE_HPP
#include "StructQryDocRep.hpp"
#include "ProxInfo.hpp"
namespace lemur 
{
  namespace retrieval 
  {
    
    // forward declaration
    class QueryNode;


    class QnList {
    public:
      QnList() {}
      ~QnList(); 
      void startIteration() {i = 0;}
      bool hasMore() {  return (i < qnList.size()); }
      QueryNode * nextNode()  {QueryNode *qn = qnList[i++]; return qn; }
      const QueryNode * getNode(int j) const{QueryNode *qn = qnList[j]; return qn; }
      int size() const{return qnList.size();}
      void push_back(QueryNode *qn){qnList.push_back(qn);}
      QueryNode *popNode() { 
        QueryNode *qn = qnList[i]; 
        qnList[i++] = NULL;
        return qn;  
      }
    private:
      mutable int i;
      vector<QueryNode *> qnList;
    };
    //------------------------------------------------------------
    //      Abstract Interface for Query Nodes 
    //------------------------------------------------------------



    class QueryNode {
    public:
      QueryNode(int id, double weight) : 
        w(weight),it(id),ch(NULL),entries(0),nextDoc(0),dCnt(0),
        dList(NULL), proxList(NULL), dw(0) {}
      QueryNode() : w(1),it(0),ch(NULL),entries(0),nextDoc(0),dCnt(0),
                    dList(NULL), proxList(NULL), dw(0){}
      QueryNode(double weight, double dWeight = 0) : w(weight), it(0), ch(NULL),
                                                     entries(0), nextDoc(0),
                                                     dCnt(0),proxList(NULL),
                                                     dList(NULL), 
                                                     dw(dWeight) {}
      virtual ~QueryNode() {
        delete[](dList);
        delete(proxList);
        delete(ch);
      }
      const QnList *children() const { return ch;}
      void setChildren(QnList *cl) {ch = cl;}
      int id() const { return it;}
      double weight() const { return w; }
      // update weight
      void setWeight(double wt) { w = wt; }
      // update entries count
      void setEntries(int cnt) { entries = cnt; }

      virtual void copyDocList(int len, int tf, const lemur::api::DocInfoList *dl, int dc) {
      }
      virtual void updateDocList(int numDocs) = 0;
      virtual double eval(const lemur::api::DocumentRep *dRep) const = 0;

      bool isProxNode() const { return proxList != NULL; }
      void startProxIteration() const {if (proxList) proxList->startIteration();}
      bool hasMoreProx() const {return proxList && proxList->hasMore();}
      bool nextProxItem() const {return proxList && proxList->nextDoc();}
      bool nextProxItem(lemur::api::DOCID_T did) const{
        return proxList && proxList->nextDoc(did);
      }

      int dCnt;
      bool *dList;
      mutable lemur::api::DOCID_T nextDoc;
      ProxInfo * proxList;

    protected:  
      void transformPassageOps();
      QnList *ch;
      int entries;
      int it;
      double w; 
      double dw;

      void unionDocList(int numDocs);
      void intersectDocList(int numDocs);
    };

    class BeliefNode : public QueryNode {
    public:
      BeliefNode(double wt) : QueryNode(wt) { }
      BeliefNode(int id, double weight) : QueryNode(id, weight) { }  
      BeliefNode(double wt, double dbelief) : QueryNode(wt, dbelief) { }
      virtual ~BeliefNode() { }
      virtual void updateDocList(int numDocs) {
        unionDocList(numDocs);   
      }
    };


    class ProxNode : public QueryNode {
    public:
      ProxNode(double wt) : QueryNode(wt) {}
  
      ProxNode(int id, double weight) :  QueryNode(id, weight) { }  
      ProxNode(double w, double d) : QueryNode(w, d), winSize(0) {}
      ProxNode(int size, double w, double d) : QueryNode(w, d), winSize(size) {}
      virtual ~ProxNode() { }
      virtual double eval(const lemur::api::DocumentRep *dRep) const {
        return proximityScore(dRep, dw);
      }
      virtual void updateDocList(int numDocs) {
        intersectDocList(numDocs);   
      }

    protected:
      int winSize;
    private:
      double proximityScore(const lemur::api::DocumentRep *dR, double defaultScore) const {
        const StructQryDocRep *dRep = (const StructQryDocRep *)dR;
        int tf = 0;
        double score;
        if(dRep->did < nextDoc) {
          return defaultScore;
        }
        // Skip to next doc id that we can score (> or == to current).
        if (proxList->nextDoc(dRep->did)) {
          double idf = dRep->computeIdfScore(dCnt);
          // compute proximity score for whole doc
          tf = proxList->count();
          score = dRep->beliefScore(tf, idf);
          // advance the prox pointer.
          if (proxList->nextDoc()) {
            nextDoc = proxList->id();
          } else {
            // No more prox entries.
            nextDoc = INT_MAX;
          }
        } else {
          score = defaultScore;
        }
        return score;
      }
    };


    class SumQnode : public BeliefNode {
    public:
      SumQnode(double wt) : BeliefNode(wt){}
      virtual ~SumQnode() {}
      virtual double eval(const lemur::api::DocumentRep *dRep) const{
        double sum = 0;
        int count = 0;
        const QueryNode *qn;
        ch->startIteration();
        while(ch->hasMore()) {
          qn = ch->nextNode();
          sum += qn->eval(dRep);
          count++;
        }
        //    return sum/entries;
        return sum/count;
      }
    };

    class WsumQnode : public BeliefNode {
    public:
      WsumQnode(double w) : BeliefNode(w) {}
      virtual ~WsumQnode() {}
      virtual double eval(const lemur::api::DocumentRep *dRep) const{
        double sum = 0;
        double total_wt = 0;
        const QueryNode *qn;
        double wt;
        ch->startIteration();
        while(ch->hasMore()) {
          qn = ch->nextNode();
          wt = qn->weight(); 
          total_wt += wt;
          sum += wt * qn->eval(dRep);
        }
        if(total_wt > 0) // normalized by the sum of the weights
          sum /= total_wt;
        // the belief is scaled by the weight 'w' of itself.
        return sum;
      }
    };


    class AndQnode : public BeliefNode {
    public:
      AndQnode(double dbelief, double wt) : BeliefNode(wt, dbelief) {}
      virtual ~AndQnode() {}
      virtual double eval(const lemur::api::DocumentRep *dRep) const{
        double prod = 1;
        const QueryNode *qn;
        double wt;
        ch->startIteration();
        while(ch->hasMore()) {
          qn = ch->nextNode();
          wt = qn->eval(dRep);
          if(wt > dw)
            prod *= wt;
          else
            prod *= dw;
        }
        return prod;
      }
    };

    class OrQnode : public BeliefNode {
    public:
      OrQnode(double dbelief, double wt) : BeliefNode(wt, dbelief) {}
      virtual ~OrQnode() {}
      virtual double eval(const lemur::api::DocumentRep *dRep) const {
        double prod = 1.0;
        const QueryNode *qn;
        double wt;
        ch->startIteration();
        while(ch->hasMore()) {
          qn = ch->nextNode();
          wt = qn->eval(dRep);
          if(wt > dw)
            prod *= (1.0 - wt);
        }
        return (1.0 - prod);
      }
    };

    class NotQnode : public BeliefNode {
    public:
      NotQnode(double dbelief, double wt) : BeliefNode(wt, dbelief) {}
      virtual ~NotQnode() {}
      virtual double eval(const lemur::api::DocumentRep *dRep) const{
        // inverting the belief in the only child node
        const QueryNode *qn;
        ch->startIteration();
        qn = ch->nextNode();
        return (1.0 - qn->eval(dRep));
      }
    };

    class MaxQnode : public BeliefNode {
    public:
      MaxQnode(double dbelief, double wt) : BeliefNode(wt, dbelief) {}
      virtual ~MaxQnode() {}
      virtual double eval(const lemur::api::DocumentRep *dRep) const{
        double mx = dw;
        const QueryNode *qn;
        double wt;
        ch->startIteration();
        while(ch->hasMore()) {
          qn = ch->nextNode();
          wt = qn->eval(dRep);
          if(wt > mx) 
            mx = wt;
        }
        return mx;
      }
    };

    class BandQnode : public BeliefNode {
    public:
      BandQnode(double dbelief, double w) : BeliefNode(w, dbelief) {}
      virtual ~BandQnode() {}
      virtual double eval(const lemur::api::DocumentRep *dRep) const{
        double prod = 1.0;
        const QueryNode *qn;
        double wt;
        StructQryDocRep * myRep = (StructQryDocRep *)dRep;
        lemur::api::DOCID_T did = myRep->did;
        ch->startIteration();
        while(ch->hasMore()) {
          qn = ch->nextNode();
          // advance child prox entry to this document
          if (qn->hasMoreProx() && qn->nextProxItem(did))
            qn->nextDoc = did; // update nextDoc for term node eval
          wt = qn->eval(dRep);
          if(wt > dw) 
            prod *= wt;
          else 
            return 0;
        }
        return prod;
      }
      virtual void updateDocList(int numDocs) {
        intersectDocList(numDocs); // different from superclass.
      }
    };

    class BandNotQnode : public BeliefNode {
    public:
      BandNotQnode(double dbelief, double wt) : BeliefNode(wt, dbelief) {}
      virtual ~BandNotQnode() {}
      virtual double eval(const lemur::api::DocumentRep *dRep) const{
        double child1Wt;
        double child2Wt;
        // boolean_and_not consider only two children
        const QueryNode *qn;
        ch->startIteration();
        qn = ch->nextNode();
        child1Wt = qn->eval(dRep);
        qn = ch->nextNode();
        child2Wt = qn->eval(dRep);
        if(child2Wt > dw)
          return 0;
        else
          return (child1Wt * (1.0 - child2Wt));
      }
    };


    class FiltRejQnode : public BeliefNode {
    public:
      FiltRejQnode(double dbelief, double wt) : BeliefNode(wt, dbelief) {}
      virtual ~FiltRejQnode() {}
      virtual double eval(const lemur::api::DocumentRep *dRep) const{
        double child1Wt;
        double child2Wt;
        // filter_reject consider only two children
        const QueryNode *qn;
        ch->startIteration();
        qn = ch->nextNode();
        child1Wt = qn->eval(dRep);
        qn = ch->nextNode();
        child2Wt = qn->eval(dRep);
        if(child1Wt > dw && child2Wt <= dw)
          return child1Wt;
        else
          return dw;
      }
    };

    class FiltReqQnode : public BeliefNode {
    public:
      FiltReqQnode(double dbelief, double wt) : BeliefNode(wt, dbelief) {}
      virtual ~FiltReqQnode() {}
      virtual double eval(const lemur::api::DocumentRep *dRep) const{
        double child1Wt;
        double child2Wt;
        // filter_require consider only two children
        const QueryNode *qn;
        ch->startIteration();
        qn = ch->nextNode();
        child1Wt = qn->eval(dRep);
        qn = ch->nextNode();
        child2Wt = qn->eval(dRep);
        if(child1Wt > dw && child2Wt > dw)
          return child1Wt;
        else
          return dw;
      }
      virtual void updateDocList(int numDocs) {
        intersectDocList(numDocs); // different from superclass.
      }
    };

    class TermQnode : public ProxNode {
    public:
      TermQnode(int id, double weight) : ProxNode(id, weight) { }
      virtual ~TermQnode() {}
      virtual double eval(const lemur::api::DocumentRep *dRep) const{ 
        StructQryDocRep * myRep = (StructQryDocRep *)dRep;
        lemur::api::DOCID_T did = myRep->did;
        double freq = 0.0;
        if (nextDoc == did) {
          freq = (double)proxList->count();
          if (hasMoreProx()) {
            // advance the prox pointer.
            nextProxItem();
            nextDoc = proxList->id();
          } else {
            // No more prox entries.
            nextDoc = INT_MAX;
          }
        }
        return(myRep->termWeight(it, freq, dCnt));
      }
      virtual void copyDocList(int len, int tf, const lemur::api::DocInfoList *dl, int dc);
    };

    class OdnQNode : public ProxNode {
    public:
      OdnQNode(int size, double w, double d) : ProxNode(size, w, d){}
      virtual ~OdnQNode() {}
      virtual void updateDocList(int numDocs) {
        ProxNode::updateDocList(numDocs);   // use superclass method
        orderedProxList(numDocs);
      }
  
    private:
      void orderedProxList(int numDocs);
      bool foundOrderedProx(int bpos, int wsize, const QnList *cl, int ith);
    };

    class UwnQNode : public ProxNode {
    public:
      UwnQNode(int size, double w, double d) : ProxNode(size, w, d) {}
      virtual ~UwnQNode() {}
      virtual void updateDocList(int numDocs) {
        ProxNode::updateDocList(numDocs);   // use superclass method
        unorderedProxList(numDocs);
      }
    private:
      void unorderedProxList(int numDocs);
      bool findUnorderedWin(const QueryNode *cqn, QnList *cl, int winSize);
    };


    // fix to be WPARSUMN 
    class PassageQNode : public ProxNode {
    public:
      PassageQNode(int size, double w) : ProxNode(w){ winSize = size; }
      virtual ~PassageQNode() {}

      virtual double eval(const lemur::api::DocumentRep *dR) const{
        StructQryDocRep *dRep = (StructQryDocRep *)dR;
        double maxScore = 0;
        double score;      
        dRep->startPassageIteration(winSize);
        while(dRep->hasMorePassage()) {
          score = passageScore(dRep);
          if(score > maxScore) {
            maxScore = score;
          }
          dRep->nextPassage();
        }
        return maxScore;
      }

      virtual void updateDocList(int numDocs) {
        unionDocList(numDocs); // different from superclass.
        transformPassageOps();
      }
    private:
      double passageScore(const StructQryDocRep *dRep) const;
    };

    class SynQNode : public ProxNode {
    public:
      SynQNode(double w, double d) : ProxNode(w, d) {}
      virtual ~SynQNode() {}
      virtual void updateDocList(int numDocs) {
        unionDocList(numDocs); // different from superclass.
        synonymProxList();
      }
  
    private:
      void synonymProxList();
    };

    class PropQNode : public OdnQNode {
    public:
      PropQNode(double w, double d) : OdnQNode(0, w, d){}
      virtual ~PropQNode() {}
    };
  }
}

#endif

---