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

Extraction de données statiques (suite)

Nous avons vu comment:

  1. Indexer un document
  2. Trouvez toutes les lignes qui contiennent une information donnée

Rappels des étapes précédantes

Indexer les numéros et adresses des lignes

  1. On représente une ligne par son index dans le fichier (son numéro de ligne). Son adresse et sa position en byte dans le fichier..
  2. Un fichier index_ligne qui donne la correspondance entre le numéro de la ligne et l’adresse dans le fichier.

Ces deux informations permet de récupérer les informations d’un numéro de ligne en deux lectures de fichiers de taille bornées. Il existe beaucoup de solution pour coder ces informations dans le fichier index_ligne. La plus économe consiste à utiliser un encodage de taille fixe pour les addresses en binaires.

Cette indexation peut être effectué en une passe.

Indexer un champ précis

Indexer un champ précis consiste pour chaque valeur possible d’être capable de trouver la liste des lignes où cette valeur aparaît. Pour ce faire plusieurs solutions existent. La suivante est relativement simple:

  1. En une passe sur les données, on récupère la liste des couples (valeurs,numéro de lignes).
  2. On trie cette liste par valeurs afin que les numéros de lignes qui possèdent la même valeur soit regroupé.
  3. La liste des numéros de lignes peut être encoder concisément dans un fichier binaires et pour chaque valeur un fichier (triée en valeur) où on associe la valeur à l’indice de début et de fin dans cette liste où elle apparaît.

Une recherche des lignes ayant une certaines valeurs nécessite alors de faire une dichotomie sur le fichier triée pour récupérer les indices de début et de fin puis on récupère les lignes par une lecture au fichier contenant les numéros de lignes. Au total, cela nécessite un nombre d’accès qui est en \(\mathcal{O}(\log(k))\) où \(k\) est le nombre de valeurs différentes.

Bonus: Compter et échantilloner

Le fichier contenant la liste des valeurs et la listes des indices contient également le nombre d’occurrence de la valeur dans le fichier initial. Il est donc possible en lisant ce fichier d’avoir une bonne idée de la répartition statistiques des valeurs, sans avoir a regarder dans le gros fichier.

Exercice:

Télécharger le fichier ici (40mo, 1000 000 lignes). Indexer ce fichier par année et par type de documents (les deux dernier champs).

Objectifs suivant: rechercher complexe avec indexations

Les données ont souvent un type. Par exemple, une date, un texte, une valeur entière, un prix, ect …. Il est utile pour faire de l’analyse de données d’être capable de faire de la recherche dans des indexes adaptés à ces types là. Par exemple, pour des valeurs entières, être capable de faire des recherches d’intervals (trouver toutes les lignes dans la date est comprise entre le 3 juin et le 6 octobre). Pour ce faire, l’indexation que nous avons proposer est insuffisant: il faut des indexes adaptés.

Pour les vacances (facultatifs pour les parcours Statistiques, obliatoire pour les WebAnalystes):

Proposez, en justifiant, des mécanismes d’indexations pour les données entières (pour faire de la recherche d’interval) et des données textuelles (trouver toutes les lignes où le mot “Choucroute” apparaît).


Compiled the: dim. 07 janv. 2024 23:19:21 CET