« Utilisatrice:Ariasuni/V2/Algo » : différence entre les versions

De Disposition de clavier bépo
m (→‎Modélisation : Mise en page + correction légère)
m (Suppression d’un paragraphe et ajout d’un avertissement sur la stagnation de la page)
 
(10 versions intermédiaires par le même utilisateur non affichées)
Ligne 1 : Ligne 1 :
{{note|Dans un soucis de simplification, cette page part du postulat que l'on souhaite placer les 34 touches qui contiennent les lettres ainsi que quelques symboles de ponctuation en Bépo, mais ceci reste encore à débattre…}}
{{note|Dans un soucis de simplification, cette page part du postulat que l’on souhaite placer les 34 touches qui contiennent les lettres ainsi que quelques symboles de ponctuation en Bépo, mais ceci reste encore à débattre…}}
 
{{note|type=attention|Au point mort depuis un moment, mais contient pas mal d’informations qui peuvent être intéressantes.}}


Le but de ce document est de décrire le fonctionnement précis des algorithmes que je proposeraient pour générer la V2.
Le but de ce document est de décrire le fonctionnement précis des algorithmes que je proposeraient pour générer la V2.


== Général ==
= Génération de dispositions =
=== Problématique ===
Le but est de générer un nombre raisonnable (pour les possibilités de calcul de l’ordinateur) de dispositions optimisées, afin de les évaluer plus en détails ensuite.
Il y a 34! possibilités différentes de dispositions de claviers, c'est à dire ≃ 3 × 10^38 (3 avec 38 zéros derrières…) Ça prendrait plusieurs milliards d'année simplement pour les générer.
 
== Choix ==
=== Méthode choisie ===
Il y a 34! possibilités différentes de dispositions de claviers, c’est à dire ≃ 3 × 10³⁸ (3 avec 38 zéros derrières…) Ça prendrait plusieurs milliards d’années simplement pour les générer!
 
La méthode que j’ai choisie d’étudier est de faire un algorithme assez classique en plusieurs étapes de sélection:
* Génération d’un ensemble de possibilités pour une partie de la solution à partir de l’étape précédente
* Sélection des X plus optimisées en appliquant un algorithme simple
Grâce à cette méthode, on a à chaque fois un nombre relativement petit de possibilités qui peuvent être traitées en un temps raisonnable (qui reste à déterminer) par l’ordinateur. On évalue ensuite les dispositions générée et on choisit la meilleure grâce au comparateur de dispositions.


La méthode de génération du Bépo est décrit sur [[Cr%C3%A9ation_de_la_version_0.1#Huiti.C3.A8me_.C3.A9tape_:_l.27algorithme_de_g.C3.A9n.C3.A9ration | cette page]].
La méthode de génération du Bépo est décrit sur [[Cr%C3%A9ation_de_la_version_0.1#Huiti.C3.A8me_.C3.A9tape_:_l.27algorithme_de_g.C3.A9n.C3.A9ration | cette page]].


=== Méthode choisie ===
=== Critères ===
La méthode que j'ai choisie d'étudier est de faire un algorithme par étapes:
Ce sont les critères surtout utilisés dans le générateur de dispositions.
* Génération d'un ensemble de possibilités pour une partie de la solution
* Sélection des X plus optimisées en appliquant un algorithme simple
Et ce plusieurs fois, afin d'obtenir un nombre raisonnable de possibilités à la fin. On évalue les dispositions et on choisi la meilleure grâce au comparateur de dispositions.


=== Critères importants ===
Par ordre d’apparition:
Indiqués par ordre d'apparition dans l'algorithme de génération de dispositions:
* alternance des mains (charge 50/50 entre les deux mains)
* alternance des mains (charge 50/50 entre les deux mains)
* roulements vers l'intérieur (surtout pour la rangée de repos)
* roulements vers l’intérieur (surtout pour la rangée de repos)
* charge des doigts adaptée (charge du petit doigt inférieure à celle de l'index par exemple)
* charge des doigts adaptée (charge du petit doigt inférieure à celle de l’index par exemple)
* alternance des doigts (le moins possible de digrammes à un doigt)
* alternance des doigts (le moins possible de digrammes à un doigt)


Pour le comparateur de frappe, on essaiera de favoriser la "roulternance". Ce néologisme (de mon invention :D) signifie «alternance de digrammes faciles (dont la majorité sont des roulements vers l'intérieur) de deux ou trois caractères». Cela signifie que la main doit faire un roulement de deux/trois lettres, puis changer de main, puis à nouveau un roulement de deux/trois lettres, puis à nouveau un changement de main, etc, et ceci le plus possible.
=== Données d’entrée ===
* La liste de tous les groupes de caractères (exemple: .:) que l’on veut placer sur le clavier
* La liste de tous les caractères et leur fréquence produit par l’analyseur de corpus.
* Une carte d’accessibilité des digrammes


=== Parties ===
=== Données produites ===
Il y a quatre parties distinctes de l'algorithme:
Des dispositions de clavier dans un format à déterminer (pour qu’il puisse être utilisé par l’évaluateur de dispositions).
* Génération de dispositions
* Évaluation d'une disposition
* Comparaison de dispositions
 
== Génération de dispositions ==
Le but est de produire un nombre raisonnable (pour les possibilités de calcul de l'ordinateur) de dispositions optimisées.


== Algorithme ==
=== Sélection des rangées de repos ===
=== Sélection des rangées de repos ===
Sélection des meilleures rangées de repos optimisées pour les roulements.
Sélection des meilleures rangées de repos optimisées pour les roulements de digrammes.


Génération des rangées de repos:
Génération des rangées de repos:
* On prend les 8 lettres les plus fréquentes des corpus. Dans notre cas, ce sont «easintru»
* On prend les 8 lettres les plus fréquentes des corpus. Dans notre cas, ce sont «easintru» (cf. la page [[fréquence des caractères]].)
* On produit toutes les combinaisons: 8! = 40320 possibilités
* On produit toutes les combinaisons: 8! = 40320 possibilités


''NOTE: on pourra envisager de placer "en dur" certaines touches si elles reviennent systématiquement lors de l'exécution de l'algorithme.''
''Note: ce procédé est remis en question par [https://mathematicalmulticore.wordpress.com/2010/06/24/new-keyboard-layout-project-have-we-been-mistaken-all-along/ ce billet], du coup on pourrait prendre 8 caractères parmi 10 ou 12…''


Sélection des rangées de repos:
Sélection des rangées de repos:
* On prend la liste des digrammes et leur fréquence (on peut ignorer les digrammes dont la fréquence est négligeable)
* On prend la liste des digrammes et leur fréquence (on peut ignorer les digrammes dont la fréquence est négligeable)
* On donne à chaque disposition une note qui est la somme des fréquences des digrammes qui obligent à faire un roulement vers l'extérieur
* On donne à chaque disposition une note qui est la somme, pour chaque digramme, de la fréquence du digramme multipliée par son accessibilité
 
On sélectionnera ensuite les X meilleures rangées de repos, en fonction de l'écart de points entre les différentes dispositions.


'''Exemple:''' soit f([digramme]) la fréquence d'un digramme. si on a trouvé AUIE pour la partie droite du clavier, AU est vers l'intérieur donc on ne donne pas de points, EI se fait vers l'extérieur donc F vaut f(EI), de même pour EU donc F vaut f(EI) + f(EU)
On sélectionnera ensuite les X meilleures rangées de repos, en fonction de l’écart de points entre les différentes dispositions.


=== Sélection des ensembles de lettres ===
=== Sélection des ensembles de lettres ===
Ligne 55 : Ligne 57 :
On considère, pour chaque rangée de repos déterminé ci-dessus, tous les ensembles de 15 caractères (sans doublons) qui contiennent les 4 lettres de la rangée de repos de la partie gauche du clavier.
On considère, pour chaque rangée de repos déterminé ci-dessus, tous les ensembles de 15 caractères (sans doublons) qui contiennent les 4 lettres de la rangée de repos de la partie gauche du clavier.


Soit F la fréquence d'utilisation de la main, qui vaut la somme de la fréquence de chacun des caractère d'un ensemble sus-nommé, on sélectionne uniquement les ensembles tels que F soit proche de 0,5, avec une marge en fonction des capacités de calcul de l'ordinateur.
Soit F la fréquence d’utilisation de la main, qui vaut la somme de la fréquence de chacun des caractère d’un ensemble sus-nommé, on sélectionne uniquement les ensembles tels que 0,48 ≤ F 0,52 (plus ou moins).


'''Exemple:''' Soit f([lettre]) la fréquence d'une lettre. Si les caractères de la rangée de repos de la partie gauche du clavier est "AUIE", on prend tous les ensembles de caractères sans doublons qui contiennent "AUIE", par exemple "BÉPOÈAUIE,ÀYX.K". Pour obtenir F, on ajoute ensuite f(B), f(É), et ainsi du suite, ce qui nous donnera un résultat entre 0 et 1.
'''Exemple:''' Soit f([lettre]) la fréquence d’une lettre. Si les caractères de la rangée de repos de la partie gauche du clavier est "AUIE", on prend tous les ensembles de caractères sans doublons qui contiennent "AUIE", par exemple "BÉPOÈAUIE,ÀYX.K". Pour obtenir F, on ajoute ensuite f(B), f(É), et ainsi du suite, ce qui nous donnera un résultat entre 0 et 1.


=== Placement des lettres ===
=== Placement des lettres ===
Le calcul pour chaque partie (droite/gauche) du clavier se fera indépendamment, et pour chaque ensemble de lettres déterminé ci-dessus.
Le calcul pour chaque partie (droite/gauche) du clavier se fera indépendamment, et pour chaque ensemble de lettres déterminé ci-dessus.


* On considère, tous les ensembles de lettres que l'on peut placer sur le doigt n°1.
* On considère, tous les ensembles de lettres que l’on peut placer sur le doigt n°1.
* Soit N la somme des fréquences des digrammes qui se font à un doigt ce doigt et cet ensemble de lettres. On ne garde que celles qui ont un N inférieur à un certain montant.
* Soit N la somme des fréquences des digrammes qui se font à un doigt ce doigt et cet ensemble de lettres. On ne garde que celles qui ont un N inférieur à un certain montant.
* On repasse à l'étape 1 mais pour le deuxième doigt.
* On repasse à l’étape 1 mais pour le deuxième doigt.


Ensuite, on génère la partie du clavier à partir des possibilités qui n'ont pas été éliminées.
Ensuite, on génère la partie du clavier à partir des possibilités qui n’ont pas été éliminées.


Soit C la charge d'un doigt, on ne garde que les cas où C(auriculaire) < C(annulaire) < C(majeur) < C(index), et on rajoutera éventuellement des règles plus fines. On calcule le N pour toute la partie droite du clavier et on ne garde que les meilleures.
Soit C la charge d’un doigt, on ne garde que les cas où C(auriculaire) < C(annulaire) < C(majeur) < C(index), et on rajoutera éventuellement des règles plus fines. On calcule le N pour toute la partie droite du clavier et on ne garde que les meilleures.


On prend toutes les possibilités de clavier à partir des parties gauches et droites générées. On recalcule N pour chaque disposition entière et on élimine encore quelques unes.
On prend toutes les possibilités de clavier à partir des parties gauches et droites générées. On recalcule N pour chaque disposition entière et on élimine encore quelques unes.
Ligne 86 : Ligne 88 :
* etc
* etc


Cet exemple montre que l'on peut représenter toutes les possibilités comme un arbre, dont les branches sont normalement beaucoup plus nombreuses et dont certaines sont éliminées par les tests.
Cet exemple montre que l’on peut représenter toutes les possibilités comme un arbre, dont les branches sont normalement beaucoup plus nombreuses et dont certaines sont éliminées par les tests.


== Évaluation d'une disposition ==
= Évaluation d’une disposition =
Le but est de modéliser une saisie de texte pour une disposition et un corpus donné et d'en tirer des statistiques qui pourront être utilisées par le comparateur de dispositions. Pour cela, on simulera la frappe digramme par digramme.
Le but est de produire, à partir d’un corpus, des données permettant de quantifier l’efficacité d’une disposition.
 
== Choix ==
=== Méthode choisie ===
On modélisera une saisie de texte digramme par digramme, ce qui nous permettra d’avoir un résultat assez proche de la réalité.


=== Critères ===
=== Critères ===
* L'alternance des doigts:
Pour le comparateur de frappe, on essaiera de favoriser la "roulternance". Ce néologisme (de mon invention :D) signifie «alternance de digrammes faciles (dont la majorité sont des roulements vers l’intérieur) de deux ou trois caractères». Cela signifie que la main doit faire un roulement de deux/trois lettres, puis changer de main, puis à nouveau un roulement de deux/trois lettres, puis à nouveau un changement de main, etc, et ceci le plus possible.
** le moins possible de digrammes à un seul doigt (critère compté dans la carte d'accessibilité des digrammes)
** Il faudra faire attention à ce que la charge des doigts soit adaptée (évaluation plus fine que la sélection de l'étape précédente)


* La "roulternance" (voir [[#Crit.C3.A8res_importants | plus haut]]):
* La "roulternance" (voir ci-dessus):
** La frappe doit permettre d'enchainer un digramme/trigramme facile (ce qui est déterminé via la carte d'accessibilité des digrammes) sur une main, puis sur l'autre, puis à nouveau sur la première, etc.
** La frappe doit permettre d’enchainer un digramme/trigramme facile (ce qui est déterminé via la carte d’accessibilité des digrammes) sur une main, puis sur l’autre, puis à nouveau sur la première, etc.
** L'énergie pour taper la barre d'espace est considérée nulle, donc les digrammes commençant par une espace ne comptent que l'énergie dépensée pour atteindre le caractère (basé sur la carte d'accessibilité des touches), et ceux finissant par une espace comptent avec une énergie nulle.
** L’énergie pour taper la barre d’espace est considérée nulle, donc les digrammes commençant par une espace ne comptent que l’énergie dépensée pour atteindre le caractère (basé sur la carte d’accessibilité des touches), et ceux finissant par une espace comptent avec une énergie nulle.
 
* L’alternance des doigts:
** le moins possible de digrammes à un seul doigt (critère compté dans la carte d’accessibilité des digrammes)
** Il faudra faire attention à ce que la charge des doigts soit adaptée (évaluation plus fine que la sélection de l’étape précédente)


* Le confort
* Le confort
** Les digrammes doivent être faciles à faire (critère calculé via la carte d'accessibilité des digrammes)
** Les digrammes doivent être faciles à faire (critère calculé via la carte d’accessibilité des digrammes)
** Le déplacement des mains et doigts doit être le plus faible possible (simulation des mouvements)
** Le déplacement des mains et doigts doit être le plus faible possible (simulation des mouvements)
** Il doit y avoir le moins possible de sauts de lignes
=== Données d’entrée ===
* Les dispositions produites par le générateur de dispositions.
* Une carte d’accessibilité des digrammes
* Une carte d’accessibilité des touches


=== Données produites ===
=== Données produites ===
Données sur:
* La fatigue musculaire: fatigue comptabilisées pour chaque frappe et chaque déplacement.
* La fatigue musculaire: fatigue comptabilisées pour chaque frappe et chaque déplacement
** La charge de chaque doigt/main (somme de l’accessibilité de chaque caractère/digramme tapé par le doigt/la main)
** La charge de chaque doigt/main (somme de l'accessibilité de chaque caractère/digramme tapé par le doigt/la main)
** La distance parcourue par chaque doigt
** La distance parcourue par chaque doigt/main
** Le nombre de déplacement de la main hors de la rangée de repos (c’est à dire le nombre de fois où taper un caractère oblige à déplacer la main assez pour que les autres doigts ne soient plus sur la rangée de repos)
* Données sur le confort: les séquences difficiles augmentent les risques de TMS, fatiguent le cerveau, et ralentissent la frappe
* Données sur le confort: les séquences difficiles augmentent les risques de TMS, fatiguent le cerveau, et ralentissent la frappe.
** Le nombre de digrammes dont l'accessibilité est supérieur à une valeur fixée (la moyenne ou au-dessus)
** Le nombre de digrammes dont l’accessibilité est supérieur à une valeur fixée (la moyenne ou au-dessus)
** Le nombre de digrammes à un doigt
** Le nombre de digrammes à un doigt
** Le nombre de sauts de rangées
** Le nombre de sauts de rangées qui sont des digrammes à un doigt
* Nombre de digramme qui respectent la roulternance


== Algorithme ==
=== Modélisation ===
=== Modélisation ===
Pour représenter une saisie de texte, on aura deux objets "Mains" qui contiennent chacun une liste d'objets "Doigts".
Pour représenter une saisie de texte, on aura deux objets "Mains" qui contiennent chacun une liste d’objets "Doigts".


Ensuite on fait passer le texte digramme par digramme. += signifie qu'on ajoute à l'opérande de gauche l'opérande de droite, ++ signifie qu'on incrémente (augmente de 1) la valeur de la variable.
Ensuite on fait passer le texte digramme par digramme. += signifie qu’on ajoute à l’opérande de gauche l’opérande de droite, ++ signifie qu’on incrémente (augmente de 1) la valeur de la variable.


  Tant que le texte n'est pas fini faire
On place les doigts sur la rangée de repos
  Tant que le texte n’est pas fini faire
     Si le digramme est fait à une main alors
     Si le digramme est fait à une main alors
         charge main += accessibilité digramme
         charge main += accessibilité digramme
Ligne 124 : Ligne 144 :
         charge doigt2 += accessibilité touche2
         charge doigt2 += accessibilité touche2
   
   
         Si le digramme est fait à un doigt alors
         Si le digramme est fait à un doigt Alors
             nombre digrammes à un doigt++
             nombre digrammes à un doigt++
         Sinon si c'est un roulement dont l'accessibilité est supérieure à X alors
         Sinon si c’est un roulement dont l’accessibilité est supérieure à X Alors
             nombre digrammes difficiles++
             nombre digrammes difficiles++
        FinSi
        Si le digramme est un saut de ligne Alors
            nombre saut de ligne++
         FinSi
         FinSi
     FinSi
     FinSi
Ligne 134 : Ligne 158 :
'''À faire:''' gestion de la position des mains et des doigts.
'''À faire:''' gestion de la position des mains et des doigts.


== Historique ==
= Comparaison de plusieurs dispositions =
=== Copier-coller de la liste de diffusion ===
Le but est de sélectionner parmi un ensemble de dispositions, celles qui sont les plus optimisées selon certains critères.
Ça permet de donner un historique de la réflexion sur l'algo de la V2, sachant qu'il n'y a que moi qui m'en occupe pour le moment (entre ceux qui sont occupés par la vraie vie, ceux qui s'occupent de l'association, et les autres qui réfléchissent à d'autres détails de la V2…)
 
== Choix ==
=== Méthode choisie ===
Élimination des moins bonnes dispositions, puis classement des dispositions selon leur note, dépendant des critères ci-dessous, dont on pourra faire varier l’influence (la pondération).
 
=== Critères ===
Voir [[#Crit.C3.A8res_2 | la liste des critères pour l’évaluateur de disposition]].
 
=== Données d’entrée ===
Les dispositions et ainsi que les données produites avec l’évaluateur de dispositions.
 
=== Données produites ===
Une liste ordonnée de dispositions dans un tableau avec chacun des critères ainsi que leur pondération et la note finale.
 
== Algorithme ==
=== Élimination des plus mauvaises dispositions ===
On pourra fixer des valeurs maximale sur les points suivantes (sinon la disposition est supprimée):
* digrammes à un doigt
* sauts de lignes
* charge et confort de frappe au niveau des doigts et des mains
* etc
 
=== Élimination des dispositions inférieure en tout point à une autre ===
On appliquera l’algorithme suivant:
* au premier tour, je met la première disposition dans une liste,
* puis à chaque tour je compare une disposition de la liste et la disposition suivante:
** si la disposition suivante est supérieure en tout point à une disposition de la liste, je l’ajoute immédiatement et j’arrête,
** sinon si une disposition de la liste est supérieure en tout point à une disposition de la liste, je m’arrête sans l’ajouter à la liste,
** sinon je l’ajoute à la liste.
 
= Historique et liens =
Ça permet de donner un historique de la réflexion sur l’algorithme de la V2.
 
== Liste de diffusion ==
Des copier-coller de la liste de diffusion


==== 14/02/2013 ====
=== 14/02/2013 ===
Je viens d'avoir une idée qui peut être extrêmement intéressante: pourquoi ne  
Je viens d’avoir une idée qui peut être extrêmement intéressante: pourquoi ne  
pas générer toutes les dispositions dont l'alternance des mains est maximale?  
pas générer toutes les dispositions dont l’alternance des mains est maximale?  
En gros, on choisi à l'avance quelles lettres iront de quel côté, et ça nous  
En gros, on choisi à l’avance quelles lettres iront de quel côté, et ça nous  
servira pour générer des dispositions qui sont déjà plutôt bien optimisées!
servira pour générer des dispositions qui sont déjà plutôt bien optimisées!




En plus c'est très très simple à mettre en œuvre:
En plus c’est très très simple à mettre en œuvre:
* on classe les lettres par ordre de fréquence et on les met deux par deux (la partie droite du clavier se coltinera les lettres les moins fréquentes tout à la fin, ce qui me parait logique)
* on classe les lettres par ordre de fréquence et on les met deux par deux (la partie droite du clavier se coltinera les lettres les moins fréquentes tout à la fin, ce qui me parait logique)
* la première de chaque groupe va sur la partie droite et la deuxième sur la partie gauche et inversement
* la première de chaque groupe va sur la partie droite et la deuxième sur la partie gauche et inversement
Ligne 151 : Ligne 209 :
Ensuite
Ensuite
* on essaie toutes les possibilités
* on essaie toutes les possibilités
* on prend les meilleures au niveau de l'alternance des mains (en tenant compte de la fréquence de chaque lettre)
* on prend les meilleures au niveau de l’alternance des mains (en tenant compte de la fréquence de chaque lettre)




À chaque fois on a un choix parmi deux, et pour les quatre derniers caractères  
À chaque fois on a un choix parmi deux, et pour les quatre derniers caractères  
on a pas le choix, ce qui fait 2^30 (de l'ordre de 10^9). C'est encore bien  
on a pas le choix, ce qui fait 2^30 (de l’ordre de 10^9). C’est encore bien  
trop. On peut décider de mettre toutes les voyelles d'un côté, ce qui fait 8  
trop. On peut décider de mettre toutes les voyelles d’un côté, ce qui fait 8  
lettres en moins à placer: leurs équivalent dans les paires de lettres seront  
lettres en moins à placer: leurs équivalent dans les paires de lettres seront  
obligatoirement dans l'autre partie du clavier. On part sur du 2^14 (ce qui  
obligatoirement dans l’autre partie du clavier. On part sur du 2^14 (ce qui  
fait 16384).
fait 16384).


Même en ne mettant que les voyelles de l'ASCII (A, E, I, O, U, Y), on aura  
Même en ne mettant que les voyelles de l’ASCII (A, E, I, O, U, Y), on aura  
2^18 (262144) possibilités. Ensuite il suffit de sélectionner les 100 ou 1000  
2^18 (262144) possibilités. Ensuite il suffit de sélectionner les 100 ou 1000  
dispositions les plus équilibrées au niveau de l'alternance (par exemple).
dispositions les plus équilibrées au niveau de l’alternance (par exemple).




Ligne 169 : Ligne 227 :
clavier sans poser de contraintes, on a 15! possibilités par groupe de lettre  
clavier sans poser de contraintes, on a 15! possibilités par groupe de lettre  
(> 10^12). Si on pose que les lettres de la rangée de repos sont les lettres  
(> 10^12). Si on pose que les lettres de la rangée de repos sont les lettres  
qui ont la plus grande fréquence dans l'ordre croissant en partant de  
qui ont la plus grande fréquence dans l’ordre croissant en partant de  
l'auriculaire, on a 11! (40 millions de possibilités).
l’auriculaire, on a 11! (40 millions de possibilités).


Avec un peu d'astuce on peut sans doute affiner (parce que sinon ça fait de 4  
Avec un peu d’astuce on peut sans doute affiner (parce que sinon ça fait de 4  
000 (10^9) à 40 000 (10^10) millions, ce qui est trop long à calculer). Je  
000 (10^9) à 40 000 (10^10) millions, ce qui est trop long à calculer). Je  
pense que là on peut se servir de l'algo de la V1, à savoir le placement par  
pense que là on peut se servir de l’algo de la V1, à savoir le placement par  
«zones» en prenant en compte une CAT, ce qui limite grandement les  
«zones» en prenant en compte une CAT, ce qui limite grandement les  
possibilités.
possibilités.




Faut pas oublier que l'évaluation d'une disposition est peut-être une  
Faut pas oublier que l’évaluation d’une disposition est peut-être une  
opération extrêmement rapide, mais tester 10^9 dispositions c'est juste pas  
opération extrêmement rapide, mais tester 10^9 dispositions c’est juste pas  
possible. Et je pense qu'avec mon idée on est sur la bonne piste!!! Faut juste  
possible. Et je pense qu’avec mon idée on est sur la bonne piste!!! Faut juste  
trouver d'autres astuces pour réduire le nombre de dispositions…
trouver d’autres astuces pour réduire le nombre de dispositions…


==== 15/02/2013 ====
=== 15/02/2013 ===
Pour l'algorithme de la V2, je pensais à un truc du style (le roulement y  
Pour l’algorithme de la V2, je pensais à un truc du style (le roulement y  
occupe une place assez importante):
occupe une place assez importante):


* l'alternance des mains: on génère des groupes de lettres (séparé en deux sous-groupes, chacun allant sur la partie gauche ou droite du clavier). On ne garde que celles qui sont proche de 50/50
* l’alternance des mains: on génère des groupes de lettres (séparé en deux sous-groupes, chacun allant sur la partie gauche ou droite du clavier). On ne garde que celles qui sont proche de 50/50


* les roulements sur la rangée de repos: on prend les lettres les plus fréquentes de chaque groupe et on teste toutes les possibilités acceptables (on place les lettres dans l'ordre décroissant de fréquence de l'index au pouce; puis on regarde si on interchange index et majeur, majeur et annulaire, annulaire et auriculaire) et on garde la meilleure.
* les roulements sur la rangée de repos: on prend les lettres les plus fréquentes de chaque groupe et on teste toutes les possibilités acceptables (on place les lettres dans l’ordre décroissant de fréquence de l’index au pouce; puis on regarde si on interchange index et majeur, majeur et annulaire, annulaire et auriculaire) et on garde la meilleure.


* Maintenant on compare toutes les dispositions et on sélectionne 1 ou 2 meilleure(s) rangée(s) de repos par groupe, puis on garde les groupes qui ont une des X meilleures rangées de repos.
* Maintenant on compare toutes les dispositions et on sélectionne 1 ou 2 meilleure(s) rangée(s) de repos par groupe, puis on garde les groupes qui ont une des X meilleures rangées de repos.


* Pour chaque groupe, on assigne les caractères restants à un doigt. On ne garde que celle ou la charge des doigts est équilibré, tout en gardant à l'esprit que le petit doigt est «faible»
* Pour chaque groupe, on assigne les caractères restants à un doigt. On ne garde que celle ou la charge des doigts est équilibré, tout en gardant à l’esprit que le petit doigt est «faible»


* pour chaque doigt on garde 1 ou 2 meilleur(s) groupe(s) de lettres assigné à un doigt. Si on en prend 2, ça fait 2^5 * 2^6 = 2^11 = 2048 possibilités par groupe de lettres.
* pour chaque doigt on garde 1 ou 2 meilleur(s) groupe(s) de lettres assigné à un doigt. Si on en prend 2, ça fait 2^5 * 2^6 = 2^11 = 2048 possibilités par groupe de lettres.
Ligne 200 : Ligne 258 :
* Tout cela nous fait 2048 combinaisons possibles dans un groupe de lettres * nombre de groupe de lettres, et on utilise le comparateur de dispositions pour trouver laquelle sera la V2.
* Tout cela nous fait 2048 combinaisons possibles dans un groupe de lettres * nombre de groupe de lettres, et on utilise le comparateur de dispositions pour trouver laquelle sera la V2.


Cette algorithme à l'avantage de pouvoir tester beaucoup de dispositions, de  
Cette algorithme à l’avantage de pouvoir tester beaucoup de dispositions, de  
pouvoir varier le nombre de dispositions testées en fonction de la puissance  
pouvoir varier le nombre de dispositions testées en fonction de la puissance  
de la machine (du coup si je trouve que l'algo est sympa je rajoute des  
de la machine (du coup si je trouve que l’algo est sympa je rajoute des  
possibilités et je le laisse tourner quelques heures).
possibilités et je le laisse tourner quelques heures).


De plus ça évite la complexité d'un algorithme génétique, c'est peut-être même  
De plus ça évite la complexité d’un algorithme génétique, c’est peut-être même  
plus simple que l'algorithme de Nicolas Chartier utilisé pour la V1 (mais  
plus simple que l’algorithme de Nicolas Chartier utilisé pour la V1 (mais  
c'est difficile à dire au pifomètre).
c’est difficile à dire au pifomètre).


N'hésitez pas à me dire ce que vous en pensez, je suis sûr qu'il y a deux  
N’hésitez pas à me dire ce que vous en pensez, je suis sûr qu’il y a deux  
trois détails qui m'ont échappé!
trois détails qui m’ont échappé!


: J'y ai repéré une incohérence (je ne peux pas déterminer la meilleure disposition des lettres par doigt). D'où (en partie) mon troisième jet.
: J’y ai repéré une incohérence (je ne peux pas déterminer la meilleure disposition des lettres par doigt). D’où (en partie) mon troisième jet.


==== 16/02/2013 ====
=== 16/02/2013 ===
Sinon pour les points «importants» pour l'algo de la V2:
Sinon pour les points «importants» pour l’algo de la V2:
* alternance des mains (pour dégrossir)
* alternance des mains (pour dégrossir)
* roulements vers l'intérieur, surtout pour la rangée de repos
* roulements vers l’intérieur, surtout pour la rangée de repos
* alternance des doigts (charge équilibrée entre les doigts)
* alternance des doigts (charge équilibrée entre les doigts)
* le moins possible de digrammes à un doigt
* le moins possible de digrammes à un doigt




Du coup si on reprend ce que j'avais dis un peu avant, je ferais:
Du coup si on reprend ce que j’avais dis un peu avant, je ferais:


* prendre les meilleures rangées de repos en prenant en compte les roulements (je prend les 8 lettres les plus utilisées, ESAITNRU, on risque fortement de retomber sur ce qu'on a pour la V1 ou très très proche).
* prendre les meilleures rangées de repos en prenant en compte les roulements (je prend les 8 lettres les plus utilisées, ESAITNRU, on risque fortement de retomber sur ce qu’on a pour la V1 ou très très proche).


* Ensuite on cherche les groupes de lettres qui contiennent deux sous-groupes, un allant sur chaque partie du clavier telle que la charge de la main droite soit à peu près égale à celle de la main gauche et qu'un minimum de digramme se fasse avec cette main.
* Ensuite on cherche les groupes de lettres qui contiennent deux sous-groupes, un allant sur chaque partie du clavier telle que la charge de la main droite soit à peu près égale à celle de la main gauche et qu’un minimum de digramme se fasse avec cette main.


* Ensuite on essaie toutes les possibilités, on élimine celles ou la charge des doigts est incohérente, (petit doigt qui travaille plus que l'index ou le majeur…), on regarde pour les roulements ÉP et YX (vers l'intérieur), on regarde SURTOUT qu'il y ai un minimum de digrammes à un doigt.
* Ensuite on essaie toutes les possibilités, on élimine celles ou la charge des doigts est incohérente, (petit doigt qui travaille plus que l’index ou le majeur…), on regarde pour les roulements ÉP et YX (vers l’intérieur), on regarde SURTOUT qu’il y ai un minimum de digrammes à un doigt.


* Avec toutes ces possibilités, on peut faire un ensemble de dispositions qu'il faudra tester une par une avec le comparateur de disposition, qui utilisera les données utilisateurs plutôt que des règles avec un coefficient plus ou moins aléatoire…
* Avec toutes ces possibilités, on peut faire un ensemble de dispositions qu’il faudra tester une par une avec le comparateur de disposition, qui utilisera les données utilisateurs plutôt que des règles avec un coefficient plus ou moins aléatoire…





Dernière version du 22 juillet 2017 à 19:35

Dans un soucis de simplification, cette page part du postulat que l’on souhaite placer les 34 touches qui contiennent les lettres ainsi que quelques symboles de ponctuation en Bépo, mais ceci reste encore à débattre…

Attention

Au point mort depuis un moment, mais contient pas mal d’informations qui peuvent être intéressantes.

Le but de ce document est de décrire le fonctionnement précis des algorithmes que je proposeraient pour générer la V2.

Génération de dispositions

Le but est de générer un nombre raisonnable (pour les possibilités de calcul de l’ordinateur) de dispositions optimisées, afin de les évaluer plus en détails ensuite.

Choix

Méthode choisie

Il y a 34! possibilités différentes de dispositions de claviers, c’est à dire ≃ 3 × 10³⁸ (3 avec 38 zéros derrières…) Ça prendrait plusieurs milliards d’années simplement pour les générer!

La méthode que j’ai choisie d’étudier est de faire un algorithme assez classique en plusieurs étapes de sélection:

  • Génération d’un ensemble de possibilités pour une partie de la solution à partir de l’étape précédente
  • Sélection des X plus optimisées en appliquant un algorithme simple

Grâce à cette méthode, on a à chaque fois un nombre relativement petit de possibilités qui peuvent être traitées en un temps raisonnable (qui reste à déterminer) par l’ordinateur. On évalue ensuite les dispositions générée et on choisit la meilleure grâce au comparateur de dispositions.

La méthode de génération du Bépo est décrit sur cette page.

Critères

Ce sont les critères surtout utilisés dans le générateur de dispositions.

Par ordre d’apparition:

  • alternance des mains (charge 50/50 entre les deux mains)
  • roulements vers l’intérieur (surtout pour la rangée de repos)
  • charge des doigts adaptée (charge du petit doigt inférieure à celle de l’index par exemple)
  • alternance des doigts (le moins possible de digrammes à un doigt)

Données d’entrée

  • La liste de tous les groupes de caractères (exemple: .:…) que l’on veut placer sur le clavier
  • La liste de tous les caractères et leur fréquence produit par l’analyseur de corpus.
  • Une carte d’accessibilité des digrammes

Données produites

Des dispositions de clavier dans un format à déterminer (pour qu’il puisse être utilisé par l’évaluateur de dispositions).

Algorithme

Sélection des rangées de repos

Sélection des meilleures rangées de repos optimisées pour les roulements de digrammes.

Génération des rangées de repos:

  • On prend les 8 lettres les plus fréquentes des corpus. Dans notre cas, ce sont «easintru» (cf. la page fréquence des caractères.)
  • On produit toutes les combinaisons: 8! = 40320 possibilités

Note: ce procédé est remis en question par ce billet, du coup on pourrait prendre 8 caractères parmi 10 ou 12…

Sélection des rangées de repos:

  • On prend la liste des digrammes et leur fréquence (on peut ignorer les digrammes dont la fréquence est négligeable)
  • On donne à chaque disposition une note qui est la somme, pour chaque digramme, de la fréquence du digramme multipliée par son accessibilité

On sélectionnera ensuite les X meilleures rangées de repos, en fonction de l’écart de points entre les différentes dispositions.

Sélection des ensembles de lettres

Sélection des lettres qui iront sur la partie gauche ou droite du clavier.

On considère, pour chaque rangée de repos déterminé ci-dessus, tous les ensembles de 15 caractères (sans doublons) qui contiennent les 4 lettres de la rangée de repos de la partie gauche du clavier.

Soit F la fréquence d’utilisation de la main, qui vaut la somme de la fréquence de chacun des caractère d’un ensemble sus-nommé, on sélectionne uniquement les ensembles tels que 0,48 ≤ F ≤ 0,52 (plus ou moins).

Exemple: Soit f([lettre]) la fréquence d’une lettre. Si les caractères de la rangée de repos de la partie gauche du clavier est "AUIE", on prend tous les ensembles de caractères sans doublons qui contiennent "AUIE", par exemple "BÉPOÈAUIE,ÀYX.K". Pour obtenir F, on ajoute ensuite f(B), f(É), et ainsi du suite, ce qui nous donnera un résultat entre 0 et 1.

Placement des lettres

Le calcul pour chaque partie (droite/gauche) du clavier se fera indépendamment, et pour chaque ensemble de lettres déterminé ci-dessus.

  • On considère, tous les ensembles de lettres que l’on peut placer sur le doigt n°1.
  • Soit N la somme des fréquences des digrammes qui se font à un doigt ce doigt et cet ensemble de lettres. On ne garde que celles qui ont un N inférieur à un certain montant.
  • On repasse à l’étape 1 mais pour le deuxième doigt.

Ensuite, on génère la partie du clavier à partir des possibilités qui n’ont pas été éliminées.

Soit C la charge d’un doigt, on ne garde que les cas où C(auriculaire) < C(annulaire) < C(majeur) < C(index), et on rajoutera éventuellement des règles plus fines. On calcule le N pour toute la partie droite du clavier et on ne garde que les meilleures.

On prend toutes les possibilités de clavier à partir des parties gauches et droites générées. On recalcule N pour chaque disposition entière et on élimine encore quelques unes.

Pour finir, on génèrera toutes les dispositions possibles à partir des groupes de lettres possibles par doigt.

Exemple: si on a "AUI" (auriculaire, annulaire et majeur du côté gauche donc chaque doigt prend trois caractères) comme rangée de repos, et que le groupe de lettres est "BÉPAUIÀYX", on a donc (premier niveau de liste = premier doigt, etc, plusieurs points de même niveau indiquent une possibilité chacun):

  • BAÀ
    • ÉUY
      • PIX
    • ÉUX
      • PIY
  • BAY
    • ÉUÀ
      • PIX
    • etc
  • etc

Cet exemple montre que l’on peut représenter toutes les possibilités comme un arbre, dont les branches sont normalement beaucoup plus nombreuses et dont certaines sont éliminées par les tests.

Évaluation d’une disposition

Le but est de produire, à partir d’un corpus, des données permettant de quantifier l’efficacité d’une disposition.

Choix

Méthode choisie

On modélisera une saisie de texte digramme par digramme, ce qui nous permettra d’avoir un résultat assez proche de la réalité.

Critères

Pour le comparateur de frappe, on essaiera de favoriser la "roulternance". Ce néologisme (de mon invention :D) signifie «alternance de digrammes faciles (dont la majorité sont des roulements vers l’intérieur) de deux ou trois caractères». Cela signifie que la main doit faire un roulement de deux/trois lettres, puis changer de main, puis à nouveau un roulement de deux/trois lettres, puis à nouveau un changement de main, etc, et ceci le plus possible.

  • La "roulternance" (voir ci-dessus):
    • La frappe doit permettre d’enchainer un digramme/trigramme facile (ce qui est déterminé via la carte d’accessibilité des digrammes) sur une main, puis sur l’autre, puis à nouveau sur la première, etc.
    • L’énergie pour taper la barre d’espace est considérée nulle, donc les digrammes commençant par une espace ne comptent que l’énergie dépensée pour atteindre le caractère (basé sur la carte d’accessibilité des touches), et ceux finissant par une espace comptent avec une énergie nulle.
  • L’alternance des doigts:
    • le moins possible de digrammes à un seul doigt (critère compté dans la carte d’accessibilité des digrammes)
    • Il faudra faire attention à ce que la charge des doigts soit adaptée (évaluation plus fine que la sélection de l’étape précédente)
  • Le confort
    • Les digrammes doivent être faciles à faire (critère calculé via la carte d’accessibilité des digrammes)
    • Le déplacement des mains et doigts doit être le plus faible possible (simulation des mouvements)
    • Il doit y avoir le moins possible de sauts de lignes

Données d’entrée

  • Les dispositions produites par le générateur de dispositions.
  • Une carte d’accessibilité des digrammes
  • Une carte d’accessibilité des touches

Données produites

  • La fatigue musculaire: fatigue comptabilisées pour chaque frappe et chaque déplacement.
    • La charge de chaque doigt/main (somme de l’accessibilité de chaque caractère/digramme tapé par le doigt/la main)
    • La distance parcourue par chaque doigt
    • Le nombre de déplacement de la main hors de la rangée de repos (c’est à dire le nombre de fois où taper un caractère oblige à déplacer la main assez pour que les autres doigts ne soient plus sur la rangée de repos)
  • Données sur le confort: les séquences difficiles augmentent les risques de TMS, fatiguent le cerveau, et ralentissent la frappe.
    • Le nombre de digrammes dont l’accessibilité est supérieur à une valeur fixée (la moyenne ou au-dessus)
    • Le nombre de digrammes à un doigt
    • Le nombre de sauts de rangées
    • Le nombre de sauts de rangées qui sont des digrammes à un doigt
  • Nombre de digramme qui respectent la roulternance

Algorithme

Modélisation

Pour représenter une saisie de texte, on aura deux objets "Mains" qui contiennent chacun une liste d’objets "Doigts".

Ensuite on fait passer le texte digramme par digramme. += signifie qu’on ajoute à l’opérande de gauche l’opérande de droite, ++ signifie qu’on incrémente (augmente de 1) la valeur de la variable.

On place les doigts sur la rangée de repos

Tant que le texte n’est pas fini faire
    Si le digramme est fait à une main alors
        charge main += accessibilité digramme
        charge doigt1 += accessibilité touche1
        charge doigt2 += accessibilité touche2

        Si le digramme est fait à un doigt Alors
            nombre digrammes à un doigt++
        Sinon si c’est un roulement dont l’accessibilité est supérieure à X Alors
            nombre digrammes difficiles++
        FinSi

        Si le digramme est un saut de ligne Alors
            nombre saut de ligne++
        FinSi
    FinSi
FinTantQue

À faire: gestion de la position des mains et des doigts.

Comparaison de plusieurs dispositions

Le but est de sélectionner parmi un ensemble de dispositions, celles qui sont les plus optimisées selon certains critères.

Choix

Méthode choisie

Élimination des moins bonnes dispositions, puis classement des dispositions selon leur note, dépendant des critères ci-dessous, dont on pourra faire varier l’influence (la pondération).

Critères

Voir la liste des critères pour l’évaluateur de disposition.

Données d’entrée

Les dispositions et ainsi que les données produites avec l’évaluateur de dispositions.

Données produites

Une liste ordonnée de dispositions dans un tableau avec chacun des critères ainsi que leur pondération et la note finale.

Algorithme

Élimination des plus mauvaises dispositions

On pourra fixer des valeurs maximale sur les points suivantes (sinon la disposition est supprimée):

  • digrammes à un doigt
  • sauts de lignes
  • charge et confort de frappe au niveau des doigts et des mains
  • etc

Élimination des dispositions inférieure en tout point à une autre

On appliquera l’algorithme suivant:

  • au premier tour, je met la première disposition dans une liste,
  • puis à chaque tour je compare une disposition de la liste et la disposition suivante:
    • si la disposition suivante est supérieure en tout point à une disposition de la liste, je l’ajoute immédiatement et j’arrête,
    • sinon si une disposition de la liste est supérieure en tout point à une disposition de la liste, je m’arrête sans l’ajouter à la liste,
    • sinon je l’ajoute à la liste.

Historique et liens

Ça permet de donner un historique de la réflexion sur l’algorithme de la V2.

Liste de diffusion

Des copier-coller de la liste de diffusion

14/02/2013

Je viens d’avoir une idée qui peut être extrêmement intéressante: pourquoi ne pas générer toutes les dispositions dont l’alternance des mains est maximale? En gros, on choisi à l’avance quelles lettres iront de quel côté, et ça nous servira pour générer des dispositions qui sont déjà plutôt bien optimisées!


En plus c’est très très simple à mettre en œuvre:

  • on classe les lettres par ordre de fréquence et on les met deux par deux (la partie droite du clavier se coltinera les lettres les moins fréquentes tout à la fin, ce qui me parait logique)
  • la première de chaque groupe va sur la partie droite et la deuxième sur la partie gauche et inversement

Ensuite

  • on essaie toutes les possibilités
  • on prend les meilleures au niveau de l’alternance des mains (en tenant compte de la fréquence de chaque lettre)


À chaque fois on a un choix parmi deux, et pour les quatre derniers caractères on a pas le choix, ce qui fait 2^30 (de l’ordre de 10^9). C’est encore bien trop. On peut décider de mettre toutes les voyelles d’un côté, ce qui fait 8 lettres en moins à placer: leurs équivalent dans les paires de lettres seront obligatoirement dans l’autre partie du clavier. On part sur du 2^14 (ce qui fait 16384).

Même en ne mettant que les voyelles de l’ASCII (A, E, I, O, U, Y), on aura 2^18 (262144) possibilités. Ensuite il suffit de sélectionner les 100 ou 1000 dispositions les plus équilibrées au niveau de l’alternance (par exemple).


Maintenant il faut se rendre compte que pour générer la partie gauche du clavier sans poser de contraintes, on a 15! possibilités par groupe de lettre (> 10^12). Si on pose que les lettres de la rangée de repos sont les lettres qui ont la plus grande fréquence dans l’ordre croissant en partant de l’auriculaire, on a 11! (40 millions de possibilités).

Avec un peu d’astuce on peut sans doute affiner (parce que sinon ça fait de 4 000 (10^9) à 40 000 (10^10) millions, ce qui est trop long à calculer). Je pense que là on peut se servir de l’algo de la V1, à savoir le placement par «zones» en prenant en compte une CAT, ce qui limite grandement les possibilités.


Faut pas oublier que l’évaluation d’une disposition est peut-être une opération extrêmement rapide, mais tester 10^9 dispositions c’est juste pas possible. Et je pense qu’avec mon idée on est sur la bonne piste!!! Faut juste trouver d’autres astuces pour réduire le nombre de dispositions…

15/02/2013

Pour l’algorithme de la V2, je pensais à un truc du style (le roulement y occupe une place assez importante):

  • l’alternance des mains: on génère des groupes de lettres (séparé en deux sous-groupes, chacun allant sur la partie gauche ou droite du clavier). On ne garde que celles qui sont proche de 50/50
  • les roulements sur la rangée de repos: on prend les lettres les plus fréquentes de chaque groupe et on teste toutes les possibilités acceptables (on place les lettres dans l’ordre décroissant de fréquence de l’index au pouce; puis on regarde si on interchange index et majeur, majeur et annulaire, annulaire et auriculaire) et on garde la meilleure.
  • Maintenant on compare toutes les dispositions et on sélectionne 1 ou 2 meilleure(s) rangée(s) de repos par groupe, puis on garde les groupes qui ont une des X meilleures rangées de repos.
  • Pour chaque groupe, on assigne les caractères restants à un doigt. On ne garde que celle ou la charge des doigts est équilibré, tout en gardant à l’esprit que le petit doigt est «faible»
  • pour chaque doigt on garde 1 ou 2 meilleur(s) groupe(s) de lettres assigné à un doigt. Si on en prend 2, ça fait 2^5 * 2^6 = 2^11 = 2048 possibilités par groupe de lettres.
  • Tout cela nous fait 2048 combinaisons possibles dans un groupe de lettres * nombre de groupe de lettres, et on utilise le comparateur de dispositions pour trouver laquelle sera la V2.

Cette algorithme à l’avantage de pouvoir tester beaucoup de dispositions, de pouvoir varier le nombre de dispositions testées en fonction de la puissance de la machine (du coup si je trouve que l’algo est sympa je rajoute des possibilités et je le laisse tourner quelques heures).

De plus ça évite la complexité d’un algorithme génétique, c’est peut-être même plus simple que l’algorithme de Nicolas Chartier utilisé pour la V1 (mais c’est difficile à dire au pifomètre).

N’hésitez pas à me dire ce que vous en pensez, je suis sûr qu’il y a deux trois détails qui m’ont échappé!

J’y ai repéré une incohérence (je ne peux pas déterminer la meilleure disposition des lettres par doigt). D’où (en partie) mon troisième jet.

16/02/2013

Sinon pour les points «importants» pour l’algo de la V2:

  • alternance des mains (pour dégrossir)
  • roulements vers l’intérieur, surtout pour la rangée de repos
  • alternance des doigts (charge équilibrée entre les doigts)
  • le moins possible de digrammes à un doigt


Du coup si on reprend ce que j’avais dis un peu avant, je ferais:

  • prendre les meilleures rangées de repos en prenant en compte les roulements (je prend les 8 lettres les plus utilisées, ESAITNRU, on risque fortement de retomber sur ce qu’on a pour la V1 ou très très proche).
  • Ensuite on cherche les groupes de lettres qui contiennent deux sous-groupes, un allant sur chaque partie du clavier telle que la charge de la main droite soit à peu près égale à celle de la main gauche et qu’un minimum de digramme se fasse avec cette main.
  • Ensuite on essaie toutes les possibilités, on élimine celles ou la charge des doigts est incohérente, (petit doigt qui travaille plus que l’index ou le majeur…), on regarde pour les roulements ÉP et YX (vers l’intérieur), on regarde SURTOUT qu’il y ai un minimum de digrammes à un doigt.
  • Avec toutes ces possibilités, on peut faire un ensemble de dispositions qu’il faudra tester une par une avec le comparateur de disposition, qui utilisera les données utilisateurs plutôt que des règles avec un coefficient plus ou moins aléatoire…


Vos remarques, toussa…

Lbt,