LNCC
Parte 1: Estruturas de dados elementares
GA-024
Antônio Tadeu A. Gomes, D.Sc.
[email protected] http://wiki.martin.lncc.br/atagomes-cursos-lncc-ga024
Sala 2C-01
LNCC
Estruturas de dados elementares
! Matrizes
! Listas encadeadas
! Pilhas e filas
! Cadeias de caracteres
LNCC
Matrizes (I) ! Conjuntos multidimensionais homogêneos ! Alocação estática:
- É necessário saber de antemão as dimensões ! Ex. (bidimensional):
- Variável que
representa matriz é um ponteiro para o primeiro elemento da primeira linha
- Há: ! Formas alternativas de inicialização na declaração ! Passagem de matrizes como parâmetros de funções
(representação “row major”)
LNCC
Matrizes (II)
! Alocação dinâmica - C e C++ só permitem alocação dinâmica de conjuntos
unidimensionais
- É necessário criar abstrações conceituais com vetores para representar matrizes alocadas dinamicamente
! Uso de TAD pode ser conveniente para encapsular abstração
float* v; … v = (float*) malloc(n * sizeof(float));
LNCC
Matrizes (III) ! TAD “Matrix” bidimensional
(elementos ponto-flutuante) - Estrutura: ??? - Operações principais:
! Matrix* matrix_create( int m, int n ): cria matriz de zeros ! Matrix* matrix_create( void ): cria a partir de stdin ! matrix_print( Matrix* m ): imprime matriz em stdout ! matrix_destroy( Matrix* m ) ! float matrix_getelem( Matrix* m, int x, int y ) ! matrix_setelem( Matrix* m, int x, int y, float elem ) ! matrix_{getcolumncount,getlinecount}( Matrix* m )
- Outras operações: ! Matrix* matrix_transpose( Matrix* m ) ! Matrix* matrix_{add,subtract,multiply}( Matrix* m, Matrix* m )
LNCC
Matrizes (IV)
! Matriz dinâmica bidimensional representada por um vetor simples:
- mat[ i ][ j ] mapeado em v[ k ] onde k = i * n + j - Implementação de matrix_getelem()?
Operação matrix_create( int m, int n ): float *mat; /* matriz m x n como um vetor */ ... mat = (float*) malloc(m*n*sizeof(float)); ...
LNCC
Matrizes (V)
! Matriz dinâmica bidimensional representada por um vetor de ponteiros:
- Cada elemento do vetor armazena o endereço do primeiro elemento de cada linha da matriz
- Implementação de matrix_getelem()?
Operação matrix_create( int m, int n ): int i; float **mat; /* matriz como um vetor de ponteiros */ ... mat = (float**) malloc(m*sizeof(float*)); for (i=0; i<m; i++) mat[i] = (float*) malloc(n*sizeof(float)); ...
LNCC
Matrizes (VI)
! Matrizes simétricas - mat é uma matriz simétrica se mat[ i ][ j ] = mat[ j ][ i ] - estratégia de armazenamento:
! basta armazenar os elementos da diagonal e metade dos elementos restantes, por exemplo, os elementos abaixo da diagonal, ou seja, mat[ i ][ j ], onde i > j
- em lugar de n2 valores, armazena-se n(n+1)/2 valores - Implementação de matrix_getelem()?
! Com vetores simples ! Com vetores de ponteiros
LNCC
Matrizes (VII)
! Matrizes esparsas
- Muitas posições preenchidas por zeros
- Ex. de aplicação: solução numérica de eq. diferenciais parciais (EDPs) (métodos diretos ou iterativos)
- Alocação ineficiente de memória tanto com vetores simples como com vetores de ponteiros
�
⇧⇧⇧⇧⇧⇧⇤
10 0 0 0 �2 03 9 0 0 0 30 7 8 7 0 03 0 8 7 5 00 8 0 9 9 130 4 0 0 2 �1
⇥
⌃⌃⌃⌃⌃⌃⌅
LNCC
Matrizes (VIII) ! Compressed Row Storage (CRS)
- Não assume características específicas da matriz
row ptr 1 3 6 9 13 17 20
val 10 -2 3 9 3 7 8 7 3 ... 9 13 4 2 -1col ind 1 5 1 2 6 2 3 4 1 ... 5 6 2 5 6
�
⇧⇧⇧⇧⇧⇧⇤
10 0 0 0 �2 03 9 0 0 0 30 7 8 7 0 03 0 8 7 5 00 8 0 9 9 130 4 0 0 2 �1
⇥
⌃⌃⌃⌃⌃⌃⌅
LNCC
Matrizes (IX)
! Variantes da CRS: - “Column-major” (CCS)
- Block-compressed (BCRS, BCCS)
! Útil na discretização de EDPs com vários graus de liberdade (tamanho do bloco determinado pelo número de graus de liberdade)
! Neste caso, vetor val armazena ponteiros para um outro vetor que contém de fato os blocos
Tamanho do bloco = 2
LNCC
Matrizes (X)
! Outras formas de representação:
- Compressed Diagonal Storage (CDS)
! Matrizes de banda fixa
�
⇧⇧⇧⇧⇧⇧⇤
10 �3 0 0 0 03 9 6 0 0 00 7 8 7 0 00 0 8 7 5 00 0 0 9 9 130 0 0 0 2 �1
⇥
⌃⌃⌃⌃⌃⌃⌅
val(:,-1) 0 3 7 8 9 2val(:, 0) 10 9 8 7 9 -1val(:,+1) -3 6 7 5 13 0
LNCC
Matrizes (XI)
! Outras formas de representação (cont.):
- Jagged Diagonal Storage (JDS) ! Mais eficiente em espaço que CDS ! Útil na implementação de métodos iterativos em
computadores paralelos/vetoriais
- Skyline Storage (SKS) ! Matrizes de banda variável ! Útil na implementação de métodos diretos e na
fatoração de matrizes em blocos
! Referência: [Barret et al., 2006, Seção 4.3]
LNCC
Listas encadeadas (I)
! Vetores e matrizes (alocadas estaticamente ou dinamicamente com vetores simples/de ponteiros)
- Ocupam (grupos de) espaços contíguos de memória ! Permitem acesso (quase) direto aos elementos
- Devem ser dimensionados com um número máximo de
elementos ! Em C, possibilidade de redimensionamento com realloc()
LNCC
Listas encadeadas (II)
! Lista encadeada: - Sequência de elementos chamados de nós
- Um nó de uma lista contém:
! a informação armazenada (homogênea ou não em relação ao resto da lista)
! um ou mais ponteiros que apontam para outros nós da lista
- Uma lista é representada por um ponteiro para um nó da lista
- Ponteiros em um nó de uma lista podem ser NULL
LNCC
Listas encadeadas (III)
! TAD “List” em C (elementos inteiros) ! Operações principais:
! List* list_create( void ): cria lista vazia ! void list_destroy( List* l) ! List* list_insert( List* l, int i ): insere nó com informação i no
início da lista ! List* list_remove( List* l, int v ): retira nó com informação v ! int list_empty(List* l): retorna 1 se lista vazia ! List* list_get(List* l, int v): retorna ponteiro para nó com
informação v ! Outras operações:
! void list_print(List* l): imprime conteúdo da lista em stdout
LNCC
Listas encadeadas (IV)
! Tipos de listas:
- Listas encadeadas simples
- Listas circulares
- Listas duplamente encadeadas
LNCC
Listas encadeadas (V) ! Ex.1: lista encadeada simples armazenando
inteiros
struct list { int info; struct list* next; }; typedef struct list List;
/* inserção no início: retorna a lista atualizada */ List* list_insert(List* l, int i) { List* novo = (List*) malloc(sizeof(List)); novo->info = i; novo->next = l; return novo; }
/* imprime valores dos elementos em stdout */ void list_print (List* l) { List* p; for (p = l; p != NULL; p = p->next) printf(“%d\n”, p->info); }
LNCC
Listas encadeadas (VI)
! Ex.1 (cont.) - Remoção
! Caso 1:
! Caso 2:
/* retira elemento da lista */ List* list_remove( List* l, int v ) { List* ant = NULL; /* ponteiro para elemento anterior */ List* p = l; /* ponteiro para percorrer a lista */ /* procura elemento na lista, guardando anterior */ while (p != NULL && p->info != v) { ant = p; p = p->next; } /* verifica se achou elemento */ if (p == NULL) return l; /* não achou: retorna lista original */ /* retira elemento */ if (ant == NULL) /* retira elemento do inicio */ l = p->next; else /* retira elemento do meio da lista */ ant->next = p->next; free(p); return l; }
LNCC
Listas encadeadas (VII) ! Ex.2: lista
encadeada simples ordenada
/* insere elemento em ordem */ List* list_insert(List* l, int v) { List* novo; List* ant = NULL; /* ponteiro para elemento anterior */ List* p = l; /* ponteiro para percorrer a lista */ /* procura posição de inserção */ while (p != NULL && p->info < v) { ant = p; p = p->next; } /* cria novo elemento */ novo = (List*) malloc(sizeof(List)); novo->info = v; /* encadeia elemento */ if (ant == NULL) { /* insere elemento no início */ novo->next = l; l = novo; } else { /* insere elemento no meio/final da lista */ novo->next = ant->next; ant->next = novo; } return l; }
LNCC
Listas encadeadas (VIII)
! Ex.3: lista circular - A lista pode ser representada por um ponteiro para um
elemento inicial qualquer da lista
- E as outras operações?
void list_print(List* l) { List* p = l; /* faz p apontar para o nó inicial */ /* testa se lista não é vazia e então percorre com do-while */ if (p) do { printf("%d\n", p->info); /* imprime informação do nó */ p = p->next; /* avança para o próximo nó */ } while (p != l); }
LNCC
Listas encadeadas (IX)
! Ex.4: lista duplamente encadeada - Cada elemento tem um ponteiro para o próximo
elemento e um ponteiro para o elemento anterior
- E as outras operações?
struct list { int info; struct list* prev; struct list* next; };
/* inserção no início: retorna a lista atualizada */ List* list_insert(List* l, int v) { List* novo = (List*) malloc(sizeof(List)); novo->info = v; novo->next = l; novo->prev = NULL; /* verifica se lista não estava vazia */ if (l != NULL) l->prev = novo; return novo; }
LNCC
Listas encadeadas (X)
! Nós de uma lista podem armazenar ponteiros para informações, ao invés das informações em si
- Permite a implementação de listas genéricas
- Demanda generalização também nas operações do TAD
! Neste caso, uso de linguagem orientada o objetos (ex. C++) facilita implementação
- Herança e polimorfismo
/* Definição de nó genérico */ struct list { int type; void *info; struct list *next; };
LNCC
Listas encadeadas (XI)
! Representação de matrizes esparsas usando listas encadeadas
- Representações CRS, BCRS, CDS, JDS, SKS etc. dão suporte a operações matemáticas eficientes (adição, multiplicação, produto interno etc.) quando a matriz é um operando, mas não a modificações na matriz (inclusão/exclusão de item) de forma eficiente
! Problema relacionado à alocação estática de memória
- Representações de lista encadeada e tabela de dispersão (hash) oferecem alternativas interessantes
LNCC
Listas encadeadas (XII)
! Implementação de matrizes esparsas usando listas encadeadas
- Cada coluna da matriz é representada por uma lista circular (com um nó cabeça)
! Idem para cada linha
- Elementos diferentes de zero na matriz (elementos ponto-flutuante) são representados por nós com a seguinte estrutura:
- Nós cabeça possuem valores de line e column iguais a -1
struct node { struct node* right; struct node* below; int line; int column; float info; } typedef struct node Node;
LNCC
Listas encadeadas (XIII)
• Comparação com implementação usando vetores?
�
⇧⇧⇤
50 0 0 010 0 20 00 0 0 0�30 0 �60 5
⇥
⌃⌃⌅
LNCC
Pilhas e filas (I)
! Pilhas - Novo elemento é inserido no topo e acesso é apenas ao
topo - O primeiro que sai é o último que entrou
(LIFO – last in, first out) - Operações básicas:
! Empilhar (push) um novo elemento, inserindo-o no topo ! Desempilhar (pop) um elemento, removendo-o do topo
LNCC
Pilhas e filas (II)
! TAD “Stack” em C (elementos ponto-flutuante): - Operações principais:
! Stack* stack_create(void) ! void stack_destroy(Stack* s) ! void stack_push(Stack* s, float v) ! float stack_pop(Stack* s) ! int stack_empty(Stack* s)
- Duas implementações principais:
! Como vetor ! Como lista encadeada
LNCC
Pilhas e filas (III)
! Implementação de pilha com vetor - elementos inseridos ocupam as primeiras posições do
vetor - elemento vet[n-1] representa o elemento do topo
#define N 50 /* número máximo de elementos */ struct stack { int n; /* vet[n]: primeira posição livre do vetor */ float vet[N]; /* vet[n-1]: topo da pilha */ /* vet[0] a vet[N-1]: posições ocupáveis */ }; typedef struct stack Stack;
Stack* stack_create(void) { Stack* s = (Stack*) malloc(sizeof(Stack)); s->n = 0; /* inicia com zero elementos */ return s; }
LNCC
Pilhas e filas (IV)
! Implementação de pilha com vetor (cont.)
void stack_push (Stack* s, float v) { if (s->n == N) { /* capacidade esgotada */ printf("Capacidade da pilha estourou.\n"); exit(1); /* aborta programa */ } /* insere elemento na próxima posição livre */ s->vet[s->n] = v; s->n++; }
float stack_pop (Stack* s) { float v; if (stack_empty(s)) { printf("Pilha vazia.\n"); exit(1); /* aborta programa */ } /* retira elemento do topo */ v = s->vet[s->n-1]; s->n--; return v; }
LNCC
Pilhas e filas (V)
! Ex.: Notações para expressões aritméticas - infixa = (1-2)*(4+5) - pós-fixa = 1 2 – 4 5 + * - pré-fixa = * - 1 2 + 4 5
! Expressões pós-fixadas podem ser avaliadas em
uma pilha - cada operando é empilhado numa pilha de valores - quando se encontra um operador
! desempilha-se o número apropriado de operandos (dois para operadores binários e um para operadores unários)
! realiza-se a operação devida ! empilha-se o resultado
LNCC
Pilhas e filas (VII)
! Filas - Um novo elemento é inserido ao final da fila - Um elemento é retirado do início da fila - Primeiro que entra é o primeiro que sai
(FIFO – first in first out) - Operações básicas:
! Enfileirar (enqueue) um novo elemento ao final da fila ! Retirar (dequeue) um elemento do início da fila
enqueue dequeue
LNCC
Pilhas e filas (VIII)
! TAD “Queue” em C (elementos ponto-flutuante): - Operações principais:
! Queue* queue_create(void) ! void queue_destroy(Queue* q) ! void queue_enqueue(Queue* q, float v) ! float queue_dequeue(Queue* q) ! int queue_empty(Queue* q)
- Duas implementações principais:
! Como vetor ! Como lista encadeada
LNCC
Pilhas e filas (IX)
! Implementação de fila com vetor - Processo de inserção e remoção em extremidades
opostas da fila faz com que a fila “ande” no vetor - Incremento das posições do vetor deve ser de forma
“circular” #define N 100 /* número máx. de elementos */ struct queue { int n; /* número de elementos na fila */ int ini; /* posição do próximo elemento a ser retirado da fila */ float vet[N]; }; typedef struct queue Queue;
Queue* queue_create(void) { Queue* q = (Queue*) malloc(sizeof(Queue)); q->n = 0; /* inicia com zero elementos */ q->ini = 0; /* escolhe posição inicial */ return q; }
LNCC
Pilhas e filas (X)
! Implementação de fila com vetor (cont.) void queue_enqueue(Queue* q, float v) { int fim; if (q->n == N) { /* capacidade esgotada */ printf("Capacidade da fila estourou.\n"); exit(1); /* aborta programa */ } /* insere elemento na próxima posição livre */ fim = (q->ini + q->n) % N; q->vet[fim] = v; q->n++; }
float queue_dequeue(Queue* q) { float v; if (queue_empty(q)) { printf("Fila vazia.\n"); exit(1); /* aborta programa */ } /* retira elemento do início*/ v = q->vet[q->ini]; q->ini = (q->ini + 1)%N; q->n--; return v; }
LNCC
Pilhas e filas (XI)
! Fila dupla: - Fila na qual é possível:
! inserir novos elementos no início e no fim ! retirar elementos de ambos os extremos
- Simula, dentro de uma mesma estrutura, duas filas, com os elementos em ordem inversa uma da outra
! Mudança no TAD, para incluir operações de queue e dequeue no início e no fim da fila
- Implementações: ! Com vetor ! Com lista duplamente encadeada
LNCC
Pilhas e filas (XII)
! Exs.: - Filas de pacotes em roteadores - Filas de tarefas aguardando a CPU em sistemas
operacionais
! Caso especial de filas: priorização dos itens - Exemplos acima! - Métodos numéricos iterativos (seleção repetida de um
item com maior/menor valor) - Sistemas de gerência de memória LRU (Least Recently
Used)
LNCC
Pilhas e filas (XIII) • Fila de prioridades: valor associado a um elemento
reflete sua habilidade relativa de abandonar o conjunto de elementos rapidamente
• TAD “PriQueue” em C (elementos ponto-flutuante): - Operações principais:
! PriQueue* priqueue_create(void) ! void priqueue_destroy(PriQueue* q) ! void priqueue_enqueue(PriQueue* q, float v) ! float priqueue_dequeue(PriQueue* q): retira maior/menor elemento ! float priqueue_peek(PriQueue* q): obtém maior/menor elem., sem
retirá-lo - Implementações principais:
! Como vetor ou lista encadeada (ordenados ou não) ! Como heap (não confundir com o homônimo usado em alocação
dinâmica de memória!)
LNCC
Pilhas e filas (XIV) • Heap: sequência de itens c[1], c[2], …, c[n] tal que
c[i] >= c[2i] e c[i] >= c[2i+1] para todo i = 1, 2, ..., n/2 • Definição corresponde a “max heaps” • Implementação usual com vetores
• Note que primeiro item tem sempre índice 1!!!
• Ex. (max heap com elementos do tipo caracter): 1 2 3 4 5 6 7
S R O E N A D
#define N 101 /* num máx de elementos +1 !!*/ struct priqueue { int n; /* número de elementos na fila */ float vet[N]; /* posições ocupáveis: 1 a N-1 */ }; typedef struct priqueue PriQueue;
PriQueue* priqueue_create(void) { PriQueue* q = (PriQueue*) malloc(sizeof(PriQueue)); q->n = 0; /* inicia com zero elementos */ return q; }
LNCC
Pilhas e filas (XV)
• Implementação de fila de prioridades com heap:
#include <float.h> … void priqueue_enqueue(PriQueue* q, float v) { if (q->n == N) { /* capacidade esgotada */ printf("Capacidade da fila estourou.\n"); exit(1); /* aborta programa */ } q->n++; q->vet[q->n] = -FLT_MAX; /*menor float existente */ increase(q, q->n, v); }
float priqueue_dequeue(PriQueue* q) { float v; if (q->n < 1) { printf("Fila vazia.\n"); exit(1); /* aborta programa */ } /* retira elemento do início*/ v = q->vet[1]; q->vet[1] = q->vet[q->n--]; rebuild(q); return v; }
float priqueue_peek(PriQueue* q) { if (q->n < 1) { printf("Fila vazia.\n"); exit(1); /* aborta programa */ } return q->vet[1]; }
LNCC
Pilhas e filas (XVI) • Operações auxiliares para priqueue_enqueue() e
priqueue_dequeue(): • static void rebuild(PriQueue *q): reconstrói a heap após retirada • (static) void (priqueue_)increase(PriQueue *q, int i, float v): aumenta
valor do elemento na posição i para v
static void rebuild(PriQueue* q) { int left = 1; int j = left*2; float v = q->vet[left]; while (j <= q->n) { if ((j < q->n) && (q->vet[j] < q->vet[j+1])) j++; if (v >= q->vet[j]) break; q->vet[left] = q->vet[j]; left = j; j = left*2; } q->vet[left] = v; }
static void increase(PriQueue* q, int i, float v) { while ((i > 1) && (v >= q->vet[i/2])) { q->vet[i] = q->vet[i/2]; i /= 2; } q->vet[i] = v; }
LNCC
Cadeias de caracteres (I) ! Tipo básico caractere:
- Em C: char (tamanho = 1 byte = 8 bits) ! Alguns alfabetos precisam de maior representatividade
- Tabela de códigos: ! correspondência
entre caracteres e códigos numéricos
! Exs.: ASCII (C/C++), Unicode (Java)...
LNCC
Cadeias de caracteres (II) ! Representação de cadeias de caracteres (strings)
em C: - Vetor do tipo char, terminado pelo caractere nulo ('\0') - É necessário reservar uma posição adicional no vetor
para o caractere de fim da cadeia ! Inicialização de cadeias de caracteres:
- Vetor de caracteres (pouco usual) - Caracteres entre aspas duplas
! caractere nulo é representado implicitamente - Exs: char s0[ ] = {’R’, ’i’, ’o’, ’\0’};
char s1[] = ""; char s2[] = "Rio de Janeiro"; char s3[81]; char s4[81] = "Rio";
LNCC
Cadeias de caracteres (III) ! Leitura de caracteres e cadeias de caracteres
através da entrada padrão (stdin) - Operação scanf()
! especificadores de formato definem comportamento ! Exs:
! O que acontece com as entradas: - “r”? - “ r”? - “rio”? - “ rio”? - “rio de janeiro\n”?
char a; ... scanf("%c", &a); ...
char a; ... scanf(" %c", &a); ...
char a[81]; ... scanf("%s", a); ...
char a[81]; ... scanf(" %[^\n]", a); ...
LNCC
Cadeias de caracteres (IV) ! Biblioteca de cadeias de caracteres padrão em C: string.h
- size_t strlen(const char *s) - char *strcpy(char *s1, const char *s2) - char *strcat(char *s1, const char *s2) - int strcmp(const char *s1, const char *s2) - char *strdup(const char *s1) - char *strstr(const char *s1, const char *s2) - ...
! Para cada uma dessas operações, pode-se imaginar implementações recursivas, se considerarmos que uma cadeia de caracteres é:
- Uma cadeia vazia ou - Um caracter seguido de uma (sub)cadeia
LNCC
Cadeias de caracteres (V)
! Uma nota sobre constantes do tipo cadeia de caracteres:
- Avaliação da constante resulta no ponteiro para onde a cadeia de caracteres está armazenada
- Cuidado: o que acontece se executarmos ?
char cidade[4]; strcpy (cidade, "Rio" ); printf ( "%s \n", cidade );
char *cidade = "Rio"; printf ( "%s \n", cidade ); ou ou
char cidade[] = "Rio"; printf ( "%s \n", cidade );
cidade[2] = 'x';
LNCC
Cadeias de caracteres (VI)
! Vetores de cadeias: - Alocação estática:
! Matriz de elementos do tipo char - Alocação dinâmica:
! Vetor de ponteiros ! Cada cadeia de caracteres (elemento do vetor) é alocada
dinamicamente
! Nota (geral!) sobre alocação dinâmica e papel de clientes e provedores no contrato de uma função:
- Idealmente (mas nem sempre!) quem aloca tem que desalocar depois
LNCC
Cadeias de caracteres (VII)
! Um caso especial em C: função main()
! Quais os valores de argc e argv caso o executável seja chamado como: ?
int main (int argc, char** argv) { … }
nome_programa param1 param2
LNCC
Cadeias de caracteres (VIII)
! Processamento de cadeias
- Inúmeras aplicações: ! Processamento de textos ! Recuperação de informação ! Sequenciamento de DNA ! Representação de imagens ! ...
- Principais operações:
! Casamento de cadeias (ou casamento de padrões) ! Compressão de cadeias
LNCC
Cadeias de caracteres (IX) ! Casamento de cadeias
- Casamento exato
- Casamento aproximado: operações de inserção, substituição e retirada de caracteres do padrão são permitidas
! Conceito de distância de edição ! Ex. (dist. edição = 1)
LNCC
Cadeias de caracteres (X) ! Casamento exato:
- Leitura dos caracteres
do texto um a um: ! Algoritmos força bruta,
Knuth-Morris-Pratt e Shift-And
! Ex. força bruta: - Códigos C++: [Ziviani, 2007, págs. 531-532]
- Uso de uma janela que desliza pelo texto, pesquisando
por sufixo da janela que casa com sufixo do padrão, por comparações da direita p/ a esquerda:
! Algoritmos Boyer-Moore-Horspool e BMH-Sunday - Códigos C++: [Ziviani, 2007, págs. 532-533]
char *forcaBruta ( char * texto, char *padrao ) { int n = strlen(texto); int m = strlen(padrao); for ( int i = 0; i < (n − m + 1) ; i ++) { int k = i; int j = 0; while ( ( j < m) && (texto[k] == padrao[j] ) ) ) { j ++; k++; } if ( j ==m) return &texto[i]; } return NULL; }
LNCC
Cadeias de caracteres (XI) ! Compressão de cadeias:
- Motivação: explosão de informação textual disponível ! Bibliotecas digitais ! Bancos de dados de documentos ! World-Wide Web
- Além da economia de espaço, deve-se considerar: ! Velocidade de compressão e de descompressão ! Possibilidade de realizar casamento de cadeias diretamente
no texto comprimido ! Permitir acesso direto a qualquer parte do texto comprimido e
iniciar a descompressão a partir da parte acessada - Algumas técnicas:
! Huffman (baseado em caracteres e palavras), Ziv-Lempel (eficiente na compressão, ineficiente no casamento), Moffat e Katajainen (melhorias no Huffman)