---

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.cs.cmu.edu/~lemur/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"

// 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; }
  QueryNode * getNode(int j){QueryNode *qn = qnList[j]; return qn; }
  int size(){return qnList.size();}
  void push_back(QueryNode *qn){qnList.push_back(qn);}
  QueryNode *popNode() { 
    QueryNode *qn = qnList[i]; 
    qnList[i++] = NULL;
    return qn;  
  }
private:
  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);
  }
  QnList *children() { return ch;}
  void setChildren(QnList *cl) {ch = cl;}
  int id() { return it;}
  double weight() { 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, DocInfoList *dl, int dc) {
  }
  virtual void updateDocList(int numDocs) = 0;
  virtual double eval(DocumentRep *dRep) = 0;

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

  int dCnt;
  bool *dList;
  int 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(DocumentRep *dRep) {
    return proximityScore(dRep, dw);
  }
  virtual void updateDocList(int numDocs) {
    intersectDocList(numDocs);   
  }

protected:
  int winSize;
private:
  double proximityScore(DocumentRep *dR, double defaultScore) {
    StructQryDocRep *dRep = (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(DocumentRep *dRep) {
    double sum = 0;
    QueryNode *qn;
    ch->startIteration();
    while(ch->hasMore()) {
      qn = ch->nextNode();
      sum += qn->eval(dRep);
    }
    return sum/entries;
  }
};

class WsumQnode : public BeliefNode {
public:
  WsumQnode(double w) : BeliefNode(w) {}
  virtual ~WsumQnode() {}
  virtual double eval(DocumentRep *dRep) {
    double sum = 0;
    double total_wt = 0;
    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(DocumentRep *dRep) {
    double prod = 1;
    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(DocumentRep *dRep) {
    double prod = 1.0;
    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(DocumentRep *dRep) {
    // inverting the belief in the only child node
    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(DocumentRep *dRep) {
    double mx = dw;
    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(DocumentRep *dRep) {
    double prod = 1.0;
    QueryNode *qn;
    double wt;
    StructQryDocRep * myRep = (StructQryDocRep *)dRep;
    int 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(DocumentRep *dRep) {
    double child1Wt;
    double child2Wt;
    // boolean_and_not consider only two children
    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(DocumentRep *dRep) {
    double child1Wt;
    double child2Wt;
    // filter_reject consider only two children
    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(DocumentRep *dRep) {
    double child1Wt;
    double child2Wt;
    // filter_require consider only two children
    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(DocumentRep *dRep) { 
    StructQryDocRep * myRep = (StructQryDocRep *)dRep;
    int 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, 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, 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(QueryNode *cqn, QnList *cl, int winSize);
};


// fix to be WPARSUMN 
// This is a prox operator with embedded belief operators spliced out.
class PassageQNode : public ProxNode {
public:
  PassageQNode(int size, double w) : ProxNode(w){ winSize = size; }
  virtual ~PassageQNode() {}

  virtual double eval(DocumentRep *dR) {
    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(StructQryDocRep *dRep);
};

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

---