---

StructQueryRep.hpp

Go to the documentation of this file.

/*==========================================================================
 * Copyright (c) 2002 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
*/

#ifndef _STRUCTQUERYREP_HPP
#define _STRUCTQUERYREP_HPP

#include "RetrievalMethod.hpp"
#include "Document.hpp"
#include "DocumentRep.hpp"
#include "StructQryDocRep.hpp"
#include "IndexedReal.hpp"
#include "Index.hpp"
#include "Counter.hpp"
#include "WeightedIDSet.hpp"
#include "FreqVector.hpp"
#include "ScoreAccumulator.hpp"

//------------------------------------------------------------
//      Abstract Interface for Structured Query 
//------------------------------------------------------------

class StructQuery : public Query {
public:
  StructQuery(Document &doc) : d(doc) {}
  virtual ~StructQuery() {}

  virtual char *id() { return d.getID();}
  virtual void startTermIteration() { d.startTermIteration();}
  virtual bool hasMore() { return d.hasMore();}
  virtual TokenTerm *nextTerm() { return d.nextTerm();}
protected:
  Document &d;
};



//------------------------------------------------------------
//      Abstract Interface for StructQuery Representation 
//------------------------------------------------------------

// forward declaration
class QueryNode;

class QnList {
public:
  QnList() {}
  virtual ~QnList();
  virtual void startIteration() {  i=0; }
  virtual bool hasMore() {  return (i < qnList.size()); }
  virtual QueryNode * nextNode(){QueryNode *qn=qnList[i++]; return qn; }
  virtual QueryNode * getNode(int i){QueryNode *qn=qnList[i]; return qn; }
  virtual int size(){return qnList.size();}
  virtual void push_back(QueryNode *qn){qnList.push_back(qn);}

protected:
  int i;
  vector<QueryNode *> qnList;
};

class ProxInfo {
public: 
  ProxInfo() : id(0),count(0),size(0),nextPos(0),posList(NULL),next(NULL) {}
  ~ProxInfo() {
    delete [](posList);
  }
  int id;
  int count;
  int size;
  int nextPos;
  int *posList;
  ProxInfo *next;
};

class QueryNode {
public:
  QueryNode(int id, double weight) : 
    w(weight),it(id),ch(NULL),entries(0),nextDoc(0),dCnt(0),
    proxList(NULL),dList(NULL) {}
  QueryNode() : w(1),it(0),ch(NULL),entries(0),nextDoc(0),dCnt(0),
                proxList(NULL),dList(NULL){}
  QueryNode(double weight) : w(weight),it(0),ch(NULL),entries(0),
                             nextDoc(0),dCnt(0),proxList(NULL),dList(NULL) {}
  ~QueryNode() {
    delete[](dList);
    while(proxList) {
      ProxInfo *prx=proxList->next;
      delete (proxList);
      proxList = prx;
    }
    delete(ch);
  }
  virtual QnList *children() { return ch;}
  virtual int id() { return it;}
  virtual double eval(DocumentRep *dRep) = 0;
  virtual double weight() { return w; }
  // update weight
  virtual void setWeight(double wt) { w=wt; }
  virtual double proximityScore(DocumentRep *dR, double defaultScore) {
    StructQryDocRep *dRep = (StructQryDocRep *)dR;
    int tf=0;
    double score;
    ProxInfo *prx;
    InvFPIndex &ind = dRep->ind;
    if(dRep->did < nextDoc) {
      return defaultScore;
    }
    while(dRep->did > nextDoc) {
      prx=proxList->next;
      delete (proxList);
      proxList = prx;
      if(!proxList)
        nextDoc = ind.docCount();
      else
        nextDoc = proxList->id;
    }
    if(dRep->did == nextDoc && proxList) {
      double idf = dRep->computeIdfScore(dCnt);
      if(ind.docLength(dRep->did) == dRep->size) {
        // compute proximity score for whole doc
        tf = proxList->count;
      } else {
        // compute proximity score for a passage
        for(int k=0; k<proxList->count; k++)
          if(proxList->posList[k]> dRep->start && 
             proxList->posList[k]<=dRep->end)
            tf++;
      }
      score = dRep->beliefScore(tf, idf);
      prx = proxList->next;
      delete (proxList);
      proxList = prx;
      if(!proxList)
        nextDoc = ind.docCount();
      else
        nextDoc = proxList->id;
    } else
      score = defaultScore;
    return score;
  }
  int dCnt;
  bool *dList;
  QnList *ch;
  ProxInfo * proxList;
  int entries;
  int nextDoc;

protected:
  int it;
  double w; 
};

class StructQueryRep : public QueryRep {
public:
  StructQueryRep(StructQuery &qry, InvFPIndex &dbIndex, double dbelief=0);

  virtual ~StructQueryRep() {
    delete(TopNode);
  }
  virtual QnList * getChildren(StructQuery &qry);
  virtual QnList * getWeightedChildren(StructQuery &qry);
  virtual QnList * getProxChildren(StructQuery &qry);
  virtual QueryNode * getQryNode(StructQuery &qry, TokenTerm *tok, double w);
  virtual QueryNode * getProxQryNode(StructQuery &qry, TokenTerm *tok);
  virtual QueryNode * topnode() {return TopNode;}
  virtual void setTopnode(QueryNode *qn) {TopNode=qn;}
  virtual void copyDocList(DocInfoList *dl, QueryNode *qn);
  virtual void unionDocList(QueryNode *qn);
  virtual void intersectDocList(QueryNode *qn);
  virtual void termOffsetList(QueryNode *qn, int did);
  virtual bool foundOrderedProx(int bpos, int wsize, QnList *cl, int ith);
  virtual void orderedProxList(QueryNode *qn);
  virtual void unorderedProxList(QueryNode *qn);
  virtual bool findUnorderedWin(QueryNode *cqn, QnList *cl, int winSize);
  virtual void synonymProxList(QueryNode *qn);

protected:
  QueryNode *TopNode;
  QueryNode *qStack[100];
  int TopqStack;
  double dw;
  InvFPIndex &ind;
};

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

class WsumQnode : public QueryNode {
public:
  WsumQnode(double 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 * (double) 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 QueryNode {
public:
  AndQnode(double dbelief, double wt) : dw(dbelief), QueryNode(wt) {}
  virtual ~AndQnode() {}
  virtual double eval(DocumentRep *dRep) {
    double prod=1;
    QueryNode *qn;
    double wt;
    ch->startIteration();
    while(ch->hasMore()) {
      qn =ch->nextNode();
      wt = (double) qn->eval(dRep);
      if(wt > dw)
        prod *= wt;
      else
        prod *= dw;
    }
    return prod;
  }
protected:
  double dw;
};

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

class NotQnode : public QueryNode {
public:
  NotQnode(double dbelief, double wt) : dw(dbelief), QueryNode(wt) {}
  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-(double) qn->eval(dRep));
  }
protected:
  double dw;
};

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

};

class BandQnode : public QueryNode {
public:
  BandQnode(double dbelief, double w) : dw(dbelief), QueryNode(w) {}
  virtual ~BandQnode() {}
  virtual double eval(DocumentRep *dRep) {
    double prod=1;
    QueryNode *qn;
    double wt;
    ch->startIteration();
    while(ch->hasMore()) {
      qn =ch->nextNode();
      wt = (double) qn->eval(dRep);
      if(wt > dw) 
        prod *= wt;
      else 
        return 0;
    }
    return prod;
  }
protected:
  double dw;
};

class BandNotQnode : public QueryNode {
public:
  BandNotQnode(double dbelief, double wt) : dw(dbelief), QueryNode(wt) {}
  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 = (double) qn->eval(dRep);
    qn =ch->nextNode();
    child2Wt = (double) qn->eval(dRep);
    if(child2Wt > dw)
      return 0;
    else
      return (child1Wt * (1.0-child2Wt));
  }
protected:
  double dw;

};


class FiltRejQnode : public QueryNode {
public:
  FiltRejQnode(double dbelief, double wt) : dw(dbelief), QueryNode(wt) {}
  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 = (double) qn->eval(dRep);
    qn =ch->nextNode();
    child2Wt = (double) qn->eval(dRep);
    if(child1Wt > dw && child2Wt <= dw)
      return child1Wt;
    else
      return dw;
  }
protected:
  double dw;

};


class FiltReqQnode : public QueryNode {
public:
  FiltReqQnode(double dbelief, double wt) : dw(dbelief), QueryNode(wt) {}
  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 = (double) qn->eval(dRep);
    qn =ch->nextNode();
    child2Wt = (double) qn->eval(dRep);
    if(child1Wt > dw && child2Wt > dw)
      return child1Wt;
    else
      return dw;
  }
protected:
  double dw;

};

class TermQnode : public QueryNode {
public:
  TermQnode(int id, double weight) : QueryNode(id, weight) {}
  virtual ~TermQnode() {}
  virtual double eval(DocumentRep *dRep) { 
    return(dRep->termWeight(it, NULL));
  }
};

class OdnQNode : public QueryNode {
public:
  OdnQNode(int size, double w, double d): winSize(size), dw(d), 
                                          QueryNode(w) {}
  virtual ~OdnQNode() {}
  virtual double eval(DocumentRep *dRep) {
    return proximityScore(dRep, dw);
  }
  int winSize;
protected:
  double dw;
};

class UwnQNode : public QueryNode {
public:
  UwnQNode(int size, double w, double d): winSize(size), dw(d), 
                                          QueryNode(w) {}
  virtual ~UwnQNode() {}
  virtual double eval(DocumentRep *dRep) {
    return proximityScore(dRep, dw);
  }
  int winSize;
protected:
  double dw;
};


class PassageQNode : public QueryNode {
public:
  PassageQNode(int size, double w) : winSize(size), QueryNode(w) {}
  virtual ~PassageQNode() {}
  virtual double eval(DocumentRep *dR) {
    StructQryDocRep *dRep= (StructQryDocRep *)dR;
    int dl = dRep->docEnd;
    dRep->increment = winSize/2;
    dRep->startPassageIteration();
    while(dRep->hasMorePassage()) {
      StructQryDocRep *psgRep= 
        new StructQryDocRep(dRep->did,dRep->ind,dRep->idf,
                            dRep->start,dRep->end);
      double score=0;
      QueryNode *child;
      ch->startIteration();
      while(ch->hasMore()) {
        child =ch->nextNode();
        score +=(double) child->eval(psgRep);
      }
      delete psgRep;
      if(score > dRep->maxScore) {
        dRep->maxScore=score;
        dRep->offset=dRep->start;
      }
      dRep->nextPassage();
    }
    return dRep->maxScore/(double)winSize;
  }
protected:
  int winSize;
};


class SynQNode : public QueryNode {
public:
  SynQNode(double w, double d) : dw(d), QueryNode(w) {}
  virtual ~SynQNode() {}
  virtual double eval(DocumentRep *dRep) {
    return proximityScore(dRep, dw);
  }
protected:
  double dw;
};

#endif /* _STRUCTQUERYREP_HPP */

---