developer_guide.rst

Developer Guide

Ce guide explique les structures de données et les algorithmes utilisés dans Velocity Search Engine.

Structures de données principales

• InvertedIndex : dictionnaire {terme: PostingList}
• PostingList : liste compressée d'IDs de documents
• Trie : dictionnaire de termes pour recherche rapide
• DocumentManager : gestion des métadonnées et mapping ID → titre

Algorithmes clés

• Indexation :

  • Tokenisation, stemming, suppression des stop words
  • Ajout des termes à l'index inversé
  • Compression des posting lists (variable byte, delta encoding)

• Recherche :

  • Intersection des posting lists
  • Calcul du score TF-IDF/BM25
  • Classement des résultats

• Compression :

  • Variable byte encoding pour les entiers
  • Delta encoding pour séquences d'IDs

Exemple d'algorithme :

def variable_byte_encode(numbers):
    bytes_list = []
    for number in numbers:
        bytes = []
        while True:
            bytes.insert(0, number % 128)
            if number < 128:
                break
            number //= 128
        bytes[-1] += 128  # Set stop bit
        bytes_list.extend(bytes)
    return bytes_list

Optimisations

• Utilisation de multiprocessing pour l'indexation
• Trie pour lookup rapide
• Sauvegarde incrémentale sur disque

Pour plus de détails, voir les modules : - src/indexer/inverted_index.py - src/indexer/trie.py - src/preprocessor/text_preprocessor.py - src/ranker/bm25_ranker.py