Comprima datos con gramáticas libres de contexto

9

Es posible comprimir algunos tipos de datos, como texto humano o código fuente, con gramáticas en línea recta. Básicamente, se crea una gramática cuyo idioma tiene exactamente una palabra: los datos sin comprimir. En esta tarea, debe escribir un programa que implemente este método de competencia de datos.

Entrada

La entrada es una cadena de no más de 65535 bytes de longitud. Se garantiza que la entrada coincide con la expresión regular [!-~]+(es decir, al menos un carácter ASCII imprimible excluyendo espacios en blanco).

Un ejemplo de entrada es

abcabcbcbcabcacacabcabab

Salida

La salida es un conjunto de reglas que forman una gramática que describe exactamente una palabra (la entrada). Cada no terminal se denota con un número decimal mayor que 9. El símbolo de inicio es el símbolo número diez. A continuación se muestra una salida de ejemplo correspondiente a la entrada de ejemplo; Su sintaxis se describe más adelante:

10=11 11 12 12 11 13 13 11 14 14
11=a 12
12=b c
13=a c
14=a b

Cada regla tiene la forma <nonterminal>=<symbol> <symbol> ...con un número arbitrario de símbolos separados por espacios en blanco en el lado derecho. Cada salida que obedece las siguientes restricciones y deriva exactamente la cadena de entrada es válida.

Restricciones

Para evitar que las personas hagan cosas extrañas, se están aplicando varias restricciones:

  • Cada no terminal debe aparecer al menos dos veces en el lado derecho de una regla. Por ejemplo, la siguiente gramática para la entrada abcabces ilegal porque la regla 12 aparece solo una vez:

    10=12
    11=a b c
    12=11 11
    
  • Ninguna secuencia de dos símbolos adyacentes puede aparecer más de una vez en todos los lados derechos de todas las reglas, excepto si se superponen. Por ejemplo, la siguiente gramática para la entrada abcabcbces ilegal ya que la secuencia bcaparece dos veces:

    10=11 11 b c
    11=a b c
    

    Una gramática válida sería:

    10=11 11 12
    11=a 12
    12=b c
    
  • Su programa debe finalizar en menos de un minuto por cada entrada válida que no supere los 65535 bytes.

  • Como de costumbre, no puede utilizar ninguna instalación de su idioma ni ninguna función de biblioteca que haga que la solución sea trivial o que implemente una gran parte de ella.

Entrada de muestra

Genere una entrada de muestra con el siguiente programa en C.

#include <stdlib.h>
#include <stdio.h>

int main(int argc, char **argv) {
  unsigned int i,j = 0,k;

  if (argc != 3
     || 2 != sscanf(argv[1],"%u",&i)
      + sscanf(argv[2],"%u",&k)) {
    fprintf(stderr,"Usage: %s seed length\n",argv[0]);
    return EXIT_FAILURE;
  }

  srand(i);

  while(j < k) {
    i = rand() & 0x7f;
    if (i > 34 && i != 127) j++, putchar(i);
  }

  return EXIT_SUCCESS;
}

La entrada de muestra generada por el programa anterior generalmente no dará como resultado buenos resultados de compresión. Considere utilizar texto humano o código fuente como entrada de ejemplo.

Criterios ganadores

Este es el código de golf; el programa con el código fuente más corto gana. Para obtener crédito adicional, escriba un programa que reconstruya la entrada de la salida.

FUZxxl
fuente
Jaja. Ya tengo algunas versiones de esto implementadas (pero no golfizadas) en Java para las preguntas de complejidad kolmogorov ...
Peter Taylor
@PeterTaylor ¿Qué preguntas exactamente?
FUZxxl
No necesariamente encuentra una respuesta lo suficientemente corta como para que valga la pena publicarla (estoy agregando estrategias de generación de gramática y motores de gramática lentamente), pero el script central en ese proyecto los prueba en codegolf.stackexchange.com/questions/1682 , codegolf .stackexchange.com / preguntas / 6043 , codegolf.stackexchange.com/questions/4191 , codegolf.stackexchange.com/questions/4356 y algunos componentes de otras preguntas.
Peter Taylor

Respuestas:

3

GolfScript, 111 108 caracteres

1/{.}{:^1<{^1$/,2>.{;,)^<.0?)!}*}do-1<.,1>{^1$/[10):10]*0+\+}{;^}if(\}while][0]%.,,]zip{))9+`"="+\~" "*+}%n*

Este es un enfoque bastante torpe con GolfScript. La segunda versión funciona mucho mejor que la inicial. Es mucho más largo que el código previsto, pero mi implementación había anidado do-loops y esto causó problemas con el intérprete.

Ejemplos:

> abcba
10=a b c b a

> abcabcbc
10=11 11 12
11=a 12
12=b c

> abcabcbcbcabcacacabcabab
10=11 12 12 13 14 14 c 11 15
11=15 13
12=c b
13=14 b
14=c a
15=a b
Howard
fuente
1

Retraído: el algoritmo no puede manejar todos los casos. C, 422 (arreglado para eliminar dups en la salida y caracteres descartados)

Implementación inicial, comenzará a jugar golf.

Dado que las reglas no requieren que realmente comprima este enfoque ingenuo de fuerza bruta ...

Puede procesar 65535 de longitud en 10 segundos

n,m[99999];
c,r[99999][2];

g,i,s,t;

main(){
    for(;(m[n]=getchar())>32;n++);

    while(!g){ // loop until no further changes
        g=1;
        for(s=0;s<n-1;s++) {
            for(t=s+2;t<n-1;t++)if(m[s]==m[t]&&m[s+1]==m[t+1]){
                // create rule
                r[c][0]=m[s];
                r[c++][1]=m[s+1];
                g=0;
                // substitute
                for(i=t=s;i<n;i++){
                    if(m[i]==r[c-1][0]&&m[i+1]==r[c-1][1]){
                        m[t++]=-c;
                        i++;
                    }else
                        m[t++]=m[i];
                }
                n=t;
            }
        }
    }

    for(s=-1;s<c;s++){
        printf("%d=",s+11);
        for(t=0;t<(s<0?n:2);t++){
            i=(s<0?m:r[s])[t];
            i<0?printf("%d ",10-i):printf("%c ",i);
        }
        printf("\n");
    }

}

Ejecución de muestra:

echo abcabcbcbcabcacacabcabab | a.out
10=11 12 13 13 12 14 14 12 12 11 
11=a b 
12=c 11 
13=c b 
14=c a

conejo bebé
fuente
Su código no funciona de acuerdo con las especificaciones. Genera una salida que viola la regla, no puede aparecer una secuencia de dos caracteres dos veces ; considere la entrada abcdabcd. Además, su código aparentemente elimina el último byte de la secuencia de entrada. Busque aquí un ejemplo para observar ambos efectos: ideone.com/3Xvtyv
FUZxxl
Además, su salida de muestra aparentemente es incorrecta.
FUZxxl
Tienes razón - Fallé - Lo miraré cuando regrese del trabajo: P
conejita
No está eliminando el último byte de la entrada para mí, y mi salida de muestra es correcta (para mí). ¡Juguemos a "detectar el error"!
baby-rabbit
La salida de muestra que publicaste definitivamente es. La forma expandida de la regla 10 termina con la regla 14 que a su vez termina con "ca". La última c es en realidad 5 posiciones antes del final.
FUZxxl