statistics.cpp

Go to the documentation of this file.

/*
  Phrasehunter - index and query text corpora
  Copyright (C) 2006  Torsten Marek (shlomme@gmx.de) &
  Armin Schmidt (armin.sch@gmail.com)
  
  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., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
*/

#include "phrasehunter/statistics.h"
#include "phrasehunter/contextreader.h"
#include "phrasehunter/token.h"
#include "phrasehunter/tokencontext.h"

#include <algorithm>
#include <map>
#include <iterator>
#include <cmath>
#include <set>
#include <tr1/unordered_set>
#include <vector>

#include <iostream>

using namespace SQLitePP;

namespace PhraseHunter {

struct RankingCriterion
{
    bool operator() (TokenPtr t1, TokenPtr t2) const
    {
        return t1->corpusFrequency() > t2->corpusFrequency();
    }
};

/**
   Functor for comparing size of two containers, e.g. instead of lexical compare
   with operator<()
*/
template<typename T>
struct Smaller
{
    bool operator() (const T& c1, const T& c2 ) const
    {
        return c1.size() < c2.size();
    }
};

StatisticsEngine::StatisticsEngine(SearchEngine* searcher, ContextReader* reader, SqliteDB& db)
    : m_searcher(searcher),
      m_reader(reader),
      m_db(db)
{
    m_sizeOfSampleSpace = 0;
    m_numberOfTypes = 0;

    Statement::Pointer stmt = m_db.statement("select word, frequency from tokens");
    unsigned long totalLength = 0; //total length of all word tokens (not types)
    for(ResultIterator ri = stmt->query(); ri.hasMoreRows(); ri.next()) {
        totalLength += ri.get<schma::UnicodePtr>(0)->length() * ri.get<int>(1);
        
        m_sizeOfSampleSpace += ri.get<int>(1);
        ++m_numberOfTypes;
    }
    m_averageWordLength = static_cast<double>(totalLength) / static_cast<double>(m_sizeOfSampleSpace);

    m_contextWindow = static_cast<unsigned>(m_averageWordLength*3);

    Statement::Pointer numDoc = m_db.statement("select sum(length(id))/4 from docs");
    ResultIterator ri = numDoc->query();
    m_numberOfDocuments = ri.get<int>(0);
}

unsigned int StatisticsEngine::rank(TokenPtr t) const
{
    if (m_searcher == NULL)
        return 0;
    
    Statement::Pointer smt = m_db.statement("select rank from tokens where id = ?");
    ResultIterator ri = (*smt)
        .bindArg(t->id())
        .query();
    return ri.get<int>(0);
}

unsigned int StatisticsEngine::overallFrequency(TokenPtr t) const 
{
    if (m_searcher == NULL)
        return 0;
    
    Statement::Pointer smt = m_db.statement("select frequency from tokens where id = ?");
    ResultIterator ri = (*smt)
        .bindArg(t->id())
        .query();
    return ri.get<int>(0);
}

unsigned int StatisticsEngine::frequency_x_intersection_y(TokenPtr x, TokenPtr y) const
{
    unsigned comm_occs = 0;
    const OccurrenceMap& shorter = std::min(x->allOccurrences(), y->allOccurrences(),
                                            Smaller<OccurrenceMap>());
    const OccurrenceMap& longer = std::max(x->allOccurrences(), y->allOccurrences(),
                                           Smaller<OccurrenceMap>());
    
    for(OccurrenceMap::const_iterator shorter_it = shorter.begin();
        shorter_it != shorter.end(); ++shorter_it) {
        
        OccurrenceMap::const_iterator longer_it = longer.find(shorter_it->first);
        
        if (longer_it != longer.end()) {
            comm_occs += freq_intersection_in_doc(shorter_it->second, longer_it->second);
        }
    }
    return comm_occs;
}

unsigned StatisticsEngine::freq_intersection_in_doc(const PositionList& p1, const PositionList& p2) const 
{
    const PositionList& shorter = min(p1, p2, Smaller<PositionList>());
    const PositionList& longer = max(p1, p2, Smaller<PositionList>());

    unsigned comm_occs = 0;
    PositionList::const_iterator i1, i2;
    for (PositionList::const_iterator it = shorter.begin();
         it != shorter.end(); ++it) {
        
        if (static_cast<int>(*it) - static_cast<int>(m_contextWindow) > 0)
            i1 = std::lower_bound(longer.begin(), longer.end(), *it-m_contextWindow);
        else
            i1 = longer.begin();

        i2 = std::lower_bound(longer.begin(), longer.end(), *it+m_contextWindow);

        if (i2 != i1)
            comm_occs += i2 - i1;  
    }
    return comm_occs;
}

double StatisticsEngine::relative_frequency(TokenPtr x) const 
{
    if (getSizeOfSampleSpace())
        return overallFrequency(x)/static_cast<double>(getSizeOfSampleSpace());
    else
        return 0.0;
}

double StatisticsEngine::mle_x_intersection_y(TokenPtr x, TokenPtr y) const 
{
    if (getSizeOfSampleSpace())
        return static_cast<double>(frequency_x_intersection_y(x,y))/static_cast<double>(getSizeOfSampleSpace());
    else
        return 0.0;
}

double StatisticsEngine::mle_x_given_y(TokenPtr x, TokenPtr y) const 
{
    double p_of_x = relative_frequency(y);
    if (p_of_x)
        return mle_x_intersection_y(x,y)/p_of_x;
    else
        return 0.0;
}

std::vector<TokenPtr> StatisticsEngine::getCandidates(TokenPtr x) const
{    
    OccurrenceMap occs = x->allOccurrences();

    std::set<TokenID> tokenIds;
    
    Statement::Pointer getWordsInRange = m_db.statement("SELECT wordid FROM occurrences WHERE docID = ? and inrange(positions, ?, ?)");

    for(OccurrenceMap::const_iterator itOccs = occs.begin(); itOccs != occs.end(); ++itOccs) {
        
        for(PositionList::const_iterator itPos=itOccs->second.begin();
            itPos!=itOccs->second.end(); ++itPos) {
            
            std::pair<IdxPos, IdxPos> bounds = contextBounds(*itPos, getContextSize());

            ResultIterator ri = (*getWordsInRange)
                .bindArgs(itOccs->first, bounds.first, bounds.second)
                .query();
            
            while(ri.hasMoreRows()) {
                tokenIds.insert(ri.get<int>(0));
            }            
        }
    }

    std::vector<TokenPtr> candidateStrings;
    
    Statement::Pointer getTokenString = m_db.statement("SELECT word FROM tokens WHERE id = ?");
    
    for(std::set<TokenID>::const_iterator tokIt = tokenIds.begin();
        tokIt != tokenIds.end();
        ++tokIt) {
        
        ResultIterator ri = (*getTokenString)
            .bindArg(*tokIt)
            .query();
        
        if(ri.hasMoreRows() && strlen(ri.get<const char*>(0)) > 3)
            candidateStrings.push_back(CorpusToken::loadFromCorpus(ri.get<schma::UnicodePtr>(0), *tokIt, m_db));        
    }
    return candidateStrings;
}

std::pair<IdxPos, IdxPos> StatisticsEngine::contextBounds(IdxPos position, int numWords) const
{
    int lower = static_cast<int>(position) - (numWords*static_cast<int>(m_averageWordLength)+numWords);
    if (lower < 0)
        lower = 0;
    IdxPos upper = position + (numWords*static_cast<int>(m_averageWordLength)+numWords);
    return std::make_pair(static_cast<IdxPos>(lower), upper);
}

class DocSet 
{
    std::set<DocID> docSet;
public:
    void operator()(TokenPtr t)
    {
        std::vector<DocID> docs = t->documentIDs();
        docSet.insert(docs.begin(), docs.end());
    }
    operator unsigned int() const
    {
        return docSet.size();
    }
};

unsigned int StatisticsEngine::sizeOfDocSet(const std::vector<TokenPtr>& tokens)
{
    return std::for_each(tokens.begin(), tokens.end(), DocSet());
}

std::map<schma::UnicodePtr, int> StatisticsEngine::getContextVector(TokenPtr t, int contextlen) const 
{
    std::map<schma::UnicodePtr, int> results;
    if (m_searcher == NULL)
        return results;

    typedef std::vector<TokenContextPtr> contextVector;
    contextVector stringContext = m_reader->context(t, static_cast<int>(contextlen*m_averageWordLength));

    for (contextVector::const_iterator it = stringContext.begin();
         it != stringContext.end(); ++it) {
        
        schma::UnicodePtr left = (*it)->leftContext();
        IdxPos spaceIdx = left->indexOf(' ');
        schma::UnicodePtr cutContext(new UnicodeString);
        left->extract(spaceIdx, left->length()-spaceIdx, *cutContext);
      
        if (cutContext->length() <= 3) //ignore stopwords - naive approach
            continue;

        int freq = ++results[cutContext];
      
        results.insert(std::make_pair(cutContext, freq));
    }
    return results;
}
    
double StatisticsEngine::mutual_information(const TokenPtr& token, const std::map<schma::UnicodePtr,int>& contextVec, schma::UnicodePtr context) const 
{
    TokenPtr contextToken;
    if (token->tokenString()->indexOf(' ') != -1)
        contextToken = m_searcher->searchPhrase(context);
    else
        contextToken = m_searcher->searchToken(context);
    
    if (contextToken == NULL)
        return 0;
    
    double frequency_w_in_c;
    
    std::map<schma::UnicodePtr,int>::const_iterator found = contextVec.find(context);
    if (found != contextVec.end())
        frequency_w_in_c = found->second;
    else
        frequency_w_in_c = 0;
        
    double numerator = frequency_w_in_c / static_cast<double>(getSizeOfSampleSpace());
    double denominator = relative_frequency(token)*relative_frequency(contextToken);
    
    double discounting_factor =
        frequency_w_in_c/(frequency_w_in_c+1) 
        * 
        (std::min(overallFrequency(token), overallFrequency(contextToken))
         /
         (std::min(overallFrequency(token), overallFrequency(contextToken))+1));
    
    return discounting_factor*(numerator/denominator);
}

double StatisticsEngine::similarity(TokenPtr t1, TokenPtr t2, int contextlen) const
{
    typedef std::map<schma::UnicodePtr,int> UnicodeFreqMap;
    
    UnicodeFreqMap c1 = getContextVector(t1, contextlen);
    UnicodeFreqMap c2 = getContextVector(t2, contextlen);
    
    UnicodeFreqMap* shorter = c1.size() <= c2.size() ? &c1 : &c2;
    double numerator_sum = 0;
    for (UnicodeFreqMap::const_iterator it = shorter->begin();
         it != shorter->end(); ++it) {
        double mi = mutual_information(t1, *shorter, it->first);
        numerator_sum += mi * mi;
    }
    
    double denominator_first_sum = 0;
    
    for (UnicodeFreqMap::const_iterator it = c1.begin(); it != c1.end(); ++it)
        denominator_first_sum += mutual_information(t1,c1,it->first);

    double denominator_second_sum = 0;
    for (UnicodeFreqMap::const_iterator it = c2.begin(); it != c2.end(); ++it)
        denominator_first_sum += mutual_information(t2,c2,it->first);
    
    return numerator_sum/std::sqrt((denominator_first_sum * denominator_first_sum)
                                   *
                                   (denominator_second_sum * denominator_second_sum));
}

std::multimap<double,TokenPtr> StatisticsEngine::similarTokens(TokenPtr t, int contextlen) const
{
    std::multimap<double,TokenPtr> sorted;

    if (t == NULL)
        return sorted;
    
    TokenVector candidates = getCandidates(t);
    
    for (TokenVector::const_iterator it = candidates.begin();
         it != candidates.end(); ++it) {
        sorted.insert(std::make_pair(similarity(t, *it, contextlen), *it));
    }
    return sorted;
}

}

---