Archives de catégorie : Informatique

Anagrammes

octobre 3, 2017 quirysse Laisser un commentaire

En passant par une page de documentation, je me suis attardé sur std::next_permutation. Ça m’a tout de suite donné des idées d’anagrammes. En effet, de pouvoir aussi facilement boucler irréfragablement sur toutes les permutations des lettres d’un mot m’a suscité l’irrépressible envie de créer un petit détecteur d’anagrammes.

Évidemment, pour détecter un anagramme, il faut d’abord et avant tout avoir une base de données de mots valides pour une langue donnée. Il se trouve que j’ai une telle base de données. En effet, il y a déjà une vingtaine d’années, j’avais réalisé une petite page web d’aide aux mots-croisés. Pour ce faire j’avais contacté, via un forum, un cruciverbiste-internaute qui avait eu la grande gentillesse de me faire parvenir ce fichier par courriel. C’était un gros fichier à l’époque: presque 3 Mo. En fait, à l’origine c’était même 26 fichiers allant de A.txt à Z.txt. Cruciverbiste-internaute des années ’90 qui se reconnait dans cette histoire, je te remercie encore une fois!

Le corpus en tant que tel date un peu: le mot courriel, par exemple, n’y apparaît même pas. Quoi qu’il en soit, avec ses 280000 entrées composées de noms propres, de substantifs et d’adjectif au singulier comme au pluriel, de verbes conjugués à toutes les formes, c’est suffisant pour tenter quelques expériences significatives.

En tout cas, c’est amplement suffisant pour tester une première version d’un détecteur d’anagramme. Une version pas très robuste mais qui a le mérite de tester l’utilisation de std::next_permutation.

La première version lit la base de données en insérant dans un std::vector> tous les mots rencontrées. Le vecteur est triée pour permettre une recherche rapide avec std::binary_search

Une fonction ressemblant à ça pourrait par exemple faire l’affaire (j’assume un compilateur C++11 ou plus qui garantit que les objets comme la base de données ne sont pas retournés par copie sur la pile mais bien en utilisant le mécanisme de Copy Elision).

typedef vector<std::string> AnagramDB ;

AnagramDB GetAnagramDB(const std::string& filename) 
{
	std::vector<std::string> words;
	std::ifstream datafile(filename);

    std::string str;
    while (datafile >> str )
	{
		words.push_back(str);
    }

    std::sort(words.begin(), words.end());
	return words;
}

Lecture de la base de données et insertion dans un vecteur trié

Avec un vecteur ainsi trié, on peut rechercher un mot avec grosso-modo la même efficacité que dans un arbre binaire. En imaginant qu’on boucle sur les différentes permutations des lettres d’un mot, on voudra tester pour chaque combinaison si le mot est présent ou pas dans la base de données. Quelque chose comme ça.

bool isInDatabase(const AnagramDB& database, const std::string& str)
{
	return std::binary_search(database.cbegin(), database.cend(), str);
}

Utilisation de binary_search pour trouver un mot dans une liste triée

Une fois qu’on a une base de données chargée et un mécanisme pour tester si un mot (une combinaison de lettres) est valide (donc présent dans le base de données), il ne reste plus qu’à obtenir un mot à tester, boucler sur toutes ses permutations et vérifier pour chaque anagramme si il correspond à un mot valide dans la langue française (ici représentée par notre fichier de base de données).

On pourrait par exemple lire en boucle sur stdin pour obtenir des mots, qu’on testerait un à la fois. Pour chacun des mots, la liste des anagrammes valides serait envoyée sur stdout, et ainsi de suite. On remarque que pour initier les permutations, le mot est tout d’abord trié en ordre lexicographique, de manière à commencer par le « premier » anagramme.

Ça ressemblerait donc à ça.

int main(int argc, char** argv)
{
	if(argc<=1) 
		return 0;
	std::string str = argv[1];
    auto db = GetAnagramDB(str);
	std::cout << "Word to look for: "; 
	while(std::cin >> str ) 
	{
		std::sort(str.begin(), str.end());
		int num = 0;
		while(std::next_permutation(str.begin(), str.end()) )
		{
			if( isInDatabase(str) ) 
			{
				std::cout << str << std::endl;; 
				num  ;
			}
		}
			
		std::cout << "Found : " << num << std::endl; 
		std::cout << "Word to look for: "; 
	 }

	return 0;
}

Boucle naïve pour la recherche d'anagrammes valides basé sur std::next_permutation

Cette boucle et ce programme fonctionne parfaitement comme il se doit. Par contre il souffre de quelques faiblesses:

Le nombre de permutations est N! ; pour un mot de 10 lettres, on a déjà plus de 3,5 millions de combinaisons à tester (3628800)
Les casses minuscule et majuscules sont considérées comme étant des lettres différentes
Les accents et autres diacritiques génèrent des lettres différentes

Dans le prochain épisode sur les anagrammes, on améliorera tout ça en repensant la base de données et en évitant les multiples permutations. On s’affranchira aussi des problèmes de casse et de diacritiques.

c++, snippet

Comment enlever les accents des caractères en C++

octobre 3, 2017 quirysse Laisser un commentaire

Souvent lorsqu’on manipule du texte, on cherche à retrouver la forme de base des caractères, c’est-à-dire sans les signes diacritiques. Ce peut être utile pour générer une liste en ordre alphabétique de mots par exemple (on notera que dans l’ordre lexicographique des dictionnaires français, le E, et le É ont la même valeur).

Cet exercice peut être assez complexe car fortement dépendant de l’encodage des caractères (UTF-8, ASCII étendu, etc.) et de la définition donnée à « forme de base« . En effet, d’une langue à l’autre, cette notion peut varier et les diacritiques dans certaines langues donne une lettre à part entière. Par exemple en espagnol, la lettre ñ est une lettre à part qui est classée après le n.

Le remplacement des accents dans une application multi-langues est une tâche complexe et pour se faire, le mieux est d’être aidé par des bibliothèques comme ICU.

En revanche, pour tous les cas relativement fréquents où les caractères sont simplement codés sur un octet en utilisant l’ASCII étendu avec l’encodage ISO-Latin-1, on pourrait utiliser le petit bout de code suivant (inspiré d’une réponse sur Stack Overflow).

char RemoveAccent(char ch)
{
    static const std::map<char, char> tr =
    {
        {'À', 'A'},
        {'Á', 'A'},
        {'Â', 'A'},
        {'Ã', 'A'},
        {'Ä', 'A'},
        {'Å', 'A'},
    
        {'Æ', 'E'},
    
        {'Ç', 'C'},
    
        {'È', 'E'},
        {'É', 'E'},
        {'Ê', 'E'},
        {'Ë', 'E'},
    
        {'Ì', 'I'},
        {'Í', 'I'},
        {'Î', 'I'},
        {'Ï', 'I'},
    
        {'Ð', 'D'},
    
        {'Ñ', 'N'},
    
        {'Ò', 'O'},
        {'Ó', 'O'},
        {'Ô', 'O'},
        {'Õ', 'O'},
        {'Ö', 'O'},
    
        {'×', 'x'},
    
        {'Ø', '0'},
    
        {'Ù', 'U'},
        {'Ú', 'U'},
        {'Û', 'U'},
        {'Ü', 'U'},
    
        {'Ý', 'Y'},
        {'Þ', 'p'},
        {'ß', 's'},
    
        {'à', 'a'},
        {'á', 'a'},
        {'â', 'a'},
        {'ã', 'a'},
        {'ä', 'a'},
        {'å', 'a'},
    
        {'æ', 'e'},
    
        {'ç', 'c'},
    
        {'è', 'e'},
        {'é', 'e'},
        {'ê', 'e'},
        {'ë', 'e'},
    
        {'ì', 'i'},
        {'í', 'i'},
        {'î', 'i'},
        {'ï', 'i'},
    
        {'ð', 'd'},
    
        {'ñ', 'n'},
    
        {'ò', 'o'},
        {'ó', 'o'},
        {'ô', 'o'},
        {'õ', 'o'},
        {'ö', 'o'},
    
        {'÷', '/'},
    
        {'ø', 'o'},
    
        {'ù', 'u'},
        {'ú', 'u'},
        {'û', 'u'},
        {'ü', 'u'},
    
        {'ý', 'y'},
        {'þ', 'p'},
        {'ÿ', 'y'}
    };

    auto it = tr.find(ch);
    if (it != tr.end()) {
        return it->second;
    }
    return ch;
}

Accent remover

c++, Informatique, Unicode

Unicode, UTF-8 et autres considérations

juillet 21, 2014 quirysse Laisser un commentaire

Unicode, UTF-8 et autres considérations

Comme mentionné précédemment, manipuler du texte en différentes langues nécessite de s’intéresser au codage des caractères. Il y a beaucoup de choses à dire sur l’ASCII (version originale à 7 bits, puis étendue à 8 bits), sur l’Unicode et les différentes façon de représenter les caractères. Mais Internet est là pour ça et beaucoup l’ont expliqué mieux que je ne saurais le faire.

Concentrons nous donc sur le problème concret de la création d’histogramme de n-gram à partir de caractères UTF-8. Selon votre langage de programmation favori, un caractère peut avoir différentes significations. En C et comme dans beaucoup de ses dérivés, un « char » est une suite de 8 bits. C’est donc simplement un nombre entier compris entre [-127, 128] ou [0, 255] selon qu’on le considère signé ou non-signé. C’est tout. Fin de l’histoire. Il n’y a aucune notion de représentation derrière, un caractère est un entier défini sur un domaine restreint de 256 valeurs. Ça tombait plutôt pas mal, le standard ASCII, après une mise à jour, associait une lettre, un élément de ponctuation, un chiffre, un caractère à chacune de ces 256 valeurs possibles. La plupart des langues basées sur l’alphabet latin peuvent être couvertes avec 256 symboles (sachant qu’il faut aussi garder de la place pour le chiffres, la ponctuation, des signes essentiels comme $, £, &, @, % et autres #. En y ajoutant quelques symboles qu’on ne voit pas mais qui sont nécessaires (comme le changement de ligne (0x0D), le son de cloche (0x07) ou le 0x15 NAK « negative acknowledge », on remplit rapidement l’espace disponible. Notons que l’euro (€) n’existait pas à l’époque, donc le symbole n’est pas inclut dans l’ASCII. On le retrouve grâce à l’Unicode.

256, c’est joli mais c’est petit

En fait, toutes les langues utilisant un alphabet latin ne peuvent pas s’écrire avec 256 symboles (moins les trucs bizarres comme le NAK). Si on met les ğ et Ş turcs, il n’y a plus de place pour les Ð, Þ ou æ islandais par exemple. Et puis vous savez quoi ? Il y a une multitude de langues qui n’utilisent pas l’alphabet latin ! Déjà que l’ascii ne couvrait pas toutes les déclinaisons de cet alphabet, on peut imaginer le problème des alphabets inuit, cyrillyque, hindî, grec, arabe ou hébreux et plus encore des idéogrammes asiatiques tels les sinogrammes ou les hiraganas.

On veut des bits

Naturellement on se dit qu’il n’y a qu’à rajouter des bits. En effet, en passant à seize (16) bits par caractères, on atteint un potentiel de 65536 symboles différents. En passant à 32 bits, on ouvre les mode des possibles à plus de 4 milliards de lettres/symboles/idéogrammes/smileys.

Bref, tout ça pour dire que l’UTF-8 peut représenter l’ensemble des caractères des langues naturelles en utilisant un nombre variable d’octets. Pour les 128 symboles de l’ASCII de base (2 ^{7 bits} = 128 possibilités) tout se passe comme il faut, un seul octet est nécessaire. Ça couvre l’anglais, la ponctuation et quelques autres caractères fondamentaux comme l’inénarrable barre verticale « | » (0x7C).

Mais me direz-vous, octet, octant, octogone, octopode ça me rappelle vaguement le nombre huit. Et bien oui, le huitième bit de l’octet UTF-8 sert à signaler qu’on est dans un cas spécial et qu’il faut combiner les bits déjà lus avec ceux de l’octet suivant pour retrouver notre caractère qui est donc en dehors du domaine des 128 codes de base. Le second octet ayant évidemment lui-même un bit signalant la possibilité d’aller voir chez l’octet suivant et ainsi de suite jusqu’à… 4. Donc un caractère codé en UTF-8 est une suite de 1, 2, 3 ou 4 octets.

L’UTF-8 a beaucoup d’avantages et est largement répandu sur Internet. Je fais donc le Postulat numéro 1 (ou serait-ce un axiome?) que les données d’entrées seront codées de cette façon. Si ce n’est pas le cas, la pléthore d’outils permettant la conversion d’autres systèmes vers UTF-8 permettra, via un pré-traitement des données, de s’assurer de la validité dudit postulat.

Mais alors, c’est quoi un caractère ?

Ça peut être beaucoup de chose. Twitter s’est d’ailleurs posé la question puisque leur mission est de les compter jusqu’à hauteur de 140 (un nombre abondant). Leur définition semble satisfaisante pour les besoins de création de n-gram. Grosso-modo, un unigramme est un « code point« , c’est à dire un ensemble de 1, 2, 3 ou 4 octets représentant une lettre, un idéogramme, un symbole.

Ce n’est pas parfait parce que l’Unicode permet la composition. Par exemple, pour faire ê, il y a plusieurs chemins. La lettre e peut être accentuée, c’est dire qu’une séquence comprenant 2 code points peut être utilisée (un « e » suivi d’un « ^ » ou vice versa, j’en sais trop rien) ou bien on peut aussi coder directement le symbole ê. C’est un exemple de non-orthogonalité flagrante selon une de ses définitions en informatique (2 façons d’arriver au même résultat). L’autre définition portant sur les effets collatéraux d’un appel de fonction sur un appel précédent. C’est dans le même esprit mais je m’égare…

Idéalement, tous les diacritiques devraient être normalisés pour être codés sous la même forme. Mais le postulat numéro 2 dit que ce n’est pas nécessaire. D’ailleurs, l’intérêt est de voir si ça marche avec n’importe qu’elle entrée ayant été le moins pré-traitée possible. Si ça ne fonctionne pas, on remettra en cause le Postulat numéro 2. Pour l’instant, on considère que le système sera assez robuste pour être efficace malgré le biais induit par les différents codages d’un même glyphe. Si ça se passe mal, on rétrogradera le postulat en hypothèse qu’on infirmera. Pour l’instant allons de l’avant.

La ponctuation ?

Les points, point d’interrogation, virgules sont de bons indicateurs de fin ou de début de mot. Ils sont donc utiles puisque selon les différentes langues, les lettres n’ont pas la même fréquence en début ou en fin de mot. L’espace (un nom féminin dans ce contexte !) joue donc aussi un rôle important et doit être considéré comme un caractère à part entière. Cependant, selon l’origine du texte, on peut se retrouver avec des suites de 2, 3 voire 10 espaces consécutives. Le trigramme » » (3 espaces à la queue-leu-leu) est même le plus fréquent avec les données Wikipedia pour le français et l’anglais sur mes premiers tests. C’est un facteur qu’il faudra prendre en compte.

Et concrètement ?

Tout ça pour dire que j’ai trouvé une façon simple de regrouper des unigrammes, des bigrammes et des trigrammes malgré le fait que chacun des code point soit en fait une une chaîne de caractères. Merci à cette librairie qui permet d’itérer sur les code points tout en gardant l’accès aux positions des octets sous-jacents. De cette façon, on peut avancer de un, deux ou trois caractères pour former les n-grammes et construire une std::string à partir des positions des octets. L’histogramme se bâtit en incrémentant les valeurs d’une std::map où la clef est une std::string et la valeur un compteur (int, long long, etc.)

[pastacode lang= »c++ » message= »Programme de création de n-grammes » highlight= » » provider= »manual »]


#include 
#include 
#include 
#include 
#include 

#include "utf8/utf8.h" //http://www.codeproject.com/Articles/38242/Reading-UTF-with-C-streams

typedef std::map histotype;
typedef std::pair histonodetype;

void PrintGrams(const histotype& gram)
{
    std::vector vectgram;

    std::copy(gram.begin(), gram.end(), std::back_inserter(vectgram));
    std::sort(vectgram.begin(), vectgram.end(), [](const histonodetype& left, const histonodetype& right){return left.second < right.second;});

    for(auto elem : vectgram )
    {
        std::cout << elem.first << " " << elem.second << std::endl;
    }
}

int main(int argc, char** argv)
{
    std::ifstream in(argv[1]);
    std::string line;

    histotype unigram;
    histotype bigram;
    histotype trigram;
    while( std::getline(in, line))
    {
        typedef  decltype(line.begin()) ittype;
        utf8::iterator it(line.begin(), line.begin(), line.end());
        utf8::iterator endit (line.begin() + line.size(),
                line.begin(), line.begin() + line.size());

        if(it==endit) // check for end of line
            continue;

        auto unibeg = it;
        auto bibeg = it;
        auto tribeg = it;

        it++;

        unigram[std::string(unibeg.base(), it.base())]++;
        it++; unibeg++;
        if(it==endit) // check for end of line
            continue;

        unigram[std::string(unibeg.base(), it.base())]++;
        bigram[std::string(bibeg.base(), it.base())]++;
        it++; unibeg++; bibeg++;
        if(it==endit) // check for end of line
            continue;

        for(;it != endit; it++, unibeg++, bibeg++, tribeg++)
        {
            unigram [ std::string(unibeg.base(), it.base())]++;
            bigram  [ std::string(bibeg.base(), it.base())  ]++;
            trigram [ std::string(tribeg.base(), it.base()) ]++;
        }
    }

    PrintGrams(unigram);
    PrintGrams(bigram);
    PrintGrams(trigram);

    return 0;
}

[/pastacode]

Ce code compile avec une version récente de gcc (il y a quelques éléments de syntaxe du c++0x11). C’est une preuve de concept, pas du code de production, mais si vous voulez expérimenter la génération de n-grammes, c’est un bon point de départ.

Pour ma part j’ai testé quelques 100 000 lignes en français et en anglais venant de Wikipedia (avec et sans les tags XML) et malgré les biais induits par les nombreuses suites d’espaces et les séquences spéciales pour mettre en forme le texte sur Wikipedia (les [[[, »’, et autre), on voit déjà poindre les « de » et « ng » en pôle position pour respectivement les trigrammes français et anglais.

Le choix et le pré-traitement des corpus d’apprentissage sera un dossier en soi, mais d’ici là, je compte travailler sur le stockage des résultats (peut-être avec SQLite) et leur mise à jour (peut-être via une API REST.

Informatique, Linguistique, Machine learning, Unicode

Identification de la langue d’un texte

Citation juillet 20, 2014 quirysse Laisser un commentaire

Identification de la langue d’un texte

Récemment, un article m’a rappelé qu’il était serait amusant de faire un système pour détecter de manière automatique la langue dans laquelle un texte est écrit. L’article en question parlait de complètement autre chose et ne faisait que reprendre les résultats d’un blog anglophone. Cependant, en présentant d’une certaine façon les distributions d’occurrence des lettres au sein de quelques langues européennes, je me suis souvenu que ces distributions donnaient une signature qu’on pouvait utiliser pour reconnaitre la langue d’un texte. Ce peut aussi d’ailleurs être utilisé pour briser les codes simples comme le chiffre de César tel que Simon Singh nous l’expliquait dans son excellent livre sur l’histoire des codes secrets.

Pour créer les signatures, on peut analyser la fréquence d’occurrence des lettres individuelles, mais aussi des séquences de deux lettres consécutives. Par exemple en français, la séquence « ch » est plus fréquente que « sh » ou « cz ». D’autres langues présenteront d’autres proportions pour ces même suites. Et pourquoi s’arrêter à deux ? On peut aussi répertorier les séquences de trois, quatre ou N lettres consécutives. C’est ce qui s’appelle des n-grams. Ça ne se résume pas qu’aux lettres et ça ne sert pas qu’à détecter une langue, mais c’est le contexte dans lequel le présent projet va les utiliser.

Sommairement, il s’agit donc de :

Créer des signatures basées sur les n-grams pour différentes langues
Extraire la signature d’un texte inconnu dont on veut identifier la langue
Comparer sa signature avec celles des langues « apprises »
En déduire l’idiome du texte

La signature n’étant que l’histogramme des fréquences d’occurrence des différents n-grams.

Heu… mais pour quoi faire ?

Clarifions tout de suite un point : je n’en ai personnellement aucune utilité. Ce n’est ni lié à des sujets professionnels, ni à un quelconque outil qui pourrait me servir. La recherche sur le sujet est bien avancée et je ne cherche pas à l’approfondir. Tous les jours on peut d’ailleurs voir à l’œuvre des sites qui ont de très bons résultats dans le domaine. Cependant, la (relative) simplicité de mise en œuvre d’une solution à un problème qui peut sembler aussi complexe est fascinante. C’est donc en pur dilettante que j’ai envie de jouer un peu avec ce problème.

D’un autre côté, bien que la solution soit conceptuellement simple, quelques détails pratiques font qu’il y a tout de même quelques petits défis à relever et questions à répondre. Comment trouver des données d’apprentissage ? Comment gérer les caractères internationaux, l’Unicode et les codages à nombre variable d’octets (par exemple l’UTF-8) ? Que faire de la ponctuation, des espaces, ou même des tags HTML dans le cas où les données viendraient de source web ? Quelle technique choisir pour mesurer la similarité des signatures (vecteurs de cardinalité et de dimensions différentes) ? Comment présenter les résultats ? Bref, suffisamment d’interrogations pour rendre le projet intéressant.

Étapes du projet

Avant de me lancer, j’ai détaillé sommairement les grands blocs ou thèmes sur lesquels il faut travailler. Je les présente ci-dessous, sachant que cela n’a rien de formel. Ce découpage est relativement orthogonal, ce qui permet de travailler indépendamment sur un sujet ou un autre.

Création des bases de données
1. Obtenir des sources de texte
2. Analyse des langues
3. Stockage des résultats
Reconnaissance de la langue
1. Analyse et création des signatures
2. Comparaison avec les signatures en base de données
3. Calcul des estimations de probabilité pour chaque langue
Interface et interaction
1. Soumission des données à analyser
2. Mise à jour de la base de données
3. Affichage des résultats

État des lieux

Corpus d’apprentissage

J’ai quelques pistes pour les corpus d’apprentissage. J’ai expérimenté un peu avec Wikipedia qui permet de télécharger l’intégralité de son contenu à un instant t. C’est trié par langue et de nombreuses langues sont disponibles. Pour récupérer le contenu de Wikipedia, c’est mieux que :

quirysse@beluga:~$ wget --random-wait -r -p -e robots=off -U mozilla http://en.wikipedia.org/wiki/Main_Page

Le problème c’est que c’est gros. Très gros.

[pastacode lang= »bash » message= »Espace occupé par deux langues sur Wikipedia » highlight= » » provider= »manual »]

wilhelm@beluga:~/WikiCrawl$ ll -h *xml
-rw-r--r-- 1 wilhelm woodself 46G Jul  9 00:58 enwiki-latest-pages-articles.xml
-rw-r--r-- 1 wilhelm woodself 12G Jul 16 21:00 frwiki-latest-pages-articles.xml
wilhelm@beluga:~/WikiCrawl$

[/pastacode]

De plus, les fichiers sont codés en XML dans le langage de Wikipedia, ce qui après quelques tests, même après avoir enlevé les tags XML, on trouve beaucoup d’occurrences de » [[ » et autres balises du genre. Ça reste quand même une option mais un peu de préparation de la base de données s’avèrera nécessaire. Il y a une piste avec European Parliament Proceedings Parallel Corpus 1996-2011. C’est d’ailleurs ce qui a été utilisé dans l’article cité plus haut.

Analyse

La génération d’histogrammes d’unigrammes, de bigrammes et de trigrammes n’est pas un souci en soi. Cependant, il faut penser au codage Unicode et comme l’UTF-8 semble tout indiqué, il faut gérer le fait qu’un caractère puisse être composé d’un nombre variable d’octets. Un article complet sur le sujet est en préparation, puisque grâce à cette bibliothèque on peut arriver rapidement à une solution.

Stockage

Les histogrammes, on en fait quoi ? Ils peuvent être longs à générer. On peut vouloir les mettre à jour en utilisant de nouveaux corpus et de nouvelles langues. Alors SQL, fichier maison ? A voir.

Détection de la langue

De façon naturelle on pense au cosinus, mais ça cause certaines difficultés. Je pense plutôt à une erreur RMS ou une distance euclidienne sur les dimensions présentes dans le vecteur d’entrée. Et puis qu’est-ce qu’on fait des hapax et des n-grams très rares. On les garde ou on nettoie le vecteur d’entrée ? Rien n’est fixé mais on en reparlera.

Interface

Évidemment, tout commence toujours pas une série de petits scripts bash et 2 ou 3 mini programmes en C++. Mais au final, une API REST pour obtenir les probabilités des différentes langues sachant une signature pour un texte en entrée, ça serait sympa, non ? Et une page web où l’on verrait les probabilité évoluer en même temps qu’on entre du texte dans un champ, ça serait encore mieux ! C’est un dossier qui est encore un peu loin, mais il y a du potentiel pour faire un système agréable. Pour l’instant, on va en rester au bash…

Conclusion

Donc, voilà où on en est. L’UTF-8 est à peu près réglé (article à suivre). Reste à faire le reste. C’est à dire, à peu près tout…

Arrosage, Bricolage, Domotique, Informatique, Raspberry Pi

Framboise en boîte 4/N

mai 15, 2014 quirysse 2 commentaires

Le futur

Dans cet article, nous aborderons les technologies futuristiques (à ne pas confondre avec futuristes) des drivers FTDI qui permettent à notre sympathique framboise de communiquer avec ses relais (là, le s s’avère nécessaire réforme ou pas¹ ).

Retour sur l’Arros-o-tron

La dernière fois, nous avons testé l’ensemble de contrôle des relais avec de la vraie eau, tout à fait vraiment vraie (et humide). Malencontreusement, quelques digressions annexes nous ont fait perdre le focus (qui a la fâcheuse propriété d’être évanescent) et la conclusion s’en est allée. Cette conclusion, je vous la donne donc directement en introduction du l’article N+1 (N est ici tout à fait déterminé, il s’agit du nombre 3. À ne pas confondre avec N, le nombre total d’articles sur le sujet qui nous occupe, qui lui n’est pas encore déterminé. Ou peut-être que si, dans l’hypothèse où vous liriez cet article dans le futur par rapport à maintenant. Peut-être n’avons-nous pas le même maintenant. Nous verrons d’ailleurs plus loin comment FTDI a répondu à cet opaque problème. Mais enfin, je m’égare).

Donc oui, ça marche. On contrôle très bien l’électrovanne à partir de l’alimentation 12V et du relai. L’eau jaillit et se tarit à souhait à partir de simples commandes (connexion ssh sur le Rapsbperry Pi et quelques commandes UNIX).

Ce ne sera pas la configuration finale, mais pour ce premier test arrosatoire, j’ai utilisé une électrovanne 24 VAC. Je l’ai commandée à partir de mon alimentation 12 VDC (voir article premier). Pas très orthodoxe, mais je suis parti de l’hypothèse que les tensions nominales sur n’avait pas à être franchement respectées. Selon notre ami Maxwell (rien à voir avec le café), s’il y a du courant dans la bobine, on pourra faire bouger un truc en utilisant la force du champ magnétique induit par le passage des électrons enivrés par les enroulements de notre conducteur. Jamais dans ses équations est dit qu’on doive respecter les tensions nominales de notre fournisseur de solénoïdes. Je fais sans doute quelques raccourcis, mais toujours est-il que ça marche (d’ailleurs pour ce test, j’ai bien appliqué 12 volts en courant continu alors que nominalement on requérait du courant alternatif, na!)

Contrôleur du travail

Les électrovannes en tant que telles pourront d’ailleurs être l’objet d’un article ultérieur tant il y a à dire sur cet objet contrôlant le travail. En effet, en autorisant ou interdisant le déplacement de masses d’eau, la vanne contrôle le travail (on se souviendra qu’il y a vaguement un lien entre la force (qui peut elle-même être liée à la masse) et le déplacement). Les joyeux jaillissements de l’eau à travers mon tuyau sont donc du travail. Et comme toute peine mérite salaire, Veolia ne manque pas de se faire rétribuer à chacune de mes saillies.

Le contrôle de la carte à relais

Nous avons déjà dit que la carte USB-X440 était munie d’un connecteur USB (et de cinq trous de quatre millimètres, mais ce dernier constat n’intervient que très peu, ou pas du tout, sur le sujet précis qui nous occupe dans cette section). En fait, la carte USB-X440 communique en série. Oui, oui, ce bon vieux port série, le RS-232, les stop bit et start bit, la parité, le baud, et tout et tout. A priori, rien de très sexy. C’est là que la technologie du future entre en jeu.

FTDI produit des chips qui permettent d’émuler une communication de type RS-232 à travers un support USB.

Petit mot sur le futur

On se souviendra que dans les années 1990, et même avant, plusieurs entreprises ajoutaient le suffixe 2000 à leur raison sociale ou à leurs produits. Du système d’exploitation au plombier du coin, tous étaient résolument tournés vers l’avenir et la modernité. Tout le monde voulait son 2000. C’était dans l’air du temps, et si l’on a moins de 20 ans, on ne s’en souvient guère. Cette bohème ne pouvait pas durer éternellement parce qu’elle avait un défaut intrinsèque: le temps passe, les années changent, et le futur d’hier devient le passé d’aujourd’hui. Si Windows 2000 n’est plus qu’un (plus ou moins bon) souvenir, tous les chauffagistes 2000, les menuisiers 2000 et autres assureurs 2000 qui ont survécus sont passés de visionnaires à passéistes, tournés à jamais vers une époque de plus en plus lointaine.

FTDI a trouvé la solution. Bien qu’issue des années 1990, cette entreprise est à jamais tournée vers l’avenir, puisque son point de fuite n’est pas une année déterminée, mais bien le futur en personne. Ce futur qui dès maintenant et pour toujours sera invariablement devant. FTDI est en effet l’acronyme de Future Technology Devices International ce qui se traduit (assez librement) par: « Bidules internationaux basés sur la technologie du futur ». Le problème de la relativité temporelle est donc résolu. Peu importe le point de vu, FTDI sera toujours devant.

Le port série automagique

Quoi qu’on en dise, les circuits FTDI on plusieurs atouts :

Ils permettent une communication simple à travers une connectique standard (USB était encore répandu au moment d’écrire ces lignes, bien que cela paraisse incongru au lecteur d’un certain futur)
Les spécifications sont ouvertes et il est donc aisé d’écrire les pilotes idoines
Ils sont supportés nativement par tous les bons noyaux près de chez vous

Ce troisième point est particulièrement intéressant. C’est la pierre d’achoppement du l’automagicité. En effet, il suffit de relier la carte munie du chip FTDI à son ordinateur (en l’occurrence, un Raspberry Pi faisant tourner une distribution Raspbian) pour n’avoir rien à faire… En fait le pilote papote avec le chip. Chacun fait sa tambouille de son côté. On finit par s’entendre sur un truc du genre 9600 8N1. Et hop, on se retrouve avec un device dans /dev/ttyUSB0

pi@nsa ~ $ ls /dev/ttyUSB0
/dev/ttyUSB0
pi@nsa ~ $

On a donc une émulation de port série, installée en quelques millisecondes, sans aucune configuration. C’est à ce demander à quoi sert de faire un blog pour en parler tellement l’opération est sans douleur.

Du coup, de façon tout à fait classique, pour envoyer une commande à la carte, on écrit dans /dev/ttyUSB0 et, symétriquement, on lit dans /dev/ttyUSB0 pour recevoir des messages (le zéro (0) pouvant bien entendu être incrémenté si plus d’un port USB émulé est présent).

D’après la documentation, la relais se commandent ainsi:

Sxb

S veut dire relai (switch?)

x, le numéro du relai

b, une valeur booléenne (0 ou 1) pour changer l’état du relai.

Il suffit donc d’écrire dans sa commande dans le tty pour pour commander une action, en utilisant echo par exemple.

Cela donne donc, comme on l’a vu précédemment:

Relai #1 au repos:

pi@nsa ~ $ echo S10 > /dev/ttyUSB0

Relai #1 actif:

pi@nsa ~ $ echo S11 > /dev/ttyUSB0

Pour écouter ce que nous dit la carte, on utilisera cat :

pi@nsa ~ $ cat /dev/ttyUSB0

La suite

On se rendra donc bien entendu à N ≥ 5 puisque nous n’avons pas encore abordé l’installation du circuit hydraulique, le creusage dans le jardin ni la plantation de tomates.

<– Précédent Suivant –>

c++, Informatique

Générer un jeu de Dobble

janvier 31, 2014 quirysse 8 commentaires

Lorsque j’ai découvert le jeu de Dobble, je me suis tout de suite demandé comment on pouvait générer un tel ensemble de cartes.

Après y avoir vainement réfléchi, j’ai trouvé quelques références ici et là qui font appel à la géométrie projective.

L’idée m’est alors venue de générer un jeu personnalisé avec des images ayant un thème commun (des visages familiers, des lieux de vacances, etc.)

Le projet :

Trouver une façon de générer les combinaisons de cartes et symboles
Générer les combinaisons et les stocker dans fichier texte
Faire un script qui génère les images de chacune des cartes avec ImageMagick
Faire imprimer les images sur un support se rapprochant d’une carte à jouer

Les points 1 à 3 étant techniquement réglés, j’en partage ici les différentes étapes. Le dernier point est encore en projet…

1. Trouver l’algorithme

Après avoir parcouru liens mentionnés plus haut, il me restait à en faire l’implémentation. Après quelques tâtonnements, je suis tombé sur ce post de stackoverflow qui propose quelques implémentations.

2. Générer les cartes

J’en ai choisi une qui est sous-optimale (elle génère 58 symboles plutôt que 57). Le jeu reste cependant tout à fait valide et le bout de code implémentait aussi une fonction de vérification du jeu généré. J’ai légèrement modifié la sortie pour avoir un fichier texte facile à lire pour la suite.

Le fichier source est ici : mainDobble.cpp

Le résultat du programme est un fichier texte de la forme suivante où chaque ligne représente une carte composée de 8 symboles, eux-même représentés par un entier.

wilhelm@beluga:~/code/dobble$ head -5 dobble.txt
0   1   2   3   4   5   6   50
7   8   9   10  11  12  13  50
14  15  16  17  18  19  20  50
21  22  23  24  25  26  27  50
28  29  30  31  32  33  34  50
wilhelm@beluga:~/code/dobble$

Le format du fichier texte contenant les cartes de Dobble

Fichier des cartes résultant : dobble.txt

On peut aussi générer des jeux avec 4, 6 ou même 12 symboles par carte. Par exemple:

3. Le script de rendu

Pour créer le rendu des cartes, un petit script bash: card.sh.

Syntaxe

Premier argument: le fichier texte en entrée. Second argument: le chemin du répertoire où sont les images. Les cartes sont générées dans un répertoire output

wilhelm@beluga:~/code/dobble$ ./card.sh dobble.txt ~/picture/dobble

Commande pour lancer le rendu des cartes.

On notera la double utilisation de shuf. L’algorithme de génération des cartes est assez ordonné. Un double brassage s’impose. Le premier, c’est pour réarranger l’ordre des cartes (le shuf de la boucle for). Le second (encapsulé dans une fonction Shuffle pour ventiler les éléments d’une ligne plutôt que des lignes), est plus important. Il s’agit de ventiler la position des symboles sur les cartes. Sinon, les mêmes symboles ont tendance à se retrouver aux mêmes positions et ça enlève un peu du piment au jeu.

La boucle principale appelle ImageMagick pour créer un montage à partir d’images stockée dans le répertoire passé en argument et du fichier texte mentionné plus haut.

#!/bin/bash

Shuffle()
{
	 echo $* | tr " " "\n" | shuf | tr -d " " 
}

##############################################
# Main
##############################################
INPUT=$1
DIR=$2
OUTDIR=ouput

BAK_IFS=${IFS}
IFS=$'\r\n' 
Image=($(ls $DIR))
IFS=${BAK_IFS}

mkdir -p ${OUTDIR}
export i=0
export SMSIZE=500
export BIGSIZE=600
export FULLSIZE=1600
shuf ${INPUT} | while read a b c d e f g h; do
	sa=( $( Shuffle ${a} ${b} ${c} ${d} ${e} ${f} ${g} ${h} ) )
	im=( \
		"${DIR}/${Image[ ${sa[0]} ]}"\
		"${DIR}/${Image[ ${sa[1]} ]}"\
		"${DIR}/${Image[ ${sa[2]} ]}"\
		"${DIR}/${Image[ ${sa[3]} ]}"\
		"${DIR}/${Image[ ${sa[4]} ]}"\
		"${DIR}/${Image[ ${sa[5]} ]}"\
		"${DIR}/${Image[ ${sa[6]} ]}"\
		"${DIR}/${Image[ ${sa[7]} ]}" ) 

	OUTPUT=${OUTDIR}/card_${i}.jpeg
	echo ${OUTPUT}
	((i  ))

	 convert  -size "${FULLSIZE}x${FULLSIZE}" xc:white  \
-gravity Center \
\( "${im[0]}" 	-resize "${SMSIZE}x${SMSIZE}"	-gravity Center -rotate -45 	-repage  0 0 		\)		\
		\( "${im[1]}" 	-resize "${SMSIZE}x${SMSIZE}" 	-gravity Center -rotate 45 		-repage  1000 0 	\)		\
		\( "${im[2]}" 	-resize "${SMSIZE}x${SMSIZE}" 	-gravity Center -rotate 0		-repage  0 600	 	\)		\
		\( "${im[3]}" 	-resize "${BIGSIZE}x${BIGSIZE}"	-gravity Center -rotate 60		-repage  400 400  	\)		\
		\( "${im[4]}" 	-resize "${SMSIZE}x${SMSIZE}"	-gravity Center -rotate 180		-repage  1200 500 	\)		\
		\( "${im[5]}" 	-resize "${SMSIZE}x${SMSIZE}"	-gravity Center -rotate -135	-repage  0 1100 	\)		\
		\( "${im[6]}" 	-resize "${SMSIZE}x${SMSIZE}"	-gravity Center -rotate 180		-repage  800 1100 	\)		\
		\( "${im[7]}"	-resize "${SMSIZE}x${SMSIZE}" 	-gravity Center -rotate 135		-repage  1100 1100	 \)		\
		-compose Multiply -layers flatten  tiff:- | convert - 	-mattecolor DarkOrange4 -frame 20x20 0 0 \
${OUTPUT}
done

Script pour le rendu des images de carte

Ci-dessous, un exemple du rendu de quelques cartes générées. Il ne reste plus qu’à ajuster un peu les dimensions en fonction des proportions des cartes à imprimer. Mais pour ça, il faut trouver un fournisseur/site web, qui propose d’imprimer 57 cartes différentes pour un prix raisonnable. C’est la fameuse étape 4, qui est encore en suspend…

c++, Informatique, snippet

Chronomètre basique

En passant janvier 29, 2014 quirysse Laisser un commentaire

On a souvent besoin d’un chronomètre multiplateforme. Celle-ci est 100% inline et ne dépend que de ctime (aka time.h). Un simple #include suffit à l’utiliser un peu partout. La classe étant basée sur clock(), la précision n’est pas garantie. Mais c’est souvent amplement suffisant.

Le fichier est disponible ici: chrono.h

[pastacode provider= »manual » lang= »c++ » message= »Contenu du fichier chrono.cpp »]

#ifndef __CHRONO_H__
#define __CHRONO_H__

#include <ctime>

/**
 * \namespace	Chrono 
 *
 * \brief	A small set of utilities encapsulating timing functions 
**/
namespace Chrono 
{

/**
* \class	Stopwatch
*
* \brief	A stopwatch
*
* \details	Allows to create a stopwatch, start, stop and getting time in various formats.
**/
class Stopwatch
{
public:
 /**
 * \fn	Stopwatch::Stopwatch();
 *
 * \brief	Default constructor. 
 *
**/
inline
Stopwatch();

 /**
 * \fn	void Stopwatch::Start();
 *
 * \brief	Starts the time counter. 
 *
**/
inline
void Start();

  /**
 * \fn	void Stopwatch::Stop();
 *
 * \brief	Stops the time counter. 
 *
**/
inline
void Stop();

  /**
 * \fn	void Stopwatch::Reset();
 *
 * \brief	Resets the time counter to 0 sec.
 *
**/
inline
void Reset();

  /**
 * \fn	double  Stopwatch::GetTimeInMilliseconds();
 *
 * \brief	Gets the time in milliseconds. 
 *
 * \return	The time in milliseconds. 
 *
**/
inline
double  GetTimeInMilliseconds();

 /**
 * \fn	double Stopwatch::GetTimeInSeconds();
 *
 * \brief	Gets the time in seconds. 
 *
 * \return	The time in seconds. 
 *
**/
inline
double  GetTimeInSeconds();

  /**
 * \fn	double Stopwatch::GetTimeInMinutes();
 *
 * \brief	Gets the time in minutes. 
 *
 * \return	The time in minutes. 
 *
**/
inline
double  GetTimeInMinutes();

  /**
 * \fn	double Stopwatch::GetTimeInHours();
 *
 * \brief	Gets the time in hours. 
 *
 * \return	The time in hours. 
 *
**/
inline
double  GetTimeInHours();

  /**
 * \fn	void Stopwatch::GetTime(int &aHours, int &aMinutes, int &aSeconds, int &aMilliseconds);
 *
 * \brief	Gets a time in a formated way
 *
 * \param [in,out]	aHours			a in hours. 
 * \param [in,out]	aMinutes		a in minutes. 
 * \param [in,out]	aSeconds		a in seconds. 
 * \param [in,out]	aMilliseconds	a in milliseconds. 
 *
**/

inline
void    GetTime(int &aHours, int &aMinutes, int &aSeconds, int &aMilliseconds);

private :
  unsigned int mStart;
  unsigned int mAccumulator;
  bool mStopped;
  };
}

inline
Chrono::Stopwatch::Stopwatch() : mAccumulator(0), mStopped(true)
{
}

inline
void Chrono::Stopwatch::Start()
{
  if(!mStopped)
   return;

  mStart = clock() - mAccumulator;
 mStopped = false;
}

inline
void Chrono::Stopwatch::Stop()
{
  if(mStopped)
   return;

  mAccumulator = clock() - mStart;
  mStopped = true;
}

inline
void Chrono::Stopwatch::Reset()
{
  Stop();
  mAccumulator = 0;
}

inline
double Chrono::Stopwatch::GetTimeInMilliseconds()
{
  return GetTimeInSeconds() * 1000.0;
}

inline
double Chrono::Stopwatch::GetTimeInSeconds()
{
  unsigned int lTime;
  if(mStopped)
   lTime = mAccumulator;
  else
   lTime = clock() - mStart;

  return lTime / (double)CLOCKS_PER_SEC;
}

inline
double Chrono::Stopwatch::GetTimeInMinutes()
{
  return GetTimeInSeconds() / 60.0;
}

inline
double Chrono::Stopwatch::GetTimeInHours()
{
  return GetTimeInSeconds() / 3600.0;
}

inline
void Chrono::Stopwatch::GetTime(int &aHours, int &aMinutes, int &aSeconds, int &aMilliseconds)
{
  double lRemainder = GetTimeInSeconds();

  aHours = (int)(lRemainder / 3600.0);
  lRemainder -= aHours;

  aMinutes = (int)(lRemainder / 60.0);
  lRemainder -= aMinutes;

  aSeconds = (int)lRemainder;
  lRemainder -= aSeconds;

  aMilliseconds = (int)lRemainder;
}

#endif // __CHRONO_H__

[/pastacode]

c++, Informatique, snippet

Écart type en une passe

janvier 29, 2014 quirysse Laisser un commentaire

On a souvent besoin de calculer quelques statistiques sur un ensemble de données. Si calculer la moyenne en une passe est trivial, le calcul de l’écart type demande un peu d’attention. Ci-dessous, une solution que je poste comme pense-bête.

Le snippet calcule aussi les valeurs min et max.

Code snippet :

manual = "std::vector<int> vec;  // Container with values
uint64_t count = 0;
uint64_t accu = 0;
uint64_t accu2 = 0;
uint64_t min = -1;
uint64_t max = 0;

for_each(begin(vec), end(vec), [&](int x){
    accu  = x;
    accu2  = x * x;
    min = (std::min)(min, x);
    max = (std::max)(max, x);
      count;
});

float average = accu / float(count);
float stdev = sqrt(accu2 * count - accu * accu) / count;

Écart type en une passe

Grandes Bidouilles

Archives de catégorie : Informatique

Anagrammes

Comment enlever les accents des caractères en C++

Unicode, UTF-8 et autres considérations

Unicode, UTF-8 et autres considérations

256, c’est joli mais c’est petit

On veut des bits

Mais alors, c’est quoi un caractère ?

La ponctuation ?

Et concrètement ?

Identification de la langue d’un texte

Identification de la langue d’un texte

Heu… mais pour quoi faire ?

Étapes du projet

État des lieux

Corpus d’apprentissage

Analyse

Stockage

Détection de la langue

Interface

Conclusion

Framboise en boîte 4/N

Le futur

Retour sur l’Arros-o-tron

Contrôleur du travail

Le contrôle de la carte à relais

Petit mot sur le futur

Le port série automagique

La suite

Générer un jeu de Dobble

1. Trouver l’algorithme

2. Générer les cartes

3. Le script de rendu

Syntaxe

Chronomètre basique

Écart type en une passe

Site sur le bricolage, la bidouille et l'informatique