Mind... - Tag - PHP

Afficher des discussions

Florent Bruneau — Thu, 01 Nov 2007 17:24:00 +0100

Lorsqu'un logiciel a pour vocation d'afficher des discussions, on attend de sa part qu'il nous permette de voir simplement qui répond à qui, dans quel contexte... Ce n'est pas toujours ce qui est le mieux fait. Par exemple, les programmes de fora en ligne à la mode (phpBB par exemple) affiche les discussion comme une succession de rectangles juxtaposés et seul le contenu du message permet de voir qu'il en cite un autre. D'autres logiciels comme Mail.app ont ce défaut et parfois la fâcheuse manie de ne pas vouloir corriger ce problème.

L'affichage de l'arborescence dans Banana est une des fonctionnalités clés... et elle va beaucoup changer dans la prochaine version.

Une ligne par entrée

La solution habituelle pour afficher l'arborescence est d'utiliser un message par ligne de telle, des + ou - pour ouvrir ou fermer les noeuds. C'est la solution actuelle de banana.

Avec cette solution, on perd très rapidement en lisibilité : dès que la discussion dépasse une vingtaine de messages, l'arborescence devient très haute et plus ça va, plus le titre dérive vers la droite rendant parfois le lien inaccessible. Lorsqu'il y a un troll, il est de fait très courant que certains nouveaux messages se trouvent perdus plusieurs pages en arrière dans l'arborescence, ou que sur certains navigateurs, il soit difficile d'y accéder. De plus l'interface se trouve souvent surchargée, à la limite de la lisibilité : c'est dur de faire tenir un maximum d'informations en un minimum de place en gardant la lisibilité de l'ensemble.

Une solution plus visuelle

Je ne sais pas combien de personnes connaissent MacSoup. Il s'agit d'un petit client NNTP pour MacOS, qui en soit n'a pas beaucoup d'intérêt (il est payant et est relativement limité). Le principal atout de MacSoup est son interface de visualisation des threads (les utilisateurs diront qu'il y a bien plus que l'interface graphique, mais également l'interface clavier etc...). On trouve sur internet quelques captures d'écran en cherchant dans les moteurs de recherche d'image :

Cette interface est compacte, visuelle et permet d'accéder rapidement à n'importe quel message du thread. Pour la prochaine version de Banana, je me suis fortement inspiré de cette interface pour réécrire de 0 l'affichage de l'arborescence. Ceci donne :

Il s'agit de la même discussion que précédemment. On voit donc ici facilement l'arborescence. Lorsqu'un message est non lu, la branche à laquelle il est attaché est noire au lieu de grise ce qui permet de l'identifier du premier coup d'oeil. Les couleurs de fond des noeuds (une idée de Falco) sont obtenue à partir d'un hash quelconque sur l'émetteur et permettent donc d'identifier les messages envoyés par la même personne. Lorsqu'on laisse la souris sur un noeud, le nom de l'expéditeur et l'heure du post s'affichent (malheureusement le pointeur de la souris n'apparaît pas sur la capture d'écran)... et bien sûr quand on clique sur un noeud, on va sur le message correspondant.

Lorsqu'on est sur un message, on garde également la vue du thread ce qui permet de toujours savoir où on est dans la discussion :

Il y a encore un peu de travail à faire pour améliorer les performances de la génération des arbres et pour augmenter sa compacité (éviter les branches qui descendent très bas alors qu'elles auraient pu trouver leur place dans le l'espace vide disponible).

La Banane et l'escargot

Florent Bruneau — Mon, 07 May 2007 17:44:00 +0200

La release de Banana 1.6 en même temps que celle de plat/al 0.9.14 a mis en évidence un certain nombre de faiblesses dans Banana. En particuliers la génération du spool (mise en cache de l'arborescence des messages) et des flux RSS s'est révélé extrêmement lourde pour plusieurs raisons :

l'accès aux mbox des Mailing-Lists nécessite d'appel du mbox-helper, et donc un fork... opération lourde, qui répétée plusieurs fois par mbox devient rapidement très lourde lorsqu'on a plusieurs dizaines de Mailing-Lists.
le traitement des données par PHP est loin d'être immédiats... et il y a clairement des goulots d'étranglement dans le code.

C'est pour ces raisons que j'ai passé Banana au profiler, c'est à dire que j'ai analysé l'exécution de Banana à l'aide d'un outil qui permet de tracer l'exécution du programme et mettant un accent particuliers sur le temps d'exécution de chaque fonction. L'outil que j'ai trouvé pour faire ça est xdebug, utilisé conjointement à KCacheGrind.

Forks

Je dois avouer que lorsque j'avais fait mes tests, je n'avais pas plusieurs centaines de Mailing-Lists à traiter... et je ne m'attendais pas à ce qu'une fois passée en production le script de mise à jour des flux RSS puisse prendre toutes les ressources de la machine pendant plusieurs minutes. Il a donc fallu sérieusement restructurer la gestion des accès aux Mailing-Lists pour restreindre au maximum le nombre d'accès au mbox-helper (un petit programme écrit en C qui se charge de tous les accès aux mbox), et, en cas d'accès, limiter au maximum le temps passer sur le mbox-helper.

Donc désormais le mbox-helper n'est plus appelé que si la mbox a changé depuis le dernier passage (le changement étant détecté par la taille du fichier). Ce qui permet donc de supprimer le lancement d'environ 500 mbox-helper lors des rafraîchissements des spools (en effet, un nombre négligeable de Mailing-List aura des nouveaux messages lors du passage du script toutes les 5, 10 ou 20 minutes). Ajouté à cela la correction d'un bug qui faisait que l'appel au mbox-helper oubliait de spécifier l'offset où chercher le message à traiter et qui forçait donc le mbox-helper à relire la totalité de la mbox, on peut se permettre de supposer que la prochaine version de Banana sera plus efficace pour la gestion des mbox.

Array_shift

Piles

Il est souvent extrêment pratique d'utiliser une pile de données. Cela permet de traiter les informations dans l'ordre de la pile sans excès de mémoire puisque chaque élément est dépilé avant d'être traité. C'est une technique que j'aime particulièrement lorsque j'ai une suite de lignes à traiter : je prend un tableau contenant une ligne par entrée et je le parcours avec array_shift qui permet de dépiler le premier élément du tableau. On obtient ainsi un code de la forme

[php]
while (!is_null($line = array_shift($lines))) {
    do_something($line);
}
do_something($lines);

Un foreach peut très bien faire la même chose, mais on perd les avantages de la piles. Avec cette structure, pour avoir le même comportement que la boucle précédente, il faut ajouter un unset() :

[php]
foreach ($lines as $key=>&$value) {
    do_something($line);
    unset($lines[$key]);
}
do_something($lines);

Certes le foreach sera sensiblement plus rapide que le while/array_shift() car il comprend un appel de fonction à chaque itération, mais on peut s'attendre raisonnablement à ce que cet appel soit en O(1), et ait donc un coût négligeable.

Profiler

Là où il y a un problème c'est que le profiler m'indique que array_shift prend 57% du temps d'exécution de Banana. Ces 57% sont partagés entre 80000 appels à la fonction, mais le plus marquant c'est que parmi ces 80000 appels, ce ne sont que 24000 d'entre eux qui prennent la quasi-totalité du temps. Pourquoi ces appels particuliers sont-ils si lourd alors que les 60000 autres ont un coût parfaitement négligeable.

La seule différence entre ces deux cas d'appels c'est que les lourds traitent un énorme tableau de 24000 lignes, alors que les légers traitent un grand nombre de petits tableaux de quelques dizaines de lignes chacun. Il est donc extrêmement clair que array_shift n'est pas une fonction en O(1)... J'ai donc changé la structure de code qui reflétait la structure de données par une simple boucle qui perd en lisibilité dans ce patch. Après ce changement, les 60000 array_shift restant ne prennent que 0.16% du temps d'exécution de Banana...

Deux approches...

Florent Bruneau — Wed, 28 Mar 2007 00:52:00 +0200

Les deux APIs avec lesquelles j'ai eu le plus la chance de travailler sont celle de Qt et celle de PHP... il n'y a pas à dire, entre ces deux bibliothèques, c'est comme le jour et la nuit.

L'API de Qt est intuitive et est conçue pour l'être. Si je veux avoir l'âge du capitaine, je ferais toujours capitaine->age(), et si je veux définir son âge, ce sera capitaine->setAge(42). Cette API est tellement prévisible qu'au bout de quelques jours d'utilisation, on n'utilise la documentation que pour chercher de nouvelles fonctionnalités, mais très rarement pour chercher des fonctions courantes. En plus, ce qui est remarquable, c'est qu'au fur et à mesure des versions de Qt, l'accent est mis sur la simplification de l'API... Qt 4 est bien plus intuitive que Qt 3 qui est pourtant déjà très facile à utiliser.

La qualité de la documentation de Qt y est également pour quelque chose : toutes les méthodes sont documentées, avec la plupart du temps un exemple. Le tout étant très facilement accessible grâce à l'assistant, un petit programme qui permet de consulter la documentation en intégrant des outils pour naviguer simplement entre les pages.

Par contre, je ne sais pas pourquoi, mais en PHP, l'API est incohérente... l'exemple le plus simple est sans doute celui du remplacement et de la recherche dans une variable. Si, par exemple, je veux rechercher un élément :

[php]
//Dans une chaîne de caractères :
strpos($string, $findme);
//Dans un tableau, c'est l'inverse :
in_array($findme, $array);
array_search($findme, $array);

Si je veux faire un remplacement dans une chaîne de caractères :

[php]
strtr($string, $search, $replace);
str_replace($search, $replace, $string);
preg_replace($search, $replace, $string);

Chic ! Grâce à ça, même si je connais le nom de la fonction à utiliser, je suis quasiment forcé à chaque fois d'aller regarder dans la documentation de PHP (ce que j'ai fait pour écrire ce paragraphe, sinon j'aurais 'forcément' inversé les arguments)... heureusement que celle-ci est bien faite et permet de trouver rapidement les fonctions dont on connaît le nom.

Quand est-ce que PHP se décidera à revoir son API pour qu'elle soit aussi intuitive que celle de Qt ? Malheureusement, sans doute jamais : il faut garder (autant que possible) la compatibilité avec les versions précédentes de PHP. Dommage, parce qu'à mon avis, si PHP continue à étoffer son API sans la rendre cohérente, sa popularité va diminuer progressivement dans les années qui viennent.

Soundex Français

Florent Bruneau — Thu, 15 Mar 2007 18:06:00 +0100

Pour faire une recherche phonétique, on utilise souvent ce qu'on appelle une transcription soundex des mots. C'est une réécriture du mot, dans un alphabet restreint et sur un nombre de caractères restreint également. La plupart des algorithmes qu'on peut trouver sur internet sont conçus uniquement à la langue anglaise. Pour utiliser la recherche phonétique en français, il faut donc adapter cet algorithme.

L'implémentation française la plus courante utilise l'algorithme décrit par Frédéric Brouard. Malheureusement cet algorithme ne me satisfait pas vraiment, car il n'est finalement pas très adapté à langue française.

En effet cet algorithme a pas mal de défauts :

il est très aléatoire dans le cas de dédoublement de consonnes. Par exemple, il ne permet de trouver que bananne (soundex BNN) est une approximation de banane (soundex BN)
il est très peu sélectif sur les voyelles. Par exemple poulpe et palpa ont le même soundex (PLP) alors que pour moi, poulpe et palpa sont deux mots éloignés, malgré leur consonnes communes. Par contre, il ne reconnaîtra pas Aymeric (soundex AYMR) comme étant un homophone de Emeric (soundex EMRC)...
il n'est pas vraiment capable de distinguer les conjugaisons. Par exemple palper (soundex PLPR) et palpé (soundex PLP) sont éloignés l'un de l'autre.

J'ai donc réalisé une nouvelle implémentation de soundex qui est plus adaptée (à mon sens) à la langue française. Je n'ai évidemment pas pour ambition de réaliser une solution parfaite (ce qui est impossible à faire à partir d'un système automatisé sans dictionnaire).

Algorithme

Mon algorithme, comme je l'ai déjà dit, est une adaptation de celui de Frédéric Brouard. Il se compose de 2 étapes principales :

le préformatage, qui consiste à transformer le chaîne de caractère brute, en une chaîne analysable.
l'analyse de la chaîne, et la recherche de entités phoniques élémentaires qui la composent

Préformatage

Le préformatage est extrêmement simple :

On converti la chaîne en majuscule
On converti chaque caractère accentué vers son caractère non-accentué correspondant
On filtre pour ne conserver que les lettres (de A à Z)

Ainsi après ce premier filtrage, Mac-Cartney devient MACCARTNEY et palpé sera PALPE

Traitement des données

Le traitement des données consiste à reconnaître les sonorités. Pour ceci on utilise la table de conversion suivante qui associe à chaque sonorité complexe un caractère :

Combinaison	Caractère
G (prononcé GUE), C (prononcé Q), CK, K, QU, Q	K
CH, SH, SCH	9
ST	T
PF (en début de mot), PH	F
Z (en fin de mot)	ZE
Z, ZZ, C (prononcé SE)	S
G (prononcé JE)	J
EAU, AU	O
IN, UN, AIN, EIN (proncés UN)	1
AON, AOM, EN, AN (prononcés EN)	A
EY, EI, AY, AI, OE, OEU, EU, ER	E
OI	O
ILLE, I	Y
OU, OW	U
ON, OM	O
KN (en début de mot)	N

Une fois qu'on a cette table de correspondances (elle n'est peut-être pas exhaustive... je n'hésiterais pas à l'améliorer), on applique toutes les modifications, on supprime les lettres qui sont présentes en doublon et finalement on supprime les H restants. Il faut également supprimer les caractères muets en fin de mot. En français, ce seront les X, T, D, S (et le L qui les précède si il existe) ou les E.

Ensuite, il faut faire un nettoyage sur la chaîne de caractère. Ce nettoyage consiste à rechercher les phonèmes importants et à supprimer les caractères muets ou peu audibles : on veut identifier ce qui fait la particularité d'une syllabe. Frédéric Brouard considère que toutes les voyelles (exceptés les Y précédés d'une voyelle) placées autre part qu'en début de mot sont insignifiantes... ça me paraît le gros point faible de sa méthode. Personnellement j'ai essayé d'identifier une liste de sonorité dominantes. Voici celles que j'ai actuellement :

Sonorité	Informations
K, T, P	Ce sont les consonnes qui sont très marquées, qui rythment le mot
A, U, O, 1	Ce sont les son qu'on entend le mieux, contrairement aux I ou aux E qui mettent plus en avant les consonnes. Le A est à mon avis particulier, car il est faible mais suffisamment marquant pour effacer des consonnes comme le R
Y	Y n'est marquant que lorsqu'il a un rôle de consonne : quand il permet de lier deux parties du mot, comme dans ''voyelle'', où il lie le ''vo'' et le ''elle''. Il est donc important lorsqu'il est encadré par une ou des voyelles. Dans les autres cas, c'est une voyelle faible
L	Contrairement aux K, T et P, le L permet d'adoucir le mot, en particulier lorsqu'il sert de liaison entre une consonne et une voyelle. Il est donc important de le conserver

Ces choix sont relativement arbitraires. Le comportement de l'algorithme est alors simple :

Si une voyelle est liée à une consonne de liaison (qui fait le lien entre la voyelle et une autre consonne, c'est souvent le cas du L ou du R, on exclut de ce cas les consommes fortes)
Si en plus il s'agit d'une voyelle forte
- alors, on supprime la consonne de liaison et on garde la voyelle

Ensuite, on supprime les voyelles faibles (sauf si elles commencent le mot). Pour cette suppression, on considère le A comme une voyelle faible.

Pour terminer on coupe la chaîne obtenue à 4 caractères (mais il est parfaitement envisageable de prendre un soundex sur plus (ou moins) de caractères. Simplement, dans la plupart des cas, 4 caractères suffisent amplement à avoir un mot significatif.

Implémentation

Mon implémentation en PHP est téléchargeable ici. Elle est testable plus bas dans cette même page. Voici le code de la fonction soundex_fr (je ne garantis pas que le code disponible sur cette page reste constamment à jour, contrairement au lien de téléchargement) :^[1]

[php]
function soundex_fr($sIn) 
{ 
    static $convVIn, $convVOut, $convGuIn, $convGuOut, $accents; 
    if (!isset($convGuIn)) { 
        $accents = array('É' => 'E', 'È' => 'E', 'Ë' => 'E', 'Ê' => 'E', 
                    'Á' => 'A', 'À' => 'A', 'Ä' => 'A', 'Â' => 'A', 'Å' => 'A', 'Ã' => 'A', 
                    'Ï' => 'I', 'Î' => 'I', 'Ì' => 'I', 'Í' => 'I', 
                    'Ô' => 'O', 'Ö' => 'O', 'Ò' => 'O', 'Ó' => 'O', 'Õ' => 'O', 'Ø' => 'O', 
                    'Ú' => 'U', 'Ù' => 'U', 'Û' => 'U', 'Ü' => 'U', 
                    'Ç' => 'C', 'Ñ' => 'N', 'Ç' => 'S', '¿' => 'E', 
                    'é' => 'e', 'è' => 'e', 'ë' => 'e', 'ê' => 'e', 
                    'á' => 'a', 'à' => 'a', 'ä' => 'a', 'â' => 'a', 'å' => 'a', 'ã' => 'a', 
                    'ï' => 'i', 'î' => 'i', 'ì' => 'i', 'í' => 'i', 
                    'ô' => 'o', 'ö' => 'o', 'ò' => 'o', 'ó' => 'o', 'õ' => 'o', 'ø' => 'o', 
                    'ú' => 'u', 'ù' => 'u', 'û' => 'u', 'ü' => 'u', 
                    'ç' => 'c', 'ñ' => 'n'); 
        $convGuIn  = array( 'GUI', 'GUE', 'GA', 'GO', 'GU', 'SCI', 'SCE', 'SC', 'CA', 'CO', 
                            'CU', 'QU', 'Q', 'CC', 'CK', 'G', 'ST', 'PH'); 
        $convGuOut = array( 'KI', 'KE', 'KA', 'KO', 'K', 'SI', 'SE', 'SK', 'KA', 'KO', 
                            'KU', 'K', 'K', 'K', 'K', 'J', 'T', 'F'); 
        $convVIn   = array( '/E?(AU)/', '/([EA])?[UI]([NM])([^EAIOUY]|$)/', '/[AE]O?[NM]([^AEIOUY]|$)/', 
                            '/[EA][IY]([NM]?[^NM]|$)/', '/(^|[^OEUIA])(OEU|OE|EU)([^OEUIA]|$)/', '/OI/', 
                            '/(ILLE?|I)/', '/O(U|W)/', '/O[NM]($|[^EAOUIY])/', '/(SC|S|C)H/', 
                            '/([^AEIOUY1])[^AEIOUYLKTPNR]([UAO])([^AEIOUY])/', '/([^AEIOUY]|^)([AUO])[^AEIOUYLKTP]([^AEIOUY1])/', '/^KN/', 
                            '/^PF/', '/C([^AEIOUY]|$)/',  '/E(Z|R)$/', 
                            '/C/', '/Z$/', '/(?<!^)Z+/', '/H/', '/W/'); 
        $convVOut  = array( 'O', '1\\3', 'A\\1', 
                            'E\\1', '\\1E\\3', 'O', 
                            'Y', 'U', 'O\\1', '9',- 
                            '\\1\\2\\3', '\\1\\2\\3', 'N', 
                            'F', 'K\\1', 'E', 
                            'S', 'SE', 'S', '', 'V'); 
    } 
    // Si il n'y a pas de mot, on sort immédiatement
    if ( $sIn === '' ) return '    '; 
    // On supprime les accents- 
    $sIn = strtr( $sIn, $accents); 
    // On met tout en minuscule- 
    $sIn = strtoupper( $sIn ); 
    // On supprime tout ce qui n'est pas une lettre
    $sIn = preg_replace( '`[^A-Z]`', '', $sIn ); 
    // Si la chaîne ne fait qu'un seul caractère, on sort avec.
    if ( strlen( $sIn ) === 1 ) return $sIn . '   '; 
    // on remplace les consonnances primaires
    $sIn = str_replace( $convGuIn, $convGuOut, $sIn ); 
    // on supprime les lettres répétitives 
    $sIn = preg_replace( '`(.)\\1`', '$1', $sIn ); 
    // on réinterprète les voyelles 
    $sIn = preg_replace( $convVIn, $convVOut, $sIn); 
 
    // on supprime les terminaisons T, D, S, X (et le L qui précède si existe)
    $sIn = preg_replace( '`L?[TDX]?S?$`', '', $sIn ); 
    // on supprime les E, A et Y qui ne sont pas en première position 
    $sIn = preg_replace( '`(?!^)Y([^AEOU]|$)`', '\\1', $sIn); 
    $sIn = preg_replace( '`(?!^)[EA]`', '', $sIn); 
    return substr( $sIn . '    ', 0, 4); 
}

Tests

Avec cette implémentation, on a par exemple :

Mot	Soundex	Mot	Soundex
Aymeric	EMRK	Emeric	EMRK
Banane	BNN	Bananne	BNN
Palper	PLP	Palpé	PLP
Palpa	PLP	Poulpe	PULP
Mario	MRYO	Marion	MRYO

On a par contre des résultats moyens lorsque des H séparent des voyelles faibles : par exemple Mouahaha donne MU (contre M avec la version précédente).

N'hésitez pas à faire des tests et à me faire part des résultats qui semblent anormaux.

Conclusion

Cette version est loin d'être parfaite, mais elle est plus adaptée au français que celle de Frédéric Brouard. Elle n'est d'ailleurs pas terminée et risque d'évoluer dans un futur proche, en particuliers pour ce qui est des tables de transcriptions et de prédominances.

Notes

[1] L'algorithme prend en compte les modifications fournies par les lecteurs et dont vous retrouverez le détail dans les commentaires. Merci donc aux commentateurs, et particulièrement à David

Un client RSS pour lire les Forums NNTP et les Mailing-Lists...

Florent Bruneau — Sun, 25 Feb 2007 19:05:00 +0100

Si il y a un bout de code dont je suis content au sein de Polytechnique.org, c'est Banana. Banana est à l'origine un client Web pour le protocole NNTP (c'est à dire le protocole utilisé par Usenet). Depuis sa dernière version (la 1.5), Banana est capable d'utiliser n'importe quel protocole comme source (les protocoles actuellement implémentés étant le NNTP et la lecture de MBox, mais on pourrait envisager d'ajouter le support des Maildir ou d'IMAP sans problème), ainsi, à Polytechnique.org, nous utilisons Banana pour offrir une plateforme Web vers nos forums et pour mettre en ligne les archives des Mailing-Lists que nous hébergeons.

Banana est à mon avis un bon outils : il permet un rendu plus que correct de la plupart des mails HTML (même ceux dont le formatage est défini dans une feuille de style), il affiche les discussions proprement et rapidement (grâce à un système de cache du côté serveur). C'est donc un gros plus en comparaison des interfaces habituelles de consultation d'archives de Mailing-List qu'on peut trouver sur Internet... et puis, ce n'est pas un forum php, pas de fioritures à la phpbb : Banana est clair, lisible et rapide... et facile à installer. Pour s'en convaincre, il suffit de regarder la fichier d'exemple qui fournit un banana totalement fonctionnel (à chacun ensuite d'y ajouter sa couche d'authentification si nécessaire).

La grande nouveauté de la prochaine version de Banana est l'intégration de flux RSS... ainsi il sera possible de lire les forums sans se connecter au site et sans client news, ou de suivre les discussions des mailing-lists sans relever son courrier (le premier des 2 cas étant certainement le plus intéressant). Pour les utilisateurs de Polytechnique.org, la fonctionnalité est d'ores et déjà disponible sur ma version de développement. Deux types de flux son disponibles : soit un flux par groupe, soit un flux regroupant tous les groupes auxquels on est abonné.