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.

• Download compressao_serie_numerica.py
• Enviar nova versão

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()

Backup em Python

Tabuadas

Tkinter - Sistema de Cadastro de Cursos, Alunos e Turmas

Exercício com números randômicos - randint

Árvore binária de busca do tipo splay

Nenhum comentário foi encontrado.