Archives de catégorie : Unicode

Unicode, UTF-8 et autres considérations

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 inuitcyrillyquehindî, 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.)

#include <fstream>
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

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

typedef std::map<std::string, int> histotype;
typedef std::pair<std::string, int> histonodetype;

void PrintGrams(const histotype& gram)
{
    std::vector<histonodetype> 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<ittype> it(line.begin(), line.begin(), line.end());
        utf8::iterator<ittype> 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;
}
Programme de création de n-grammes

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.

 

Identification de la langue d’un texte

 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.

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$
Espace occupé par deux langues sur Wikipedia

 

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…