Compressão de dados - Classificação

Com perdas e sem perdas

Esta é a forma mais conhecida de se classificar os métodos de compressão de dados. Diz-se que um método de compressão é sem perdas (em inglês, lossless) se os dados obtidos após a compressão são idênticos aos dados originais, ou os dados que se desejou comprimir. Esses métodos são úteis para dados que são obtidos diretamente por meios digitais, como textos, programas de computador, planilhas eletrônicas, etc., onde uma pequena perda de dados acarreta o não funcionamento ou torna os dados incompreensíveis. Um texto com letras trocadas, uma planilha com valores faltantes ou inexatos, ou um programa de computador com comandos inválidos são coisas que não desejamos e que podem causar transtornos. Algumas imagens e sons precisam ser reproduzidos de forma exata, como imagens e gravações para perícias, impressões digitais, etc.

Por outro lado, algumas situações permitem que perdas de dados poucos significativos ocorram. Em geral quando digitalizamos informações que normalmente existem de forma analógica, como fotografias, sons e filmes, podemos considerar algumas perdas que não seriam percebidas pelo olho ou ouvido humano. Sons de frequências muito altas ou muito baixas que os humanos não ouvem, detalhes muito sutis como a diferença de cor entre duas folhas de uma árvore, movimentos muito rápidos que não conseguimos acompanhar num filme, todos estes detalhes podem ser omitidos sem que as pessoas percebam que eles não estão lá. Nesses casos, podemos comprimir os dados simplesmente por omitir tais detalhes. Assim, os dados obtidos após a compressão não são idênticos aos originais, pois "perderam" as informações irrelevantes, e dizemos então que é um método de compressão com perdas (em inglês, lossy). Um exemplo bastante expressivo da citação acima é a imagem a seguir:

Compressão de dados - Introdução

A compressão de dados é o ato de reduzir o espaço ocupado por dados num determinado dispositivo. Essa operação é realizada através de diversos algoritmos de compressão, reduzindo a quantidade de Bytes para representar um dado, sendo esse dado uma imagem, um texto, ou um arquivo (ficheiro) qualquer.

Comprimir dados destina-se também a retirar a redundância, baseando-se que muitos dados contêm informações redundantes que podem ou precisam ser eliminadas de alguma forma. Essa forma é através de uma regra, chamada de código ou protocolo, que, quando seguida, elimina os bits redundantes de informações, de modo a diminuir seu tamanho nos ficheiros. Por exemplo, a sequência "AAAAAA" que ocupa 6 bytes, poderia ser representada pela sequência "6A", que ocupa 2 bytes, economizando 67% de espaço.

Além da eliminação da redundância, os dados são comprimidos pelos mais diversos motivos. Entre os mais conhecidos estão economizar espaço em dispositivos de armazenamento, como discos rígidos, ou ganhar desempenho (diminuir tempo) em transmissões.

Embora possam parecer sinônimos, compressão e compactação de dados são processos distintos. A compressão, como visto, reduz a quantidade de bits para representar algum dado, enquanto a compactação tem a função de unir dados que não estejam unidos. Um exemplo clássico de compactação de dados é a desfragmentação de discos.

Nas próximas postagens estudaremos sobre esse assunto, aguardem as postagens.

Microsoft Azure

O Microsoft Azure é uma plataforma especial para execução de aplicativos e serviços, possui conceitos de

computação em nuvem é um serviço completamente controlado pela microsoft (hospedado) , desse modo o microsoft azure não é  vendido para maquinas físicas como computadores, tablets e etc, ou seja tudo é feito na nossa amiga intente, então você meu caro leitor deve se perguntar o que diabos estou falando sobre essa plataforma se o blog é sobre big data ?, cara criatura inocente computação em nuvem usa grande volume de dados não estruturados e podem definir perfis sobre os usuários e naturalmente essa plataforma prevê essa possibilidade, sendo assim é uma poderosa ferramenta para sistemas que usam Big data. Para uma descrição mais completa segue o link : http://azure.microsoft.com/pt-br/solutions/big-data/

Infoq

Boa noite galera!

Navegando na net achei um site legal que envolve um bocado de assuntos do meio da computação, o Infoq.
Lá vocês vão achar tanto a parte de hardware como também a parte de desenvolvimento, computação inteligente, big data e outros assuntos mais!

Bom aprendizado e aproveitem!

Especialização em Big Data

Bom meus caros, nosso blog não fala sobre carreira, mas porque não falar sobre especialização em Big Data? Se trata de algumas instituições no Brasil que oferecem ao publico especialização nessa área, que
consiste em capturar,processar e aplicar ao negocio de interesse(Empresa ou órgão), desse modo vale a pena ler a matéria da computer word.
Link: http://computerworld.com.br/carreira/2014/07/10/seis-universidades-passam-a-oferecer-especializacao-em-big-data/

Algoritmos de Ordenação - Merge Sort

O merge sort, ou ordenação por mistura, é um exemplo de algoritmo de ordenação do tipo dividir-para-conquistar.

Sua ideia básica consiste em Dividir(o problema em vários sub-problemas e resolver esses sub-problemas através da recursividade) e Conquistar(após todos os sub-problemas terem sido resolvidos ocorre a conquista que é a união das resoluções dos sub-problemas).Como o algoritmo do Merge Sort usa a recursividade em alguns problemas esta técnica não é muito eficiente devido ao alto consumo de memória e tempo de execução.

Os três passos úteis dos algoritmos dividir-para-conquistar, ou divide and conquer, que se aplicam ao merge sort são:

1. Dividir: Dividir os dados em subsequências pequenas;
2. Conquistar: Classificar as duas metades recursivamente aplicando o merge sort;
3. Combinar: Juntar as duas metades em um único conjunto já classificado.

Como todo código, ele também tem desvantagens. Por utilizar funções recursivas pra fazer a quebra do vetor, o código automaticamente precisa de mais poder de processamento, caso seja um vetor muito grande, por exemplo.

Por ser um algorítimo complexo, necessita de um gasto extra de memória. Ele cria uma cópia do vetor para cada nível da chamada recursiva, totalizando um uso adicional de memória igual a (n log n).

Animação:

Algoritmos de Ordenação - Selection Sort

Este algoritmo é baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o segundo menor valor para a segunda posição e assim sucessivamente, até os últimos dois elementos.

Neste algoritmo de ordenação é escolhido um número a partir do primeiro, este número escolhido é comparado com os números a partir da sua direita, quando encontrado um número menor, o número escolhido ocupa a posição do menor número encontrado. Este número encontrado será o próximo número escolhido, caso não for encontrado nenhum número menor que este escolhido, ele é colocado na posição do primeiro número escolhido, e o próximo número à sua direita vai ser o escolhido para fazer as comparações. É repetido esse processo até que a lista esteja ordenada.

Figura 3: Esquema de funcionamento do Selection Sort

• Neste passo o primeiro número escolhido foi o 3, ele foi comparado com todos os números à sua direita e o menor número encontrado foi o 1, então os dois trocam de lugar.
• O mesmo processo do passo 1 acontece, o número escolhido foi o 5 e o menor número encontrado foi o 2.
• Não foi encontrado nenhum número menor que 3, então ele fica na mesma posição.
• O número 5 foi escolhido novamente e o único número menor que ele à sua direita é o 4, então eles trocam.
• Vetor já ordenado.

Animações:

Arvore AVL

Mais uma vez meus leitores vamos falar sobre estrutura de dados, dessa vez vamos observar arvore AVL, primeiramente uma arvore AVL é uma arvore binaria de busca, ou seja possui limitações no modo de inserir e  no grau da arvore, bom mais uma vez vale lembrar sem ED não existe bons sistemas, nem tudo pode ser feito de maneira intuitiva, bom então essa é mais uma base para o uso efetivo de Big data em suas aplicações, segue o material :

Árvores Balanceadas AVL

---

Definição: Uma árvore é considerada AVL quando a altura de suas subárvores direita e esquerda diferem no máximo 1 unidade, isto é, a árvore permanece sempre balanceada. AVL vem da abreviatura dos nomes de seus criadores G.M. Adelson-Velskii e  E.M. Landis, em 1962.

Definição de uma árvore AVLtype
   TDirecao = (NoEsquerdo, NoDireito);
   PNo = ^No;
   No = record
           Dado : Tipo_do_Dado;
           Links : array[NoEsquerdo..NoDireito] of PNo;
           Balanco : -1..1;
   end;
   ArvoreAVL = PNo;

Exemplo: Observe os balanços de cada nó da árvore AVL abaixo


Exemplo: Efetuando uma inserção em uma árvore AVL

Após a inserção de B no exemplo acima, a árvore passou a ficar desbalanceada. Para corrigir tal situação, aplicamos rotações para tornar a árvore balanceada novamente.

Rotações

---

Rotação Simples para Direita: Quando pivô e filho esquerdo têm mais elementos no lado esquerdo.

Após a inserção do valor 3, a árvore AVL ficou desbalanceada. O pivô (nó que contém 8) tem balanço 2 e seu filho esquerdo (nó que contém 4) tem balanço 1. Ao aplicar a rotação simples para direita, a árvore volta a ficar balanceada.

procedure RotacaoParaDireita(var Pivo : PNo);
var Temp, FilhoEsq : PNo;
begin
   FilhoEsq := Pivo^.Links[NoEsquerdo];
   Temp := FilhoEsq^.Links[NoDireito];
   FilhoEsq^.Links[NoDireito] := Pivo;
   Pivo^.Links[NoEsquerdo] := Temp;
end;

Rotação Simples para Esquerda: Quando pivô e filho direito têm mais elementos no lado direito.

Após a inserção do valor 13, a árvore AVL ficou desbalanceada. O pivô (nó que contém 10) tem balanço -2 e seu filho esquerdo (nó que contém 12) tem balanço -1. Ao aplicar a rotação simples para esquerda, a árvore volta a ficar balanceada.

procedure RotacaoParaEsquerda(var Pivo : PNo);
var Temp, FilhoDir : PNo;
begin
   FilhoDir := Pivo^.Links[NoDireito];
   Temp := FilhoDir^.Links[NoEsquerdo];
   FilhoDir^.Links[NoEsquerdo] := Pivo;
   Pivo^.Links[NoDireito] := Temp;
end;

Rotação Dupla uma para Esquerda outra para Direita: Quando pivô tem mais elementos do lado esquerdo e filho tem mais elementos do lado direito.

Após a inserção do valor 7, a árvore fica desbalanceada. Como o pivô (nó com valor 8) tem mais elementos do lado esquerdo, mas seu filho esquerdo (nó com valor 4) possui mais elementos do lado direito, é preciso primeiro fazer uma rotação à esquerda em torno do filho esquerdo para depois efetuar a rotação para a direita sobre o pivô.

Rotação Dupla uma para Direita outra para Esquerda: Quando pivô tem mais elementos do lado direito e filho tem mais elementos do lado esquerdo.

Após a inserção do valor 11, a árvore fica desbalanceada. Como o pivô (nó com valor 10) tem mais elementos do lado direito, mas seu filho direito (nó com valor 12) possui mais elementos do lado esquerdo, é preciso primeiro fazer uma rotação à direita em torno do filho direito para depois efetuar a rotação para a esquerda sobre o pivô (nó com valor 10).

De forma geral, teríamos o quadro abaixo:

Fonte:http://200.17.141.213/~alberto/2012-2/ed1/aulas/arvores_avl.htm