Estoy buscando un R-aplicación de la Lempel-Ziv algoritmo de compresión de datos, para estimar el origen de la entropía de un momento de la serie que consta de una secuencia de símbolos.
En lugar de simplemente medir la entropía de la (tiempo acumulado) símbolo-de la distribución de frecuencia, el Lempel-Ziv algoritmo puede ser utilizado para la estimación de la entropía de la ordenación temporal dentro de la misma secuencia.
Las secuencias estoy estudiando son derivados de animales de trayectorias; cada una de las $x,y$ ubicación se le asigna una etiqueta arbitraria (a,B,...,Z). Representada de esta forma, la trayectoria de un movimiento de los animales se ve como B,G,G,S,Y,G,Y,H,D,S,a,B,B,G,G,G,H, etc. Por lo tanto, estoy interesado en la medición de la $\textit{predictability}$ de la secuencia.
El procedimiento para la estimación de la fuente de entropía es (brevemente) se describe en la Información Complementaria de la Canción et al (2010), y que describen la Lempel-Ziv estimador como:
$$ S^{est} = \left( \frac {1}{n} \sum_{i=1} \Lambda_i \right)^{-1} ln~n $$ donde $\Lambda_i$ es la longitud de la menor subcadena que empieza en la posición $i$ $\textit{doesn't}$ anteriormente aparecen a partir de la posición 1 a $i$-1.
Así que, ¿alguien tiene alguna sugerencia de cómo calcular el anterior en R?
Por cierto, debo mencionar que tengo varias trayectorias entre los que me gustaría hacer entropía comparaciones, sin embargo, algunas de las trayectorias de contener huecos que corresponden a los tiempos de cuando el animal no fue observado.
REFERENCIA:
La canción, Qu, Blumm Y Barabasi (2010) Límites de la Previsibilidad de la Movilidad Humana. $\textit{Science}$. 19. http://www.sciencemag.org/content/327/5968/1018.short
ACTUALIZACIÓN: La función siguiente es lo que me llegó. Sin embargo, en lugar de chugging a través de todos los posibles sub-secuencias después de la i-esima índice, y luego encontrar el más corto de los nuevos sub-secuencia, sería más rápido utilizar un bucle while. Del mismo modo yo soy la actualización del diccionario de la recién adquirida único subcadenas utilizando rbind, que no es eficiente. OTOH las secuencias estoy usando son cortas (<300), así que esto no es un problema, pero sin duda hay espacio para la mejora.
PREDICTABILITY <- function(Sequence, Max_String)
{
output <- matrix(NA,nrow=length(Sequence), ncol=1)
dictionary <- NULL
## cycle through each entry, i, in the Sequence
for (i in 1:(length(Sequence)-Max_String) )
{
## Compile list of increasingly-long substrings, starting at position i; i+0,i+1,i+2,...,i+Max_String
codons <- matrix(NA, nrow=Max_String, ncol=1)
for (STRL in 0:Max_String)
{
codons[STRL,] <- paste(Sequence [i:(i+STRL-1)], collapse="")
}
## Find which of these codons have NOT been seen before
new <- codons[!codons %in% dictionary]
## check for no new codons
ifelse ((length(new)>0),
record <- min(nchar(new)), ## if we have new codons, find the shortest among them
record <- NA ) ## if none are new (because we aren't searching far enough ahead), assign NA...
## find the shortest of these unseen codons
output[i,] <- record
## Finally, add the unseen codons to the dictionary
dictionary <- c(dictionary, new)
}##i
## Calculate source entropy (i.e. predictability) from formula in Song et al (2010)
n <- length(output[!is.na(output)])
S <- (1/mean(output, na.rm=TRUE)) * log(n) ## Source entropy ?natural log means the units are nats?
return(S)}
