searchengine.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 <climits>

#include <unicode/regex.h>

#include "phrasehunter/searchengine.h"
#include "phrasehunter/tokenizer.h"
#include "phrasehunter/token.h"

using namespace SQLitePP;

namespace PhraseHunter {

SearchEngine::SearchEngine(SqliteDB& db):
    m_db(db), SPECIAL_CHARACTERS(".[{()\\*+?|^$")
{}

TokenVector SearchEngine::searchRegexToken(schma::UnicodePtr re) const
{
    UErrorCode c = U_ZERO_ERROR;    
    RegexMatcher matcher(*re, 0, c);
    
    std::vector<TokenPtr> results;
    std::string cutRe = cutRegex(schma::toStdString(re));
    Statement::Pointer s;
    
    if(cutRe.empty()) {
        s = m_db.statement("SELECT word FROM tokens ORDER BY word");
    }
    else {
        s = m_db.statement("SELECT word FROM tokens WHERE word LIKE ? ORDER BY word");
        s->bindArgs(cutRe + "%");
    }
    
    for(ResultIterator ri = s->query(); ri.hasMoreRows(); ri.next()){
        matcher.reset(*(ri.get<schma::UnicodePtr>(0)));
        
        if(matcher.find())
            results.push_back(searchToken(ri.get<schma::UnicodePtr>(0)));
    }
    return results;
}

struct LengthComparator
{
    bool operator()(const TokenVector& a, const TokenVector& o) const
    {
        return a.size() < o.size();
    }
};

struct TokenVectorValidator
{
    bool operator()(const TokenVector& a) const
    {
        return !a.empty();
    }
};

struct TokenVectorMerger
{
    TokenVector operator()(const TokenVector& v1, const TokenVector& v2) const
    {
        TokenVector results;
        results.reserve(v1.size() * v2.size());
        for(TokenVector::const_iterator i=v1.begin(); i!=v1.end(); ++i) {
            for(TokenVector::const_iterator j=v2.begin(); j!=v2.end(); ++j) {
                TokenPtr phrase = Phrase::mergeTokens(*i, *j);
                if (*phrase)
                    results.push_back(phrase);
            }
        }
        return results;
    }
};

TokenVector SearchEngine::searchPhrasalRegex(schma::UnicodePtr re) const
{
    typedef std::vector<TokenVector> TokenMatrix;
    
    static TokenVector emptyVector;
    schma::UnicodeVector regexes = schma::splitString(schma::toStdString(re));
    
    if(regexes.size() < 1) {
        return emptyVector;
    }
    
    TokenMatrix matrix;
    matrix.reserve(regexes.size());
    for(schma::UnicodeVector::const_iterator i = regexes.begin(); i != regexes.end(); ++i) {
        matrix.push_back(searchRegexToken(*i));
        if(matrix.back().empty()) {
            return emptyVector;
        }
    }
    return combine(TokenMatrix::const_iterator(matrix.begin()),
                   TokenMatrix::const_iterator(matrix.end()),
                   LengthComparator(),
                   TokenVectorMerger(),
                   TokenVectorValidator());
}

std::string SearchEngine::cutRegex(const std::string& re) const
{
    std::string::size_type firstSpecial = re.find_first_of(SPECIAL_CHARACTERS);
    std::string result(re, 0, firstSpecial);
    if(re[firstSpecial] == '\\') {
        for(unsigned int i = static_cast<unsigned int>(firstSpecial);
            i < re.length(); ++i) {
            if(SPECIAL_CHARACTERS.find(re[i+1]) == std::string::npos)
                return result;
            result.push_back(re[i+1]);
            ++i;
        }
    }
    return result;
}

TokenPtr SearchEngine::searchToken(schma::UnicodePtr stringtoken) const
{
    Statement::Pointer getID = m_db.cachedStatement("SELECT id FROM tokens WHERE word = ?");
    getID->bindArgs(stringtoken);
      
    ResultIterator ri = getID->query();
    return (ri.hasMoreRows())
        ? CorpusToken::loadFromCorpus(stringtoken, ri.get<int>(0), m_db)
        : EmptyToken::instance();
}

struct OccurrenceComparator 
{
    bool operator()(const TokenPtr& a, const TokenPtr& o) const
    {
        return a->corpusFrequency() < o->corpusFrequency();
    }
};

struct TokenValidator
{
    bool operator()(const TokenPtr& a) const  
    {
        return *a;
    }
};

struct TokenMerger
{
    TokenPtr operator()(const TokenPtr& a, const TokenPtr& o) const
    {
        return Phrase::mergeTokens(a, o);
    }
};

TokenPtr SearchEngine::searchPhrase(schma::UnicodePtr search_string) const
{
    Tokenizer t(new StringInput(schma::toStdString(search_string)));
    if(!t.hasMoreTokens()) 
        return EmptyToken::instance();
    bool whitespace;
    
    TokenVector tokens;

    while(t.hasMoreTokens()) {
        TokenPtr token = searchToken(schma::UnicodePtr(new UnicodeString(t.nextUnencodedToken(&whitespace).c_str())));
        if(!*token) {
            return token;
        }
        tokens.push_back(token);
    }
    return combine(TokenVector::const_iterator(tokens.begin()),
                   TokenVector::const_iterator(tokens.end()),
                   OccurrenceComparator(),
                   TokenMerger(),
                   TokenValidator());
    
}

template<typename _RandomAccessIt,
         typename _MinChooser,
         typename _Merger,
         typename _Validator>
typename _RandomAccessIt::value_type SearchEngine::combine(_RandomAccessIt begin,
                                                           _RandomAccessIt end,
                                                           _MinChooser better,
                                                           _Merger merge,
                                                           _Validator valid) const
{
    _RandomAccessIt start = 
        std::min_element(begin, end, better);
    
    _RandomAccessIt left = start - 1;
    _RandomAccessIt right = start + 1;
    
    typename _RandomAccessIt::value_type aggregate = *start;
    
    for(int i = 0; valid(aggregate) && i < (end - begin) - 1; ++i) {
        if (left < begin || 
            (right != end &&
             better(*right, *left))) {
            aggregate = merge(aggregate, *right);
            ++right;
        } else {
            aggregate = merge(*left, aggregate);
            --left;
        }
    }
    return aggregate;
}

}

---