le débit des connexions Internet, la quantité de mémoires vives et la rapidité de calcul des ordinateurs individuels, s'accroissent exponentiellement selon la loi de Moore. Grosso-modo ils doublent tous les deux ans.
Pour répondre à une requète d'un utilisateur sur une base de données centralisée, il devient plus simple et plus libre, de transférer l'intégralité de la base de données. Et de faire calculer la requète par l'ordinateur de l'utilisateur, en exécutant des scripts mis à sa disposition, paramétrables par lui-même, assemblables par lui-même, voir programmables par lui-même.
La technologie la plus adaptée pour mettre en oeuvre ce principe actuellement, est l'utilisation d'un navigateur Internet tel que Mozilla Firefox, qui assure une très grande portabilité, et l'utilisation du javascript, du CSS, du DOM, voir du JQuery, et de la commande XMLHttpRequest propre aux applications AJAX. Par contre nous n'utiliserons pas le langage XML qui alourdie considérablement les données en textes brutes, mais plutôt le langage JSON et toute sorte d'autres langages texte adaptés à des types de données brutes spécifiques, que nous tenterons d'unifier.
Voici un script qui récupère dans la variable H.responseText une base de données sous format texte dont le chemin relatif est par exemple "base1.txt" :
var H = new XMLHttpRequest()
H.open("GET", "base1.txt", false)
H.send(null)
Aprés l'exécution de ce code javascript qui interroge le serveur de façon synchrone, la base de données se trouve mémorisée sous forme d'une string dans la variable H.responseText
Il n'y a pas en principe de limite à la taille des strings en javascript. Néanmoins il se peut qu'il y en est une, fonction du navigateur et de l'architecture de l'ordinateur. Il y 15 ans, la taille d'un méga-octet était considérée comme limite. Maintenant on télécharge par exemple 23 méga-octets de données texte sans problème comme suit :
On considère des bases de données séquentielles. Une base de données est une succession de caractères de taille mémoire fixe mémorisés dans un fichier. Une fois copiée en mémoire vive, le fichier est d'accès direct, c'est à dire que l'on peut lire directement un caractère si on connait son addresse.
On s'intéresse à la création de bases de données séquentielles. On entend par là, l'utilisation d'un langage spécifique pour mémoriser les données, qui soit plus complet, mais plus simple pour les structures simples et moins verbeux que le XML, en permettant une grande souplesse dans la factorisation de l'information et son organisation. On commence par des types de base particulièrement simples. Puis on concevra par induction logique, un langage de données définissant des types de données. Et ce langage devra être à la fois ; pratique, efficace pour les types de données simples, lisible par un humain et adaptable à toutes les situations. Cela nous ramène aux fondements des mathématiques et de l'informatique, à une relecture de l'algèbre et du dénombrement, à une sorte de nomenclature et d'algébrisation des algorithmes de base, car la disposition la plus adéquate des données est liée aux types d'algorithmes qui y sont appliqués.
Les moyens techniques actuels garantissent une quasi-infaillibilité des mécanismes de copies. On considère que la copie des bases de données se fait sans erreur. Autrement dit, on ne s'en préoccupe pas. On reporte sur d'autres systèmes le soin de vérifier la conformité exacte de la copie. Notez que ce principe ne contredit nullement l'exigence pour la base de données séquentielle brute d'être lisible par un humain. Mais, concernant les effets d'une altération fusse-t-elle minime sur une base de données séquentielle, on ne cherchera pas à en minorer ses effets. Néanmoins la question pourra se reposer en d'autres termes dans le mécanisme non pas de recopie, mais de création, ou des erreurs d'un autre niveau peuvent être faites.
La première structure à laquelle on pense, est la liste de mots, tel qu'on peut l'extraire par exemple d'un corpus d'une oeuvre littéraire, une succession de mots séparées par le caractère blanc et les caractères de ponctuation. Cette liste est la mieux représentée par une liste de strings ne possédant qu'un seul caractère de séparation qui est par défaut la virgule ou le caractère blanc ou encore le passage à la ligne '\n'. Les mots peuvent alors être par exemple des nombres écrits en décimal, ou encore n'importe quelle chaine de caractères (appelée aussi string) ne comprenant pas le caractère de séparation, et dont la signification n'est pas limitée. Cette première structure s'appelle une Liste de mots séparés par '\n'.
Si cette liste est un ensemble, c'est à dire si les mots doivent être distincts, alors on le précise avant, dans le nom de la structure. C'est un typage pré-défini, signifiant un ensemble de mots, une propriété que la liste de mots doit respecter, les mots doivent être distincts. Et il s'agit en faite d'un arrangement, c'est à dire un ensemble ordonné, car il est ordonné par l'ordre d'apparition des éléments dans la séquence. Cette seconde structure s'appelle donc un Arrangement de mots séparés par '\n' ou Liste de mots clés séparés par '\n'. En ajoutant ainsi le qualificatif clés, on précise que les mots doivent être distincts.
C'est alors qu'interviennent les différents mécanismes de manipulation des données, les différents algorithmes que l'on veut utiliser. La base de données étant copiée intégralement en mémoire, cette recopie peut être enrichie d'espaces mémoires supplémentaires pour des clés, indexes, flags, etc., et d'un pré-traitement en vue d'utilisation d'algorithmes spécifiques. Une des caractéristique de notre langage est qu'il intégrera dans les données elles-mêmes, des informations relatives à leur traitement informatique préconisé. Ces informations sont à la croisée des définitions de structures de données et des types d'algorithmes qui leurs conviennent.
Le caractère de séparation entre mots fait partie d'un protocole de bas niveau. Il correspond au dernier caractère du mot mais n'est pas compris dans le mot, c'est un caractère de fin de mot qui s'ajoute à la suite du mot, de tel sorte que le dernier mot d'une structure introduit encore ce caractère. De même, on introduit un autre caractère de séparation, qu'est celui entre structures. C'est le caractère de fin de structure, et cela peut être le même si on exclut la présence de mot vide, deux caractères de fin successifs signifiant alors la fin du dernier mot et la fin de la structure.
Si une structure est composée de mots de même taille et que cette taille est indiquée, alors il n'est pas nécessaire d'utiliser un caractère de fin de mot. De même si la taille d'une structure est donnée, il n'est pas nécessaire de mettre un caractère séparateur à la fin de la structure. Mais ces choix doivent être indiqués pour ne pas créer d'ambiguités. La structure peut même prévoir comment calculer le début et la fin de chacun de ses mots et ainsi encore ne pas utiliser de caractère de fin de mot. Ces cas se présentent lorsque de nombreux mots ne sont composés que d'un seul caractère, car alors le caractère de fin de mot double l'espace mémoire et complexifie inutilement la représentation de la donnée.
Remarquez qu'il n'y a pas de différence entre une donnée et un programme, un programme peut être une donnée et une donnée peut être un programme. C'est à cause de ce constat que l'analyse des base de données est similaire à l'analyse des ordinateurs.
On refait le même raisonnement de conception des ordinateurs en utilisant non pas l'octet comme unité de mémoire mais le caractère lisible par un humain, afin que les données puissent toujours être lisibles par un humain. Cela n'altert en rien le raisonnement, et le gain de mémoire et de rapidité que l'on peut obtenir en passant du caractère au bit, s'obtient par un mécanisme de compilation qui peut être traité plus tard.
L'aspect séquentiel de la mémoire est une caractéristique fondamentale de l'ordinateur contemporain, et davantage encore, de celle d'un flux d'informations simple. La mémoire de l'ordinateur se comporte comme une liste `M` de cases mémoire de même taille et contenant chacun un caractère. Chaque case mémoire de l'ordinateur est numérotée dans l'ordre, et ce numéro constitue l'adresse absolue du caractère mémorisé.
`M[0], M[1], M[2], M[3],...`
De la même façon que l'on peut concevoir ce qu'est un processus informatique, on conçoit ce qu'est un objet informatique comme étant un bloc mémoire constitué d'un seul morceau, ayant un devenir et interagissant avec d'autres objets, pouvant se déplacer et changer de taille au cours de sa vie dans la mémoire de l'ordinateur. Et on concevra des objects beaucoup plus complexes auxquels on donnera un autre nom que celui d'objet, qui seront composés de plusieurs objets disposés de façon non contigüe dans la mémoire de l'ordinateur.
La façon dont l'objet interagit avec les autres objets, et qui définie son comportement, constitue son type.
L'objet est dit de type statique s'il ne peut pas changer de type au cours de sa vie. Et il est dit de type dynamique dans le cas contraire. Le type de l'objet comprend une partie pré-définie qui n'est pas mémorisée ni référencée dans le bloc mémoire de l'objet, et une partie post-définie qui est mémorisé ou référencé dans le bloc mémoire de l'objet.
La partie pré-définie du type d'un objet ne peut pas changer au cours de la vie de l'objet. Car ce changement constiturait une information qu'il faudrait nécessairement transmettre à tous les acteurs pouvant interagire avec l'objet. Une telle transmission consommerait énormement de temps de calcul et constiturait un gaspillage démeusuré.
Parcontre la partie post-définie du type peut changer au cours de la vie de l'objet. Sauf si le type pré-défini l'interdit. Dans ce cas, il y a une partie de la mémoire de l'objet qui ne peut pas être changé, qui est figé, et qui constitue une partie statique du type de l'objet. Reste à savoir si cette restriction programmative est pertinente.
Tout ce qui est contenue dans le bloc mémoire et qui n'est pas une partie du type de l'objet, constitue la valeur de l'objet.
Les objets complexes contiennent des objects plus simples, appellés éléments, et qui sont disposés dans l'ordre de leur apparition dans le bloc mémoire contiguë de l'object. Le type de l'objet est appelé sa structure ou encore sa classe. Et par abstraction on parlera de structure pour désigner un object générique ayant cette structure. L'objet est en fait, une instanciation de sa structure ou de sa classe. L'object que l'on désignera sous forme d'une variable, évolue dans le temps et possède une vie en quelque sorte. Il interagit, se change et se déplace dans la mémoire de l'ordinateur avec les autres objets selon des règles comportementales décrites par son type.
L'objet a une adresse mémoire qui est l'adresse de son bloc contiguë de mémoire au sein de la mémoire séquentielle de l'ordinateur. C'est l'adresse du premier caractère du bloc. On appel cette adresse, l'adresse absolue. Et si l'objet se trouve être un élément d'un objet parent qui le contient, alors on considère une seconde addresse qui est l'adresse relative à cet objet parent.
On distingue deux genres d'objets, l'objet de taille invariante, qui restent de même taille tout au cours de sa vie, et que nous appellons modon, et l'objet de taille variable, qui peut changer de taille au cours de sa vie, et que nous appellons varon.
Les données supplémentaires à la liste d'éléments d'un objet, tel la partie post-définie de son type, sont placées dans une entête dont la taille est déterminé par le type, car c'est le moyen le plus pratique permettant d'accéder aux éléments en incrémentant l'adresse de la taille de l'entête, et aussi peuvent être placées dans les éventuels caractères de fin de l'élément. L'entête constitue alors lui-même un objet, ramenant l'objet parent à une liste d'objets sans entête. Et les caractères de fin d'élément ne sont pas sensés porter d'autre information que la fin de l'élément. S'il y avait nécessité, on ajouterais un objet à la fin de chaque élément, ce qui constiturait encore une liste d'éléments. La conclusion de ces deux remarques, est qu'un object est nécessairement une liste sans entête, d'éléments avec caractère de fin d'élément, ou bien une liste sans entête, d'éléments sans caractère de fin d'élément, mais dans ce cas le type de l'objet doit permettre de déterminer l'adresse de début et de fin de chaque élément.
La base de données transmise est le premier object qui englobe tous les autres objets relatifs aux données transmises. La base se présente sous forme d'une liste de caractères, et les caractères doivent tous avoir la même taille mémoire. Chaque caractère possède une adresse relative à la base de données. Le caractère suivant possède l'adresse suivante c'est à dire incrémentée de `1`. Un mot est une succession de caractères. Chaque mot possède une adresse, sous-entendu relative à la base de donnée qui le contient, qui est celle de son premier caractère. Chaque liste de mots possède une adresse qui est celle de son premier mot.
Et d'une manière générale, on conçoit ainsi une arborescence d'objets emboitées. Un objet contient une liste de sous-objets appellés éléments. Chaque objet à comme adresse, l'adresse de son premier élément, et c'est le type de l'objet qui précise comment accéder à ses éléments.
Etant donné une structure `S`, ou autrement dit, une chaine de caractères (appelée aussi une string), puisque tout objet se ramène à une chaine de caractères :
La base de données est transmie et mise en mémoire vives. Elle a pour object parent la mémoire de l'ordinateur.
Nous avons :
`#S(:n:) = #S + n`
`&S(:n:) = &S + n`
Parc contre, c'est le type de `S` qui nous permettra de calculer `#S[n]` et nous avons :
`&S[n] = &S + #S[n]`
Etant donné une liste de mots `L`, on note `L[0]` son premier mot, `L[1]` son second, `L[2]` son troisième, etc.. Les numéros `0, 1, 2`, ect. sont appellés des indexes. L'adresse absolue de `L[n]` se note `&L[n]`, tandis que l'adresse de `L[n]` relative à `L` se note `#L[n]`.
Si les mots contenus dans la liste `L` sont tous de même taille. L'adresse relative à `L` du mot `L[n]`, notée `#L[n]`, est égale à `n` fois la Taille des mots incrémentée de `1`.
`#L[n] = n**`(Taille_des_mots `+1)`
Cette troisième structure qui met en oeuvre l'adressage direct, s'appelle un Tableau de mots séparés par '\n', ou s'ils sont distincts, un Tableau de mots clés séparés par '\n'. Cette structure doit transmettre la taille des mots. On remarque que la taille des mots peut être calculée par un pré-traitement rapide en lisant le premier mot du tableau, et donc qu'il n'est pas nécessaire de la mémoriser dans la base. Il suffit seulement de transmettre l'information comme quoi cela est préconisé. Et cela se fait par l'indication du type de structure.
`#L[n] = n**(`Taille`(L[0])"+"1)`
L'accès à un élément d'un tableau est beaucoup plus rapide que l'accès à un élément d'une liste, c'est la raison pour laquel il est pertinent de distinguer ces deux types.
Le caractère de fin de mot '\n' sépare les éléments appartenant à une structures. Il devient pertinent de vouloir s'en débarasser dans le seul cas d'un tableau de mots où la taille des mots est réduite à un seul caractère. Car, en effet, dans ce cas, la présence inutile de ce caractère de fin de mots va doubler la taille du tableau. Dans les autres cas, on laisse ce caractère de fin de mot. Ce nous amène à la quatrième structure que nous appellons un Tableau de caractères, ou si les caractères sont distincts, un Tableau de caractères clés.
---- 22 février 2018 ----
Le tableau a comme inconvénient d'imposer une taille égale à chacun de ses éléments ce qui occasionne un gaspillage de mémoire qui peut être gigantesque. Pour remédier à cela, on utilise l'adressage indirect, c'est à dire un premier adressage qui retourne une adresse permettant un second adressage. Il y a donc deux tableaux, un tableaux `T` d'adresses, appellé tableau d'indexes, suivie d'un tableau de caractères qui correspond à la liste de mots `L` oté de son premier mot qui est `T`. Comme on veut que tout soit lisible par un humain, les adresses sont écrites en nombres décimaux en commençant si nécessaire par des caractères blancs, car ils doivent tous avoir le même nombre de caractères. Pour accéder au mots `L[n]`, on effectue un adressage indirecte :
`&L=&T`
`L[0]=T`
`#L[n]=T[n] = L[0][n]`
On remarque alors que `T` peut être calculé par un pré-traitement rapide et donc qu'il n'est pas nécessaire de le mémoriser dans la base. Il suffit seulement de transmettre l'information comme quoi cela est préconisé. Et cela se fait par l'indication du type de structure. Cette sixième structure s'appelle par exemple une Liste de mots indexés. Toute liste de mots peut devenir une liste de mots indexés. Le qualificatif "indexé" préconise la constitution d'un tableau d'indexes pour cette suite. Les mots étant de taille variable et donc non réduit à un seul caractère, l'évition du caractère de fin de mots n'apporte pas grand chose. Aussi on le maintient. Exemple :
pomme
chat
rue
elephant
---- 21 février 2017 ----
L'opération inverse qui consiste à partir d'un mot, de retrouver ses indexes dans une liste `L` de mots ou de constater qu'il n'y est pas, peut nécessiter de relire la liste en entier ce qui occasionne une perte de temps importante. Pour trouver plus rapidement les indexes d'un mot dans une liste de mots, ou la certitude que ce mot n'y appartient pas, on utilise une fonction `f` de hachage, un tableau `H` de hachage et une liste `L` de listes d'indexe de mots dans la liste `L`.
---- 11 février 2018 ----
Cela consiste à hacher le mot à l'aide d'une fonction de hachage pour en produire un entier compris entre `0` et `N` où `N` est le nombre d'éléments de la table de hachage. Lorsque la fonction de hachage est injective, deux mots ne peuvent pas avoir le même code de hachage.
`"mot"_1"≠""mot"_2 => f("mot"_1)"≠"f("mot"_2)`
La table de hachage contient alors les adresses des mots en fonction de leur code de hachage.
Le mot est reconnue si T`[H[f("mot")]] = "mot"`
L'algorithme prend en entré un mot `"mot"`, calcul son code de hachage `f("mot")` puis calcul l'adresse `H[f("mot")]` puis compare s'il s'agit du mots concerné `T[H[f("mot")]] = "mot"`. Si le mot n'est pas le bon, c'est qu'il n'appartient pas à `T`.
Mais dans la réalité la fonction de hachage n'est pas injective. Il arrive que plusieurs mots aient le même code de hachage. Dans ce cas on indique dans le tableau de hachage non pas l'adresse d'un mot directement, mais l'adresse d'une liste contenant plusieurs adresses de mots, les mots qui ont ce même code de hachage, et on laisse le soin à l'arlgorithme de comparer ces différents mots.
Le mot est reconnue si `T[L[H[f("mot")]][0]] = "mot"_1`
Le mot est reconnue si `T[L[H[f("mot")]][1]] = "mot"_2`
Le mot est reconnue si `T[L[H[f("mot")]][2]] = "mot"_3`
etc..
L'algorithme prend en entré un mot `"mot"`, calcul son code de hachage `f("mot")` puis calcul l'adresse `H[f("mot")]` de la liste des adresses de mots de même codes de hachage, puis calcul l'adresse du premier mot de même code de hachage L[H[f("mot")]][0]et vérifie si c'est le bon mot `T[L[H[f("mot")]][0]] = "mot"` Puis si ce n'est pas le bon mot alors calcul l'adresse du mot suivant de même code de hachage `L(H[f("mot")])(1)` et vérifie si c'est le bon mot `T[L[H[f("mot")]][1]] = "mot"`, etc.. Si le mot n'est jamais le bon, c'est qu'il n'appartient pas à `T`.
L'opération inverse qui consiste à partir d'un mot, de retrouver son adresse dans un tableau `T` de mots clés ou de constater qu'il n'y est pas, peut nécessiter de relire le tableau en entier ce qui occasionne une perte de temps importante. Pour trouver plus rapidement l'adresse d'un mot dans un tableau de mots, ou la certitude que ce mot n'y appartient pas, on utilise une fonction `f` de hachage, un tableau `H` de hachage et une liste `L` de listes d'adresses de mots dans le tableau `T`.
Cela consiste à hacher le mot à l'aide d'une fonction de hachage pour en produire un entier compris entre `0` et `N` où `N` est le nombre d'éléments de la table de hachage. Lorsque la fonction de hachage est injective, deux mots ne peuvent pas avoir le même code de hachage.
`"mot"_1"≠""mot"_2 => f("mot"_1)"≠"f("mot"_2)`
La table de hachage contient alors les adresses des mots en fonction de leur code de hachage.
Le mot est reconnue si T`[H[f("mot")]] = "mot"`
L'algorithme prend en entré un mot `"mot"`, calcul son code de hachage `f("mot")` puis calcul l'adresse `H[f("mot")]` puis compare s'il s'agit du mots concerné `T[H[f("mot")]] = "mot"`. Si le mot n'est pas le bon, c'est qu'il n'appartient pas à `T`.
Mais dans la réalité la fonction de hachage n'est pas injective. Il arrive que plusieurs mots aient le même code de hachage. Dans ce cas on indique dans le tableau de hachage non pas l'adresse d'un mot directement, mais l'adresse d'une liste contenant plusieurs adresses de mots, les mots qui ont ce même code de hachage, et on laisse le soin à l'arlgorithme de comparer ces différents mots.
Le mot est reconnue si `T[L[H[f("mot")]][0]] = "mot"_1`
Le mot est reconnue si `T[L[H[f("mot")]][1]] = "mot"_2`
Le mot est reconnue si `T[L[H[f("mot")]][2]] = "mot"_3`
etc..
L'algorithme prend en entré un mot `"mot"`, calcul son code de hachage `f("mot")` puis calcul l'adresse `H[f("mot")]` de la liste des adresses de mots de même codes de hachage, puis calcul l'adresse du premier mot de même code de hachage L[H[f("mot")]][0]et vérifie si c'est le bon mot `T[L[H[f("mot")]][0]] = "mot"` Puis si ce n'est pas le bon mot alors calcul l'adresse du mot suivant de même code de hachage `L(H[f("mot")])(1)` et vérifie si c'est le bon mot `T[L[H[f("mot")]][1]] = "mot"`, etc.. Si le mot n'est jamais le bon, c'est qu'il n'appartient pas à `T`.
---- 10 février 2018 ----
On ajoute à la liste de mots des informations supplémentaires permettant de les retrouver plus rapidement.
est d'ajouter l'adresse du mot suivant
Etant donné un tel ensemble on peut vouloir constituer une liste de sous-ensembles. Et il existe une représentation binaire des sous-ensembles. Un sous-ensemble d'un ensemble de `n` éléments peut être défini par un `n`-uplet de booléens. Délors, soit la définition est posée à priori comme par exemple une liste de sous-ensembles de `E`, qui est donc une liste de strings où les strings sont une succession de 0 ou 1 en nombre égal à la taille de `E`. Ou bien elle est posée à posteriori comme par exemple une liste mixte accéptant des sous-ensembles de `E`, qui est donc une liste de strings où certaines strings comprendront une déclaration de type précisant qu'il s'agit d'un sous-ensemble de `E` et une valeur qui sera une succession de 0 ou 1 en nombre égal à la taille de `E`.
Mais de façon plus exacte, il faudra parler de sous-arrangement car ils héritent de l'ordre de l'arrangement initial.
Puis, il faut encore être plus précis en introduisant les opérations informatiques permises de faite par l'organisation des données.
Un tableau où chaque données est accessible par un adressage indirecte grace à un indexe est un objet en terme informatique beaucoup plus riche qu'un arrangement. Cette troisième structure s'appelle un Tableau de strings. l'inconvennient d'un tel tableau c'est que chaque string doit avoir la même taille. Et si on doit ajouter une donnée plus grande dans le tableau, on doit alors réécrire tout le tableau en agrandissant la taille de toutes ses strings, ce qui occasionne un gaspillage de temps, et aussi un gaspillage de la mémoire.
La donnée étant une succession de caractères, mémorisée dans un fichier en accès séquentiel (qu'il soit en mémoire vive ou non), chaque caractère possède une adresse physique, et chaque string possède une adresse physique, celle de son premier caractère.
De même, un arrangement pour lequel chaque élément contiendrait l'adresse de l'élément suivant est un plus car il n'est pas nécessaire de parcourir tout l'élément pour aller sur le suivant. Un tel arrangement s'appelle un Arrangement chainé avant. De même il peut être chainé arrière ou encore les deux à la fois au quel cas on parlera simplement d'Arrangement chainé. Et la même chose se produit pour une liste. L'avantage de cette autre organisation et que la structure peut se complexifier en adressant comme élément suivant, des éléments se trouvant ailleurs. On parlera d'arrangement chainé mêlé.
Quant au sous-ensemble binaire, s'ils sont quasi-vide, il convient de changer la représentation et de passer à une représentation en liste croissante des indexes ou liste des sauts d'indexe. Par exemple considérons l'arrangement `(: "toto", "titi", "tata", "ga", "bu", "zo", "un", "deux", "trois", "hypo", "basta" :)`
Le sous ensemble binaire 00100001001 est égal à `(: "tata", "deux", "basta" :)` et se met sous forme de liste de sauts d'indexe `2,5,3`. Néanmoins cette rprésentation avec sauts d'indexe perd de son intérêt si les indexes ne s'applique pas à un tableau mais seulement à un arrangement qui peut être même pas chainé.
----- 5 février 2018 -----
---------------------
Un élément est une construction dans un langage d'opérateurs, qui sert de référence pour désigner toute chose que nous créons.
Le premier type d'assemblage que l'on conçoit sont les listes d'éléments. Elles correspondent à un paradigme de programmation qu'est l'ordonnencement de liens. On distingue `4` types de liste de la plus particulière à la plus générale :
Le 1-graphe enraciné connexe par la racine englobe dans sa généralité, l'arbre enraciné partagé, l'arbre enraciné et la séquence.
Mais il est possible de généraliser encore en enlevant la restriction qui interdit un lien de désigner une feuille de l'arbre de construction qui serait encore un lien. On obtient alors un objet quelque peu hétéroclite dont nous n'avons pas encore utilité ni nom à lui donner. La recherche des mécanismes premiers de structuration se fait en parallèle avec la recheche des mécanismes premiers de programmation.
Les listes sont construites par des programmes. Un programme est par principe de taille finie, mais il peut énumérer une liste infinie. Dans le cas des listes finies, la liste elle-même constitue un programme qui l'énumére.
La liste vide `( )` constitue un élément particulier.
----------------------
des bases de données simples conistant en un tableau de donnée avec les intitulés de chaque colonne et les intitulés de chaque ligne.
composées d'un unique tableau. Chaque ligne correspond à l'enregistrement d'un object mémorisé dans la base de donnée. Chaque colonne correspond à un attribut devant être renseigné.
On considère deux types de colonnes, les colonnes contenant au plus 8 valeurs distinctes, et les colonnes texte contenant au plus une quarantaine de caractères.
On se propose de programmer un interface web en javascript qui permet d'importer de telles bases de données, de présenter un filtre modifiable par l'utilisateur qui lui donne des informations quantitatives pour chaque attribut relativement au filtrage en cours, et qui extrait les enregistrements selon le filtrage en cours.
Une telle base peut être écrite en JSON sous forme d'un tableau de données. Chaque ligne correspond à un enregistrement, un élément de la base. Chaque colonne corespond à un attribut, un champ.
On complète les données par des métadonnées, écrite également en JSON sous forme d'une liste de listes, qui décrit chaque champs du tableau de données c'est à dire chaque attribut.
Considérons par exemple une base de donnée sur les plantes tel qu'on peut en trouver dans de nombreux ouvrages. Une telle base doit comprendre une description des attribus que l'on regroupe en un tableau appelé metadata, et les données proprement dites que l'on regroupe dans un tableau appelé data. La base regroupant les metadata et les data s'écrit en JSON comme suit :
{ "metadata" : [ ["Zone_1","c1",3,"Oui","Non"], ["Zone_2","c1",2,"Oui","Non"], ["Zone_3","c1",2,"Oui","Non"], ["Vent","c2",2,"Oui","Non"], ["Embruns","c2",2,"Oui","Non"], ["Gel_précoce","c2",2,"Oui","Non"], ["Couleur","c3",5,"Rouge","Bleu","Jaune","Violet","Marron"], ["Aprovision","c4",3,"Facile","Assez facile", "Difficile"], ["Plantation","c5",4,"Fin d'été","Hiver","Printemps"], ["Nom","c0",0], ["Famille","c0",0], ["Ordre","c0",0] ], "data" : [ [1,0,1,1,0,1,2,3,2,"toto","ito","ga"], [1,1,0,0,1,0,3,1,1,"tarbi","ito","ga"], [1,1,1,1,0,1,4,3,1,"troto","ito","ga"], [2,1,1,0,0,1,2,2,2,"tarasci","grono","ga"], [0,0,0,1,0,1,0,1,0,"tarasgane","grono","ga"], [1,0,1,0,1,0,1,2,2,"tarapec","grono","ga"], [1,1,1,1,0,1,1,0,0,"hypac","esoles","boc"], [2,0,0,0,0,0,0,0,1,"hyphil","esoles","boc"], [2,0,0,1,1,0,2,2,0,"hypotalis","cariol","boc"], [0,1,1,0,1,0,4,2,0,"hypocampt","cariol","boc"], [1,1,0,1,1,1,3,1,0,"hypofont","cantris","boc"], [1,0,0,0,0,1,4,1,1,"hypofrate","cantris","boc"] ] }
La liste "metadata" énumère pour chaque champ :
Le tableau data comprend pour chaque enregistrement et pour chaque attribut, sa valeur codée en partant de 0, c'est à dire une valeur comprise entre 0 et le nombre de réponses possibles moins un, ou bien si c'est un champ texte, le texte en question.
Une grande quantité de données peut être transmise et mémorisée de façons dense si elle tient dans une successions d'attribut au nombre de réponse distinctes possibles réduites (ici entre 2 et 8). Cette représentation des champs à nombre de réponse réduite permet d'effectuer un codage dense et de compresser considérablement cette partie de la base dite sélective, par une sorte de code barre pour chaque enregistrement. Ce code barre est un nombre en base adapté à chaque taille de champs, qui peut être exprimé en la base 26+26+10 = 62 si on prend en compte les lettres minuscules, les lettres majuscules et les chiffres.
Pour compresser les champs textes au grand nombre de réponses distinctes, d'autres procédés devront être mis en oeuvre qui sort du cadre de ce projet.
Les débits réseaux et la rapidité de calcul s'accroissant régulièrement d'un facteur constant (loi de Nielson et loi de Moore), il devient plus simple de télécharger la base complète et d'effectuer les recherches avec des instructions javascript mise à disposition des utilisateurs via un interface web.
Dans l'entête de la page web qui servira d'interface, afin que les caractères accentués apparaissent normalement, on précise l'encodage des caractères comme suit
<meta http-equiv="content-type" content="text/html; charset=iso-8859-1" />
Puis le script contient une fonction getH( ) qui récupère la base de donnée JSON à une adresse devant se trouver sur le même domaine internet qui est ici une adresse relative "test.text" :
La variable Z précise le codage des caractères utilisés iso-8859-1.
L'instruction H.setRequestHeader('Content-type', Z) précise que ce codage est utilisé pour les messages envoyés.
L'instruction H.overrideMimeType(Z) précise que ce codage est utilisé pour les messages reçus.