CodeS-SourceS
Rechercher un code, un tuto, une réponse

Implementation d un index inversé

Septembre 2017


Utilisation d'un index inversé



Introduction


Ce tutorial décrit l'utilisation de Mifluz . Mifluz est un index inversé du projet GNU.

Cette librairie se contente de sauvegarder des data dans une base basée sur un arbre binaire. Le résultat des recherche est donc extrêmement rapide.

L'indexer


La première étape est de créer un algorithme pour extraire et compter les mots d un fichier texte.

Avant de commencer à charger le fichier, nous avons besoin d'un modèle de données, puis de règle de filtrage de caractères.

La structure de données de sauvegarde:
struct wordCounting{ 
 string word; 
 int nb; 
 string filename; 
}; 


Le filtre des caractères:
char charFilter (char pin)
{
        pin=tolower(pin);
        if (pin == 'é' || pin=='è' || pin=='ê' || pin =='ë' )
                return 'e';
        if (pin == 'à' || pin=='â' || pin =='ä')
                return 'a';
        if (pin == 'î' || pin=='ï'  )
                return 'i';
        if (pin == 'ô' || pin=='ö'  )
                return 'o';
        if (pin == 'ù' || pin=='û'  || pin=='ü')
                return 'u';
        if (pin == ',' || pin=='"'  || pin=='\''|| pin==';'|| pin=='!'|| pin=='?'|| pin=='$'|| pin=='&'|| pin==')'|| pin=='('|| pin=='.'|| pin==':' || pin=='-'|| pin=='_' || pin=='--' || pin==' * ' || pin=='[' || pin=='/' )
                return ' ';
        return pin;
}


Puis le filtrage d'un mot entier:
string stringFilter (string &pin)
{
        stringstream ret;
        for (unsigned int i=0;i<pin.length();i++)
        {
                ret<<charFilter (pin.at(i));
        }
        return ret.str();
}


Avec ces règles de filtrage et ce modèle de données, nous pouvons commencer à filtrer notre fichier:
map<string,wordCounting *> parseWords (string &pFile)
{
        map<string,wordCounting *> list;
        char c;
        ifstream is;
        is.open (pFile.c_str());        // open file
        string wordstream;
        map<string,wordCounting *>::iterator it;
        while (is.good())     // loop while extraction from file is possible
        {       is.get(c);       // get character from file
                c=charFilter(c);
                if (c==' '||c=='\n' || c=='\t' || c=='\0')
                {       if (!wordstream.empty())
                        {
                              wordCounting *res;
                              it=list.find(wordstream);
                              if( it == list.end() ) {
                                   res = new wordCounting();
                                   res->word=wordstream;
                                   res->nb=0;
                                   res->filename=pFile;
                                   list.insert( make_pair( wordstream, res ) ); 
                              }
                              else
                                   res=it->second;
                              res->nb++;
                        }
                        wordstream="";
                }
                else
                {
                        wordstream+=c;
                }
        }
        is.close();
        return list;
}


Une fois le fichier parsé, il faut commencer à entrer dans Mifluz

Enregistrement dans Mifluz


Mifluz a besoin d un modèle de données pour sauvegarder les datas
Le premier élément du modèle est toujours le nom qui sera recherché, puis on peut ajouter des paramètres. Dans notre exemple, nous ajoutons un Ranking et un identifiant correspondant au fichier référent.
static ConfigDefaults defaultsInd *  = {
   { "wordlist_wordkey_description","Word 30/Rank 15/Location 15"},
  { 0 }
};


Il nous reste a transformer notre modèle indexer en notre nouveau modèle Mifluz
static map file_list; 
void addList(map<string,wordCounting *> &list,WordList *words)
{
        map::iterator iteror;
        map<string,wordCounting *>::iterator iter;
        for( iter = list.begin(); iter != list.end(); iter++ ) {
                bool isOnList=false;
                int idFile=-100;
                for (iteror=file_list.begin();iteror!=file_list.end();iteror++)
                {
                        if (iteror->second==iter->second->filename)
                        {
                                idFile=iteror->first;
                                isOnList=true;
                                break;
                        }
                }
                if (!isOnList)
                {
                   idFile=file_list.size()+1;
                   file_list.insert(make_pair(idFile,iter->second->filename));
                }
                stringstream el;
                el<second->word<<" "<second->nb<<" "<Override(words->Word(el.str().c_str()));
        }
}

La création d un environnement Mifluz


void action(WordContext* context)
{
  WordList *words = context->List();
  words->Open("words2.db", O_RDWR|O_TRUNC);
  string file = "file1.test";
  map<string,wordCounting *> list=parseWords (file);
  //..... on peut effectuer ces recherche
  words->Close();
  delete words;
}

La recherche


La recherche est extrêmement simple:
  List *results = words->FindWord("which");
  WordReference *match;
  for(results->Start_Get(); (match = (WordReference*)results->Get_Next());) {
    map::iterator iteror;
    iteror = file_list.find(match->Key().Get(2));
    cout <<"on File ="<second<<" with nb words="<<match->Key().Get(1) <<endl;
  }


Le code complet peut être trouvé à l'adresse:
http://cvs.savannah.gnu.org/viewvc/mifluz/examples/example1.cc?root=mifluz&view=markup

Le site de mifluz: http://www.gnu.org/software/mifluz/

A voir également

Publié par sefidom.
Ce document intitulé «  Implementation d un index inversé  » issu de CodeS-SourceS (codes-sources.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.
Ajouter un commentaire

Commentaires

Donnez votre avis
Les bienfaits de l'option "whole program optimisation" du compilateur c++ de visual studio 2002 et supérieur
Les autotools : autoconf, automake et libtool