Cadeia de caracteres

Na programação de computadores, uma cadeia de caracteres ou string é uma sequência de caracteres, geralmente utilizada para representar palavras, frases ou textos de um programa.

Nas maioria das linguagens de programação, as cadeias de caracteres podem ser expressas tanto na forma literal, como através de algum tipo de variável. Quando expressos através de variáveis, o conteúdo da cadeia geralmente pode ser alterado pela inclusão/exclusão de elementos ou pela substituição de seus elementos por outros elementos, formando uma nova cadeia. Assim, uma cadeia de caracteres é vista como sendo um tipo de dado e normalmente é implementada através de um arranjo de bytes que armazena os elementos da cadeia em sequência, utilizando alguma codificação preestabelecida.

Nas linguagens formais, uma cadeia de caracteres é uma sequência finita de símbolos escolhidos a partir de conjunto denominado alfabeto.

Propósito

O propósito principal das cadeias de caracteres (strings) é armazenar texto legível por humanos, como palavras e frases. As strings são usadas para comunicar informações de um programa de computador para o usuário do programa. Um programa também pode aceitar a entrada de strings de seu usuário. Além disso, as strings podem armazenar dados expressos como caracteres, mas que não se destinam à leitura humana.

Exemplos de strings e seus propósitos:

• Uma mensagem como "upload de arquivo concluído" é uma string que o software exibe aos usuários finais. No código-fonte do programa, esta mensagem provavelmente apareceria como uma string literal.
• Texto inserido pelo usuário, como "consegui um novo emprego hoje" como uma atualização de status em uma rede social. Em vez de uma literal, o software provavelmente armazenaria essa string em um banco de dados.
• Dados alfabéticos, como "AGATGCCGT", representando sequências de ácidos nucleicos de ADN.
• Configurações ou parâmetros de computador, como "{{{1}}}" como uma string de consulta (query string) de URL. Frequentemente, estas são destinadas a serem um pouco legíveis por humanos, embora seu propósito principal seja a comunicação entre computadores.

O termo "string" também pode designar uma sequência de dados ou registros de computador que não sejam caracteres — como uma "cadeia de bits" — mas, quando usado sem qualificação, refere-se a cadeias de caracteres.

História

O uso da palavra "string" (em português, corda, sequência ou cadeia) para significar quaisquer itens organizados em linha, série ou sucessão remonta a séculos. Na tipografia do século XIX, os compositores utilizavam o termo para designar um comprimento de tipos impressos em papel; a "string" era medida para determinar o pagamento do compositor.

O uso da palavra "string" para significar "uma sequência de símbolos ou elementos linguísticos em uma ordem definida" surgiu da matemática, da lógica simbólica e da teoria linguística para descrever o comportamento formal de sistemas simbólicos, abstraindo o significado dos símbolos.

Por exemplo, o lógico C. I. Lewis escreveu em 1918:

Um sistema matemático é qualquer conjunto de sequências (strings) de marcas reconhecíveis nas quais algumas das sequências são tomadas inicialmente e as demais derivadas destas por operações realizadas de acordo com regras que são independentes de qualquer significado atribuído às marcas. Que um sistema consista de 'marcas' em vez de sons ou odores é imaterial.

De acordo com Jean E. Sammet, "a primeira linguagem realista de manipulação de strings e correspondência de padrões" para computadores foi a COMIT na década de 1950, seguida pela linguagem SNOBOL no início da década de 1960.

Tipos de dados de string

Um tipo de dado de string é um tipo de dado modelado na ideia de uma string formal. Strings são tipos de dados tão importantes e úteis que são implementados em quase todas as linguagens de programação. Em algumas linguagens, estão disponíveis como tipos primitivos e, em outras, como tipos compostos. A sintaxe da maioria das linguagens de alto nível permite que uma string, geralmente entre aspas, represente uma instância desse tipo; tal meta-string é chamada de literal ou string literal.

Comprimento da string

Embora as strings formais possam ter um comprimento finito arbitrário, o comprimento em linguagens reais é frequentemente restringido a um máximo artificial. Em geral, existem dois tipos: **strings de comprimento fixo**, que possuem um tamanho máximo determinado em tempo de compilação e usam a mesma quantidade de memória independentemente da necessidade; e **strings de comprimento variável**, cujo tamanho não é fixo e podem usar quantidades variadas de memória dependendo dos requisitos em tempo de execução (veja Gerenciamento de memória). A maioria das linguagens modernas utiliza strings de comprimento variável. O comprimento pode ser armazenado como um inteiro separado ou implicitamente através de um caractere de terminação (geralmente um caractere nulo, como em C).

Codificação de caracteres

Historicamente, os tipos de string alocavam um byte por caractere (baseados em ASCII ou EBCDIC). Idiomas logográficos como o chinês, japonês e coreano (CJK) exigem muito mais do que os 256 caracteres permitidos por um byte de 8 bits. As soluções iniciais envolviam representações de dois bytes, mas isso gerava problemas de compatibilidade e corrupção de dados em sistemas que não foram projetados para tal (como o ISO-2022 e Shift-JIS).

O Unicode simplificou esse cenário. A maioria das linguagens agora possui suporte nativo para strings Unicode. O formato de fluxo de bytes preferencial do Unicode, o UTF-8, foi projetado para evitar problemas de sincronização das codificações multibyte antigas. UTF-8, UTF-16 e UTF-32 exigem que o programador saiba que as unidades de código de tamanho fixo são diferentes dos "caracteres" visíveis.

Implementações

Algumas linguagens, como C++, Perl e Ruby, permitem que o conteúdo de uma string seja alterado após a criação; estas são chamadas de strings mutáveis. Em outras, como Java, JavaScript, Python e Go, o valor é fixo e uma nova string deve ser criada para qualquer alteração; estas são chamadas de strings imutáveis. A imutabilidade simplifica a segurança entre threads (thread safety).

As strings são tipicamente implementadas como arrays de bytes ou caracteres. Algumas linguagens de alto nível as tratam como tipos primitivos (JavaScript, PHP), enquanto outras as tratam como tipos compostos com suporte especial para literais (Java, C#). Linguagens como C e Erlang evitam um tipo de dado dedicado, representando strings como listas de códigos de caracteres.

Representações

Dope vectors

O comprimento de uma string pode ser armazenado em um vetor de controle (dope vector), separado do local onde estão os caracteres. O compilador PL/I (F) da IBM utilizava um string dope vector (SDV) que continha o comprimento atual, o comprimento máximo e um ponteiro para o início da string.

Terminação em nulo (Null-terminated)

O comprimento pode ser armazenado implicitamente usando um caractere terminador especial, geralmente o caractere nulo (NUL), convenção perpetuada pela linguagem C. Por isso, essa representação é comumente chamada de C string. Uma string de n caracteres ocupa n + 1 espaços de memória.

Exemplo de uma string terminada em nulo "FRANK" em um buffer de 10 bytes:

F	R	A	N	K	NUL	k	e	f	w
4616	5216	4116	4E16	4B16	0016	6B16	6516	6616	7716

Prefixo de comprimento

O comprimento também pode ser armazenado explicitamente como um prefixo (comum em dialetos Pascal, daí o nome Pascal string ou P-string). Se o prefixo for de 1 byte, a string é limitada a 255 caracteres. Implementações modernas usam palavras de 32 ou 64 bits para o prefixo, permitindo que as strings sejam limitadas apenas pela memória disponível.

Strings como registros

Muitas linguagens orientadas a objetos implementam strings como registros com uma estrutura interna:

public final class String {
    private unsigned long length; // comprimento da string
    private UniquePointer<char[]> text; // ponteiro para os caracteres

    // métodos públicos...
}

Outras representações

Para maior eficiência em editores de texto, podem ser usadas estruturas como ropes ou gap buffers, que facilitam inserções e deleções em grandes volumes de texto.

Problemas de segurança

Diferentes layouts de memória afetam a segurança. Strings terminadas em nulo são suscetíveis a problemas de estouro de buffer (buffer overflow) se o caractere terminador estiver ausente ou for manipulado por um invasor. Representações com campo de comprimento também são vulneráveis se o valor do comprimento puder ser manipulado. É responsabilidade do programa realizar a validação dos dados para evitar ataques de injeção de código.

Teoria formal

Seja Σ um conjunto finito e não vazio de símbolos (ou caracteres) chamado de o alfabeto. Uma cadeia sobre Σ é qualquer sequência finita de caracteres contidos em Σ.

• Se o alfabeto Σ = {0, 1}, então 0, 1, 01, 000001 e 101 são cadeias sobre o alfabeto Σ.

O comprimento ou cardinalidade da cadeia é a quantidade de caracteres utilizados para sua composição. À cadeia de comprimento zero dá-se o nome de cadeia vazia e é usualmente denotada na literatura pelos símbolos ε ou λ.

• Se o alfabeto Σ = {0, 1}, então |00| = 2, |0101| = 4 e |ε| = 0.'

O conjunto de todas as possíveis cadeias de tamanho n sobre um alfabeto Σ qualquer de tamanho é denotado por Σⁿ.

• Se o alfabeto Σ = {0, 1}, então Σ² = {00, 01, 10, 11}. Notar que Σ⁰ = {ε} para qualquer alfabeto Σ.

O conjunto de todas as possíveis cadeias sobre Σ de qualquer tamanho é denotado por Σ*. Em termos de Σⁿ, Σ* = Σ⁰ ∪ Σ¹ ∪ Σ²….

• Se o alfabeto Σ = {0, 1} então Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, …}.

Apesar do conjunto Σ* possuir infinitos elementos, todos os elementos de Σ* possuem comprimento finito.

Um conjunto de cadeias sobre um alfabeto Σ (isto é, qualquer subconjunto de Σ*) é chamado de linguagem formal sobre Σ.

Concatenação e sub-cadeias

Concatenação é uma importante operação binária em Σ*. Para qualquer duas cadeias s e t em Σ*, sua concatenação é definida pela sequência de caracteres de s seguida pela sequência de caracteres em t, denotada por st. Por exemplo se Σ = {a, b, …, z}, s = bear e t = hug, então st = bearhug e ts = hugbear.

A concatenação de cadeias é uma operação associativa, mas não comutativa. A cadeia vazia serve como um elemento identidade: para qualquer cadeia s, εs = sε = s. Portanto, o conjunto Σ* e a operação de concatenação formam um monóide.

A cadeia s é dita uma subcadeia (ou fator) de t se existem cadeias (possivelmente vazias) u e v de forma que t = usv.

Ordenação lexicográfica

Geralmente é necessário definir uma ordenação em um conjunto de cadeias. Se um alfabeto Σ possui uma relação de ordem (como a ordem alfabética) pode-se definir uma relação de ordem em Σ* chamada ordem lexicográfica. Note que como Σ é finito, é sempre possível definir uma ordenação em Σ e portanto em Σ*. Por exemplo, se Σ = {0, 1} e 0 < 1, então a ordenação lexicográfica em Σ* é ε < 0 < 00 < 000 < … < 011 < 0110 < … < 01111 < … < 1 < 10 < 100 < … < 101 < … < 111 …

Strings literais

Às vezes, as cadeias de caracteres precisam ser incorporadas em um arquivo de texto que seja legível por humanos e destinado ao processamento por uma máquina. Isso é necessário, por exemplo, no código-fonte de linguagens de programação ou em arquivos de configuração. Nesse caso, o caractere NUL não funciona bem como terminador, pois normalmente é invisível (não imprimível) e difícil de inserir via teclado. Armazenar o comprimento da string também seria inconveniente, pois o cálculo manual e o rastreamento do comprimento são tarefas tediosas e propensas a erros.

Duas representações comuns são:

• **Cercadas por aspas** (aspas duplas ASCII 0x22 "str" ou aspas simples ASCII 0x27 'str'), utilizadas pela maioria das linguagens de programação. Para permitir a inclusão de caracteres especiais, como a própria aspa, caracteres de nova linha ou caracteres não imprimíveis, frequentemente estão disponíveis sequências de escape, geralmente prefixadas pelo caractere de barra invertida (ASCII 0x5C).
• **Terminadas por uma sequência de nova linha**, como ocorre, por exemplo, em arquivos INI do Windows.

Strings não textuais

Embora as cadeias de caracteres sejam usos muito comuns de strings, em ciência da computação, uma "string" pode se referir genericamente a qualquer sequência de dados de tipos homogêneos. Uma cadeia de bits (bit string) ou cadeia de bytes (byte string), por exemplo, pode ser usada para representar dados binários não textuais recuperados de um meio de comunicação. Esses dados podem ou não ser representados por um tipo de dado específico para strings, dependendo das necessidades da aplicação, da vontade do programador e das capacidades da linguagem de programação utilizada. Se a implementação de string da linguagem não for 8-bit clean, pode ocorrer corrupção de dados.

Programadores C fazem uma distinção nítida entre uma "string" (também chamada de "cadeia de caracteres"), que por definição é sempre terminada em nulo, e um "array de caracteres", que pode estar armazenado no mesmo array, mas que frequentemente não possui o terminador nulo. O uso de funções de manipulação de strings em C em tais arrays de caracteres costuma parecer funcionar inicialmente, mas acaba levando a problemas de segurança.

Funções de cadeias de caracteres

As funções de string são utilizadas para criar cadeias de caracteres ou alterar o conteúdo de uma string mutável. Elas também são usadas para consultar informações sobre uma determinada string. O conjunto de funções e seus nomes variam dependendo da linguagem de programação de computadores.

O exemplo mais básico de uma função de string é a função de comprimento de string – a função que retorna o comprimento de uma cadeia (sem contar quaisquer caracteres terminadores ou informações estruturais internas da string) e não modifica a string original. Esta função é frequentemente nomeada como length, len ou size. Por exemplo, length("hello world") retornaria 11. Outra função comum é a concatenação, onde uma nova string é criada ao anexar duas cadeias, sendo frequentemente representada pelo operador de adição +.

A arquitetura do conjunto de instruções de alguns microprocessadores contém suporte direto para operações de string, como cópia de bloco (ex: no Intel x86, o comando REPNZ MOVSB).

Cadeia de caracteres como tipo de dado

Um tipo de dado cadeia de caracteres (referido em programação geralmente como string) é uma modelagem de uma cadeia formal de caracteres. São bastante usados em programação, sendo implementados em quase todas as linguagens de programação. Em algumas linguagens esse tipo é definido nativamente, em outras é um tipo composto, derivado.