Écrivez un programme qui prend du texte en entrée et produit un programme qui le reproduit

Question

Récemment je suis tombé sur un problème de nice, qui a donné aussi simple à comprendre que difficile de trouver une façon de les résoudre. Le problème, c'est:

Écrire un programme qui lit un texte à partir d'une entrée et d'estampes de certains autres programme de la sortie. Si nous compiler et exécuter le programme imprimé, il doit sortie le texte original.

La saisie de texte est censé être assez grande (plus de 10 000 caractères).

La seule (et très fort) exigence est que la taille de l'archive (c'est à dire le programme imprimé) doit être strictement plus petit que la taille du texte original. Cela rend impossible de solutions évidentes comme

std::string s;
/* read the text into s */
std::cout << "#include<iostream> int main () { std::cout<<\"" << s << "\"; }";

Je crois que certaines techniques d'archivage doivent être utilisés ici.

Answer 1

Malheureusement, un tel programme n'existe pas.

Pour voir pourquoi il en est ainsi, nous devons faire un peu de maths. Tout d'abord, nous allons compter jusqu'à combien de chaînes binaires, il y a de longueur n. Chacun des bits peut être 0 ou 1, ce qui nous donne l'un des deux choix pour chacun de ces bits. Puisqu'il y a deux choix par bit et de n bits, il y a donc un total de 2ⁿ chaînes binaires de longueur n.

Maintenant, supposons que nous voulons construire un algorithme de compression qui toujours comprime un bitstring de longueur n dans un bitstring de longueur inférieure à n. Pour que cela fonctionne, nous avons besoin de compter jusqu'à combien de différentes chaînes de longueur inférieure à n, il existe. Eh bien, c'est le nombre de chaînes de bits de longueur 0, plus le nombre de chaînes de bits de longueur 1, plus le nombre de chaînes de bits de longueur 2, etc., tout le chemin jusqu'à n - 1. Ce total est

2⁰ + 2¹ + 2² + ... + 2^{n - 1}

À l'aide d'un peu de maths, on ne peut obtenir que ce nombre est égal à 2ⁿ - 1. En d'autres termes, le nombre total de chaînes de bits de longueur inférieure à n est plus petit que le nombre de chaînes de bits de longueur n.

Mais c'est un problème. Pour que nous puissions avoir une compression sans perte algorithme de toujours les cartes une chaîne de longueur n d'une chaîne de caractères de longueur au plus n - 1, on aurait un moyen d'associer à chaque bitstring de longueur n avec certains plus courte bitstring à ce qu'aucune des deux chaînes de bits de longueur n sont associés à la même plus courte bitstream. De cette façon, nous pouvons compresser la chaîne de correspondre à l'associé chaîne plus courte, et l'on peut décompresser par l'inversion de la cartographie. La restriction qu'aucune des deux chaînes de bits de longueur n de la carte à la même chaîne plus courte, est ce qui rend ce sans perte - si deux de la longueur n des chaînes de bits ont été à la carte à la même plus courte bitstring, puis, quand il est venu le temps de décompresser de la chaîne, il n'y aurait pas un moyen de savoir qui des deux premières chaînes de bits nous avait comprimé.

C'est là que nous arrivons à un problème. Puisqu'il y a 2ⁿ différentes chaînes de bits de longueur n et 2ⁿ-1 courtes chaînes de bits, il n'est pas possible, nous pouvons jumeler chaque bitstring de longueur n avec certains plus courte bitstring sans affectation d'au moins deux de la longueur n des chaînes de bits de la même chaîne plus courte. Cela signifie que peu importe combien nous essayons, peu importe comment intelligent que nous sommes, et peu importe la façon créative, nous obtenons avec notre algorithme de compression, il est difficile de mathématiques limite qui dit qu'on ne peut pas toujours rendre le texte plus court.

Alors, comment fonctionne cette carte à votre problème? Eh bien, si nous obtenons une chaîne de texte de longueur au moins 10000 et besoin à la sortie d'un plus court programme qui imprime, alors nous devrions disposer d'une méthode de cartographie de chacun des 2¹⁰⁰⁰⁰ chaînes de longueur 10000 sur les 2¹⁰⁰⁰⁰ - 1 chaînes de caractères de longueur de moins de 10000. Que la cartographie a d'autres propriétés, à savoir que nous avons toujours à produire un programme valide, mais c'est hors de propos ici - il n'existe tout simplement pas assez de chaînes plus courtes pour faire le tour. En conséquence, le problème que vous souhaitez résoudre est impossible.

Cela dit, nous pourrions être en mesure d'obtenir un programme qui permet de compresser tous, mais l'une des chaînes de longueur 10000 à une courte chaîne. En fait, on peut trouver un algorithme de compression qui fait cela, ce qui signifie qu'avec la probabilité 1 - 2¹⁰⁰⁰⁰ toute chaîne de caractères de longueur 10000 pourrait être compressé. C'est une forte probabilité que, si nous avons gardé la cueillette des chaînes pour la durée de vie de l'univers, nous serions presque certainement jamais deviner Une Mauvaise Chaîne.

---

Pour plus de lecture, il y a un concept de la théorie de l'information appelé la complexité de Kolmogorov, qui est la longueur du plus petit programme nécessaire pour produire une chaîne donnée. Certaines chaînes sont facilement comprimé (par exemple, abababababababab), tandis que d'autres ne le sont pas (par exemple, sdkjhdbvljkhwqe0235089). Il existe des chaînes de caractères qui sont appelés incompressible chaînes, dont la chaîne ne peut pas être comprimé dans tout petit espace. Cela signifie que tout programme qui allait imprimer cette chaîne devrait être au moins aussi longue que la chaîne donnée. Pour une bonne introduction à la Complexité de Kolmogorov, vous souhaiterez peut-être consulter le Chapitre 6 de "l'Introduction à la Théorie de Calcul, Deuxième Édition" par Michael Sipser, qui offre un excellent aperçu de quelques-uns de la glacière résultats. Pour plus de rigueur et en profondeur, il est conseillé de lire les "Éléments de Théorie de l'Information", chapitre 14.

Espérons que cette aide!

Answer 2

Si nous parlons de texte ASCII...

Je pense que cela pourrait être fait, et je pense que la restriction que le texte sera inférieur à 10000 caractères est là pour une raison (pour vous donner le codage de la chambre).

Les gens d'ici disent que la chaîne ne peut pas être compressé, mais il peut.

Pourquoi?

Exigence: la SORTIE de L'ORIGINAL du TEXTE

Le texte n'est pas de données. Quand vous lisez de saisie de texte que vous lisez ASCII caractères (octets). Qui ont à la fois imprimable et non imprimable des valeurs à l'intérieur.

Prenez cet exemple:

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

Depuis que vous avez à imprimer le texte de la sortie, vous ne sont pas intéressés dans la gamme (0x00-0x08,0x0E-0x1F). Vous pouvez compresser les octets d'entrée en utilisant un autre stockage et la récupération de mécanisme (schémas binaires), puisque vous n'avez pas à récupérer les données d'origine, mais le texte original. Vous pouvez recalculer ce que l'stockées les valeurs de la moyenne et de réajuster leur octets à imprimer. Vous devez efficacement lâche seulement les données qui n'a pas de texte, de données, de toute façon, et n'est donc pas imprimable ou inputtable. Si WinZip ferait qu'il serait un grand pas, mais pour vos exigences énoncées simplement, il n'a pas d'importance.

Étant donné que l'exigence stipule que le texte est 10000 caractères et vous pouvez enregistrer 26 255, si votre emballage n'a pas perdu tout vous sont effectivement d'économiser près de 10% de l'espace, ce qui signifie que si vous pouvez le code de la "décompression" dans 1000 (10% de 10000 caractères, vous pouvez le faire. Vous aurez à traiter des groupes de 10 octets 11 caractères, et à partir de là extrapoler te 11, par quelque méthode d'extrapolation pour votre gamme de 229. Si cela peut être fait, alors le problème est résoluble.

Néanmoins, il nécessite intelligente de la pensée, et de compétences de codage qui peut réellement faire que dans 1 kilo-octet.

Bien sûr, c'est juste un modèle conceptuel de réponse, pas une fonctionnelle. Je ne sais pas si je pourrais jamais y parvenir.

Mais j'ai eu l'envie de donner mes 2 cents sur ce, puisque tout le monde a estimé qu'il ne peut pas être fait, en étant sûr à ce sujet.

Le vrai problème dans votre problème est de comprendre le problème et les exigences.

Answer 3

Ce que vous décrivez est essentiellement un programme pour la création d'auto-extraction des archives zip, avec la petite différence que l'un des auto-extraire l'archive zip serait d'écrire les données d'origine dans un fichier plutôt que sur la sortie standard stdout. Si vous voulez faire un tel programme vous-même, il existe de nombreuses implémentations d'algorithmes de compression, ou vous pourriez mettre en œuvre par exemple DÉGONFLER (l'algorithme utilisé par gzip) de vous-même. L ' "extérieur" programme doit compresser les données d'entrée et de sortie, le code de la décompression, et d'intégrer les données compressées dans le code.

Pseudo-code:

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;

Answer 4

1. En supposant que le "caractère" signifie "byte" et en supposant que la saisie de texte peut contenir au moins autant de caractères valides comme langage de programmation, il est impossible de faire cela pour toutes les entrées, depuis que templatetypedef expliqué, pour toute longueur de texte de saisie de tous les "strictement plus petit" des programmes sont eux-mêmes les entrées possibles avec la plus petite longueur, ce qui signifie qu'il y a plus d'entrées possibles qu'il peut jamais être sorties. (Il est possible d'organiser la sortie au plus un peu plus longue que celle de l'entrée en utilisant un schéma de codage qui commence avec un "si c'est 1, ce qui suit est juste la forme non codée d'entrée parce qu'il ne pouvait pas être comprimées" bits)

2. En supposant que ses suffisante pour avoir ce travail pour la plupart des intrants (par exemple. les entrées qui se composent principalement de caractères ASCII et pas sur toute la plage de valeurs d'octets), alors la réponse facilement existe: utiliser gzip. C'est ce que ses bon. Rien ne va être beaucoup mieux. Vous pouvez créer des archives auto-extractibles, ou de traiter les gzip format comme la "langue" de sortie. Dans certains cas, il peut être plus efficace en ayant un langage de programmation complet ou exécutable que votre sortie, mais souvent, la réduction de la surcharge en ayant un format conçu pour résoudre ce problème, c'est à dire. gzip, sera plus efficace.

Answer 5

C'est ce qu'on appelle un archiveur de fichiers produisant des archives auto-extractibles.