Discussion :

[Gamache]

Bonjour!

Je suis en train d'essayer d'écrire un programme d'optimisation de clavier d'ordinateur. Pour faire cela, j'ai ramassé dans une liste la fréquence de chaque enchaînement de deux caractères dans un très long texte. J'ai aussi mesuré le temps moyen que prend un humain pour faire chaque combinaison de deux caractères.

Soit Tn le temps qui est pris pour faire le nième enchaînement de deux dispositions de touches et Fm la fréquence du mième enchaînement dans la langue française, je veux minimiser la somme des Tn*Fm.

Pour faire cela, je dois essayer toutes les possibilités de claviers possibles. Étant débutant en Python, je n'ai aucune idée comment faire.

Mes deux banques de données sont dans des listes. En voici un aperçu :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
frequences=["as13491", "do20541",...] #où la chaîne de caractères as est apparue 13491 fois dans le long texte et do 2054 fois
 
temps=["ho0.34985743", "go0.69043234",...]#où cela prend 0.34985743 secondes faire ho et ainsi de suite.

À partir de ces données, quelqu'un aurait un moyen efficace d'analyser intelligemment les claviers qui ont le plus de potentiel d'être la solution de ce problème d'optimisation?

Merci

Gamache

[dividee]

Je suis pas sûr de tout comprendre. Tu possèdes des statistiques sur le temps pour taper chaque digramme sur chaque disposition de clavier ? Donc, autant de tableaux "temps" qu'il y a de dispositions de clavier ?

D'après ce que je comprends de tes données, tu peux calculer le temps total pour taper le long texte comme ceci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
# convertir le tableau de fréquences en un dictionnaire
frequences = {e[:2]:int(e[2:]) for e in frequences}
# idem pour le temps
temps = {e[:2]:float(e[2:]) for e in temps}
# calculer la somme des produits
temps_total = sum(frequences[digram]*temps.get(digram, 0) for digram in frequences)

J'ai utilisé temps.get(digram,0) au lieu de temps[digram] au cas où il manquerait des statistiques sur certains digrammes. Si les statistiques sont fort incomplètes il faudrait utiliser une estimation plus réaliste que 0.

On pourrait normaliser les fréquences mais si le texte est toujours le même, le tableau de fréquences ne change pas et il n'est pas nécessaire de normaliser.

Pour aller plus loin, il faudrait que tu donnes plus de détails...

[Gamache]

Je suis pas sûr de tout comprendre. Tu possèdes des statistiques sur le temps pour taper chaque digramme sur chaque disposition de clavier ? Donc, autant de tableaux "temps" qu'il y a de dispositions de clavier ?

D'après ce que je comprends de tes données, tu peux calculer le temps total pour taper le long texte comme ceci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
# convertir le tableau de fréquences en un dictionnaire
frequences = {e[:2]:int(e[2:]) for e in frequences}
# idem pour le temps
temps = {e[:2]:float(e[2:]) for e in temps}
# calculer la somme des produits
temps_total = sum(frequences[digram]*temps.get(digram, 0) for digram in frequences)

J'ai utilisé temps.get(digram,0) au lieu de temps[digram] au cas où il manquerait des statistiques sur certains digrammes. Si les statistiques sont fort incomplètes il faudrait utiliser une estimation plus réaliste que 0.

On pourrait normaliser les fréquences mais si le texte est toujours le même, le tableau de fréquences ne change pas et il n'est pas nécessaire de normaliser.

Pour aller plus loin, il faudrait que tu donnes plus de détails...

En fait, je n'ai pas essayé toutes les dispositions de claviers.

Ce que j'ai fait, c'est que j'ai demandé à une centaine de cobayes de taper un texte qui contenait toutes les combinaisons de deux lettres avec un clavier QWERTY dans une fenêtre Tkinter qui prenait en note le temps pris pour faire chacune de ces combinaisons de deux caractères. J'ai fait la moyenne des résultats pour connaître la moyenne de temps qui est pris pour taper chaque deux caractère.

Pour la fréquence, j'ai, avec un corpus de textes, analysé avec Python la fréquence d'apparition de chaque deux caractères dans la langue française.

Ce que je veux faire, c'est essayer chaque disposition de clavier possiblement la plus rapide. Par exemple, si le programme analysait le clavier QWERTY, il calculerait le produit de la fréquence de la combinaison "aa" dans la langue française par le temps moyen pour taper la combinaison "aa". Il ajouterait à ce produit le même produit, mais pour "ab", et ainsi de suite jusqu'à "zz". Cette somme donnerait enfin un nombre quelconque. On fera ensuite la même démarche, mais avec la disposition de clavier suivante. Si le nombre donné est plus petit que celui du QWERTY, on conservera celle du nouveau à la place de la valeur associée au QWERTY. Si elle est supérieure, on conserve celle du QWERTY. Ce que nous voulons faire, c'est cet exercice, mais avec toutes les dispositions de clavier possiblement les meilleures. Par exemple, les probabilités que la lettre la moins fréquente se retrouve à l'emplacement où se trouve la touche la plus accessible sont nulles, alors essayer une telle chose serait inutile et contribuerait à la lenteur.

J'espère que c'est bien expliqué...

Merci

Clement Gamache

[dividee]

Si je comprends bien, ce que tu as mesuré c'est le temps pour taper une séquence de deux touches. Par exemple, le temps mesuré pour taper WE sur un clavier QWERTY correspondrait au temps pour taper ZE sur un clavier AZERTY ?

Par exemple, si le programme analysait le clavier QWERTY, il calculerait le produit de la fréquence de la combinaison "aa" dans la langue française par le temps moyen pour taper la combinaison "aa". Il ajouterait à ce produit le même produit, mais pour "ab", et ainsi de suite jusqu'à "zz". Cette somme donnerait enfin un nombre quelconque.

C'est ce nombre que calcule mon code précédent, pour le clavier de base je suppose (QWERTY donc).

C'est un problème d'optimisation: tu as un fonction dont le domaine est l'ensemble des dispositions de clavier, et l'ensemble d'arrivée est l'ensemble des réels, qui correspond à la valeur dont tu as détaillé le calcul. Une disposition de clavier peut être encodée, par exemple, comme une chaîne de longueur 26 contenant une permutation de toutes les lettres de l'alphabet (ou bien une liste contenant une permutation des entiers entre 1 et 26).

Sans tenir compte du fait que les touches associées aux lettres peuvent ne pas être les mêmes dans toutes les dispositions de clavier (comme le M entre QWERTY et AZERTY), il reste tout de même 26! combinaisons possibles, ce n'est donc pas réaliste de les essayer toutes, mais il existe des tas d'algorithmes d'optimisations qui peuvent s'appliquer pour trouver une solution approchée: algorithmes gloutons (descente de gradient), algorithmes génétiques, recuit simulé, etc.

Un exemple d'algorithme glouton: tu pars de ton clavier d'origine, tu calcules sa valeur (la somme des produits des fréquences et des temps, qu'il faut minimiser). Tu essaies toutes les façons possibles de permuter deux touches de ce clavier (si je ne trompe pas, il y 325 possibilités) en calculant à chaque fois la valeur du clavier résultant. Tu gardes celui qui a la valeur la plus petite. Ensuite tu recommences au début, en partant de ce clavier-là: tu testes toutes les permutations de 2 touches, etc. Cela jusqu'à ce que tu sois bloqué, c'est à dire qu'aucune permutation ne te permette d'améliorer le clavier actuel. Tu peux relancer l'algorithme plusieurs fois à partir de disposition de claviers aléatoires pour voir si tu ne trouves pas une meilleure solution.

Ce n'est sans doute pas la méthode la plus puissante, mais c'est certainement une des plus facile à coder. Si tu veux utiliser une méthode plus avancée, tu peux aussi demander sur le forum Algorithmes s'ils n'ont pas une méthode à te conseiller.

[Gamache]

Un exemple d'algorithme glouton: tu pars de ton clavier d'origine, tu calcules sa valeur (la somme des produits des fréquences et des temps, qu'il faut minimiser). Tu essaies toutes les façons possibles de permuter deux touches de ce clavier (si je ne trompe pas, il y 325 possibilités) en calculant à chaque fois la valeur du clavier résultant. Tu gardes celui qui a la valeur la plus petite. Ensuite tu recommences au début, en partant de ce clavier-là: tu testes toutes les permutations de 2 touches, etc. Cela jusqu'à ce que tu sois bloqué, c'est à dire qu'aucune permutation ne te permette d'améliorer le clavier actuel. Tu peux relancer l'algorithme plusieurs fois à partir de disposition de claviers aléatoires pour voir si tu ne trouves pas une meilleure solution.

Ce n'est sans doute pas la méthode la plus puissante, mais c'est certainement une des plus facile à coder. Si tu veux utiliser une méthode plus avancée, tu peux aussi demander sur le forum Algorithmes s'ils n'ont pas une méthode à te conseiller.

Oui, c'est exactement ce que tu croyais. L'algorithme glouton a l'air d'être adéquat pour la tâche que j'ai à accomplir, mais est-il possible de l'appliquer avec Python?

Si oui, ce serait parfait, car je pourrais m'inspirer de claviers déjà existants comme le Dvorak ou le Colemak pour identifier le clavier parfait.

[dividee]

Ben oui, bien sûr qu'on peut l'appliquer avec Python.

Voici un bout de code pour t'aider à démarrer:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
frequences=["as13491", "do20541",...] # à compléter
temps=["ho0.34985743", "go0.69043234",...] # à compléter
 
# conversion en dictionnaires
freq = {e[:2]:int(e[2:]) for e in frequences}
time = {e[:2]:float(e[2:]) for e in temps}
 
qwerty = "qwertyuiopasdfghjklzxcvbnm" # disposition du clavier d'acquisition des données
 
# une disposition de clavier (layout) est une liste d'entiers:
#    - la position dans la liste indique la touche
#    - la valeur est l'indice dans la chaîne qwerty qui contient la lettre
 
def layout_to_string(layout):
    return ''.join(qwerty[i] for i in layout)
 
def string_to_layout(s):
    return [qwerty.index(c) for c in s]
 
#exemple:
layout = string_to_layout('azertyuiopqsdfghjklwxcvbnm') # c'est un peu foireux à cause du M qui n'est pas à la bonne place, mais bon...
 
def score(layout):
    "calcule le score d'une disposition de clavier"
    result = 0.0
    for i in range(len(layout)):
        for j in range(len(layout)):
            keys = qwerty[i] + qwerty[j]  # touches appuyées
            digram = qwerty[layout[i]] + qwerty[layout[j]]  # lettres générées
            result += freq[digram] * time[keys]
    return result