Entrepôts de données, année 2019

Extraction de données statiques: indexation des données

Dans ce cours, l’utilisation du terminal est très fortement recommandé.

Pour simplifier, vous pouvez télécharger une version du listing de données encore plus courte que la précédente, afin de pouvoir faire des testes plus rapidement ici.

L’objectif de ce TD est d’apprendre à indexer les données statiques afin d’accélérer l’extraction de contenus. L’essentiel du TD est à faire en Python

Vous aurez besoin dans la suite de documentation sur la gestion des fichiers en Python. Vous trouverez cette documentation ici.

1. À l’aide d’un script en Python, déterminer la longueur maximal d’une ligne dans le fichier ̀scihub. Vous stockerais ce nombre sous la forme d’une variable globale longueur_max.

Deux version possibles. Une version fonctionnelle. N’hésitez pas à aller lire la documentation sur la fonction map.

path = '/path/to/file/scihub'
with open(path) as f:
    longueur_max = max(map(lambda ligne:len(ligne), f)) 
print(longueur_max)

Une version plus classique avec une boucle FOR.

path = '/path/to/file/scihub'
with open(path) as f:
    longueur_max = 0
    for ligne in f:
        longueur_max = max(len(ligne), longueur_max) 
print(longueur_max)

2. Créer un fichier index_ligne en une lecture du fichier qui contient pour chaque ligne leur position précise dans le fichier. Par exemple, si la 18 ème ligne commence à la position 23493, vous ajouter un ligne dans le fichier index_ligne qui contient 18\t2393 (18 séparé par une tabulation de 2393).

Pour cette question, il faut faire atteion à ne pas charger en mémoire tous le fichier pour éviter une erreur d’allocation de mémoire. Cela peut arriver sans qu’on fasse attention si avec les fonctions readlines par exemple.

path_scihub = '/path/to/file/scihub'
path_index = '/path/to/file/index_ligne'

with open(path_scihub) as f, open(path_index,"w") as g: 
# attention à ouvrir le fichier en écriture avec l'option "w"
    current_index = 0
    count_line = 0
    for line in f:
        g.write("{}\t{}\n".format(count_line, current_index)) 
        # documentez vous sur le fonctionnement de format. 
        count_line += 1
        current_index += len(line)

Remarquez qu’on pourrait faire un fichier plus petit en écrivant pas count_line qui est redondant avec les séparateurs \n.

La version binaire est bien plus efficace en terme d’espace disque prise par le fichier d’index et en terme d’efficacité de code pour la fonction de la question suivante. (Voire question 4)

3. Créer une fonction recupere_ligne(n) qui regarde dans le fichier index_ligne la position de la ligne n, lit le fichier scihub à cette position un nombre longueur_max de caractères et retourne la ligne.

Il y a deux stratégies pour recupere_ligne: tout stocker en mémoire (si le fichier tient en mémoire) ou faire un parcourt séquentiel du fichier d’index. Le premier point est mieux quand on doit appeler recupere_ligne souvent et qu’on ne charge le fichier qu’une seule fois en mémoire. Ici on va faire une version simple et pas efficace. Pour une version optimiser, voire la question 4.

def recupere_ligne(n):
    with open(path_index) as g:
        iter_index = map(lambda e:e.split(), g) #construit un itérateur mais ne charge rien en mémoire
        index = {int(e):int(f) for e,f in iter_index} #on pourrait prendre une liste plutôt.
        # la construction de l'index est très couteux ici. 
    address = index[n] #on gaspille index ce qui est dommage ...
    with open(path_scihub) as f:
        f.seek(address)
        ligne = f.read(longueur_max)
    return ligne.split("\n")[0]

Attention, le code précédant ne marche pas bien. Par exemple, si on prend le fichier scihub.shorter.shorter.tab alors si on teste avec recupere_ligne(0) on obtient bien la première ligne mais recupere_ligne(1) retourne la chaîne de caractère vide. Le problème vient de la gestion des accents et de la fonction f.seek qui positionne le curseur à une adresse en byte et non en longueur de caractères. Or la première ligne du fichier contient la chaîne de caractère “Bogotá” qui est de longueur 5 mais dont l’encodage en byte est de longueur 6. En effet les caractères unicode avec accent sont codé sur deux bytes.

Pour corriger ce problème, il suffit de modifier la création du fichier d’index comme suit:

path_scihub = '/path/to/file/scihub'
path_index = '/path/to/file/index_ligne'

with open(path_scihub) as f, open(path_index,"w") as g: 
# attention à ouvrir le fichier en écriture avec l'option "w"
    current_index = 0
    count_line = 0
    for line in f:
        g.write("{}\t{}\n".format(count_line, current_index)) 
        # documentez vous sur le fonctionnement de format. 
        count_line += 1
        current_index += len(line.encode()) 
        # on mesure l'adresse en byte en convertissant la chaine en bytes.

Sur un disque dure efficace (SSD), on récupère une ligne en quelque centaines µs. La reconstruction de l’index prend par contre de l’ordre de 100ms. Il est donc impératif de le stocker une fois pour toute s’il tient en mémoire.

4. Il est possible d’améliorer les performances de recupere_ligne en changeant le fichier index_ligne et en utilisant un codage en binaire. Proposer une solution pour cela. Comparer les performances de la nouvelle version et de l’ancienne.

On va améliorer les fonctions précédentes en codant en binaire et en permettant un accès direct sur disque à l’adresse de la ligne. Pour ce faire, il nous faut la valeur maximal que prend une ligne pour savoir combien de bytes réserver par adresse. La dernière adresse pour scihub.shorter.shorted.tab à la valeur 14848641 qui nécessite 3 bytes pour être encodé. Pour savoir le nombre de bytes il faut avoir en tête qu’un byte code pour 8 bits et donc que le nombre de bytes nécessaire pour un entier n provient de la formule: \(\lfloor\frac{\log(n)}{8*\log(2)} \rfloor + 1\) où \(\lfloor x \rfloor\) est la partie entière de \(x\).

path_scihub = '/path/to/file/scihub'
path_index = '/path/to/file/index_ligne_bin'

with open(path_scihub) as f, open(path_index,"wb") as g: 
# attention à ouvrir le fichier en écriture avec l'option "w"
    current_index = 0
    for line in f:
        g.write(current_index.to_bytes(3,"little")) 
        count_line += 1
        current_index += len(line.encode()) 
        # on mesure l'adresse en byte en convertissant la chaine en bytes.

On modifie la fonction recupere_ligne en prenant en compte le fait qu’il est facile d’accéder directement à l’information de la ligne \(n\) dans l’index binaire, puisqu’elle est stocker à l’adresse \(3n\). Cela vient du faire que chaque entier prend une place fixe dans le fichier.

def recupere_ligne(n):
    with open(path_index,"rb") as g:
        g.seek(3*n)
        bin_address = g.read(3)
    address = int.from_bytes(bin_address, "little")
    with open(path_scihub) as f:
        f.seek(address)
        ligne = f.read(longueur_max)
    return ligne.split("\n")[0]

Les performances sont du même ordre (~100µs de plus) que dans la question 3 sans avoir besoin de mémoire.

Il faut faire très attention néanmoins car les disques dure peuvent mettre en cache des données et biaiser les benchmarks. La place sur disque de l’index binaire est par contre bien meilleur. À tester sur les plus gros fichier pour une meilleur idée des performances.

Indexer les données géographiques

5. Créer un fichier position_geographique qui contient une ligne pour chaque couples pays,villes. Créer une fonction charge_geographie qui retourne un dictionnaire index_geographie associant un couple (pays,ville) associe la position du couple dans le fichier position_geographique.

6. Créer un fichier temp_position_geographique, qui pour chaque ligne du fichier scihub ajoute une ligne contenant index_geographie[(pays,ville)]\tn_ligne où n_ligne est le numéro de la ligne dans le fichier scihub.

7. À l’aide de la commande sort, triez le fichier temp_position_geographique en utilisant la valeur numérique du premier champ de temp_position_geographique (option -n).

8. À l’aide d’un script python et du fichier trié temp_position_geographique , créer un fichier index_geographie où la ligne numéro n contient la liste des lignes du fichier scihub contenant le couple (pays,ville) où ce couple vérifie n = index_geographie[(pays,ville)]. Autrement dit, si dans temp_position_geographie vous avez les lignes
   n,k1\nn,k2\n....\nn,kp où \n est le symbole de saut de ligne,
   alors vous ajoutez à la ligne numéro n de index_geographie la ligne k1\t k2\t .... kp.

9. Modifier le fichier position_geographique pour rajouter la position dans le fichier du début et de fin de la ligne n.

10. Créez une fonction recherche_geographie(pays, ville) qui retourne les lignes contenant (pays,ville) dans scihub à ’laide des fichiers position_geographie et index_geographie.

Devoir maison noté (à rendre pour le 10/02)

1. Pour avoir la moyenne:

Adapter le TD précédant pour indexer le champ du fichier contenant des url. Il faut donc créer des fichiers contenants les informations nécessaires à la réalisation d’une fonction recherche_url(url).

Attention, il pourra être nécessaire de faire une indexation de l’index.

2. Pour avoir une bonne note:

Réaliser une indexation de la date par mois et par jours.

3. Pour avoir 20:

Proposer une analyse détailler et éclairer des performances de votre système d’indexation.

Compiled the: mer. 08 janv. 2025 11:51:31 CET