En programación de computadoras , una cadena es tradicionalmente una secuencia de caracteres , ya sea como una constante literal o como algún tipo de variable . Este último puede permitir que sus elementos sean mutados y cambiar la longitud, o puede ser fijo (después de la creación). Una cadena generalmente se considera un tipo de datos y a menudo se implementa como una estructura de datos de matriz de bytes (o palabras ) que almacena una secuencia de elementos, generalmente caracteres, utilizando alguna codificación de caracteres . Cadena también puede denotar matrices más generales u otras estructuras y tipos de datos de secuencia (o lista ).
Dependiendo del lenguaje de programación y del tipo de datos preciso utilizado, una variable declarada como una cadena puede hacer que el almacenamiento en la memoria se asigne estáticamente para una longitud máxima predeterminada o emplear una asignación dinámica para permitirle contener un número variable de elementos.
Cuando una cadena aparece literalmente en el código fuente , se conoce como cadena literal o cadena anónima. [1]
En los lenguajes formales , que se utilizan en lógica matemática e informática teórica , una cadena es una secuencia finita de símbolos que se eligen de un conjunto llamado alfabeto .
El propósito principal de las cadenas es almacenar texto legible por humanos, como palabras y oraciones. Las cadenas se utilizan para comunicar información de un programa de computadora al usuario del programa. [2] Un programa también puede aceptar entradas de cadenas de su usuario. Además, las cadenas pueden almacenar datos expresados como caracteres que aún no están destinados a la lectura humana.
Cadenas de ejemplo y sus propósitos:
file upload complete" es una cadena que el software muestra a los usuarios finales . En el código fuente del programa , este mensaje probablemente aparecería como una cadena literal .I got a new job today", como actualización de estado en un servicio de redes sociales . En lugar de una cadena literal, el software probablemente almacenaría esta cadena en una base de datos .AGATGCCGT" que representan secuencias de ácidos nucleicos del ADN . [3]?action=edit" como cadena de consulta de URL . A menudo, están destinados a ser legibles por humanos, aunque su propósito principal es comunicarse con las computadoras.El término cadena también puede designar una secuencia de datos o registros informáticos distintos de caracteres (como una "cadena de bits "), pero cuando se utiliza sin calificación se refiere a cadenas de caracteres. [4]
El uso de la palabra "cadena" para referirse a cualquier elemento dispuesto en una línea, serie o sucesión se remonta a siglos atrás. [5] [6] En la composición tipográfica del siglo XIX, los compositores usaban el término "cadena" para indicar la longitud del tipo impreso en papel; la cuerda se mediría para determinar el salario del compositor. [7] [4] [8]
El uso de la palabra "cadena" para significar "una secuencia de símbolos o elementos lingüísticos en un orden definido" surgió de las matemáticas, la lógica simbólica y la teoría lingüística para hablar sobre el comportamiento formal de los sistemas simbólicos, dejando de lado el significado de los símbolos. [4]
Por ejemplo, el lógico CI Lewis escribió en 1918: [9]
Un sistema matemático es cualquier conjunto de cadenas de marcas reconocibles en el que algunas de las cadenas se toman inicialmente y el resto se deriva de ellas mediante operaciones realizadas de acuerdo con reglas que son independientes de cualquier significado asignado a las marcas. Que un sistema esté compuesto por "marcas" en lugar de sonidos u olores es irrelevante.
Según Jean E. Sammet , "el primer lenguaje realista de manejo de cadenas y coincidencia de patrones" para computadoras fue COMIT en la década de 1950, seguido por el lenguaje SNOBOL de principios de la década de 1960. [10]
Un tipo de datos de cadena es un tipo de datos modelado según la idea de una cadena formal. Las cadenas son un tipo de datos tan importante y útil que se implementan en casi todos los lenguajes de programación . En algunos idiomas están disponibles como tipos primitivos y en otros como tipos compuestos . La sintaxis de la mayoría de los lenguajes de programación de alto nivel permite que una cadena, generalmente citada de alguna manera, represente una instancia de un tipo de datos de cadena; dicha metacadena se denomina literal o literal de cadena .
Aunque las cadenas formales pueden tener una longitud finita arbitraria, la longitud de las cadenas en los lenguajes reales a menudo está limitada a un máximo artificial. En general, hay dos tipos de tipos de datos de cadena: cadenas de longitud fija , que tienen una longitud máxima fija que se determinará en el momento de la compilación y que utilizan la misma cantidad de memoria, ya sea que este máximo sea necesario o no, y cadenas de longitud variable , cuya longitud no es fija arbitrariamente y que puede utilizar diferentes cantidades de memoria dependiendo de los requisitos reales en tiempo de ejecución (consulte Gestión de memoria ). La mayoría de las cadenas en los lenguajes de programación modernos son cadenas de longitud variable. Por supuesto, incluso las cadenas de longitud variable están limitadas en longitud (por el tamaño de la memoria disponible de la computadora ). La longitud de la cadena se puede almacenar como un número entero separado (lo que puede imponer otro límite artificial a la longitud) o implícitamente a través de un carácter de terminación, generalmente un valor de carácter con todos los bits cero, como en el lenguaje de programación C. Consulte también "Terminado en nulo" a continuación.
Históricamente, los tipos de datos de cadena han asignado un byte por carácter y, aunque el conjunto de caracteres exacto variaba según la región, las codificaciones de caracteres eran lo suficientemente similares como para que los programadores a menudo pudieran ignorar esto, ya que los caracteres que un programa trataba de manera especial (como el punto, el espacio y la coma) ) estaban en el mismo lugar en todas las codificaciones que encontraría un programa. Estos conjuntos de caracteres normalmente se basaban en ASCII o EBCDIC . Si el texto en una codificación se mostraba en un sistema que usaba una codificación diferente, el texto a menudo estaba mutilado , aunque a menudo era algo legible y algunos usuarios de computadoras aprendían a leer el texto mutilado.
Los lenguajes logográficos como el chino , el japonés y el coreano (conocidos colectivamente como CJK ) necesitan mucho más de 256 caracteres (el límite de una codificación de un byte de 8 bits por carácter) para una representación razonable. Las soluciones normales implicaban mantener representaciones de un solo byte para ASCII y usar representaciones de dos bytes para ideogramas CJK . El uso de estos con el código existente generó problemas con la coincidencia y el corte de cadenas, cuya gravedad dependía de cómo se diseñó la codificación de caracteres. Algunas codificaciones, como la familia EUC , garantizan que un valor de byte en el rango ASCII representará solo ese carácter ASCII, lo que hace que la codificación sea segura para sistemas que utilizan esos caracteres como separadores de campos. Otras codificaciones, como ISO-2022 y Shift-JIS , no ofrecen tales garantías, lo que hace que la coincidencia de códigos de bytes sea insegura. Estas codificaciones tampoco eran "autosincronizadas", por lo que localizar los límites de los caracteres requería hacer una copia de seguridad hasta el inicio de una cadena, y pegar dos cadenas juntas podría provocar la corrupción de la segunda cadena.
Unicode ha simplificado un poco el panorama. La mayoría de los lenguajes de programación ahora tienen un tipo de datos para cadenas Unicode. El formato de flujo de bytes preferido de Unicode, UTF-8 , está diseñado para no tener los problemas descritos anteriormente para codificaciones multibyte más antiguas. UTF-8, UTF-16 y UTF-32 requieren que el programador sepa que las unidades de código de tamaño fijo son diferentes de los "caracteres", la principal dificultad actualmente son las API diseñadas incorrectamente que intentan ocultar esta diferencia (UTF-32 no hacer que los puntos de código tengan un tamaño fijo, pero estos no son "caracteres" debido a la composición de los códigos).
Algunos lenguajes, como C++ , Perl y Ruby , normalmente permiten cambiar el contenido de una cadena después de haberla creado; éstas se denominan cadenas mutables . En otros lenguajes, como Java , JavaScript , Lua , Python y Go , el valor es fijo y se debe crear una nueva cadena si se va a realizar alguna modificación; estas se denominan cadenas inmutables . Algunos de estos lenguajes con cadenas inmutables también proporcionan otro tipo que es mutable, como Java y .NET ,StringBuilder Java seguro para subprocesos StringBuffery Cocoa NSMutableString . La inmutabilidad tiene ventajas y desventajas: aunque las cadenas inmutables pueden requerir la creación de muchas copias de manera ineficiente, son más simples y completamente seguras para subprocesos .
Las cadenas normalmente se implementan como matrices de bytes, caracteres o unidades de código, para permitir un acceso rápido a unidades o subcadenas individuales, incluidos los caracteres cuando tienen una longitud fija. Algunos lenguajes como Haskell los implementan como listas enlazadas .
Algunos lenguajes, como Prolog y Erlang , evitan implementar un tipo de datos de cadena dedicado, adoptando en su lugar la convención de representar cadenas como listas de códigos de caracteres.
Las representaciones de cadenas dependen en gran medida de la elección del repertorio de caracteres y del método de codificación de caracteres. Las implementaciones de cadenas más antiguas se diseñaron para funcionar con el repertorio y la codificación definidos por ASCII o extensiones más recientes como la serie ISO 8859 . Las implementaciones modernas suelen utilizar el extenso repertorio definido por Unicode junto con una variedad de codificaciones complejas como UTF-8 y UTF-16.
El término cadena de bytes generalmente indica una cadena de bytes de propósito general, en lugar de cadenas de solo caracteres (legibles), cadenas de bits o similares. Las cadenas de bytes a menudo implican que los bytes pueden tomar cualquier valor y que cualquier dato puede almacenarse tal cual, lo que significa que no debe haber ningún valor interpretado como un valor de terminación.
La mayoría de las implementaciones de cadenas son muy similares a las matrices de longitud variable con las entradas que almacenan los códigos de caracteres de los caracteres correspondientes. La principal diferencia es que, con determinadas codificaciones, un único carácter lógico puede ocupar más de una entrada en la matriz. Esto sucede, por ejemplo, con UTF-8, donde los códigos únicos ( puntos de código UCS ) pueden ocupar de uno a cuatro bytes, y los caracteres individuales pueden ocupar un número arbitrario de códigos. En estos casos, la longitud lógica de la cadena (número de caracteres) difiere de la longitud física de la matriz (número de bytes en uso). UTF-32 evita la primera parte del problema.
La longitud de una cadena se puede almacenar implícitamente mediante el uso de un carácter de terminación especial; a menudo se trata del carácter nulo (NUL), que tiene todos los bits cero, una convención utilizada y perpetuada por el popular lenguaje de programación C. [11] Por lo tanto, esta representación se conoce comúnmente como cadena C. Esta representación de una cadena de n caracteres ocupa n + 1 espacio (1 para el terminador) y, por lo tanto, es una estructura de datos implícita .
En cadenas terminadas, el código de terminación no es un carácter permitido en ninguna cadena. Las cadenas con campo de longitud no tienen esta limitación y también pueden almacenar datos binarios arbitrarios .
Un ejemplo de una cadena terminada en nulo almacenada en un búfer de 10 bytes , junto con su representación ASCII (o UTF-8 más moderna) como números hexadecimales de 8 bits es:
La longitud de la cadena en el ejemplo anterior, " FRANK", es de 5 caracteres, pero ocupa 6 bytes. Los caracteres posteriores al terminador no forman parte de la representación; pueden ser parte de otros datos o simplemente basura. (Las cadenas de este formato a veces se denominan cadenas ASCIZ , en honor a la directiva del lenguaje ensamblador original utilizada para declararlas).
Históricamente, el uso de un byte especial distinto de nulo para terminar cadenas ha aparecido tanto en hardware como en software, aunque a veces con un valor que también era un carácter de impresión. $fue usado por muchos sistemas ensambladores, :usado por sistemas CDC (este carácter tenía un valor de cero), y el ZX80 usó "[12] ya que este era el delimitador de cadena en su lenguaje BASIC.
Algo similar, las máquinas de "procesamiento de datos" como la IBM 1401 usaban un bit de marca denominativa especial para delimitar cadenas a la izquierda, donde la operación comenzaría a la derecha. Este bit tenía que quedar claro en todas las demás partes de la cadena. Esto significó que, si bien el IBM 1401 tenía una palabra de siete bits, casi nadie pensó en usarla como una característica y anular la asignación del séptimo bit para (por ejemplo) manejar códigos ASCII.
Los primeros software de microcomputadoras se basaban en el hecho de que los códigos ASCII no usaban el bit de orden superior y lo configuraban para indicar el final de una cadena. Debe restablecerse a 0 antes de la salida. [13]
La longitud de una cadena también se puede almacenar explícitamente, por ejemplo, anteponiendo la longitud a la cadena como un valor de byte. Esta convención se utiliza en muchos dialectos de Pascal ; como consecuencia, algunas personas llaman a dicha cadena cadena Pascal o cadena P. El almacenamiento de la longitud de la cadena como bytes limita la longitud máxima de la cadena a 255. Para evitar tales limitaciones, las implementaciones mejoradas de cadenas P utilizan palabras de 16, 32 o 64 bits para almacenar la longitud de la cadena. Cuando el campo de longitud cubre el espacio de direcciones , las cadenas están limitadas sólo por la memoria disponible .
Si la longitud está limitada, entonces se puede codificar en un espacio constante, normalmente una palabra de máquina, lo que lleva a una estructura de datos implícita , tomando n + k espacio, donde k es el número de caracteres de una palabra (8 para 8 bits). ASCII en una máquina de 64 bits, 1 para UTF-32/UCS-4 de 32 bits en una máquina de 32 bits, etc.). Si la longitud no está limitada, codificar una longitud n requiere un espacio log( n ) (consulte el código de longitud fija ), por lo que las cadenas con prefijo de longitud son una estructura de datos concisa , que codifica una cadena de longitud n en un espacio log( n ) + n. .
En el último caso, el campo de prefijo de longitud en sí no tiene una longitud fija, por lo tanto, los datos reales de la cadena deben moverse cuando la cadena crece de modo que sea necesario aumentar el campo de longitud.
Aquí hay una cadena Pascal almacenada en un búfer de 10 bytes, junto con su representación ASCII/UTF-8:
Muchos lenguajes, incluidos los orientados a objetos, implementan cadenas como registros con una estructura interna como:
cadena de clase { tamaño_t longitud ; carácter * texto ; }; Sin embargo, dado que la implementación suele estar oculta , se debe acceder a la cadena y modificarla mediante funciones miembro. textes un puntero a un área de memoria asignada dinámicamente, que puede ampliarse según sea necesario. Véase también cadena (C++) .
Tanto la terminación de caracteres como los códigos de longitud limitan las cadenas: por ejemplo, las matrices de caracteres C que contienen caracteres nulos (NUL) no pueden ser manejadas directamente por las funciones de la biblioteca de cadenas C : las cadenas que utilizan un código de longitud están limitadas al valor máximo del código de longitud.
Ambas limitaciones pueden superarse mediante una programación inteligente.
Es posible crear estructuras de datos y funciones que los manipulen que no tengan los problemas asociados con la terminación de caracteres y que, en principio, puedan superar los límites de longitud del código. También es posible optimizar la cadena representada utilizando técnicas de codificación de longitud de ejecución (reemplazando caracteres repetidos por el valor del carácter y una longitud) y codificación Hamming [ aclaración necesaria ] .
Si bien estas representaciones son comunes, otras son posibles. El uso de cuerdas hace que ciertas operaciones de cadenas, como inserciones, eliminaciones y concatenaciones, sean más eficientes.
La estructura de datos central en un editor de texto es la que administra la cadena (secuencia de caracteres) que representa el estado actual del archivo que se está editando. Si bien ese estado podría almacenarse en una única y larga serie consecutiva de caracteres, un editor de texto típico utiliza una representación alternativa como estructura de datos de secuencia (un búfer de espacio , una lista enlazada de líneas, una tabla de piezas o una cuerda ), lo que hace que Ciertas operaciones de cadenas, como inserciones, eliminaciones y deshacer ediciones anteriores, son más eficientes. [14]
Los diferentes diseños de memoria y requisitos de almacenamiento de las cadenas pueden afectar la seguridad del programa que accede a los datos de la cadena. Las representaciones de cadenas que requieren un carácter de terminación suelen ser susceptibles a problemas de desbordamiento del búfer si el carácter de terminación no está presente, debido a un error de codificación o a que un atacante altere deliberadamente los datos. Las representaciones de cadenas que adoptan un campo de longitud separado también son susceptibles si la longitud se puede manipular. En tales casos, el código del programa que accede a los datos de la cadena requiere una verificación de límites para garantizar que no acceda ni cambie inadvertidamente datos fuera de los límites de memoria de la cadena.
Los datos de cadena se obtienen frecuentemente a partir de la entrada del usuario a un programa. Como tal, es responsabilidad del programa validar la cadena para garantizar que representa el formato esperado. Realizar una validación limitada o nula de la entrada del usuario puede hacer que un programa sea vulnerable a ataques de inyección de código .
A veces, es necesario incrustar cadenas dentro de un archivo de texto que sea legible por humanos y destinado a ser consumido por una máquina. Esto es necesario, por ejemplo, en el código fuente de los lenguajes de programación o en los archivos de configuración. En este caso, el carácter NUL no funciona bien como terminador ya que normalmente es invisible (no imprimible) y es difícil ingresarlo mediante un teclado. Almacenar la longitud de la cadena también sería inconveniente ya que el cálculo manual y el seguimiento de la longitud son tediosos y propensos a errores.
Dos representaciones comunes son:
"str" o comillas simples ASCII 0x27 'str'), utilizadas por la mayoría de los lenguajes de programación. Para poder incluir caracteres especiales como las comillas, caracteres de nueva línea o caracteres no imprimibles, a menudo están disponibles secuencias de escape , generalmente precedidas por el carácter de barra invertida (ASCII 0x5C).Si bien las cadenas de caracteres son usos muy comunes de las cadenas, una cadena en informática puede referirse genéricamente a cualquier secuencia de datos tipificados de manera homogénea. Se puede utilizar una cadena de bits o una cadena de bytes , por ejemplo, para representar datos binarios no textuales recuperados de un medio de comunicaciones. Estos datos pueden representarse o no mediante un tipo de datos específico de cadena, según las necesidades de la aplicación, el deseo del programador y las capacidades del lenguaje de programación que se utiliza. Si la implementación de cadenas del lenguaje de programación no es limpia en 8 bits , se pueden producir daños en los datos.
Los programadores de C hacen una clara distinción entre una "cadena", también conocida como "cadena de caracteres", que por definición siempre termina en nulo, frente a una "cadena de bytes" o "pseudocadena" que puede almacenarse en la misma matriz pero no a menudo no tiene terminación nula. El uso de funciones de manejo de cadenas C en una "cadena de bytes" de este tipo a menudo parece funcionar, pero luego genera problemas de seguridad. [15] [16] [17]
Existen muchos algoritmos para procesar cadenas, cada uno con diversas compensaciones. Los algoritmos en competencia se pueden analizar con respecto al tiempo de ejecución, los requisitos de almacenamiento, etc. El nombre stringología fue acuñado en 1984 por el informático Zvi Galil para la teoría de los algoritmos y las estructuras de datos utilizados para el procesamiento de cadenas. [18] [19] [20]
Algunas categorías de algoritmos incluyen:
Los algoritmos de cadenas avanzados a menudo emplean mecanismos y estructuras de datos complejos, entre ellos árboles de sufijos y máquinas de estados finitos .
Las cadenas de caracteres son un tipo de datos tan útil que se han diseñado varios lenguajes para que las aplicaciones de procesamiento de cadenas sean fáciles de escribir. Los ejemplos incluyen los siguientes idiomas:
Muchas utilidades de Unix realizan manipulaciones de cadenas simples y pueden usarse para programar fácilmente algunos algoritmos potentes de procesamiento de cadenas. Los archivos y flujos finitos pueden verse como cadenas.
Algunas API, como la interfaz de control multimedia , SQL incorporado o printf , utilizan cadenas para contener los comandos que se interpretarán.
Muchos lenguajes de programación de scripts , incluidos Perl, Python , Ruby y Tcl, emplean expresiones regulares para facilitar las operaciones de texto. Perl se destaca particularmente por su uso de expresiones regulares, [21] y muchos otros lenguajes y aplicaciones implementan expresiones regulares compatibles con Perl .
Algunos lenguajes como Perl y Ruby admiten la interpolación de cadenas , que permite evaluar e incluir expresiones arbitrarias en cadenas literales.
Las funciones de cadena se utilizan para crear cadenas o cambiar el contenido de una cadena mutable. También se utilizan para consultar información sobre una cadena. El conjunto de funciones y sus nombres varía según el lenguaje de programación del ordenador .
El ejemplo más básico de una función de cadena es la función de longitud de cadena : la función que devuelve la longitud de una cadena (sin contar los caracteres de terminación ni la información estructural interna de la cadena) y no modifica la cadena. Esta función suele denominarse lengtho len. Por ejemplo, length("hello world")devolvería 11. Otra función común es la concatenación , donde se crea una nueva cadena agregando dos cadenas; a menudo, este es el operador de suma +.
Las arquitecturas de conjuntos de instrucciones de algunos microprocesadores contienen soporte directo para operaciones de cadenas, como la copia en bloque (por ejemplo, en Intel x86m ). [22] REPNZ MOVSB
Sea Σ un conjunto finito de símbolos (alternativamente llamados caracteres), llamado alfabeto . No se hace ninguna suposición sobre la naturaleza de los símbolos. Una cadena (o palabra ) sobre Σ es cualquier secuencia finita de símbolos de Σ. [23] Por ejemplo, si Σ = {0, 1}, entonces 01011 es una cadena sobre Σ.
La longitud de una cadena s es el número de símbolos en s (la longitud de la secuencia) y puede ser cualquier número entero no negativo ; a menudo se denota como | s |. La cadena vacía es la cadena única sobre Σ de longitud 0 y se denota como ε o λ . [23] [24]
El conjunto de todas las cadenas sobre Σ de longitud n se denota como Σ n . Por ejemplo, si Σ = {0, 1}, entonces Σ 2 = {00, 01, 10, 11}. Tenemos Σ 0 = {ε} para cada alfabeto Σ.
El conjunto de todas las cadenas sobre Σ de cualquier longitud es la clausura de Kleene de Σ y se denota Σ * . En términos de Σ n ,
Por ejemplo, si Σ = {0, 1}, entonces Σ * = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ...}. Aunque el conjunto Σ * en sí mismo es contablemente infinito , cada elemento de Σ * es una cadena de longitud finita.
Un conjunto de cadenas sobre Σ (es decir, cualquier subconjunto de Σ * ) se denomina lenguaje formal sobre Σ. Por ejemplo, si Σ = {0, 1}, el conjunto de cadenas con un número par de ceros, {ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111, ...}, es un lenguaje formal sobre Σ.
La concatenación es una operación binaria importante en Σ * . Para dos cadenas cualesquiera s y t en Σ * , su concatenación se define como la secuencia de símbolos en s seguida por la secuencia de caracteres en t , y se denota st . Por ejemplo, si Σ = {a, b, ..., z}, s = beary t = hug, entonces st = bearhugy ts = hugbear.
La concatenación de cadenas es una operación asociativa , pero no conmutativa . La cadena vacía ε sirve como elemento de identidad ; para cualquier cadena s , ε s = s ε = s . Por tanto, el conjunto Σ * y la operación de concatenación forman un monoide , el monoide libre generado por Σ. Además, la función de longitud define un homomorfismo monoide de Σ * a los enteros no negativos (es decir, una función tal que ).
Se dice que una cadena s es una subcadena o factor de t si existen cadenas (posiblemente vacías) u y v tales que t = usv . La relación "es una subcadena de" define un orden parcial en Σ * , cuyo elemento menor es la cadena vacía.
Se dice que una cadena s es un prefijo de t si existe una cadena u tal que t = su . Si u no está vacío, se dice que s es un prefijo propio de t . Simétricamente, se dice que una cadena s es un sufijo de t si existe una cadena u tal que t = us . Si u no está vacío, se dice que s es un sufijo propio de t . Los sufijos y prefijos son subcadenas de t . Tanto las relaciones "es un prefijo de" como "es un sufijo de" son órdenes de prefijo .
El reverso de una cadena es una cadena con los mismos símbolos pero en orden inverso. Por ejemplo, si s = abc (donde a, byc son símbolos del alfabeto), entonces el reverso de s es cba. Una cadena que es el reverso de sí misma (por ejemplo, s = señora) se llama palíndromo , que también incluye la cadena vacía y todas las cadenas de longitud 1.
Se dice que una cadena s = uv es una rotación de t si t = vu . Por ejemplo, si Σ = {0, 1} la cadena 0011001 es una rotación de 0100110, donde u = 00110 y v = 01. Como otro ejemplo, la cadena abc tiene tres rotaciones diferentes, a saber. abc mismo (con u =abc, v =ε), bca (con u =bc, v =a) y cab (con u =c, v =ab).
A menudo resulta útil definir un orden en un conjunto de cadenas. Si el alfabeto Σ tiene un orden total (cf. orden alfabético ), se puede definir un orden total en Σ * llamado orden lexicográfico . El orden lexicográfico es total si el orden alfabético lo es, pero no está bien fundamentado para ningún alfabeto no trivial, incluso si el orden alfabético lo es. Por ejemplo, si Σ = {0, 1} y 0 < 1, entonces el orden lexicográfico en Σ * incluye las relaciones ε < 0 < 00 < 000 < ... < 0001 < ... < 001 < ... < 01 < 010 < ... < 011 < 0110 < ... < 01111 < ... < 1 < 10 < 100 < ... < 101 < ... < 111 < ... < 1111 < ... < 11111 ... Con respecto a este orden, por ejemplo, el conjunto infinito { 1, 01, 001, 0001, 00001, 000001, ... } no tiene ningún elemento mínimo.
Consulte Shortlex para conocer un orden de cadenas alternativo que preserva la solidez. Para el alfabeto de ejemplo, el orden shortlex es ε < 0 < 1 < 00 < 01 < 10 < 11 < 000 < 001 < 010 < 011 < 100 < 101 < 0110 < 111 < 0000 < 0001 < 0010 < 0011 <... < 1111 < 00000 < 00001 ...
En la teoría formal ocurren comúnmente varias operaciones adicionales sobre cuerdas. Estos se dan en el artículo sobre operaciones con cadenas .
Las cadenas admiten la siguiente interpretación como nodos en un gráfico, donde k es el número de símbolos en Σ:
La topología natural en el conjunto de cadenas de longitud fija o cadenas de longitud variable es la topología discreta, pero la topología natural en el conjunto de cadenas infinitas es la topología límite , considerando el conjunto de cadenas infinitas como el límite inverso de los conjuntos de cuerdas finitas. Esta es la construcción utilizada para los números p -ádicos y algunas construcciones del conjunto de Cantor , y produce la misma topología.
Los isomorfismos entre representaciones de cadenas de topologías se pueden encontrar normalizando según la rotación de cadenas lexicográficamente mínima .
Las cadenas literales (o constantes) se denominan "cadenas anónimas".
{{cite web}}: Mantenimiento CS1: URL no apta ( enlace )Inventó los términos "stringología", que es un subcampo de los algoritmos de cadenas,
El término stringología es un apodo popular para los algoritmos de cadenas y de texto.
{{cite book}}: Mantenimiento CS1: falta el editor de la ubicación ( enlace )La fortaleza más famosa de Perl es la manipulación de cadenas con expresiones regulares.