Filtrage par motif
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Le filtrage par motif, en anglais pattern matching, est la vérification de la présence de constituants d'un motif dans un programme informatique. Par contraste avec la reconnaissance de forme, les motifs sont spécifiés rigidement. De tels motifs concernent conventionnellement des séquences ou des arbres.

On utilise le filtrage par motif pour vérifier que l'objet (De manière générale, le mot objet (du latin objectum, 1361) désigne une entité définie dans un espace à trois dimensions, qui a une fonction...) filtré a la structure désirée, pour y trouver une structure appropriée, pour y retrouver des parties alignées ou pour substituer quelque chose d'autre aux motifs reconnus.

Les séquences (particulièrement les chaînes de caractères) sont souvent décrites par des expressions rationnelles. Elles peuvent aussi être vues comme des arbres.

Les motifs d'arbre (Un arbre est une plante terrestre capable de se développer par elle-même en hauteur, en général au delà de sept mètres. Les arbres acquièrent une structure rigide composée...) peuvent être utilisés par les langages de programmation (La programmation dans le domaine informatique est l'ensemble des activités qui permettent l'écriture des programmes informatiques. C'est une étape importante de la conception de logiciel (voire de matériel, cf. VHDL).) comme un outil (Un outil est un objet finalisé utilisé par un être vivant dans le but d'augmenter son efficacité naturelle dans l'action. Cette augmentation se traduit par la simplification des actions...) général pour traiter leur structure. Certains langages de programmation fonctionnelle (Un langage fonctionnel est un langage de programmation dont la syntaxe et les caractéristiques encouragent la programmation fonctionnelle. Le langage...) tels que Haskell, ML et le langage de mathématiques (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que les nombres, les figures, les structures et les transformations. Les mathématiques...) symboliques Mathematica ont une syntaxe spéciale pour exprimer les motifs d'arbre et une construction de langage pour l'exécution conditionnelle et la récupération de valeurs fondée sur celle-ci. Pour des raisons d'efficacité et de simplicité, ces motifs d'arbre n'ont pas toutes les fonctionnalités propres aux expressions rationnelles.

Selon le langage, les expressions de reconnaissance de motif peuvent être utilisées comme argument de fonctions, dans des expressions case où de nouvelles variables sont liées, ou dans des situations très limitées comme l'affectation (En algorithmique (informatique), une affectation est une opération qui permet d'attribuer une valeur à une variable.) en Python. Il est souvent possible de donner des motifs alternatifs qui sont essayés en séquence. La reconnaissance de motif peut bénéficier de gardes.

Les langages de réécriture de termes reposent sur le filtrage par motif comme manière fondamentale (En musique, le mot fondamentale peut renvoyer à plusieurs sens.) pour un programme d'évaluer un résultat.

Le filtrage par motif est le plus approprié quand la structure de données (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction d'affaire, d'un événement, etc.) sous-jacente est aussi simple et flexible que possible. C'est particulièrement le cas pour les langages avec un penchant symbolique. Dans ceux-ci, les motifs sont du même type que le reste des données, et peuvent donc être passés en paramètres à des fonctions. En d'autre termes, ce sont des entités de première classe (Dans un moyen de transport (avion, train ou bateau), la première classe est la classe la plus confortable et celle offrant généralement le plus de prestations. En outre, l'ambiance y est feutrée, la...).

Le filtrage par motif reconnaît un motif dans une structure arborescente préexistante tandis que les expressions rationnelles reconnaissent un motif dans une structure plate. Perl 6 propose un système qui intègre les deux sémantiques dans une syntaxe concrète (La concrète est une pâte plus ou moins dure obtenue après extraction d’une matière première fraîche d’origine...) unifiée.

Exemple de filtrage en OCaml

Dans cet exemple écrit en OCaml, on crée une liste puis on définit une fonction récursive (En informatique et en mathématiques, le terme fonction récursive désigne deux concepts liés, mais distincts. Plus généralement les termes « récursif », « récursivement », « récursion », « récursivité »,...) de recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances...) dans la liste à l'aide d'un filtrage.

 
 # let l1 = [3 ; 4 ; 5];; 
 val l1: int list = [3; 4; 5] 
 # let rec est_dans_liste x l = match l with 
 | [] -> false 
 (* fin de la liste: l'élément n'a pas été trouvé *) 
 | i::l' -> x = i or est_dans_liste x l' 
 (* il y a au moins un élément dans la liste: on le compare et si ce n'est pas le bon on continue le parcours récursif de l *) 
 ;; 
 val est_dans_liste: 'a -> 'a list -> bool =  
 # est_dans_liste 4 l1;; (* recherche de l'entier 4 dans la liste l1 *) 
 -: bool = true 
 # est_dans_liste 4 [];; (* recherche de l'entier 4 dans une liste vide (Le vide est ordinairement défini comme l'absence de matière dans une zone spatiale.) *) 
 -: bool = false 
 
Page générée en 0.068 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique