Forum bépo

Forum des utilisateurs du bépo

Vous n'êtes pas identifié(e).

#1 23/5/2014 16:00:42

lawrent
Membres
Inscription : 2/2/2013
Messages : 129

[pantoufle] À propos de "l'algorithme"

Je dupplique ici un message que j'ai déjà posté ailleurs concernant ce que je vois comme étant l'algorithme pour la V2. À lire les commentaires par-ci par-là j'ai l'impression que certains entendent faire une partie du boulot à la main et basé sur plusieurs heuristiques (par exemple, si on devait faire comme pour la V1: mettre toutes les voyelles à gauche et la ponctuation sous les index).

J'aimerais donc proposer une approche moins arbitraire pour la V2 qui se base sur des paramètres précis. Elle est très inspirée de http://mtgap.bilfo.com/keyboard.html .

Tout le monde est d'accord là-dessus: on veut un clavier qui minimise l' "effort de frappe" basé sur les doigts utilisés, les digrammes et trigrammes fréquents. Voilà donc l'algo (ou plutôt le modèle) que je propose. Par simplicité on va supposer que les touches maj, altgr et autres sont fixes et qu'on ne fait que décider de l'emplacement des caractères sur les 35 touches centrales:
- on associe à la touche x du clavier une valeur correspondant à sa pénalité et on stocke ca dans un tableau V1[x] (c'est la carte d'accessibilité http://bepo.fr/wiki/Carte_d%27accessibi … s_touches)
- on fait pareil pour les digrammes: chaque succession de touches xy on associe une valeur stockée dans un tableau V2[x][y]
- pareil pour les successions de 3 touches: V3[x][y][z] contient la valeur de la séquence de touches xyz.

De l'autre côté on suppose qu'on a un corpus qui a été filtré de telle sorte qu'il soit réduit à 35 caractères (on supprime les touches non présentes ou on remplace û par ^u, etc). Ses stats sont résumées dans 3 tableaux correspondant aux tableaux de pénalité:
- F1[x] contient la fréquence d'apparition de la lettre x
- F2[x][y] contient la fréquence d'apparition de la succession de lettres xy
- F3[x][y][z], vous devinez ce qu'il y a dedans...

Étant donnés ces paramètres, on cherche la disposition qui minimise la pénalité totale du corpus. Pour ca on va dire que f est une permutation des nombres 1,2,...,35 qui place chaque caractère quelque part sur le clavier. On cherche la permutation f telle que

SUM_x F1[f(x)] * V1[x]  +  SUM_x,y F2[f(x)][f(y)] * V2[x][y]  +  SUM_x,y,z F3[f(x)][f(y)][f(z)] * V3[x][y][z]

soit minimal. Pour résoudre ce problème d'optimisation on passe par l'algorithme évolutif proposé sur la page du MTGAP:
- on part de 10 dispositions aléatoires
- sur chacune de ces dispositions on échange la position de 2 lettres tirées au hasard: ca fait 20 dispositions en tout
- on évalue les 20 dispositions et on retire les 10 qui ont le score le plus élevé et on garde en mémoire celle qui a le score le plus bas
- on répète jusqu'à ce qu'une disposition attent le score le plus bas pendant 10 rounds consécutifs.

Voilà. C'est tout. On pourrait compliquer le modèle en tenant compte de la place des modificateurs et en cherchant éventuellement à optimiser la couche altgr en même temps mais dans un premier temps on ne doit pas se compliquer la vie inutilement. On a un modèle et un algo qui trouve la disposition optimale suivant les paramètres V1, V2, V3, F1, F2, F3 qu'on lui donne. Si la disposition qu'il nous en ressort est pourrie, ca veut dire que les paramètres qu'on lui a donnés ne sont pas réalistes. Toute la partie délicate sera de faire de l'essai-erreur pour trouver des valeurs aussi réalistes que possibles. Notons également qu'on devra choisir quels caractères on place dans les 35. Comme premier choix je prendrais les 35 les plus fréquents du corpus.

Pour se simplifier la vie, je propose qu'on se restreigne à 5 scores différents pour les di/trigrammes: MAUVAIS, mauvais, neutre, bon, BON. Neutre a une pénalité de 0, les autres seront à fixer. Comme il y a 35^2 digrammes et 35^3 trigrammes je propose qu'on n'associe une pénalité qu'aux di/trigrammes bons/mauvais qui nous viennent en tête et que tous les autres soient mis à 0.

Vous en pensez quoi? Vous avez des trucs à reprocher/ajouter?

Dernière modification par lawrent (23/5/2014 16:02:46)

Hors ligne

#2 23/5/2014 22:29:06

ariasuni
Admin
Lieu : France, Seine-Saint-Denis (93)
Inscription : 2/11/2012
Messages : 579
Site Web

Re : [pantoufle] À propos de "l'algorithme"

Comme dit précédemment, je ne suis pas trop d’accord avec le fait de comptabiliser à la fois touches, digrammes et trigrammes (et je ne suis pas encore sûr moi-même de la meilleure façon de procéder) ainsi que le modèle de générations de nouvelles dispositions. Pour le reste, c’est plutôt intéressant, mais j’ai pas encore eu le temps de me pencher dessus étant donné que je m’occupe des dépôts. Je discuterais volontiers plus en détail à ce moment-là.


Écrit selon l’orthographe de 1990.
Ma page utilisateur, mon site web.

Hors ligne

#3 24/5/2014 05:14:49

Laurent
Membres
Inscription : 9/8/2009
Messages : 695
Site Web

Re : [pantoufle] À propos de "l'algorithme"

lawrent a écrit :

Vous en pensez quoi? Vous avez des trucs à reprocher/ajouter?

Je te suis complètement sur l’algo.

Note que c’est un algo optimisé pour la rapidité d’évaluation d’une disposition, mais qu’il y a des trucs qu’il vaudrait mieux faire par calcul avant.

lawrent a écrit :

Par simplicité on va supposer que les touches maj, altgr et autres sont fixes et qu'on ne fait que décider de l'emplacement des caractères sur les 35 touches centrales:
- on associe à la touche x du clavier une valeur correspondant à sa pénalité et on stocke ca dans un tableau V1[x] (c'est la carte d'accessibilité http://bepo.fr/wiki/Carte_d%27accessibi … s_touches)

Si on considère les 35 touches centrales plus la barre espace, ça fait 36.
Si on considérait aussi les positions en Maj, AltGr et AltGr+Maj, ça ferait 36×4 = 144.
Ce n’est pas la même chose d’enchaîner les touches [A] et [L] que d’enchaîner [Maj]+[A] et [AltGr]+[L] ou [Maj]+[A] et [Maj+[L] (pas du même côté du clavier, on est sensé utiliser pour chaque la touche [Maj] opposée).

lawrent a écrit :

- on fait pareil pour les digrammes: chaque succession de touches xy on associe une valeur stockée dans un tableau V2[x][y]

Là, en ne considérant que les positions directes ce sont les arrangements de 2 parmi 36, soit 1260, sauf erreur.
Si on considérait aussi les positions en Maj, AltGr et AltGr+Maj, ce serait les arrangements de 2 parmi 144, soit 20592.

lawrent a écrit :

- pareil pour les successions de 3 touches: V3[x][y][z] contient la valeur de la séquence de touches xyz.

Là, en ne considérant que les positions directes ce sont les arrangements de 3 parmi 36, soit 42840.
Si on considérait aussi les positions en Maj, AltGr et AltGr+Maj, ce serait les arrangements de 3 parmi 144, soit 2924064. Bon, ça consommerait quand même en mémoire. Enfin de nos jours, la mémoire se compte en gigas, par contre, ça réduit les chances que le processeur trouve les valeurs dans son cache.

À mon sens, il y a un algo avant l’algo pour calculer la pondération de chaque possibilité (parce que bon, le faire à la main…).
C’est là qu’on doit faire entrer et pondérer nos critères (roulement facile, alternance, digramme difficile à une main, digramme à un doigt…).

Note que si on travaille avec des triplets de touches, on peut préadditionner les valeurs pour les touches elles-mêmes et les couples de touches dans le tableau des triplets et ne considérer que celui-ci (les deux premières touches pour le contexte et la troisième pour la touche tapée actuellement), enfin à condition de gérer en plus des touches le cas [rien] (ça permet de traiter le premier et le second caractère d’un texte ou d’une ligne si l’on considère qu’on réinitialise après [Entrée]) et le cas [un caractère compliqué qu’on ne place pas encore pour l’instant]. Du coup, les arrangements, c’est avec 38 (1406 arrangements) au lieu de 36 et 146 (3048480 arrangements) au lieu de 144.

Donc, en fait, ça nous ferait trois algos.

En préparation,
– un algo pour factoriser un corpus en trigrammes (facile, sauf qu’il faut s’emmerder avec la taille variable de l’UTF-8),
– un algo pour pondérer le « coût » de chaque triplet de touches (j’ai des idées sur ce point).
Et finalement,
– un algo génétique pour faire évoluer une disposition à partir des données fournies par les deux algos précédents.

Dernière modification par Laurent (24/5/2014 06:05:07)

Hors ligne

#4 27/5/2014 17:10:10

medug
Membres
Inscription : 22/12/2010
Messages : 42
Site Web

Re : [pantoufle] À propos de "l'algorithme"

Le systéme de cartographie de difficultés des touches prises une par une est bien mais n'est pas suffisant selon moi.
Il faudrait avoir une cartographie de difficulté des touches par rapport à une seule autre.
Par exemple, prenons la lettre C en Bépo. Quels efforts dois-je fournir pour passer sur la même main à une lettre suivante comme le L, le R, le N ou le H.
Je pense que c'est de là que l'on retire une utilité aux digrammes; voir des trigrammes modifié en digramme en enlevant la lettre du milieu.
Personnellement, je parle d'efforts de transition, qui prend en compte en quelque sorte le roulement.
Il faut une carte par touche prise en compte plus la cartographie globale.
(Implicitement ce que je viens de dire signifie qu'il faut optimiser l'alternance des mains; ce qui mécaniquement fait baisser l'utilisation d'un même doigt consécutif.Bref)
On additionne le coût des mouvements et le coût des transitions de digramme lorsqu'il se fait sur la même main. On peut aller jusqu'au trigramme modifié en digramme.
Pas besoin de pondérer quoique ce soit selon moi, car plus les occurences arrivent plus elles "coutent".

Pour le Bvofrak, c'est ce que j'ai fait mais très empiriquement et par tatonnement sur excel, ne sachant pas programmer pour tester toutes possibilités.

******************
Si l'on partait d'un clavier vierge à construire,je pense qu'il faudrait prendre en compte au minimum les touches Maj, Entrée et Effacer.
1 majuscule par phrase, soit ≃2,4% des frappes, ≃70% des majuscules touchent une consonne
2-3% de faute de frappe, 0,8% pour Entrée(retour chariot).
Sauf que l'on part d'un clavier (mal foutu) existant.

Donc ne compliquez pas le problème sachant aussi que c'est le corpus de texte qui fait le résultat et pas seulement le calcul.


***********
Pour l'analyse fréquentiel d'un texte il existe un logiciel bien fait :
http://www.sttmedia.com/wordcreator

wortgenerator6-max-en.gif


BvoFRak : la disposition qui vous donne 1 coup 2 main passe en version 1 béta.

Hors ligne

#5 28/5/2014 11:35:59

ariasuni
Admin
Lieu : France, Seine-Saint-Denis (93)
Inscription : 2/11/2012
Messages : 579
Site Web

Re : [pantoufle] À propos de "l'algorithme"

Hubert a écrit :

La frappe avec une seule main de 15 mots de 5 lettres
est elle plus lente ou plus rapide que des mots répartis sur les deux mains ?

Clairement, pour moi, alité ou delta sont plus faciles à écrire que aboie ou boyau.

Hubert a écrit :

Méthode de frappe : sur un clavier azerty décalé je constate que les repères sous les index sont mal placés
ils ne devraient pas être à  F et J
mais à G et K

On a déjà discuté de ça, et on était tous plus ou moins d’accord sur le fait que non parce que sinon la disposition ne marchait pas sur les claviers ergonomiques. Après je ne dis pas que ça ne peut pas être rediscuté, mais à mon avis on va retomber sur la même conclusion.

Ça ne t’empêche pas de tester une disposition de ce type, d’ailleurs normalement on pourra réutiliser les outils de la v2 pour le faire.


Écrit selon l’orthographe de 1990.
Ma page utilisateur, mon site web.

Hors ligne

#6 29/5/2014 13:25:39

rat bière sé
Le vilain admin
Inscription : 15/3/2012
Messages : 809

Re : [pantoufle] À propos de "l'algorithme"

Modération Merci d'arrêter de faire dériver les discussions : le sujet c'est l'algorithme, point barre.
Toute discussion concernant la disposition doit se faire ailleurs.


GNU/Linux depuis 2/2012 : Ubuntu→ Xubuntu 4/12→ Debian (Xfce) 10/12 + Cubian 10/13
BOINC (World Community Grid) depuis 4/11 - BÉPO depuis 3/12 - Vapoteur depuis 10/13
Claviers Cherry G80-3000 (MXClear), TIPRO MID KM128A (MXBlack) Noppo MID 87 ANSI (MXRed)
Kensington Orbit trackball (à gauche), Wacom Intuos3 A4

Hors ligne

Pied de page des forums