Corda (estrutura de dados)

Em programação de computadores, uma corda é uma estrutura de dados composta de pequenas sequências de caracteres que é usada de forma eficiente para armazenar e manipular uma cadeia muito longa. Por exemplo, um programa de edição de texto pode utilizar uma corda para representar o texto que está sendo editado, para que operações como inserção, exclusão, acesso aleatório possam ser realizadas de forma eficiente.

Uma simples corda construída sobre a sequência de caracteres: "Hello_my_name_is_Simon".

Descrição

Uma corda é uma árvore binária onde cada nó folha contém uma cadeia de caracteres curta. Cada nó tem um peso de valor igual ao comprimento de sua cadeia somado com a adição de todos os pesos dos nós folha na subárvore à esquerda. O peso de um nó é o comprimento total de sua sequência de caracteres na sua subárvore à esquerda de um nó não folha, ou o comprimento de cadeia de si mesmo para um nó folha. Assim sendo, um nó com dois filhos, divide-se a sequência inteira em duas partes: a subárvore esquerda armazena a primeira parte da sequência de caracteres. A subárvore à direita armazena a segunda parte da sequência de caracteres. O peso deste nó é dado pela a soma de do peso dos sub-nós à  esquerda e o tamanho da sequência de caracteres.

A árvore binária pode ser vista como vários níveis de nós: o nível inferior contém todos os nós que contêm uma sequência de caracteres; níveis mais elevados têm cada vez menos de nós; o nível superior é composto de uma única "raiz", assim como uma árvore binária. A corda é construída colocando os nós com cadeias curtas no nível inferior, em seguida, anexa-se uma metade de nós aleatória para nós pais no próximo nível.

Operações

Nas seguintes definições, N é o comprimento da corda.

Índice

Figura 2.1: Exemplo de índice de pesquisa em uma corda.

Definição: Índice(i): retorna o caracter na posição i

Tempo de complexidade: $O(\log N)$

Para obter o i-ésimo caractere, começamos uma busca recursiva a partir do nó raiz:

Por exemplo, para encontrar o caractere em i=10 na Figura 2.1, inicia-se no nó raiz (A), achar que 22 é maior que 10 e existe um nó filho à esquerda, então vá para este nó (B). 9 é menor do que 10, então, subtrai-se 9 de 10 (deixando-o i=1) e vá para a o filho à direita (D). Em seguida, porque 6 é maior que 1 e há um filho à esquerda, então vá para o nó filho à esquerda (G). 2 é maior que 1 e não há um nó filho à direita, então vá para a esquerda novamente (J). Finalmente, 2 é maior que 1, mas não há nó filho à esquerda, assim, o carácter de cada índice 1 da curta sequência de caracteres "na", é a resposta.

Concatenação

Figura 2.2: Concatenação de duas cordas em uma única corda.

Definição: Concatenar(S1, S2): concatenar duas cordas, S₁ e S₂, em uma única corda.

Tempo de complexidade: $O(1)$ (ou $O(\log N)$ tempo para calcular a raiz de peso)

Uma concatenação pode ser realizada simplesmente através da criação de um novo nó raiz com left = S1 e right = S2, que é a constante de tempo. O peso do nó pai é definida como o comprimento do filho à esquerda de S₁, o que levaria a $O(\log N)$ tempo, se a árvore é balanceada.

Como a maioria corda operações requerem árvores balanceadas, a árvore precisa ser re-equilibrada após a concatenação.

Divisão

Figura 2.3: a Divisão de uma corda na metade.

Definição: Divisão(i, S): dividir a corda S em duas novas sequências de S₁ e S₂, onde S₁ = C₁, …, C_i e S₂ = C_{i + 1}, …, C_m.

Tempo de complexidade: $O(\log N)$

Há dois casos que devem ser tratados:

1. Se o ponto de divisão estiver no final de uma sequência de caracteres (por exemplo, após o último caractere de um nó folha)
2. Se o ponto de divisão está no meio de uma sequência de caracteres.

O segundo caso reduz ao primeiro dividindo a corda no ponto de divisão para criar dois novos nós de folha e, em seguida, criar um novo nó que é o pai das duas cadeias componentes.

Por exemplo, para dividir a cadeia da corda ilustrada na Figura 2.3 em duas cordas iguais de comprimento 11, é necessário consultar o caracter 12 para localizar o nó K no nível inferior. Remove-se a ligação entre K e G e o algoritmo prossegue para o pai de G e subtrai o peso de K a partir do peso de D. Então, o algoritmo se move para cima na árvore e remover qualquer link direto para sub-árvores, cobrindo de caracteres passado posição 11, subtraindo-se o peso de K a partir de seus nós pais (somente o nó D e Um, neste caso). Finalmente, constrói-se os nós K e H ao concatená-los e a cria-se um novo pai P com peso igual ao comprimento da esquerda nó K.

Como a maioria corda operações requerem árvores balanceadas, a árvore precisa ser re-equilibradas após a divisão.

Inserção

Definição: Inserir(i, S'): inserir a cadeia de caracteres "S", começando na posição i da string s, para formar uma nova sequência de caracteres C₁, …, C_i, S', C_{i + 1}, …, C_m.

Tempo de complexidade: $O(\log N)$.

Esta operação pode ser feita por uma operação de Divisão() e duas operações de Concatenar(). O custo é a soma dos três.

Remover

Definição: Remover(i, j): eliminar a subsequência de caracteres C_i, …, C_{i + j − 1}, a partir de s para formar uma nova sequência de caracteres C₁, …, C_{i − 1}, C_{i + j}, …, C_m.

Tempo de complexidade: $O(\log N)$.

Esta operação pode ser feita por duas operações de Divisão() e uma operação de Concatenar() operação. Primeiro, divide-se a corda em três, pelo i-ésimo e i+j-ésimo caractere respectivamente, onde se extrai a sequência de caracteres para excluir um nó separado. Então, concatene os outros dois nós.

Relatório

Definição: Relatório(i, j): saída a sequência de caracteres C_i, …, C_{i + j − 1}.

Tempo de complexidade: $O(j+\log N)$

Para reportar a sequência de caracteres C_i, …, C_{i + j − 1}, localize o nó u que contém C_i e peso(u) >= je, em seguida, atravesse T iniciando no nó u. Saída C_i, …, C_{i + j − 1}.

Comparação com vetores monolítico

Desempenho^{[carece de fontes]}

Operação	Corda	Cadeia
Índice	O(log n)	O(1)
Divisão	O(log n)	O(1)
Concatenar (destrutiva)	O(log n) sem rebalancear / O(n) pior caso	O(n)
Concatenar (não destrutiva)	O(n)	O(n)
Iterar sobre cada caractere	O(n)	O(n)
Inserir	O(log n) sem rebalancear / O(n) pior caso	O(n)
Anexar	O(log n) sem rebalancear / O(n) pior caso	O(1)
Remover	O(log n)	O(n)
Relatório	O(j + log n)	O(1)
Construção	O(n)	O(n)

Vantagens:

• Cordas permitem fazer operações de inserção e exclusão de texto mais rápido que vetores monolíticos de sequência de caracteres, nos operações tem complexidade de tempo O(n).
• Cordas não requerem O(n) memória extra para realizar operações (vetores precisam de memória extra para as operações de cópia).
• Cordas não exigem grande de espaço contíguo de memória.
• Se apenas versões não-destrutivas de operações são usadas, a corda é um estrutura de dados  persistente. Para o programa de edição de texto, por exemplo, resulta em fácil suporte para desfazer múltiplos níveis.

Desvantagens:

• Cordas usam mais espaço quando não estão sendo operadas, principalmente para armazenar os nós do pai. Existe uma troca entre o quanto de memória total sobrecarrega e como redações de longas cadeias de dados estão sendo processados como sequências de caracteres. As sequências de caracteres em números de exemplo acima são inacreditavelmente curtas em arquiteturas modernas. A sobrecarga é sempre de O(n), mas essa constante pode ser feito arbitrariamente pequena.
• Aumento no tempo para gerenciar o armazenamento extra.
• O aumento de complexidade do código-fonte; maior risco de bugs

A tabela compara os algoritmos para vetores monolíticos e implementações para cordas, e não a sua velocidade bruta. Sequência de caracteres, baseadas em vetores, tem menor sobrecarga, de modo que, operações de concatenação e divisão são mais rápidas em pequenos conjuntos de dados. No entanto, quando esta implementação é usada para cadeias mais longas, o tempo, a complexidade e o uso de memória para inserir e eliminar caracteres tornar-se inaceitavelmente grande. Em contraste, uma estrutura de dados de corda tem o desempenho estável, independentemente do tamanho dos dados. Além disso, o espaço complexidade para cordas e vetores são O(n). Em resumo, as cordas são preferíveis quando o volume dados é grande e modificado frequentemente.

Ver também

• O ambiente de programação Cedar usou cordas "quase desde a sua criação"
• Gap de buffer, uma estrutura de dados comumente utilizadas em editores de texto que permite a eficiente inserção e exclusão de operações de cluster perto do mesmo local