Compressão de série numérica em Python

Publicado por leandro peçanha scardua (última atualização em 28/07/2017)

[ Hits: 660 ]

Download compressao_serie_numerica.py




Esse script comprime uma série numérica, isto é, dada uma série de números, ele gera uma outra série com os pontos mais representativos da série original com n pontos (que é um parâmetro do algoritmo). A série comprimida deve se assemelhar à série original, mas destacando os picos e vales contidos nos dados.

Pode ser usado, por exemplo, para destacar as subidas e descidas na cotação dos preços de uma ação na Bovespa, por exemplo.

Essa é uma versão inicial. A performance pode ser melhorada usando a biblioteca numpy.

  



Esconder código-fonte

# para o algoritmo só é necessário math
import math

# apenas para apresentação em gráfico
import matplotlib.pyplot as plt

#
# Classe para abstrair um ponto da série numérica
#
# É uma classe auxiliar, intermediaria.
#
class Ponto:
   
   def __init__(self, val, ind):
      # é o número propriamente dito
      self.valor = val
      # distância entre o número e a reta teórica que liga os pivots da esquerda e da direita
      self.dist = 0
      # este número já foi inserido na série comprimida?
      self.usado = False
      # índice que o número ocupa na série original.Existe apenas para facilitar o algoritmo
      self.indice = ind

# calcula a inclinação entre dois pontos no plano cartesiano. Ou seja, calcula a tangente.Há implementações para essa função na 
# biblioteca math. Ou seja, esta função será substituída no futuro
def inclinacao(p1,ind1, p2,ind2):
   tg = (p2.valor - p1.valor)/(ind2 - ind1)
   return tg

# calcula a distância entre o valor e a reta suporte traçada entre dois pontos, que no algoritmo serão os pivots 
#esquerdo e direito
def calcDistancia(serie, ind1, ind2):
   p0 = serie[ind1]
   pn = serie[ind2]

   tg = inclinacao(p0,ind1,pn,ind2)   
   for i in range(ind1, ind2):
      y = tg * (i-ind1) + p0.valor
      serie[i].dist = math.fabs(serie[i].valor - y)

# função para selecionar o ponto mais distante da reta de suporte. Na verdade, como as distâncias são atualizadas apenas em
# um trecho da série, a busca é global, ou seja, em toda a série
def obterPivot(serie):
   indice = 0
   maior = -1
   for i in range(0, len(serie)):
      if (serie[i].usado == True):
         continue

      if(serie[i].dist > maior):
         indice = i
         maior = serie[i].dist

   return indice

# se um pivot foi selecionado, adicione-o aa serie comprimida marcando-o como em uso
def marcarPonto(serie, indice):
   serie[indice].usado = True

# quando um pivot é escolhido, é necessario atualizar a distancia no trecho entre os
# dois pontos de referencia anteriores. Aqui será retornado o ponto aa esquerda
def obterReferenciaEsquerda(serie,ind):
   indice = ind-1
   for i in range(indice,-1,-1):
      if serie[i].usado == True:
         indice = i
         break

   return indice

#aqui o ponto aa direita
def obterReferenciaDireita(serie,ind):
   indice = ind+1
   for i in range(indice, len(serie)):
      if serie[i].usado == True:
         indice = i
         break

   return indice

# 
# aqui está o algoritmo propriamente dito.
#
# o algoritmo funciona marcando o ponto inicial e o final da série. A seguir, calcula a inclinação entre os dois pontos
# e calcula a distância entre cada ponto da série original a uma reta que inicia no ponto inicial. 
# Em seguida o algotitmo seleciona o ponto com maior distancia a esta reta de suporte e marca-o como usado (está sendo adicionado aa serie comprimida).
# Em seguida os passos anteriores são repetidos no trecho entre o ponto inicial (que será referencia aa esquerda) e o ponto final(referencia aa direita). 
# Nos dois trechos será calculada a inclinação, distância etc, até que o número de pontos para a série comprimida seja alcançado.
# um detalhe importante a ser mencionado é que no n-ésimo ponto o pivot pode estar no meio da série e haver outros pontos que já foram pivots e que, portanto,
# fazem parte da série comprimida. Esses pontos são as referencias aa direita e aa esquerda para calcular a inclinação, distancia etc e só é atualizada neste trecho.
#
# o algoritmo foi criando usando as funções padrão de lista do python. Ou seja, pode ter a performance melhorada usando a biblioteca numpy, o que pretendo fazer no futuro.
#
def comprimir(serie, n):
   
   if n <= 2:
      return
   
   p0 = 0
   pn = len(serie)-1
   serie[p0].usado = True
   serie[pn].usado = True
   pivot = -1
   
   for x in range(0, n-2):   
      if x == 0:         
         calcDistancia(serie, p0, pn)
         
      pivot = obterPivot(serie)
      marcarPonto(serie, pivot)
      esquerda = obterReferenciaEsquerda(serie, pivot)
      direita = obterReferenciaDireita(serie, pivot)
      
      p0 = esquerda
      pn = direita

      # a série será atualizada no trecho entre os pontos de pivot anteriores, que só coincidirao com o valor inicial e final nos primeiros passos do algoritmo
      if(x > 0):
         calcDistancia(serie, p0, pivot)   
         calcDistancia(serie, pivot, pn)

      #imprime_dist(serie)
      #print ("pivot=%d"%pivot)
      #print ("esquerda=%d"%(esquerda))
      #print ("direita=%d\n------"% (direita))

#
# -----------------------------------------------------------------------------------------------------------------------------------------------------
#

# função auxiliar para extrair os números marcados e criar uma lista independente
def extrair_lista_comprimida(serie):
   lstX = list()
   lstY = list()
   for p in serie:
      if p.usado == True:
         lstX.append(p.indice)
         lstY.append(p.valor)

   return lstX, lstY

if __name__ == "__main__":
   #
   # criação da série numérica original
   #

   linhas = [1.0, 3.0, 12,6.0, 2.0,1.0,5.0,9.0,2.0,10,4.0, 9,10]

   #
   # criacao de uma serie auxiliar para guardas os objetos do tipo Ponto
   #
   serie = list()

   #
   # criação de uma lista de pontos para guardas as informações intermediárias do algoritmo
   #
   i = 0
   for p in linhas:      
      pt = Ponto(p,i)   
      serie.append(pt)
      i = i+1

   #
   # chamando o algorimo propriamente dito. O segundo parametro é o numero de pontos que estarão na série comprimida. Pode ser entendido
   # como nível de compressão da série
   #
   comprimir(serie,4)

   #
   # extraindo a série numérica comprimida resultante
   #
   lsX, lsY = extrair_lista_comprimida(serie)

   #
   # agora vamos mostrar o gráfico final
   #
   plt.plot(linhas)
   plt.plot(lsX, lsY)
   plt.show()

Scripts recomendados

Desenha poligonos

Algoritmo de Abraao

Correios - Rastreador de encomendas

Calculadora de area de poligonos e circulos

Gerador de referência cruzada de texto


  

Comentários

Nenhum comentário foi encontrado.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor HostGator.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Viva o Android

Tópicos

Top 10 do mês

Scripts