c++ - programacion - Escriba un programa que tome el texto como entrada y produzca un programa que reproduzca ese texto
que es tags h1 y cursiva (5)
Suponiendo que "carácter" significa "byte" y asumiendo que el texto de entrada puede contener al menos tantos caracteres válidos como el lenguaje de programación, es imposible hacer esto para todas las entradas, ya que como templatetypedef explicado, para cualquier longitud dada de texto de entrada, todo "estrictamente" los "programas más pequeños" son en sí mismos entradas posibles con una longitud menor, lo que significa que hay más entradas posibles que salidas alguna vez. (Es posible organizar que la salida sea como máximo un bit más larga que la entrada utilizando un esquema de codificación que comienza con "si esto es 1, la siguiente es solo la entrada no codificada porque no se puede comprimir más" bit )
Suponiendo que es suficiente para hacer que esto funcione para la mayoría de las entradas (por ejemplo, entradas que consisten principalmente en caracteres ASCII y no en el rango completo de posibles valores de bytes), entonces la respuesta existe: use gzip. En eso es bueno. Nada va a ser mucho mejor. Puede crear archivos autoextraíbles o tratar el formato gzip como el resultado de "idioma". En algunas circunstancias, puede ser más eficiente teniendo como salida un lenguaje de programación completo o ejecutable, pero a menudo, reduciendo la sobrecarga teniendo un formato diseñado para este problema, es decir. gzip, será más eficiente.
Recientemente me encontré con un problema agradable, que resultó ser tan fácil de entender como difícil de encontrar. El problema es:
Escriba un programa, que lea un texto de la entrada e imprima algún otro programa en la salida. Si compilamos y ejecutamos el programa impreso, debe mostrar el texto original.
El texto de entrada se supone que es bastante grande (más de 10000 caracteres).
El único (y muy fuerte) requisito es que el tamaño del archivo (es decir, el programa impreso) debe ser estrictamente menor que el tamaño del texto original. Esto hace imposible soluciones obvias como
std::string s;
/* read the text into s */
std::cout << "#include<iostream> int main () { std::cout<</"" << s << "/"; }";
Creo que algunas técnicas de archivo se van a utilizar aquí.
Desafortunadamente, tal programa no existe.
Para ver por qué esto es así, tenemos que hacer un poco de matemática. Primero, vamos a contar cuántas cadenas binarias hay de longitud n. Cada uno de los bits puede ser 0 o 1, lo que nos da una de dos opciones para cada uno de esos bits. Como hay dos opciones por bit y n bits, hay un total de 2 n cadenas binarias de longitud n.
Ahora, supongamos que queremos construir un algoritmo de compresión que siempre comprima una cadena de bits de longitud n en una cadena de bits de longitud menor que n. Para que esto funcione, necesitamos contar cuántas cadenas de longitud diferentes hay menos de n. Bueno, esto viene dado por el número de bits de longitud 0, más el número de bits de longitud 1, más el número de bits de longitud 2, etc., hasta n - 1. Este total es
2 0 + 2 1 + 2 2 + ... + 2 n - 1
Usando un poco de matemática, podemos obtener que este número sea igual a 2 n - 1. En otras palabras, el número total de bitstrings de longitud menor que n es uno más pequeño que el número de bitstrings de longitud n.
Pero esto es un problema Para que tengamos un algoritmo de compresión sin pérdida que siempre asigna una cadena de longitud n a una cadena de longitud como máximo n - 1, deberíamos tener alguna forma de asociar cada cadena de bits de longitud n con una cadena de bits más corta de forma que no dos bitstrings de longitud n están asociados con el mismo bitstream más corto. De esta forma, podemos comprimir la cadena simplemente asignándola a la cadena asociada más corta, y podemos descomprimirla invirtiendo la asignación. La restricción de que no hay dos bitstrings de longitud n correlacionados con la misma cadena más corta es lo que hace que este sin pérdidas: si dos cadenas de bits de longitud y n se asignaran a la misma cadena de bits más corta, cuando llegara el momento de descomprimir la cadena, no habría ser una forma de saber cuál de las dos cadenas de bits originales que teníamos comprimidas.
Aquí es donde llegamos a un problema. Como hay 2 n cadenas de bits diferentes de longitud ny solo 2 n -1 de cadenas de bits más cortas, no hay forma posible de emparejar cada cadena de bits de longitud n con una cadena de bits más corta sin asignar al menos dos cadenas de bits de longitud-n al mismo cuerda. Esto significa que no importa cuánto lo intentemos, no importa cuán listos seamos, y no importa cuán creativos seamos con nuestro algoritmo de compresión, hay un límite matemático difícil que dice que no siempre podemos acortar el texto.
Entonces, ¿cómo se correlaciona esto con tu problema original? Bueno, si tenemos una cadena de texto de longitud de al menos 10000 y necesitamos generar un programa más corto que lo imprima, entonces tendríamos que tener alguna manera de mapear cada una de las 2 10000 cadenas de longitud de 10000 en el 2 10000 - 1 cadenas de longitud inferior a 10000. Ese mapeo tiene otras propiedades, a saber, que siempre tenemos que producir un programa válido, pero eso es irrelevante aquí, simplemente no hay suficientes cadenas más cortas para todos. Como resultado, el problema que quiere resolver es imposible.
Dicho esto, podríamos obtener un programa que pueda comprimir todas menos una de las cadenas de longitud 10000 en una cadena más corta. De hecho, podríamos encontrar un algoritmo de compresión que hace esto, lo que significa que con probabilidad 1 - 2 10000 cualquier cadena de longitud 10000 podría ser comprimida. Esta es una probabilidad tan alta que si seguimos seleccionando cadenas durante toda la vida del universo, casi con seguridad nunca adivinaremos el One Bad String.
Para una lectura posterior, existe un concepto de la teoría de la información llamado complejidad de Kolmogorov , que es la longitud del programa más pequeño necesario para producir una cadena dada. Algunas cadenas se comprimen fácilmente (por ejemplo, abababababababab), mientras que otras no (por ejemplo, sdkjhdbvljkhwqe0235089). Existen cadenas que se llaman cadenas incompresibles , por lo que la cadena no puede ser comprimida en ningún espacio más pequeño. Esto significa que cualquier programa que imprimiría esa cadena tendría que ser al menos tan largo como la cadena dada. Para una buena introducción a la Complejidad de Kolmogorov, es posible que desee consultar el Capítulo 6 de "Introducción a la teoría de la computación, segunda edición" de Michael Sipser, que ofrece una excelente descripción de algunos de los resultados más fríos. Para una mirada más rigurosa y profunda, considere leer "Elementos de la teoría de la información", capítulo 14.
¡Espero que esto ayude!
Lo que está describiendo es esencialmente un programa para crear archivos zip autoextraíbles, con la pequeña diferencia de que un archivo zip autoextraíble normal escribiría los datos originales en un archivo en lugar de stdout. Si desea hacer un programa de este tipo usted mismo, hay muchas implementaciones de algoritmos de compresión, o podría implementar, por ejemplo, DEFLATE (el algoritmo utilizado por gzip) usted mismo. El programa "externo" debe comprimir los datos de entrada y generar el código para la descompresión, e insertar los datos comprimidos en ese código.
Pseudocódigo:
string originalData;
cin >> originalData;
char * compressedData = compress(originalData);
cout << "#include<...> string decompress(char * compressedData) { ... }" << endl;
cout << "int main() { char compressedData[] = {";
(output the int values of the elements of the compressedData array)
cout << "}; cout << decompress(compressedData) << endl; return 0; }" << endl;
Se llama archivador de archivos y produce archivos autoextraíbles.
Si estamos hablando de texto ASCII ...
Creo que esto podría hacerse, y creo que la restricción de que el texto será más grande que 10000 caracteres está ahí por una razón (para darle espacio de codificación).
La gente aquí dice que la cadena no se puede comprimir, pero sí puede.
¿Por qué?
Requisito: SALIDA DEL TEXTO ORIGINAL
El texto no es información Cuando lee texto de entrada, lee caracteres ASCII (bytes). Que tienen valores imprimibles y no imprimibles adentro.
Toma esto por ejemplo:
ASCII values characters
0x00 .. 0x08 NUL, (other control codes)
0x09 .. 0x0D (white-space control codes: ''/t'',''/f'',''/v'',''/n'',''/r'')
0x0E .. 0x1F (other control codes)
... rest of printable characters
Como tiene que imprimir texto como salida, no está interesado en el rango (0x00-0x08, 0x0E-0x1F). Puede comprimir los bytes de entrada utilizando un mecanismo diferente de almacenamiento y recuperación (patrones binarios), ya que no tiene que devolver los datos originales, sino el texto original. Puede recalcular lo que significan los valores almacenados y reajustarlos en bytes para imprimir. De hecho, perderá solo datos que no son datos de texto de todos modos, y por lo tanto no es imprimible o ingresable. Si WinZip hiciera eso, sería un gran error, pero para sus requisitos establecidos simplemente no importa.
Dado que el requisito establece que el texto tiene 10000 caracteres y puede guardar 26 de 255, si su embalaje no presentaba ninguna pérdida, está ahorrando alrededor del 10% de espacio, lo que significa que puede codificar la ''descompresión'' en 1000 (10% de 10000) personajes puedes lograr eso. Tendría que tratar grupos de 10 bytes como 11 caracteres, y a partir de ahí extrapolar el 11, por algún método de extrapolación para su rango de 229. Si eso se puede hacer, entonces el problema se puede resolver.
Sin embargo, requiere un pensamiento inteligente y habilidades de codificación que realmente pueden hacer eso en 1 kilobyte.
Por supuesto, esto es solo una respuesta conceptual, no funcional. No sé si alguna vez podría lograr esto.
Pero tenía ganas de dar mis 2 centavos en esto, ya que todos sintieron que no se podía hacer, al estar tan seguros de ello.
El problema real en su problema es comprender el problema y los requisitos.