Différences
Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
tc_info:cm3 [2018/11/19 15:05] – [4.2 Indexation] edauce | tc_info:cm3 [2019/11/20 12:22] (Version actuelle) – edauce | ||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
+ | ==== CM3 : Données non structurées | ||
+ | |||
+ | ===== 3. Données non structurées ===== | ||
+ | |||
+ | < | ||
+ | **TBD** : Manu | ||
+ | |||
+ | * chaine de caractères | ||
+ | * fichiers textes (stockage, utf8, lecture et ecriture) | ||
+ | * expressions régulières | ||
+ | </ | ||
+ | |||
+ | ==== 3.1 Données texte ==== | ||
+ | |||
+ | === 3.1.1 Codage des caractères === | ||
+ | <code python> | ||
+ | x = ' | ||
+ | </ | ||
+ | * '' | ||
+ | * '' | ||
+ | |||
+ | * | ||
+ | * Codage ASCII : | ||
+ | * codage de symboles du clavier numérique. | ||
+ | * Le nombre de symboles étant inférieur à 256, on le code sur un octet : 2⁸ (= 256) valeurs différentes | ||
+ | * Codage UTF-8 : | ||
+ | * codage universel qui permet entre autre de coder les accents | ||
+ | * Codage ISO 90... | ||
+ | |||
+ | === 3.1.2 Codage des mots et du texte === | ||
+ | Chaîne de caractère : | ||
+ | <code python> | ||
+ | s = " | ||
+ | </ | ||
+ | * '' | ||
+ | * ''" | ||
+ | * " | ||
+ | * assimilable à un tableau de caractère : | ||
+ | <code python> | ||
+ | for c in s : | ||
+ | print (c) | ||
+ | </ | ||
+ | Affiche : | ||
+ | b | ||
+ | o | ||
+ | n | ||
+ | j | ||
+ | o | ||
+ | u | ||
+ | r | ||
+ | |||
+ | Le programme affiche les caractère 1 par 1, c’est une " | ||
+ | |||
+ | === 3.1.3 Textes et bases de textes === | ||
+ | |||
+ | Un texte, au même titre qu'un mot, est une chaîne de caractères (dont la longueur est définie par la longueur de | ||
+ | la séquence de caractères qui définissent le textes, ponctuations, | ||
+ | <note tip> ** Les caractères séparateurs ** | ||
+ | |||
+ | Par définition les caractères séparateurs définissent la taille des espaces entre les mots, ainsi que les passages à la ligne lors de l' | ||
+ | * ''""'' | ||
+ | * ''" | ||
+ | * ''" | ||
+ | * ''" | ||
+ | * ''" | ||
+ | * etc. | ||
+ | </ | ||
+ | * Bases de textes : ensemble constitué de plusieurs textes | ||
+ | * Bases de documents, | ||
+ | * Dossiers contenant des documents | ||
+ | * Collections de livres (électroniques) | ||
+ | * → 10 - 10⁴ | ||
+ | * Contenus en ligne (descriptifs de films, articles de journaux, descriptifs de produits.) | ||
+ | * → 10⁵ - 10⁶ | ||
+ | * Ensemble du web (les pages web, en tant que telles, peuvent être considérées comme du texte mis en forme par du html). | ||
+ | * → 10⁹ | ||
+ | * Messageries, | ||
+ | * 10³ - 10⁶ | ||
+ | |||
+ | ==== 3.2 Recherche dans les textes ==== | ||
+ | ==Exemples :== | ||
+ | * → Recherche d’un terme : “artichaud” | ||
+ | * → Recherche d’un motif (expression régulière) : une adresse email, une URL, un expéditeur, | ||
+ | |||
+ | ==Problématiques de la recherche de texte :== | ||
+ | |||
+ | * temps de réponse des algorithmes : | ||
+ | * l’utilisateur classique veut attendre moins de 2 à 3 secondes. | ||
+ | * Sur des bases extrêmement grandes (type recherche web), il faut donc être très performant pour atteindre ces temps de réponses. | ||
+ | * Stockage des données : | ||
+ | * intégralité des textes ou simple descriptif/ | ||
+ | * Les moteurs de recherche par exemple ne stockent aucune page web, ils ne stockent que des index et des références. | ||
+ | |||
+ | |||
+ | ==Remarque :== | ||
+ | Un document texte pourra être décrit soit comme : | ||
+ | * une séquence de caractères (lettres) | ||
+ | * une séquence de termes (mots) | ||
+ | |||
+ | |||
+ | === 3.2.1 Recherche simple === | ||
+ | < | ||
+ | TODO | ||
+ | </ | ||
+ | |||
+ | '' | ||
+ | On cherche un algorithme qui retourne toutes les occurrences (position dans le doc) d’un certain terme '' | ||
+ | |||
+ | '' | ||
+ | |||
+ | '' | ||
+ | |||
+ | "Les amis de mes amis sont mes amis." | ||
+ | | ||
+ | | ||
+ | |||
+ | * → La position de la première occurrence du terme t : | ||
+ | * → Les positions de toutes les occurrences du terme t : | ||
+ | * Complexité : $O(m \times k)$ | ||
+ | |||
+ | **Remarque :** Il peut être nécessaire de vérifier que le terme est précédé et suivi par les caractères d’espacement pour éviter de détecter les mots dont le mot recherché est préfixe ou suffixe. | ||
+ | |||
+ | === 3.2.2 Compter les mots === | ||
+ | < | ||
+ | TODO | ||
+ | </ | ||
+ | |||
+ | Lecture séquentielle des caractères : | ||
+ | "Les amis de mes amis sont mes amis." | ||
+ | | ||
+ | | ||
+ | |||
+ | * Il ne faut compter que les debuts de mots | ||
+ | * Un début de mot est un caractère // | ||
+ | < | ||
+ | {a, | ||
+ | </ | ||
+ | * Tout ce qui n'est pas alphanumérique est un caractère // | ||
+ | < | ||
+ | {!,#, | ||
+ | </ | ||
+ | * Autrement dit on compte les couples (caractère séparateur, | ||
+ | * remarque : le début de chaîne compte comme un caractère séparateur | ||
+ | |||
+ | **remarque** : pour extraire la liste des mots présents dans le texte, on doit identifier les débuts et les fins de mots : | ||
+ | * un début de mot est un couple (sep., alphanum.) | ||
+ | * une fin de mot est un couple (alphanum., sep.) | ||
+ | |||
+ | === 3.2.3 Recherche de motifs et expressions régulières === | ||
+ | |||
+ | De manière plus générale recherche d’expressions peut être effectuée à l’aide d’**automates finis**. | ||
+ | * Un automate fini est un graphe défini par des états et des transitions d’état. | ||
+ | * Parmi les états on distingue les états initiaux et terminaux. | ||
+ | * Les transitions permettent de passer d’un état à l’autre selon une condition : | ||
+ | * Si la condition est remplie l’automate change d’état | ||
+ | * Si aucune condition n’est remplie, l’automate s’arrête | ||
+ | * Lorsque l' | ||
+ | |||
+ | Lecture séquentielle des caractères : | ||
+ | "Les amis de mes amis sont mes amis." | ||
+ | | ||
+ | | ||
+ | |||
+ | Représentation graphique : | ||
+ | {{http:// | ||
+ | (source : '' | ||
+ | |||
+ | * les états dans des cercles, | ||
+ | * l’unique état initial par une flèche pointant sur un état, | ||
+ | * les états terminaux par un double cercle concentrique sur l’état. | ||
+ | * Les transitions d’état quant à elles sont représentées par une flèche allant de l’état de départ jusqu’à l’état d’arrivée indexée par le caractère (ou le groupe de caractères) autorisant la transition. | ||
+ | |||
+ | Traduction sous forme d' | ||
+ | (a|b)*ab | ||
+ | Ce motif reconnaît les mots suivants : | ||
+ | ab | ||
+ | aab | ||
+ | bab | ||
+ | aaab | ||
+ | abab | ||
+ | baab | ||
+ | bbab | ||
+ | aaaab | ||
+ | etc.. | ||
+ | |||
+ | **Remarques** : | ||
+ | * Les classes d' | ||
+ | * En python, les expressions régulières s' | ||
+ | |||
+ | **Exemples**: | ||
+ | * Reconnaître un mot : | ||
+ | {{: | ||
+ | * Reconnaître un nombre entier : '' | ||
+ | {{: | ||
+ | * Reconnaître un nombre réel : | ||
+ | * ?? | ||
+ | |||
+ | === Syntaxe des expressions régulières Python === | ||
+ | |||
+ | Définition : Il s’agit d’une syntaxe “condensée” de description d’automates finis permettant de reconnaître des motifs dans un texte. | ||
+ | |||
+ | En Python, les expressions régulières sont implémentées dans la librairie '' | ||
+ | |||
+ | <code python> | ||
+ | |||
+ | import re | ||
+ | |||
+ | d = "Les astronautes de la mission Gemini 8 sont désignés le 20 septembre 1965 : Armstrong est le commandant et David Scott le pilote. Ce dernier est le premier membre du groupe d' | ||
+ | |||
+ | liste_termes = re.findall(r" | ||
+ | </ | ||
+ | |||
+ | == Transitions : caractères et groupes de caractères== | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | |||
+ | Def : une expression est définie comme une suite de transition. Le mot est accepté lorsque la suite de transitions est respectée | ||
+ | |||
+ | Exemple : | ||
+ | r" | ||
+ | accepte chalet et chalut | ||
+ | r" | ||
+ | accepte tous les mots de 3 lettres | ||
+ | == Branchements et Récursion == | ||
+ | * Les parenthèses permettent : | ||
+ | * de délimiter une expression (qui peut alors être traitée comme une transition) | ||
+ | * '' | ||
+ | * de définir des branchements : | ||
+ | * '' | ||
+ | |||
+ | * '' | ||
+ | * '' | ||
+ | * ''?'' | ||
+ | |||
+ | ==exemples== | ||
+ | |||
+ | * reconnaître une adresse mail : | ||
+ | < | ||
+ | | ||
+ | </ | ||
+ | ==== 3.3 Comparaison/ | ||
+ | |||
+ | < | ||
+ | TODO | ||
+ | </ | ||
+ | ==== 3.4 Complétion / Correction ==== | ||
+ | < | ||
+ | TODO | ||
+ | </ | ||
+ | |||