Voir la source de Création de la version 0.1

{{navigation|icone=Méthodologie.png|Méthodologie|{{PAGENAME}}}}
[[Catégorie:Historique]]
{{note|Cet article a été élaboré à partir d'un e-mail envoyé sur la [http://if-gpl.insa-lyon.fr/cgi-bin/mailman/listinfo/dvorak-fr/ liste de diffusion] par [[Utilisateur:Crako|Nicolas Chartier]].}}

Un autre mail à rallonge pour présenter plusieurs points :
* rappeler comment la [[version 0.1]] a été générée ;
* quels sont les points sur lesquels on peut jouer et quels sont ceux sur lesquels il n'est pas forcément nécessaire de le faire (du moins dans l'immédiat).

Je vais essayer d'être le plus précis possible afin de pouvoir détecter assez rapidement les points qui ont été faits par consensus à l'époque, ceux que j'ai choisi de façon arbitraire (que ce soit purement arbitraire, ou un minimum réfléchi), ceux qui j'ai choisi après retour sur les premières dispositions générées et essai de ces dispositions, etc. (bon en fait, après rédaction du mail, je me rends compte que je sais plus trop distinguer précisément tous les cas, donc il faudrait vérifier les mails fin 2004 - début 2005).

== Première étape : le corpus ==

J'ai testé plusieurs corpus proposés : celui de Thomas Tempé, et d'autres créés de mon coté à base de mails, logs IRC, extrait de code source en tout genre.

Pour la partie mail j'avais enlevé tout ce qui était typiquement lié au mail (adresse mail, suppression des passages cités, signatures...).

Pour la partie IRC, idem (limiter aux éléments de type message, suppression des références aux pseudonymes qui sont en général obtenu par complétion).

Pour la partie code source, je les avait séparé en deux parties :
* la partie texte (commentaires, zone de texte des rapports fait en LaTeX, zone de texte des pages HTML)
* la partie code (bin le reste...)

Au final, ça s'est averé assez fastidieux, et pas assez volumineux, donc quite à prendre le même principe que le corpus élaboré par Thomas, j'ai simplement pris son corpus...

J'ai alors séparé son corpus en deux parties :
* la partie texte
* la partie code source

La partie texte n'a pas eu de traitement supplémentaire, la partie code source en a eu une. En effet, la partie texte contient des symboles utilisés en programmation, et la partie code source contient des symboles utilisés en français courant. Donc l'idée que j'ai eu à ce moment là, c'est que la partie code source ne doit pas influencer les statistiques des symboles utilisés aussi en français, principalement dans la ponctuation.

Par exemple, on utilise beaucoup ; et . en programmation, donc je n'ai pas tenu compte des statistiques de ; et de . dans le corpus « code source » pour les placer. Par contre, le nombre de {} en français étant plus que restreint, là je les ai utilisés, mais après placement des symboles utilisés en français.
C'est donc pour cela que les symboles qui sont utilisés en programmation et pas en français sont tous en AltGr.

Intérêt de tout ceci : mettre fin à la question sans fin du pourcentage de code source dans le corpus.

== Deuxième étape : génération des statistiques de fréquences des symboles ==

C'est une partie qui peut sembler très simple, ce n'est pas forcément le cas. C'est en effet une partie où il y a plusieurs points qui sont arbitraires.

Comment ça des points arbitraires dans la partie qui semble la plus systématique ?!

Alors, les statistiques, comment ça se passe. La base est très simple :
* on parcourt le fichier de corpus
* pour chaque symbole rencontré, on augmente son nombre d'occurrence de 1
C'est simple, oui, mais... on a plein de symboles, et on a que 48 touches.

Précision sur le contexte :
* à l'époque on était parti pour se limiter au charset latin9 (aka ISO-8859-15) ;
* je dis 48 touches parce que je compte LSGT (touche [<]), qui n'est pas présente mais mon sentiment à l'époque devait être quelque chose du genre « bon, le projet il avance plus à rien, on fait que de l'abstrait et on a toujours rien comme résultat, alors je me lance, et je pars pour une disposition pour clavier pc105 » (tout ressemblance avec l'état actuel sur le projet ne serait que purement fortuite).

Donc, potentiellement 192 symboles (256 du latin9 - 4*16 non imprimables), 48 touches, forcément ça passe pas. Il y a donc des symboles qui sont en accès direct, d'autres accessible via shift, altgr, altgr+shift.

À l'époque on a aussi dit qu'on voulait toutes les lettres accentuées accessibles en majuscules via shift. C'était implicite qu'on allait en faire autant pour les 26 lettres non accentuées.

Toujours à la même époque, on était plutôt parti pour mettre les chiffres en majuscules. On était aussi contre le fait de mettre des lettres sur la rangée supérieure (du moins pas des non accentuées comme k w z...).

À ce niveau, qu'est-ce qu'on a ? 48 accès direct, 48 shift. Bon, on a 26 lettres, et les mêmes 26 lettres en majuscules en shift. Restent 22 places en direct et 12 en shift (car 10 en shift pour les chiffres).
À cela on ajoute les lettres accentuées : é, à, è, ê, ç, ù, û, ô, î, â, ï, ë, ü, ä. Ah zut, ça fait un peu beaucoup là quand même. Qu'à cela ne tienne, on fait une touche morte pour l'accent circonflexe et une pour le tréma. Ça donne quoi du coup : é, à, è, ç, ù, dead-^, dead-"

Ensuite, on a la ponctuation : {,}, {?}, {'}, {!}, {.}, {;}, {:}, {/}...

Et là on est parti pour l'arbitraire. Il reste 22 places, on a 5 lettres, au moins une touche pour le circonflexe, et quasiment une dizaine de symboles de ponctuations courants. À cela il faut ajouter tous les symboles courant restant (parenthèses, guillemets, symboles arithmétiques). Bref, ça rentre pas.

Qu'est-ce qu'on fait dans ce cas, bin la même chose que sur les autres claviers, on regroupe les symboles de ponctuations, et on en met certains accessible via shift.

Comme à l'époque l'idée était de mettre l'espace insécable en shift-espace, quoi de plus logique que de mettre sur shift les symboles de ponctuations fréquement précédés et/ou suivi de la-dite espace insécable ? C'est parti, ça nous donne ? ! ; / sur shift. Sur shift, oui, mais sur shift-quoi... Et hop, ça n'est absolument pas une justification, mais j'ai fait comme ça « parce que ça fait comme l'azerty », et aussi parce que j'ai regroupé par ordre de fréquence (ce qui n'a rien de logique, mais rien d'illogique non plus...).

Donc on a :
* ? sur shift ,
* ; sur shift .
* / sur shift :
* ! sur shift '

Dans la série arbitraire : j'ai mis le tréma mort en shift circonflexe mort.

En réalité, la partie regroupement des symboles de ponctuations par paire, et la partie générations des statistiques des circonflexes et tréma sont faites en deux passes distinctes, mais c'est du détail d'implémentation...

Et voilà, on a des jolies statistiques, non plus des symboles, mais des regroupement de symboles qu'on aura à mettre en face des touches.

== Troisième étape : génération des statistiques de fréquences des digrammes ==

But du jeu : faire des statistiques sur les enchainements de deux symboles. Là encore, pas si simple, même si y'a peut-être un peu moins d'arbitraire.

Avant de se lancer tête baissée dans la génération de statistiques, il faut savoir à quoi elles vont servir, sinon on va être tout content de générer des données, mais beaucoup moins quand on verra qu'on saura pas quoi en faire...

Les statistiques vont servir à répartir les touches sur le clavier de façon à optimiser les contraintes qu'on a (alternance des mains, frappe dirigée vers l'intérieur du clavier...). De façon générale : fluidifier la frappe. Avoir une frappe fluide c'est bien, mais il y a certains points à ne pas oublier : on va pas s'amuser à remapper la touche espace et la touche enter. Vu leur placement, la première peut être frappé avec les pouces de façon indifférente, la deuxième forcément avec l'auriculaire droit en grande extension donc rupture de continuité de la frappe.
Donc en fait, on a limité les statistiques de digrammes aux digrammes ne comportant ni espace (espace, tabulation...), ni retour à la ligne.

Ensuite, il faut tenir compte de ce qu'on a décidé plus haut, à savoir que les lettres accentuées à base de circonflexe sont faite via touche morte, donc il faut penser à ne pas mettre de digramme « tê » mais un « t^ » et un « ^e ».

Enfin, dans la série rupture de continuiter de la frappe : l'utilisation de shift. On notera d'ailleurs que c'est pas gênant vu que c'est en général en début de phrase (voire de mot en cours de phrase pour les noms propre). On peut d'ailleurs généraliser ce principe en ne comptant que les 48 symboles qui sont en accès direct.

Et voilà, des statistiques de fréquences des digrammes.

== Quatrième étape : génération des statistiques de fréquences des trigrammes ==

C'est simple, il suffit de faire pareil, mais sur une longueur de motif de 3 au lieu de 2. Oui, c'est simple, sauf que... l'algorithme qui va servir après est incapable de les utiliser tels quels. On verra à la 42e étape qu'en fait, ce qui m'intéresse dans les statistiques des trigrammes, c'est en fait la première et la troisième lettre du trigramme. Donc au final, on regroupe les trigrammes ayant les mêmes premier et troisième symboles, et associe au digramme obtenu la somme des nombres d'occurrences de chaque trigramme qu'il regroupe.

== Cinquième étape : la carte d'accessibilité des touches ==

Ce point est particulièrement sensible, on l'a encore vu récement sur la mailing-list. Suite à quelques discussions quelqu'un avait proposé une [[Carte_d%27accessibilit%C3%A9_des_touches|carte d'accessibilité des touches]] (à l'heure où j'écris c'est la deuxième, celle en couleur).

On était plusieurs à pas vraiment être complètement d'accord, en particulier sur la rangée du bas coté gauche.

J'ai essayé plusieurs CAT, puis fait tourner l'algo de génération, avec plus ou moins de succès. J'ai repéré assez rapidement les gros défauts de chacune des dispositions générées, et j'ai corrigé la CAT en fonction. Au final je suis arrivé à la première ([[Carte_d%27accessibilit%C3%A9_des_touches|sur la même page]]).

Pour les besoins de l'algorithme, la CAT est faite par groupe de touches, et non pas par touche.

== Sixième étape : génération des ditouches ==

Tout d'abord, pourquoi des ditouches ? Simple, pour chaque paire de symboles on a une nombre d'occurence (ou une fréquence, ça revient au même), et l'algorithme qu'on va voir après va essayer de les placer un peu dans tous les sens. Pour chaque résultat possible, on va regarder comment se tape chaque digrammes (s'il faut changer de main, si c'est orienté vers le centre du clavier, etc.). Pour ça, j'ai fait un script qui, à partir d'un fichier indiquant sur quel doigt et sur quelle ligne se trouve une touche, va permettre de générer un autre fichier qui va indiquer pour chaque ditouche :
* s'il se tape à deux mains (catégorie 1) ;
* si sa frappe se fait vers l'intérieur (catégorie 2) ;
* si sa frappe se fait vers l'extérieur (catégorie 3) ;
* si sa frappe utilise le même doigt (catégorie 4).

== Septième étape : génération des tritouches ==

Même principe, sauf qu'en fait il s'agit pas de tritouches, mais de ditouches pour trigrammes. Pour les trigrammes on a simplifié à deux symboles, la seule chose qui m'intéresse c'est de savoir si le premier et le dernier symbole d'un trigramme se tape sur la même main ou pas. Donc pour chaque ditouche :
* s'il se tape à deux mains (catégorie 1) ;
* sinon (catégorie 2).

== Huitième étape : l'algorithme de génération ==

Alors, si on résume on a des statistiques d'utilisation des symboles, une CAT, des statistiques de digrammes/trigrammes, des informations sur les ditouches/tritouches.

Il suffit alors de calculer une fonction de coût pour les 48! associations symbole/touche possible. Pour information, 48! ça fait jamais que 12413915592536072670862289047373375038521486354677760000000000, c'est à dire un peu trop (ordre de grandeur 10^61).

Bref, pour simplifier le calcul, j'ai violemment élagué l'arbre de recherche avec la simplification suivante : on suppose que les touches d'un même groupe dans la CAT ont la même accessibilité, et que de fait, la fréquence des symboles ne sert qu'à dire tel symbole va dans tel groupe, et c'est tout. Le positionnement des symboles au sein d'un groupe ne se fait qu'en utilisant les digrammes.

Vu la CAT utilisée, et si on ne compte pas le groupe 6 (qui a 13 touches et qui ne comporte que des symboles dont les statistiques ne sont pas du tout pertinentes), ça nous donne 8! * 9! * 5! * 9! * 4! = ... (ordre de grandeur 10^19). Ça nous permettra de générer le layout en 5s au lieu de plusieurs milliard de milliard de fois l'âge de l'univers.

Venons-en à l'algorithme proprement dit.

Comme dit précédemment, on procède par groupe de touches, et groupe de symboles pour aller avec.
On prend le premier groupe de touches, le groupe de symboles associés. On teste toutes les combinaisons possibles (il y en a 8!). Pour chacune des combinaisons, on va calculer une fonction de coût basée sur la façon dont vont être tapés les digrammes. Pour chacune des quatre catégories de digrammes on défini un coût.

Alors là on se dit que c'est arbitraire, ça l'est effectivement, mais je me suis rendu compte par la suite que ce qui comptait vraiment, c'était que les quatre coûts soient dans l'ordre croissant.
Donc, pour chaque digramme de symboles placé, on calcul un coût partiel qui est le produit du coût associé à la catégorie du ditouche, lui-même associé au digramme en question. Et on fait la somme des coûts partiels, ça donne le coût de la disposition.

Le problème, c'est que là on va avoir le coût de la disposition, qui n'a pour l'instant que 8 touches de placées... et on ne tient absolument pas compte de l'éventuel placement des autres symboles.

Pour compenser un peu ce problème, c'est là que j'ai fait entrer en ligne de compte les trigrammes/tritouches. En supposant que les symboles qui ne sont pas encore placés le seront par la suite de façon idéale, ça veut dire qu'on va essayer d'avoir les premiers et dernier symboles de chaque trigramme sur la même main. D'où les deux catégories pour les tritouches.

Une fois qu'on a calculé le coût pour chacune des 8! combinaisons pour le premier groupe, on calcule le deuxième groupe. Ce coup-ci, on va tenir compte des touches déjà placées. Et on va tenir compte de celles pas encore placées de la même façon (à coup de trigrammes/tritouches).

Ensuite, on passe au troisième groupe ? Et bien non. On supprime le placement du premier groupe, et on le recalcule en tenant compte de ce qui a été placé par la suite, à savoir le deuxième groupe.

Ensuite on supprime le deuxième groupe, et on le recalcule.

Et on répète ses deux étapes jusqu'à ce le résultat converge, à savoir qu'on ait un résultat stable.

Ensuite on fait le troisième groupe, toujours pareil. Puis on refait le premier, puis le deuxième, puis le troisième. Et ainsi de suite jusqu'à stabilisation du résultat.

Et ainsi de suite jusqu'au sixième groupe.

Voilà, le tout nous donne un truc assez proche de la 0.1.

== Neuvième étape : on remplit le reste ==

L'algorithme a aussi placé les 13 symboles de la rangée des chiffres et euh... c'était complètement pas pertinent, donc je l'ai faite à la main.

Idem pour les symboles en AltGr.