Chaîne de caractères (informatique)

De nombreux langages, y compris ceux orientés objet, implémentent des chaînes sous forme d'enregistrements avec une structure interne comme :

chaîne de classe { size_t length ; char * texte ; };

Cependant, comme l'implémentation est généralement masquée , la chaîne doit être consultée et modifiée via des fonctions membres. textest un pointeur vers une zone de mémoire allouée dynamiquement, qui peut être étendue selon les besoins. Voir aussi string (C++) .

Les codes de longueur et de terminaison de caractère limitent les chaînes : par exemple, les tableaux de caractères C contenant des caractères nuls (NUL) ne peuvent pas être gérés directement par les fonctions de la bibliothèque de chaînes C : les chaînes utilisant un code de longueur sont limitées à la valeur maximale du code de longueur.

Ces deux limitations peuvent être surmontées grâce à une programmation intelligente.

Il est possible de créer des structures de données et des fonctions qui les manipulent sans avoir les problèmes associés à la terminaison de caractères et qui peuvent en principe surmonter les limites du code de longueur. Il est également possible d'optimiser la chaîne représentée en utilisant des techniques de codage de longueur d'exécution (remplacement des caractères répétés par la valeur du caractère et une longueur) et de codage de Hamming .

Bien que ces représentations soient courantes, d'autres sont possibles. L'utilisation de cordes rend certaines opérations de chaîne, telles que les insertions, les suppressions et les concaténations, plus efficaces.

La structure de données principale d'un éditeur de texte est celle qui gère la chaîne (séquence de caractères) qui représente l'état actuel du fichier en cours d'édition. Alors que cet état pourrait être stocké dans un seul long tableau consécutif de caractères, un éditeur de texte classique utilise plutôt une représentation alternative comme structure de données de séquence (un tampon d'espacement , une liste chaînée de lignes, une table de pièces ou une corde ), ce qui rend certaines opérations de chaîne, telles que les insertions, les suppressions et l'annulation de modifications précédentes, plus efficaces.

La configuration de mémoire et les exigences de stockage différentes des chaînes peuvent affecter la sécurité du programme accédant aux données de la chaîne. Les représentations de chaîne nécessitant un caractère de fin sont généralement sujettes à des problèmes de dépassement de mémoire tampon si le caractère de fin n'est pas présent, en raison d'une erreur de codage ou d'une modification délibérée des données par un attaquant . Les représentations de chaîne adoptant un champ de longueur distinct sont également sujettes à des problèmes si la longueur peut être manipulée. Dans de tels cas, le code du programme accédant aux données de la chaîne nécessite une vérification des limites pour garantir qu'il n'accède pas par inadvertance ou ne modifie pas les données en dehors des limites de la mémoire de la chaîne.

Les données de chaîne sont souvent obtenues à partir des entrées utilisateur dans un programme. Il incombe donc au programme de valider la chaîne pour s'assurer qu'elle représente le format attendu. Une validation limitée ou inexistante des entrées utilisateur peut rendre un programme vulnérable aux attaques par injection de code .

Parfois, les chaînes doivent être intégrées dans un fichier texte à la fois lisible par l'homme et destiné à être utilisé par une machine. Cela est nécessaire, par exemple, dans le code source des langages de programmation ou dans les fichiers de configuration. Dans ce cas, le caractère NUL ne fonctionne pas bien comme terminateur car il est normalement invisible (non imprimable) et difficile à saisir via un clavier. Le stockage de la longueur de la chaîne serait également peu pratique, car le calcul manuel et le suivi de la longueur sont fastidieux et sujets aux erreurs.

Deux représentations courantes sont :

• Entouré de guillemets ( guillemets doubles ASCII 0x22"str" ou guillemets simples ASCII 0x27 'str'), utilisés par la plupart des langages de programmation. Pour pouvoir inclure des caractères spéciaux tels que le guillemet lui-même, des caractères de nouvelle ligne ou des caractères non imprimables, des séquences d'échappement sont souvent disponibles, généralement préfixées par le caractère barre oblique inverse (ASCII 0x5C).
• Terminé par une séquence de nouvelle ligne , par exemple dans les fichiers INI de Windows .

Bien que les chaînes de caractères soient des utilisations très courantes des chaînes, une chaîne en informatique peut faire référence de manière générique à toute séquence de données typées de manière homogène. Une chaîne de bits ou une chaîne d'octets , par exemple, peut être utilisée pour représenter des données binaires non textuelles récupérées à partir d'un support de communication. Ces données peuvent ou non être représentées par un type de données spécifique à la chaîne, en fonction des besoins de l'application, du désir du programmeur et des capacités du langage de programmation utilisé. Si l'implémentation de chaîne du langage de programmation n'est pas propre sur 8 bits , une corruption des données peut s'ensuivre.

Les programmeurs C font une nette distinction entre une « chaîne », c'est-à-dire une « chaîne de caractères », qui par définition est toujours terminée par un caractère nul, et une « chaîne d'octets » ou une « pseudo-chaîne » qui peut être stockée dans le même tableau mais qui n'est souvent pas terminée par un caractère nul. L'utilisation de fonctions de gestion de chaînes C sur une telle « chaîne d'octets » semble souvent fonctionner, mais conduit ensuite à des problèmes de sécurité.

Il existe de nombreux algorithmes de traitement de chaînes, chacun présentant des compromis différents. Les algorithmes concurrents peuvent être analysés en fonction du temps d'exécution, des besoins de stockage, etc. Le nom de stringologie a été inventé en 1984 par l'informaticien Zvi Galil pour la théorie des algorithmes et des structures de données utilisés pour le traitement des chaînes.

Certaines catégories d’algorithmes incluent :

• Algorithmes de recherche de chaîne pour trouver une sous-chaîne ou un modèle donné
• Algorithmes de manipulation de chaînes
• Algorithmes de tri
• Algorithmes d'expression régulière
• Analyse d'une chaîne
• Extraction de séquences

Les algorithmes de chaînes avancés utilisent souvent des mécanismes et des structures de données complexes, parmi lesquels des arbres de suffixes et des machines à états finis .

Les chaînes de caractères sont un type de données tellement utile que plusieurs langages ont été conçus pour faciliter l'écriture d'applications de traitement de chaînes. Les exemples incluent les langages suivants :

• AWK
• Icône
• OREILLONS
• Perl
• Rexx
• Rubis
• sed
• SNOBOL
• Tcl
• TTM

De nombreux utilitaires Unix effectuent des manipulations simples de chaînes et peuvent être utilisés pour programmer facilement des algorithmes puissants de traitement de chaînes. Les fichiers et les flux finis peuvent être considérés comme des chaînes.

Certaines API comme Multimedia Control Interface , Embedded SQL ou printf utilisent des chaînes pour contenir des commandes qui seront interprétées.

De nombreux langages de programmation de scripts , dont Perl, Python , Ruby et Tcl, utilisent des expressions régulières pour faciliter les opérations sur texte. Perl est particulièrement connu pour son utilisation d'expressions régulières, et de nombreux autres langages et applications implémentent des expressions régulières compatibles avec Perl .

Certains langages tels que Perl et Ruby prennent en charge l'interpolation de chaîne , ce qui permet d'évaluer des expressions arbitraires et de les inclure dans des littéraux de chaîne.

Les fonctions de chaîne sont utilisées pour créer des chaînes ou modifier le contenu d'une chaîne mutable. Elles sont également utilisées pour interroger des informations sur une chaîne. L'ensemble des fonctions et leurs noms varient en fonction du langage de programmation informatique .

L'exemple le plus basique d'une fonction de chaîne est la fonction de longueur de chaînelength , qui renvoie la longueur d'une chaîne (sans compter les caractères de terminaison ni les informations structurelles internes de la chaîne) et ne modifie pas la chaîne. Cette fonction est souvent nommée ou len. Par exemple, length("hello world")elle renvoie 11. Une autre fonction courante est la concaténation , où une nouvelle chaîne est créée en ajoutant deux chaînes, il s'agit souvent de l'opérateur d'addition +.

Certaines architectures de jeu d'instructions de microprocesseurs contiennent un support direct pour les opérations de chaîne, telles que la copie de bloc (par exemple dans Intel x86m ). REPNZ MOVSB

Soit Σ un ensemble fini de symboles distincts et non ambigus (appelés aussi caractères), appelé l' alphabet . Une chaîne (ou un mot ou une expression séquence finie de symboles de Σ. Par exemple, si Σ = {0, 1}, alors 01011 est une chaîne sur Σ.

La longueur d'une chaîne s est le nombre de symboles dans s (la longueur de la séquence) et peut être n'importe quel entier non négatif ; elle est souvent notée | s |. La chaîne vide est la chaîne unique sur Σ de longueur 0, et est notée ε ou λ .

L'ensemble de toutes les chaînes de caractères sur Σ de longueur n est noté Σ ⁿ . Par exemple, si Σ = {0, 1}, alors Σ ² = {00, 01, 10, 11}. On a Σ ⁰ = {ε} pour tout alphabet Σ.

L'ensemble de toutes les chaînes sur Σ de n'importe quelle longueur est la fermeture de Kleene de Σ et est noté Σ ^* . En termes de Σ ⁿ ,

Par exemple, si Σ = {0, 1}, alors Σ ^* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ...}. Bien que l'ensemble Σ ^* lui-même soit dénombrablement infini , chaque élément de Σ ^* est une chaîne de longueur finie.

Un ensemble de chaînes sur Σ (c'est-à-dire tout sous-ensemble de Σ ^* ) est appelé langage formel sur Σ. Par exemple, si Σ = {0, 1}, l'ensemble des chaînes avec un nombre pair de zéros, {ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111, ...}, est un langage formel sur Σ.

La concaténation est une opération binaire importante sur Σ ^* . Pour deux chaînes s et t quelconques dans Σ ^* , leur concaténation est définie comme la séquence de symboles dans s suivie de la séquence de caractères dans t , et est notée st . Par exemple, si Σ = {a, b, ..., z}, s = bearet t = hug, alors st = bearhuget ts = hugbear.

La concaténation de chaînes est une opération associative , mais non commutative . La chaîne vide ε sert d' élément d'identité ; pour toute chaîne s , ε s = s ε = s . Par conséquent, l'ensemble Σ ^* et l'opération de concaténation forment un monoïde , le monoïde libre engendré par Σ. De plus, la fonction de longueur définit un homomorphisme de monoïde de Σ ^* vers les entiers non négatifs (c'est-à-dire une fonction , telle que ).

Une chaîne s est dite sous-chaîne ou facteur de t s'il existe des chaînes u et v (éventuellement vides) telles que t = usv . La relation « est une sous-chaîne de » définit un ordre partiel sur Σ ^* , dont le plus petit élément est la chaîne vide.

Une chaîne s est dite préfixe de t s'il existe une chaîne u telle que t = su . Si u n'est pas vide, s est dite préfixe propre de t . Symétriquement, une chaîne s est dite suffixe de t s'il existe une chaîne u telle que t = us . Si u n'est pas vide, s est dite suffixe propre de t . Les suffixes et les préfixes sont des sous-chaînes de t . Les relations « est préfixe de » et « est suffixe de » sont des ordres de préfixes .

L'inverse d'une chaîne est une chaîne contenant les mêmes symboles mais dans l'ordre inverse. Par exemple, si s = abc (où a, b et c sont des symboles de l'alphabet), alors l'inverse de s est cba. Une chaîne qui est l'inverse d'elle-même (par exemple, s = madam) est appelée un palindrome , qui comprend également la chaîne vide et toutes les chaînes de longueur 1.

On dit qu'une chaîne s = uv est une rotation de t si t = vu . Par exemple, si Σ = {0, 1} la chaîne 0011001 est une rotation de 0100110, où u = 00110 et v = 01. Autre exemple, la chaîne abc a trois rotations différentes, à savoir abc elle-même (avec u = abc, v = ε), bca (avec u = bc, v = a) et cab (avec u = c, v = ab).

Il est souvent utile de définir un ordre sur un ensemble de chaînes de caractères. Si l'alphabet Σ possède un ordre total (cf. ordre alphabétique ) on peut définir un ordre total sur Σ ^* appelé ordre lexicographique . L'ordre lexicographique est total si l'ordre alphabétique l'est, mais n'est bien fondé pour aucun alphabet non trivial, même si l'ordre alphabétique l'est. Par exemple, si Σ = {0, 1} et 0 < 1, alors l'ordre lexicographique sur Σ ^* inclut les relations ε < 0 < 00 < 000 < ... < 0001 < ... < 001 < ... < 01 < 010 < ... < 011 < 0110 < ... < 01111 < ... < 1 < 10 < 100 < ... < 101 < ... < 111 < ... < 1111 < ... < 11111 ... Par rapport à cet ordre, par exemple l'ensemble infini { 1, 01, 001, 0001, 00001, 000001, ... } n'a pas d'élément minimal.

Voir Shortlex pour un autre ordre de chaîne qui préserve la validité. Pour l'exemple d'alphabet, l'ordre Shortlex est ε < 0 < 1 < 00 < 01 < 10 < 11 < 000 < 001 < 010 < 011 < 100 < 101 < 0110 < 111 < 0000 < 0001 < 0010 < 0011 < ... < 1111 < 00000 < 00001 ...

Un certain nombre d'opérations supplémentaires sur les chaînes de caractères sont courantes dans la théorie formelle. Elles sont présentées dans l'article sur les opérations sur les chaînes de caractères .

Les chaînes admettent l'interprétation suivante en tant que nœuds sur un graphique, où k est le nombre de symboles dans Σ :

• Les chaînes de longueur fixe de longueur n peuvent être considérées comme les emplacements entiers dans un hypercube à n dimensions avec des côtés de longueur k -1.
• Les chaînes de longueur variable (de longueur finie) peuvent être considérées comme des nœuds sur un arbre k -aire parfait .
• Les chaînes infinies (autrement non prises en compte ici) peuvent être considérées comme des chemins infinis sur un graphe complet à k nœuds .

La topologie naturelle sur l'ensemble des chaînes de longueur fixe ou variable est la topologie discrète, mais la topologie naturelle sur l'ensemble des chaînes infinies est la topologie limite , considérant l'ensemble des chaînes infinies comme la limite inverse des ensembles de chaînes finies. C'est la construction utilisée pour les nombres p -adiques et certaines constructions de l' ensemble de Cantor , et elle donne la même topologie.

Les isomorphismes entre les représentations de chaînes de topologies peuvent être trouvés en normalisant selon la rotation de chaîne lexicographiquement minimale .