Qui veut gagner la complexité de Kolmogorov?

22

Votre mission aujourd'hui est d'inventer un compresseur de texte.

Tâche

Vous écrirez deux fonctions:

  • Le packer est une fonction qui accepte une chaîne de caractères ASCII (U + 0000 à U + 007F) et génère une chaîne Unicode (U + 0000 à U + 10FFFF), contenant le moins de caractères possible.

  • Le décompresseur est une fonction qui accepte une chaîne Unicode codée et génère exactement la chaîne ASCII d'origine.

Contribution

La seule entrée autorisée est la chaîne ASCII (pour le conditionneur) et la chaîne Unicode compressée (pour le décompresseur). Aucune entrée utilisateur, aucune connexion Internet, aucune utilisation du système de fichiers.

Vos fonctions peuvent avoir accès à cette liste de mots anglais . Vous pouvez utiliser cette liste en tant que fichier txt local ou copier son contenu dans votre code source sous la forme d'une chaîne ou d' un tableau de chaînes .

Vous ne pouvez pas coder en dur les extraits ci-dessous dans vos fonctions.

Sortie

La seule sortie autorisée pour les deux fonctions est une chaîne.

La sortie du décompresseur doit contenir exactement les mêmes caractères que l'entrée du packer.

Vos entrées et sorties peuvent utiliser n'importe quel encodage de caractères prenant en charge tous les Unicode (UTF-8/16/32, GB18030, ...), car votre score ne dépendra que du nombre de caractères Unicode dans la sortie. Veuillez préciser l'encodage que vous utilisez, cependant.

Pour compter le nombre de caractères Unicode dans votre sortie, vous pouvez utiliser cet outil: http://mothereff.in/byte-counter

Notation

Votre entrée doit pouvoir emballer et décompresser les 10 extraits de texte suivants (que j'ai pris sur ce forum).

Votre score sera la somme des tailles de vos 10 chaînes compressées (en caractères Unicode) + la taille de vos deux fonctions (en caractères Unicode aussi)

Ne comptez pas la taille du dictionnaire si vous l'utilisez.

Veuillez inclure dans vos entrées le "score" de chaque extrait et leur version compactée.

Le score le plus bas l'emporte.

Les données

Voici les extraits à encoder pour calculer votre score:

1: paroles de Rick Roll (1870b): Nous ne sommes pas étrangers au code du golf, vous connaissez les règles, et moi aussi

Nous ne sommes pas des étrangers à aimer
Vous connaissez les règles et moi aussi
Un engagement total à quoi je pense
Vous n'obtiendrez cela d'aucun autre gars
Je veux juste te dire comment je me sens
Je dois te faire comprendre

Je ne t'abandonnerai jamais
Je ne te laisserai jamais tomber
Je ne vais jamais courir et te déserter
Je ne te ferai jamais pleurer
Je ne te dirai jamais au revoir
Je ne vais jamais mentir et te blesser

Nous nous connaissons depuis si longtemps
Votre cœur a mal mais
Tu es trop timide pour le dire
À l'intérieur, nous savons tous les deux ce qui se passe
Nous connaissons le jeu et nous allons y jouer
Et si tu me demandes comment je me sens
Ne me dis pas que tu es trop aveugle pour voir

Je ne t'abandonnerai jamais
Je ne te laisserai jamais tomber
Je ne vais jamais courir et te déserter
Je ne te ferai jamais pleurer
Je ne te dirai jamais au revoir
Je ne vais jamais mentir et te blesser

Je ne t'abandonnerai jamais
Je ne te laisserai jamais tomber
Je ne vais jamais courir et te déserter
Je ne te ferai jamais pleurer
Je ne te dirai jamais au revoir
Je ne vais jamais mentir et te blesser

(Ooh, abandonne-toi)
(Ooh, abandonne-toi)
(Ooh)
Je ne donnerai jamais, je ne donnerai jamais
(T'abandonner)
(Ooh)
Je ne donnerai jamais, je ne donnerai jamais
(T'abandonner)

Nous nous connaissons depuis si longtemps
Votre cœur a mal mais
Tu es trop timide pour le dire
À l'intérieur, nous savons tous les deux ce qui se passe
Nous connaissons le jeu et nous allons y jouer

Je veux juste te dire comment je me sens
Je dois te faire comprendre

Je ne t'abandonnerai jamais
Je ne te laisserai jamais tomber
Je ne vais jamais courir et te déserter
Je ne te ferai jamais pleurer
Je ne te dirai jamais au revoir
Je ne vais jamais mentir et te blesser

Je ne t'abandonnerai jamais
Je ne te laisserai jamais tomber
Je ne vais jamais courir et te déserter
Je ne te ferai jamais pleurer
Je ne te dirai jamais au revoir
Je ne vais jamais mentir et te blesser

Je ne t'abandonnerai jamais
Je ne te laisserai jamais tomber
Je ne vais jamais courir et te déserter
Je ne te ferai jamais pleurer
Je ne te dirai jamais au revoir
Je ne vais jamais mentir et te blesser

2: Le golfeur (412b): Golf ASCII-art

      '\. . |> 18 >>
        \. '. |
       O >>. «o |
        \. |
        / \. |
       / /. » |
 jgs ^^^^^^^ `^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^

3: le diamant numéro (233b): Imprimez ce diamant

        1
       121
      12321
     1234321
    123454321
   12345654321
  1234567654321
 123456787654321
12345678987654321
 123456787654321
  1234567654321
   12345654321
    123454321
     1234321
      12321
       121
        1

4: l'alphabet quatre fois (107b): imprimer l'alphabet quatre fois

abcdefghijklmnopqrstuvwxyz
qwertyuiopasdfghjklzxcvbnm
pyfgcrlaoeuidhtnsqjkxbmwvz
zyxwvutsrqponmlkjihgfedcba

5: Paroles d'Old McDonald's (203b): Fonction Old MacDonald

Old MacDonald avait une ferme, EIEIO,
Et sur cette ferme, il avait une vache, EIEIO,
Avec un moo moo ici et un moo moo là,
Ici un moo, là un moo, partout un moo moo,
Le vieux MacDonald avait une ferme, EIEIO!

6: Paroles de chanson Rock around the clock (144b): Rock Around the Clock

1, 2, 3 heures, 4 heures rock,
5, 6, 7 heures, 8 heures rock,
9, 10, 11 heures, 12 heures rock,
On va basculer 24 heures sur 24 ce soir.

7: Hello World (296b): Dites "Bonjour" au monde dans l'art ASCII

 _ _ _ _ _ _ _
| | | | ___ | | | ___ __ _____ _ __ | | __ | | |
| | _ | | / _ \ | | / _ \ \ \ / \ / / _ \ | «__ | | / _` | |
| _ | __ / | | (_) | \ VV / (_) | | | | (_ | | _ |
| _ | | _ | \ ___ | _ | _ | \ ___ () \ _ / \ _ / \ ___ / | _ | | _ | \ __, _ (_)
                    | /

8: bénédiction irlandaise (210b): une vieille bénédiction irlandaise

Que la route monte pour te rencontrer
Que le vent soit toujours dans ton dos
Que le soleil brille chaud sur votre visage
Les pluies tombent doucement sur vos champs
Et jusqu'à ce que nous nous revoyions
Que Dieu vous tienne au creux de sa main

9: Il y avait une vieille dame (1208b): Il y avait une vieille dame

Il y avait une vieille dame qui a avalé une mouche.  
Je ne sais pas pourquoi elle a avalé cette mouche,  
Peut-être qu'elle mourra.

Il y avait une vieille dame qui a avalé une araignée,  
Cela se tortillait, se tortillait et se tortillait en elle.  
Elle a avalé l'araignée pour attraper la mouche,  
Je ne sais pas pourquoi elle a avalé cette mouche,  
Peut-être qu'elle mourra.

Il y avait une vieille dame qui a avalé un oiseau,  
Quelle absurdité d'avaler un oiseau.  
Elle a avalé l'oiseau pour attraper l'araignée,  
Elle a avalé l'araignée pour attraper la mouche,  
Je ne sais pas pourquoi elle a avalé cette mouche,  
Peut-être qu'elle mourra.

Il y avait une vieille dame qui a avalé un chat,  
Imaginez cela pour avaler un chat.  
Elle a avalé le chat pour attraper l'oiseau,  
Elle a avalé l'oiseau pour attraper l'araignée,  
Elle a avalé l'araignée pour attraper la mouche,  
Je ne sais pas pourquoi elle a avalé cette mouche,  
Peut-être qu'elle mourra.

Il y avait une vieille dame qui a avalé un chien,  
Quel porc pour avaler un chien.  
Elle a avalé le chien pour attraper le chat,  
Elle a avalé le chat pour attraper l'oiseau,  
Elle a avalé l'oiseau pour attraper l'araignée,  
Elle a avalé l'araignée pour attraper la mouche,  
Je ne sais pas pourquoi elle a avalé cette mouche,  
Peut-être qu'elle mourra.

Il y avait une vieille dame qui a avalé un cheval,  
Elle est morte bien sûr.

10: adresse de Gettysburg (1452b): quelle est l'adresse aléatoire de Gettysburg

Il y a quatre ans et sept ans, nos pères ont fait naître sur ce continent une nouvelle nation, conçue dans la liberté et dédiée à la proposition que tous les hommes sont créés égaux. Nous sommes maintenant engagés dans une grande guerre civile, testant si cette nation, ou toute nation ainsi conçue et si dévouée, peut durer longtemps. Nous sommes rencontrés sur un grand champ de bataille de cette guerre. Nous en sommes venus à consacrer une partie de ce domaine, comme lieu de repos final pour ceux qui ici ont donné leur vie pour que cette nation puisse vivre. Il est tout à fait approprié et approprié que nous le fassions. Mais, dans un sens plus large, nous ne pouvons pas dédier, nous ne pouvons pas consacrer, nous ne pouvons pas sanctifier ce terrain. Les braves, vivants et morts, qui ont lutté ici, l'ont consacré, bien au-dessus de notre pauvre pouvoir d'ajouter ou de nuire. Le monde ne remarquera pas, ni ne se souviendra longtemps de ce que nous disons ici, mais il ne peut jamais oublier ce qu'ils ont fait ici. Il nous appartient plutôt aux vivants de se consacrer ici à l'œuvre inachevée qu'ils ont jusqu'ici si noblement avancé. C'est plutôt pour nous d'être ici dédiés à la grande tâche qui nous attend - que de ces morts honorés nous consacrons une plus grande dévotion à cette cause pour laquelle ils ont donné la dernière pleine mesure de dévotion - que nous résolvons ici fortement que ces morts ne sont morts en vain - que cette nation, sous Dieu, aura une nouvelle naissance de liberté - et que le gouvernement du peuple, par le peuple, pour le peuple, ne périsse pas de la terre.

Total (non compressé): 6135 caractères / octets.

S'amuser!

xem
la source
7
Ce n'est pas un défi d'inventer un langage, c'est un défi de compresser quelque chose.
Justin
2
Je pense que ne pas inclure la taille du compilateur / exécuteur (compresseur / décompresseur) dans la partition rend ce défi un peu ouvert. À un certain point, la ligne entre le dictionnaire et le codage en dur deviendra très mince.
Dennis
2
Bon sang, et là je tapais déjà private static final String RICK_ROLL_RETURN = "We're no strangers to love...
Graph Theory
1
Je ne pense pas que vous ayez répondu à l'observation de Dennis.
Peter Taylor
1
@xem Je pense que le message pourrait être amélioré en organisant les informations en sections telles que #Task, #Input, #Output, #Scoring. Je pense également que la taille du code source du compresseur et du décompresseur devrait être incluse dans la partition. Cela ne fait rien de mal, mais cela résout le problème signalé par Dennis.
Rainbolt

Réponses:

6

Haskell - 5322 points

Octets de code: 686

Format original : 6147 = 1871+415+234+108+204+145+297+211+1209+1453

Taille codée: 4636 = 1396+233+163+92+153+115+197+164+979+1144

But : 686+ 4636

Compression du nombre de caractères: ~25%

Code

Mis à part les optimisations, cela stocke les valeurs entre 0et7f en caractères unicode comme facteurs premiers.

Il ne réduit pas le nombre d'octets de la sortie codée, il ne fait que diminuer le nombre de caractères unicode. Par exemple, le test n ° 4 contient des 108caractères et la sortie encodée, 92. Leurs tailles respectives sont cependant 108et en 364octets.

import Data.Bits
import Data.List
import Data.Numbers.Primes
import qualified Data.Text as T
a=nub$concat$map(primeFactors)[0..127]
d(a:r)c=let s=shift c 5in if s<=0x10ffffthen d r(s+a)else c:d r a
d[]c=[c]
f(a:r)=let o=a.&.0x1fin(if o/=a then f((shiftR a 5):r)else f r)++[o]
f[]=[]
g=T.pack.map(toEnum).(\(a:r)->d r a).concatMap j.map(map(\x->head$elemIndices x a)).map(primeFactors.fromEnum).T.unpack
h=T.pack.map(toEnum.product.map((!!)a)).i.f.reverse.map(fromEnum).T.unpack
i(a:r)=let z=a`clearBit`4;x=if a`testBit`4then(take z$repeat$head r,tail r)else splitAt z r in[fst x]++i(snd x)
i[]=[]
j x@(a:_)=let l=length x in if(take l(repeat a))==x then[l`setBit`4,a]else[l]++x
j[]=[0]

Comment ça marche

  • Codage

    1. Chaque caractère est converti en son équivalent numérique, appelons ce numéro n.
    2. n est ensuite converti en une liste de ses facteurs premiers, ps .
      • Il arrive que les nombres de 0 à 127 aient 32 facteurs premiers communs, à l'exclusion 1. Cela signifie qu'ils, les facteurs, peuvent être stockés sous forme d'index sur aussi peu que 5 bits.
      • 1 est un cas particulier et est représenté par une liste vide.
    3. Avec psl'encodage peut maintenant commencer.
      1. Chaque nombre de psest converti en son index dans la liste de 32 facteurs uniques (dans le code ci-dessus, cette liste est identifiée comme a).
      2. (Gardez à l'esprit qu'à ce stade, nous avons affaire à une liste de listes d'indices de facteurs premiers) Pour passer à l'étape suivante, il psfaut l'aplatir. Pour préserver l'intégrité des données, chaque liste est convertie en une autre liste de deux parties
        1. Le premier élément stocke sa longueur et s'il est composé du même facteur.
          • Il y a au plus 6 facteurs premiers par liste, ces informations sont stockées sur les 3 bits les plus à droite. Le cinquième bit est utilisé comme indicateur pour indiquer si la liste est composée d'un seul facteur.
        2. Les éléments restants sont les index eux-mêmes ou un index unique s'il y a moins de deux facteurs différents dans la liste.
      3. Ces listes sont ensuite enchaînées en une seule liste aplaties, fs.
    4. Les éléments de fspeuvent ensuite être regroupés en caractères unicode en utilisant le décalage de bits.
  • Décodage

    • Effectuez les étapes d'encodage à l'envers.
    • Si vous vous demandez comment cela 1s’inscrit, je voudrais vous le rappeler product [] == 1.

Les tests

L'utilisation de cette interface pour les tests serait pénible, j'ai donc utilisé cette fonction pour fournir les résultats ci-dessous.

edTest f = do
    t <- readFile f
    let txt = T.pack t
        enc = g txt
        dec = h enc
        tst = txt == dec
    putStrLn $ (show $ T.length txt) ++ "," ++ (show $ T.length enc) ++ "," ++ (show $ T.length dec)++","++(show tst)
    putStrLn $ if not tst then T.unpack txt ++ "\n---NEXT---\n" ++ T.unpack dec else ""


λ> edTest "1"
1871,1396,1871,True

λ> edTest "2"
412,233,412,True

λ> edTest "3"
234,163,234,True

λ> edTest "4"
108,92,108,True

λ> edTest "5"
204,153,204,True

λ> edTest "6"
145,115,145,True

λ> edTest "7"
297,197,297,True

λ> edTest "8"
211,164,211,True

λ> edTest "9"
1209,979,1209,True

λ> edTest "10"
1453,1144,1453,True

Échantillon

La sortie de la fonction d'encodage gpour le test # 4 est ceci
"\99429\582753\135266\70785\35953\855074\247652\1082563\68738\49724\164898\68157\99429\67973\1082404\587873\73795\298017\330818\198705\69861\1082435\595009\607426\36414\69873\855074\265249\346275\67779\68738\77985\1082513\821353\132131\101410\247652\1082562\49724\164898\67649\594977\34915\67746\50273\135265\103997\563265\103457\1086021\99399\584802\70753\73889\34882\582722\411459\67779\68740\1084516\1082563\1091681\103491\313282\49724\164897\68705\135741\69858\50241\607426\35905\608421\1082435\69858\50274\71777\43075\298018\280517\1082404\67971\36017\955425\67665\919600\100452\132129\214883\35057\856097\101474\70753\135737"
ou si vous êtes un adepte du charabia, ceci
𘑥򎑡𡁢𑒁豱󐰢𼝤􈓃𐲂숼𨐢𐨽𘑥𐦅􈐤򏡡𒁃񈰡񐱂𰠱𑃥􈑃򑑁򔓂踾𑃱󐰢񀰡񔢣𐣃𐲂𓂡􈒑󈡩𠐣𘰢𼝤􈓂숼𨐢𐡁򑐡衣𐢢쑡𡁡𙘽򉡁𙐡􉉅𘑇򎱢𑑡𒂡衂򎑂񤝃𐣃𐲄􈱤􈓃􊡡𙑃񌟂숼𨐡𐱡𡈽𑃢쑁򔓂豁򔢥􈑃𑃢쑢𑡡ꡃ񈰢񄟅􈐤𐦃貱󩐡𐡑󠠰𘡤𠐡𴝣裱󑀡𘱢𑑡𡈹

Notes supplémentaires

  • En utilisant http://mothereff.in/byte-counter , les listes de répertoires etedTest la taille des tests sont tous cohérents mais diffèrent toujours de la taille indiquée dans la question.
  • Le test n ° 10 contient quelques DASH EM ( ) que j'ai remplacés -car ils sont en dehors de la plage 0- 7f.
  • Une compression supplémentaire pourrait être obtenue en utilisant le quatrième bit restant pendant l'aplatissement, par exemple, 00le cas de base, 01tout 10répéter , répéter sauf le dernier, 11répéter sauf les deux derniers.
  • Les fichiers de test et le code sont tous disponibles ici https://github.com/gxtaillon/codegolf/tree/master/Kolmogorov
gxtaillon
la source
Bonjour, merci pour cette réponse! :) Je ne comprenais pas ce qui se passe en binaire lorsque vous convertissez abcdefghijklm...à 𘑥򎑡𡁢𑒁豱󐰢𼝤..., pourriez - vous expliquer un peu plus s'il vous plaît? De plus, j'ai corrigé le nombre de caractères et converti les em-tirets dans # 10, dans la question. Cependant, mon nombre d'ombles est toujours différent du vôtre. Je ne sais pas pourquoi, j'ai utilisé l'outil mothereff.in.
xem
@xem Les détails complexes ont été révélés.
gxtaillon
Mon esprit est (au figuré) littéralement soufflé par l'idée que les nombres 0 et 2-127 peuvent être encodés sur 5 bits. Avez-vous trouvé cela par vous-même ou était-ce quelque chose de connu? Question bonus: de combien de bits avez-vous besoin pour stocker uniquement les caractères ascii imprimables, soit 95 caractères différents?
xem
@xem Les nombres ne sont pas codés sur 5 bits, chacun de leurs facteurs le sont. Je serais très heureux si j'avais trouvé un moyen d'encoder 7 bits sur seulement 5. Quant aux caractères ascii, en utilisant cette méthode, ils auraient encore besoin de 5 bits chacun.
gxtaillon
1
Étant donné que dans la plage que vous avez spécifiée, il y a au plus 6 facteurs par nombre, la longueur utilise 3 "blocs" sur 5 bits. Ensuite, les index sont codés sur 5 bits, oui. Dans cette implémentation, l'un des 2 bits inutilisés du bloc de longueur est utilisé pour obtenir une compression supplémentaire.
gxtaillon
4

C ++ (C ++ 11), 2741 points

Cette réponse utilise UTF-32 comme codage pour le texte compressé.

#include <cstdio>
#include <iostream>
#include <locale>
#include <string>
#define L locale
using namespace std;long b,n,i,l;void c(){string d;char x;while((x=cin.get())!=EOF)d+=x;b=(d.size()*7)%20;n=5;wcout.imbue(L());for(char y:d){b=b<<7|y&127;n+=7;if(n>=20)wcout.put(b>>(n-=20)&0xFFFFF);}if(n)wcout.put(b<<20-n&0xFFFFF);}void d(){wstring d;wchar_t w;wcin.imbue(L());while((w=wcin.get())!=EOF)d+=w;l=-1;for(wchar_t y:d){b=b<<20|y;n+=20;if(l<0)l=b>>15&31,n-=5;while(n>=7&(i<d.size()-1|n>20-l))cout.put(b>>(n-=7)&127);++i;}}int main(int t,char**a){L::global(L("en_US.utf8"));**++a<'d'?c():d();}

Le nombre de caractères et le score

Code: 593 caractères (la nouvelle ligne de fin est supprimée)

Textes compressés (caractères Unicode) : 654 + 145 + 82 + 38 + 51 + 104 + 73 + 423 + 506 = 2148 (compté avec wc -mpour le nombre de caractères Unicode plutôt que d'octets, le nombre d'octets est, comme avec la réponse de @ gxtaillon , supérieur aux originaux, 8413 octets au total, comme compté avec wc -c).

Taux de compression (ASCII à unicode) : 35,01% (en utilisant les 6 135 octets de la question (les mêmes que wc -c))

Il faut se méfier:

De nombreux shells ne peuvent pas gérer les caractères unicode produits par ce programme. Ainsi, la décompression peut entraîner la coupure du texte quelque part lorsque le shell ne peut pas gérer un caractère, car la saisie est effectuée via stdinle shell.

Compilation

Il devrait compiler avec clang++et g++ -std=c++11, mais il affichera quelques avertissements sur la priorité des opérateurs, car une expression comme b<<20-n&0xFFFFFne sera pas traitée comme ((b << 20) - n) & 0xFFFFF, comme on pourrait s'y attendre, mais plutôt comme (b << (20 - n)) & 0xFFFFF.

Usage

  • Compilez le programme dans un exécutable, par exemple ./compress.
  • Exécutez le programme ./compress cpour compresser ou ./compress ddécompresser. (Attention, laisser de côté l'option donne un SEGFAULT (la vérification des erreurs coûte tellement cher ...) et d'autres options (comme utiliser à la Dplace de d) peuvent donner des résultats inattendus
  • L'entrée est lue stdinet la sortie est écrite dansstdout

Comment ça marche

Non golfé

#include <cstdio>
#include <iostream>
#include <locale>
#include <string>

using namespace std;

long b, n, i, l;

// Compress
void c() {
    string d;
    char x;
    // Read from STDIN until EOF
    while((x = cin.get()) != EOF)
        d += x;
    // Calculate the number of bits used from the last unicode character
    // (maximum 19) and store it into the first 5 bits
    b = (d.size() * 7) % 20;
    n = 5;
    // Set the output locale to allow unicode
    wcout.imbue(locale());
    // For each character in the input...
    for (char y : d) {
        // Add its bit representation (7 bits) to the right of the buffer
        // by shifting the buffer left and ORing with the character code
        b = (b << 7) | (y & 127);
        // Add 7 to the bit counter
        n += 7;
        // If enough data is present (20 bits per output character),
        // calculate the output character by shifting the buffer right,
        // so that the last 20 bits are the left 20 bits of the buffer.
        // Also decrement the bit counter by 20, as 20 bits are removed.
        if (n >= 20)
            wcout.put((b >> (n -= 20)) & 0xFFFFF);
    }
    // If there are still bits in the buffer, write them to the front of
    // another unicode character
    if (n)
        wcout.put((b << (20 - n)) & 0xFFFFF);
}

// Decompress
void d() {
    wstring d;
    wchar_t w;
    // Set STDIN to UNICODE
    wcin.imbue(locale());
    // Read wide characters from STDIN (std::wcin) until EOF
    while ((w = wcin.get()) != EOF)
        d += w;
    // `l' represents the number of bits used in the last unicode character.
    // It will be set later
    l = -1;
    // For each input character...
    for (wchar_t y : d) {
        // Add it to the buffer and add 20 to the bit counter
        b = (b << 20) | y;
        n += 20;
        // If the number of bits in the last unicode character has not been
        // set yet, read the first 5 buffer bits into `l'. This is
        // necessary because the last character may contain more than 7
        // (one entire uncompressed character) unused bits which may
        // otherwise be interpreted as garbage.
        if (l < 0) {
            l = (b >> 15) & 31;
            n -= 5;
        }
        // As long as there is data to turn into output characters
        // (at least 7 bits in the buffer and either not the last
        // unicode character or before the unused bits)
        while (n >= 7 && ((i < d.size() - 1) || (n > (20 - l)))
            cout.put((b >> (n -= 7)) & 127); // Output the left 7 bits in the buffer as an ASCII character
        ++i; // Increment the character index, so that we know when we reach the last input character
    }
}
int main(int t, char**a) {
    // Set the default locale to en_US.utf8 (with unicode)
    locale::global(locale("en_US.utf8"));
    // Decide whether to compress or decompress.
    // This is just fancy pointer stuff for a[1][0] < 'd' ? c() : d()
    (**(++a) < 'd') ? c() : d();
}

Explication

Comme tous les caractères unicode de U+0000à U+10FFFFsont autorisés, nous pouvons utiliser 20 bits par caractère unicode:U+FFFFF utilise 20 bits et est toujours inclus dans la plage autorisée. Ainsi, nous essayons simplement de mettre tous les bits de caractère ASCII individuels dans les caractères unicode pour stocker plusieurs caractères ASCII dans un caractère unicode. Cependant, nous devons également stocker le nombre de bits utilisés dans le dernier caractère unicode, car les bits inutiles non utilisés peuvent être interprétés comme des caractères ASCII compressés appropriés. Comme le nombre maximum de bits utilisés dans le dernier caractère unicode est de 20, nous aurons besoin de 5 bits pour cela, qui sont placés au début des données compressées.

Exemple de sortie

Ceci est la sortie de l'exemple # 4 (tel que donné par less):

<U+4E1C5><U+8F265><U+CD9F4><U+69D5A><U+F66DD><U+DBF87><U+1E5CF><U+A75ED>
<U+DFC79><U+F42B8><U+F7CBC><U+BA79E><U+BA77F>쏏𦛏<U+A356B><U+D9EBC><U+63ED8>
<U+B76D1><U+5C3CE><U+6CF8F><U+96CC3><U+BF2F5><U+D3934><U+74DDC><U+F8EAD>
<U+7E316><U+DEFDB><U+D0AF5><U+E7C77><U+EDD7A><U+73E5C><U+786FD><U+DB766>
<U+BD5A7><U+467CD><U+97263><U+C5840>

( 쏏𦛏donnez des <U+C3CF><U+266CF>codes de caractères, mais je me suis peut-être trompé)

hlt
la source
2

Python 3, 289 + 818 = 1107 points

Seulement légèrement joué au golf.

import zlib as Z
def p(s):
 z=int.from_bytes(Z.compress(s),'big');o=''
 while z:
  z,d=divmod(z,1<<20)
  if d>0xd000:d+=1<<16
  o+=chr(d)
 return o[::-1]
def u(s):
 i=0
 for c in s:
  d=ord(c)
  if d>0xe000:d-=1<<16
  i=(i<<20)+d
 return Z.decompress(i.to_bytes(i.bit_length()//8+1,'big'))

La taille totale du code est de 289 octets et code les 6 135 octets donnés en 818 caractères Unicode - le nombre total d'octets de sortie est de 3 201 octets, nettement plus petit que les entrées d'origine.

Encode en utilisant zlib, puis secondairement en utilisant l'encodage unicode. Une logique supplémentaire était nécessaire pour éviter les substituts (que Python déteste vraiment).

Exemple de sortie de # 4, vu par less(37 caractères Unicode):

x<U+AC0DC><U+BB701><U+D0200><U+D00B0><U+AD2F4><U+EEFC5>𤆺<U+F4F34>멍<U+3C63A><U+2F62C><U+BA5B6><U+4E70A><U+F7D88><U+FF138><U+40CAE>
<U+CB43E><U+C30F5><U+6FFEF>𥠝<U+698BE><U+9D73A><U+95199><U+BD941><U+10B55E><U+88889><U+75A1F><U+4C4BB><U+5C67A><U+1089A3><U+C75A7>
<U+38AC1><U+4B6BB><U+592F0>ᚋ<U+F2C9B>

Programme pilote pour les tests:

if __name__ == '__main__':
    import os
    total = 0
    for i in range(1,10+1):
        out = p(open('data/%d.txt'%i,'rb').read())
        total += len(out)
        open('out/%d.bin'%i,'w',encoding='utf8').write(out)
    print(total)
    for i in range(1,10+1):
        out = u(open('out/%d.bin'%i,'r',encoding='utf8').read())
        open('data2/%d.txt'%i,'wb').write(out)

Nombre d'octets de sortie:

 607 out/1.bin
 128 out/2.bin
 101 out/3.bin
 143 out/4.bin
 177 out/5.bin
 145 out/6.bin
 186 out/7.bin
 222 out/8.bin
 389 out/9.bin
1103 out/10.bin
3201 total
nneonneo
la source
1
N'est-ce pas le fait d'utiliser une bibliothèque de compression qui triche un peu?
Beta Decay du
@BetaDecay: Cela ne limite pas cela dans la question, j'ai donc pensé que c'était un jeu équitable.
nneonneo
En outre, vous devez inclure un décompresseur.
Beta Decay
@BetaDecay: pest le packer, uest le déballeur.
nneonneo
1

Python 2 - 1141 points

from zlib import *;v=256
def e(b):
 x=0
 for c in compress(b,9):x=(x*v)+ord(c)
 b=bin(x)[2:]
 return "".join(unichr(int("1"+b[a:a+19],2))for a in range(0,len(b),19))
def d(s):
 y=int("".join(bin(ord(a))[3:]for a in s),2);x=""
 while y:y,d=(y/v,chr(y%v));x=d+x
 return decompress(x)

La taille du code est en 281octets et il code les 6135octets en860 caractères unicode.

Comment ça marche:

Pour encoder:

  1. Compressez la chaîne à encoder.
  2. Interprétez la chaîne compressée comme un nombre de base 256.
  3. Convertissez le nombre en binaire.
  4. Divisez le binaire en groupes de 19bits, ajoutez un 1peu au début de chacun d'eux, puis convertissez-les en caractères Unicode.

Le décodage est l'inverse.

Notez que certaines versions de python ne peuvent gérer que des caractères unicode jusqu'à 0xFFFF, et donc ce code soulèvera un ValueError.

pppery
la source