Corda (estrutura de dados)

Origem: Wikipédia, a enciclopédia livre.
Uma simples corda construída sobre a sequência de caracteres: "Hello_my_name_is_Simon".

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.[1]

Descrição[editar | editar código-fonte]

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[editar | editar código-fonte]

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

Índice[editar | editar código-fonte]

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:

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[editar | editar código-fonte]

Figura 2.2: Concatenação de duas cordas em uma única corda.
Definição: Concatenar(S1, S2): concatenar duas cordas, S1 e S2, em uma única corda.
Tempo de complexidade: (ou 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 S1, o que levaria a 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[editar | editar código-fonte]

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 S1 e S2, onde S1 = C1, …, Ci e S2 = Ci + 1, …, Cm.
Tempo de complexidade:

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[editar | editar código-fonte]

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 C1, …, Ci, S', Ci + 1, …, Cm.
Tempo de complexidade: .

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[editar | editar código-fonte]

Definição: Remover(i, j): eliminar a subsequência de caracteres Ci, …, Ci + j − 1, a partir de s para formar uma nova sequência de caracteres C1, …, Ci − 1, Ci + j, …, Cm.
Tempo de complexidade: .

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[editar | editar código-fonte]

Definição: Relatório(i, j): saída a sequência de caracteres Ci, …, Ci + j − 1.
Tempo de complexidade:

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

Comparação com vetores monolítico[editar | editar código-fonte]

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 um trade-off 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.

Veja também[editar | editar código-fonte]

  • 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

Referências[editar | editar código-fonte]

  1. «Ropes: an Alternative to Strings». Software—Practice & Experience. 25. doi:10.1002/spe.4380251203