Cadenas de caracteres (informática)

Aunque las cadenas formales pueden tener una longitud finita arbitraria, en los lenguajes de programación reales la longitud de las cadenas suele estar limitada a un máximo artificial. En general, existen dos tipos de datos de cadena: cadenas de longitud fija , que tienen una longitud máxima fija que se determina en tiempo de compilación y que utilizan la misma cantidad de memoria independientemente de si se necesita este máximo o no; y cadenas de longitud variable , cuya longitud no está fijada arbitrariamente y que pueden utilizar cantidades variables de memoria según los requisitos reales en tiempo de ejecución (véase Gestión de memoria ). La mayoría de las cadenas en los lenguajes de programación modernos son de longitud variable. Por supuesto, incluso las cadenas de longitud variable están limitadas en longitud por la cantidad de memoria disponible. La longitud de la cadena se puede almacenar como un entero independiente (lo que puede imponer otro límite artificial a la longitud) o implícitamente mediante un carácter de terminación, normalmente un valor de carácter con todos los bits a cero, como en el lenguaje de programación C. Véase también " Terminado en nulo " más adelante.

Históricamente, los tipos de datos de cadena asignaban 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 esta diferencia, ya que los caracteres que un programa trataba de forma especial (como el punto, el espacio y la coma) se encontraban en la misma posición en todas las codificaciones que el programa pudiera encontrar. Estos conjuntos de caracteres se basaban típicamente en ASCII o EBCDIC . Si un texto con una codificación se mostraba en un sistema que utilizaba una codificación diferente, el texto a menudo aparecía distorsionado , aunque con frecuencia era algo legible, y algunos usuarios de computadoras aprendieron a leer el texto distorsionado.

Los idiomas logográficos como el chino , el japonés y el coreano (conocidos colectivamente como CJK ) requieren muchos 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 habituales consistían en mantener representaciones de un byte para ASCII y utilizar representaciones de dos bytes para los ideogramas CJK . El uso de estas con el código existente generaba problemas de coincidencia y corte de cadenas, cuya gravedad dependía del diseño de la codificación de caracteres. Algunas codificaciones, como la familia EUC, garantizan que un valor de byte en el rango ASCII representará únicamente ese carácter ASCII, lo que las hace seguras 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 "autosincronizables", por lo que localizar los límites de los caracteres requería retroceder al inicio de una cadena, y la unión de dos cadenas podía provocar la corrupción de la segunda.

Unicode ha simplificado un poco el panorama. La mayoría de los lenguajes de programación ahora tienen un tipo de dato para cadenas Unicode. El formato de flujo de bytes preferido de Unicode , UTF-8, está diseñado para evitar 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 radica en las API mal diseñadas que intentan ocultar esta diferencia (UTF-32 sí hace que los puntos de código sean de tamaño fijo, pero estos no son "caracteres" debido a la composición de códigos).

Algunos lenguajes, como C++ , Perl y Ruby , normalmente permiten que el contenido de una cadena se cambie después de haber sido creada; estas 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 .NETStringBuilder , Java seguro para subprocesos StringBuffery Cocoa . La inmutabilidad trae ventajas y desventajas: si bien las cadenas inmutables pueden requerir la creación ineficiente de NSMutableStringmuchas copias, son más simples y completamente seguras para subprocesos .

Las cadenas de caracteres suelen implementarse como matrices de bytes, caracteres o unidades de código, para permitir un acceso rápido a unidades individuales o subcadenas, incluidos los caracteres cuando tienen una longitud fija. Algunos lenguajes, como Haskell, las implementan como listas enlazadas .

Muchos lenguajes de alto nivel proporcionan cadenas como un tipo de dato primitivo, como JavaScript y PHP , mientras que la mayoría de los demás las proporcionan como un tipo de dato compuesto, algunos con soporte especial del lenguaje para escribir literales, por ejemplo, Java y C# .

Algunos lenguajes, como C , Prolog y Erlang , evitan implementar un tipo de dato específico para cadenas de caracteres, optando en su lugar por representarlas como listas de códigos de caracteres. Incluso en lenguajes de programación que sí cuentan con un tipo de cadena específico, estas suelen poder recorrerse como una secuencia de códigos de caracteres, al igual que las listas de enteros u otros valores.

La representación de cadenas depende en gran medida del repertorio de caracteres elegido 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 diversas codificaciones complejas como UTF-8 y UTF-16.

El término cadena de bytes suele referirse a una cadena de bytes de uso general, en lugar de cadenas de caracteres (legibles), cadenas de bits, etc. Las cadenas de bytes suelen implicar que los bytes pueden tomar cualquier valor y que cualquier dato puede almacenarse tal cual, lo que significa que no debería haber ningún valor que se interprete como un valor de terminación.

La mayoría de las implementaciones de cadenas son muy similares a los arreglos de longitud variable, donde las entradas almacenan los códigos de los caracteres correspondientes. La principal diferencia radica en que, con ciertas codificaciones, un solo carácter lógico puede ocupar más de una entrada en el arreglo. Esto ocurre, por ejemplo, con UTF-8, donde los códigos individuales ( puntos de código UCS ) pueden ocupar entre uno y 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 del arreglo (número de bytes utilizados). UTF-32 evita la primera parte del problema.

public final class String { private unsigned long length ; // longitud de la cadena private UniquePointer < char [] > text ; // propiedad explícita // métodos públicos... }

Las distintas distribuciones de memoria y los requisitos de almacenamiento de las cadenas pueden afectar la seguridad del programa que accede a los datos de la cadena. Las representaciones de cadena que requieren un carácter de terminación suelen ser vulnerables a problemas de desbordamiento de búfer si dicho carácter no está presente, ya sea por un error de codificación o por la alteración deliberada de los datos por parte de un atacante . Las representaciones de cadena que utilizan un campo de longitud independiente también son vulnerables si la longitud puede manipularse. En estos casos, el código del programa que accede a los datos de la cadena requiere una comprobación de límites para garantizar que no acceda ni modifique datos fuera de los límites de memoria de la cadena.

Los datos de tipo cadena se obtienen frecuentemente de la entrada del usuario a un programa. Por lo tanto, es responsabilidad del programa validar la cadena para asegurar que tenga el formato esperado. 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 .

La concatenación es una operación binaria importante en${\displaystyle \Sigma ^{*}}$. Para cualesquiera dos cadenas${\displaystyle s}$y${\displaystyle t}$en${\displaystyle \Sigma ^{*}}$, su concatenación se define como la secuencia de símbolos en${\displaystyle s}$seguido de la secuencia de caracteres en${\displaystyle t}$y se denota${\displaystyle st}$. Por ejemplo, si${\displaystyle \Sigma =\{{\texttt {a}},{\texttt {b}},...,{\texttt {z}}\}}$(es decir, el alfabeto inglés en minúsculas ),${\displaystyle s={\texttt {bear}}}$, y${\displaystyle t={\texttt {hug}}}$, entonces${\displaystyle st={\texttt {bearhug}}}$y${\displaystyle ts={\texttt {hugbear}}}$.

La concatenación de cadenas es una operación asociativa , pero no conmutativa . La cadena vacía${\displaystyle \varepsilon }$sirve como elemento identidad ; para cualquier cadena${\displaystyle s}$,${\displaystyle \varepsilon s=s\varepsilon =s}$. Por lo tanto, el conjunto${\displaystyle \Sigma ^{*}}$y la operación de concatenación forman un monoide , el monoide libre generado por${\displaystyle \Sigma }$Además, la función de longitud define un homomorfismo monoide de${\displaystyle \Sigma ^{*}}$a los enteros no negativos (es decir, una función${\displaystyle L:\Sigma ^{*}\mapsto \mathbb {N} \cup \{0\}}$, de tal manera que${\displaystyle L(st)=L(s)+L(t)\quad \forall s,t\in \Sigma ^{*}}$).

Una cuerda${\displaystyle s}$Se dice que es una subcadena o factor de${\displaystyle t}$si existen cadenas (posiblemente vacías)${\displaystyle u}$y${\displaystyle v}$de tal manera que${\displaystyle t=usv}$. La relación "es una subcadena de" define un orden parcial en${\displaystyle \Sigma ^{*}}$, cuyo elemento más pequeño es la cadena vacía.

Una cuerda${\displaystyle s}$Se dice que es un prefijo de${\displaystyle t}$si existe una cadena${\displaystyle u}$de tal manera que${\displaystyle t=su}$. Si${\displaystyle u}$no está vacío,${\displaystyle s}$Se dice que es un prefijo propio de${\displaystyle t}$. Simétricamente, una cuerda${\displaystyle s}$Se dice que es un sufijo de${\displaystyle t}$si existe una cadena${\displaystyle u}$de tal manera que${\displaystyle t=us}$. Si${\displaystyle u}$no está vacío,${\displaystyle s}$Se dice que es un sufijo propio de${\displaystyle t}$. Los sufijos y prefijos son subcadenas de${\displaystyle t}$. Tanto la relación "es un prefijo de" como "es un sufijo de" son órdenes de prefijo .

La inversa de una cadena es una cadena con los mismos símbolos pero en orden inverso. Por ejemplo, si${\displaystyle s={\texttt {abc}}}$(dónde${\displaystyle {\texttt {a}}}$,${\displaystyle {\texttt {b}}}$, y${\displaystyle {\texttt {c}}}$son símbolos del alfabeto), entonces lo contrario de${\displaystyle s}$es${\displaystyle {\texttt {cba}}}$. Una cadena que es la inversa de sí misma (por ejemplo,${\displaystyle s={\texttt {madam}}}$) se llama palíndromo , que también incluye la cadena vacía y todas las cadenas de longitud${\displaystyle 1}$.

Una cuerda${\displaystyle s=uv}$Se dice que es una rotación de${\displaystyle t}$si${\displaystyle t=vu}$. Por ejemplo, si${\displaystyle \Sigma =\{{\texttt {0}},{\texttt {1}}\}}$la cuerda${\displaystyle {\texttt {0011001}}}$es una rotación de${\displaystyle {\texttt {0100110}}}$, dónde${\displaystyle u={\texttt {00110}}}$y${\displaystyle v={\texttt {01}}}$. Como otro ejemplo, la cadena${\displaystyle {\texttt {abc}}}$tiene tres rotaciones diferentes, a saber:${\displaystyle {\texttt {abc}}}$sí mismo (con${\displaystyle u={\texttt {abc}}}$,${\displaystyle v=\varepsilon }$),${\displaystyle {\texttt {bca}}}$(con${\displaystyle u={\texttt {bc}},v={\texttt {a}}}$), y${\displaystyle {\texttt {cab}}}$(con${\displaystyle u={\texttt {c}},v={\texttt {ab}}}$).

A menudo resulta útil definir un orden en un conjunto de cadenas. Si el alfabeto${\displaystyle \Sigma }$tiene un orden total (cf. orden alfabético ) se puede definir un orden total en${\displaystyle \Sigma ^{*}}$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${\displaystyle \Sigma =\{{\texttt {0}},{\texttt {1}}\}}$y${\displaystyle {\texttt {0}}<{\texttt {1}}}$, luego el orden lexicográfico en${\displaystyle \Sigma ^{*}}$incluye las relaciones${\displaystyle \varepsilon <{\texttt {0}}<{\texttt {00}}<{\texttt {000}}<...<{\texttt {0001}}<...<{\texttt {001}}<...<{\texttt {01}}<{\texttt {010}}<...<{\texttt {011}}<{\texttt {0110}}<...<{\texttt {01111}}<...<{\texttt {1}}<{\texttt {10}}<{\texttt {100}}<...<{\texttt {101}}<...<{\texttt {111}}<...<{\texttt {1111}}<...<{\texttt {11111}}...}$Con respecto a este ordenamiento, por ejemplo, el conjunto infinito${\displaystyle \{{\texttt {1}},{\texttt {01}},{\texttt {001}},{\texttt {0001}},{\texttt {00001}},{\texttt {000001}},...\}}$no tiene ningún elemento mínimo.

Consulte Shortlex para ver un ordenamiento de cadenas alternativo que preserva la buena fundamentación. Para el alfabeto de ejemplo, el orden de Shortlex es${\displaystyle \varepsilon <{\texttt {0}}<{\texttt {1}}<{\texttt {00}}<{\texttt {01}}<{\texttt {10}}<{\texttt {11}}<{\texttt {000}}<{\texttt {001}}<{\texttt {010}}<{\texttt {011}}<{\texttt {100}}<{\texttt {101}}<{\texttt {0110}}<{\texttt {111}}<{\texttt {0000}}<{\texttt {0001}}<{\texttt {0010}}<{\texttt {0011}}<...<{\texttt {1111}}<{\texttt {00000}}<{\texttt {00001}}...}$

En la teoría formal, suelen aparecer varias operaciones adicionales sobre cadenas. Estas se describen en el artículo sobre operaciones con cadenas .

Las cadenas admiten la siguiente interpretación como nodos en un grafo, donde${\displaystyle k}$es el número de símbolos en${\displaystyle \Sigma }$:

• Cadenas de longitud fija de longitud${\displaystyle n}$se puede ver como las ubicaciones enteras en un${\displaystyle n}$Hipercubo dimensional con lados de longitud${\displaystyle k-1}$.
• Las cadenas de longitud variable (de longitud finita) pueden verse como nodos en una cadena perfecta.${\displaystyle k}$-ario árbol .
• Las cadenas infinitas (que no se consideran aquí) pueden verse como caminos infinitos en una${\displaystyle k}$-grafo completo del nodo .

La topología natural en el conjunto de cadenas de longitud fija o variable es la topología discreta, pero la topología natural en el conjunto de cadenas infinitas es la topología límite , que considera el conjunto de cadenas infinitas como el límite inverso de los conjuntos de cadenas 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.

Se pueden encontrar isomorfismos entre representaciones de cadenas de topologías normalizando según la rotación de cadena lexicográficamente mínima .