Compressão e descompressão de dados e Grafos

Prévia do material em texto

por Helen Deuner Ferreira
Compressão de Descompressão de Dados
Compressão: reduz o tamanho do arquivo, diminuindo espaço na memória e tempo de
transmissão. Faz isso retirando as redundâncias que a maioria dos arquivos apresentam. Não
é possível comprimir um arquivo já comprimido, pois as redundâncias já foram removidas.
Com a compressão há possibilidade da perda da qualidade.
Lossy: remove algumas partes dos dados de forma permanente - JPG, MP3.
Lossless: remove apenas a parte não essencial dos dados - FLAC, GIF.
Algoritmo LZW: algoritmo de compressão de dados do tipo lossless. Usado em
sistemas baseados no Unix e compressão de imagens GIF.
O primeiro passo é criar um dicionário de 8 ou 12 bits para as entradas na tabela. Por
padrão, é usado o código ASCII ou UTF8. Tanto na compressão quanto descompressão, os
dados do arquivo são lidos símbolo a símbolo, comparando cada símbolo do arquivo com os
existentes no dicionário.
Grafos
Os grafos possuem como objetos básicos os vértices (nodos) e os relacionamentos
entre eles são chamados de arestas (arcos ou links). Também são um tipo abstrato de dados.
G = (V, E) // v = vertex (vértice), e = edge (aresta)
Exemplos:
★ objeto - websites / relacionamento - hiperlinks
★ objeto - torres de celular / relacionamento - área de cobertura
★ objeto - pessoa / relacionamento - amigos
★ busca do airbnb - achar a casa que possua todas as x características
Formas de representação:
★ matriz de adjacências
Tipos de grafos: não direcionado, direcionado, com laço, com arestas paralelas.
Terminologia:
★ nós terminais: os nós associados a arestas;
★ extremidade de uma aresta: vértice da aresta;
★ função aresta-extremidade: associa aresta a vértices;
★ laço/loop: aresta somente com nó terminal;
★ arestas paralelas: arestas associadas ao mesmo conjunto de vértices;
★ adjacentes: dois vértices conectados por uma aresta e/ou duas arestas
incidentes ao mesmo vértice;
★ adjacente a si próprio: vértice que é nó terminal de um laço;
★ incidente: a aresta é incidente a cada um dos seus nós terminais;
★ isolado: vértice que não possui nenhuma aresta incidente;
★ vazio: grafo sem vértices.