Implémenter l'encodage de longueur d'exécution de bzip2

14

Contexte

Après avoir appliqué le BWT (comme on le voit dans Burrows, Wheeler et Back ) et le MTF (comme on le voit dans Move to the imprimable ASCII front ), le compresseur bzip2 applique une forme plutôt unique d'encodage de longueur.

Définition

Aux fins de ce défi, nous définissons la transformation BRLE comme suit:

Étant donné une chaîne d'entrée s composée uniquement de caractères ASCII avec des points de code compris entre 0x20 et 0x7A, procédez comme suit:

  1. Remplacez chaque série de caractères égaux par une seule occurrence du caractère et stockez le nombre de répétitions après la première.

  2. Encode le nombre de répétitions après la première occurrence du caractère , en utilisant la numération bijective base-2 et les symboles {et }.

    Un entier non négatif n est codé comme la chaîne b k … b 0 telle que n = 2 k i (b k ) +… + 2 0 i (b 0 ) , où i ( {) = 1 et i ( }) = 2 .

    Notez que cette représentation est toujours unique. Par exemple, le nombre 0 est codé comme une chaîne vide.

  3. Insérez la chaîne entre accolades qui code le nombre de répétitions après l'occurrence unique du caractère correspondant.

Exemple pas à pas

Input:  "abbcccddddeeeeeffffffggggggghhhhhhhh"
Step 1: "abcdefgh" with repetitions 0, 1, 2, 3, 4, 5, 6, 7
Step 2: "" "{" "}" "{{" "{}" "}{" "}}" "{{{"
Step 3: "ab{c}d{{e{}f}{g}}h{{{"

Tâche

Implémentez un programme ou une fonction involutive qui lit une chaîne unique à partir de STDIN ou comme argument de ligne de commande ou de fonction et imprime ou renvoie soit le BRLE soit son inverse de la chaîne d'entrée.

Si l'entrée ne contient pas de crochets, appliquez le BRLE. Si l'entrée contient des accolades, appliquez son inverse.

Exemples

INPUT:  CODEGOLF
OUTPUT: CODEGOLF

INPUT:  PROGRAMMING
OUTPUT: PROGRAM{ING

INPUT:  PUZ{LES
OUTPUT: PUZZLES

INPUT:  444488888888GGGGGGGGGGGGGGGGWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
OUTPUT: 4{{8{{{G{{{{W{{{{{

INPUT:  y}}}{{
OUTPUT: yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy

Règles supplémentaires

  • Vous ne pouvez pas utiliser de fonctions intégrées qui calculent le BRLE ou son inverse d'une chaîne.

  • Vous pouvez utiliser des fonctions intégrées qui:

    • Calculez le RLE ou le RLD d'une chaîne, tant que le nombre de répétitions n'est pas stocké dans la base bijective-2.

    • Effectuez une conversion de base de tout type.

  • Votre code peut imprimer une nouvelle ligne de fin si vous choisissez STDOUT pour la sortie.

  • Votre code doit fonctionner pour toute entrée de 1000 caractères ASCII ou moins dans la plage de 0x20 à 0x7A, plus les accolades (0x7B et 0x7D).

  • Si l'entrée contient des accolades, vous pouvez supposer que c'est un résultat valide de l'application du BRLE à une chaîne.

  • Les règles de golf à code standard s'appliquent. La soumission la plus courte en octets l'emporte.

Dennis
la source
Pourquoi les buildins ne sont-ils pas autorisés?
MilkyWay90

Réponses:

4

CJam, 50 48 octets

l_{}`:T&1${_T#)_(@a?)+}%{(\2b)*}%@e`{(2b1>Tf=}%?

Merci pour Dennis d'avoir économisé 2 octets.

Essayez-le en ligne.

Explication

l_              e# Read and duplicate input.
{}`:T           e# T = "{}"
&               e# If the input has '{ or '}:
    1$          e# Input.
    {           e# For each character:
        _T#)    e# If it is '{ or '}:
            _(  e# Return 0 for '{ or 1 for '}.
            @a  e# Otherwise, convert the character itself to an array (string).
        ?
        )+      e# If it is a number, increment and append to the previous array.
                e# If it is a string with at least 1 character, do nothing.
    }%
    {(\         e# For each character and bijective base 2 number:
        2b)*    e# Repeat the character 1 + that many times.
    }%
                e# Else:
    @           e# Input.
    e`          e# Run-length encoding.
    {(          e# For each character and length:
        2b1>    e# Convert the length to base 2 and remove the first bit.
        Tf=     e# Map 0 to '{ and 1 to '}.
    }%
?               e# End if.
jimmy23013
la source
3

Pyth, 48 50 octets

J`Hs?m*hdi+1xLJtd2tczf-@zTJUz@Jzsm+ed@LJtjhd2rz8

2 octets grâce à @Maltysen.

Manifestation. Harnais de test.

Explication:

J`Hs?m*hdi+1xLJtd2tczf-@zTJUz@Jzsm+ed@LJtjhd2rz8
                                                    Implicit: z = input()
                                                    H is empty dict.
J`H                                                 J = repr(H) = "{}"
   s                                                Print the concatenation of
    ?                        @Jz                    If z and J share any chars:
                     f     Uz                       Filter range(len(z))
                      -@zTJ                         On the absence of z[T] in J.
                   cz                               Chop z at these indices.
                                                    just before each non '{}'.
                  t                                 Remove empty initial piece.
     m*hd                                           Map to d[0] *
         i       2                                  the base 2 number                             
            xLJtd                                   index in J mapped over d[:-1]
          +1                                        with a 1 prepended.
                                             rz8    Otherwise, run len. encode z
                                 m                  map over (len, char)
                                         jhd2       Convert len to binary.
                                        t           Remove leading 1  
                                     @LJ            Map to element of J.
                                  +ed               Prepend char.
                                s                   Concatenate. 
isaacg
la source
au lieu de "{}"vous pouvez utiliser `H, à égalité avec CJam :)
Maltysen
@Jakube Désolé pour la confusion.
isaacg
2

OCaml, 252

t est la fonction qui fait la transformation.

#load"str.cma"open Str
let rec(!)=group_beginning and
g=function|1->""|x->(g(x/2)^[|"{";"}"|].(x mod 2))and($)i s=if g i=s then i else(i+1)$s and
t s=global_substitute(regexp"\(.\)\1*\([{}]*\)")(fun s->String.make(1$matched_group 2 s)s.[!1]^g(!2- !1))s

Au début, je pensais que je devais vérifier la présence d'appareils orthopédiques, mais cela s'est avéré inutile. Le décodage n'a clairement aucun effet sur les chaînes qui sont déjà décodées, et la partie encodage s'est avérée tout aussi inoffensive pour celles qui étaient déjà encodées.

feersum
la source
the encoding part proved equally harmlessle fait-il? 4{{8{{{G{{{{W{{{{{Vous ne comprenez pas le codage 4{{8{}G{{{W{{}?
edc65
@ edc65 Non, j'obtiens la réponse spécifiée dans les exemples. Comment le testez-vous?
feersum
"4 {{8 {{{G {{{{W {{{{{{") en entrée ne fait pas partie des exemples. L'avez-vous essayé?
edc65
@ edc65 C'est l'inverse de l'un des exemples et je les ai testés dans les deux sens. Oui, je l'ai essayé, à la fois avant de poster et après votre commentaire.
feersum
OK bien. J'ai souligné la phrase citée, car un encodage "simple" (comme le mien) ne serait pas du tout inoffensif avec le cas de test donné. De toute évidence, votre partie d'encodage est plus intelligente.
edc65
1

JavaScript ( ES6 ), 162

f=s=>
(t=s[R='replace'](/[^{}][{}]+/g,n=>n[0].repeat('0b'+n[R](/./g,c=>c!='{'|0))))==s
?s[R](/(.)\1*/g,(r,c)=>c+r.length.toString(2).slice(1)[R](/./g,c=>'{}'[c])):t

// TEST
out=x=>O.innerHTML += x + '\n';

test=s=>O.innerHTML = s+' -> '+f(s) +'\n\n' + O.innerHTML;

[['CODEGOLF','CODEGOLF']
,['PROGRAMMING','PROGRAM{ING']
,['PUZ{LES','PUZZLES']
,['444488888888GGGGGGGGGGGGGGGGWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW','4{{8{{{G{{{{W{{{{{']
,['y}}}{{','yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy']]
.forEach(v=>{
  w=f(v[0])  
  out('Test ' + (w==v[1]?'OK':'Fail')+'\nInput:    '+v[0]+'\nExpected: '+v[1]+'\nResult:   '+w)
})  
Your test: <input id=I style='width:300px'><button onclick='test(I.value)'>-></button>
<pre id=O></pre>

Quelques explications

Numéro n à BB2 en utilisant 0 et 1:(n+1).toString(2).slice(1)

Chaîne dans BB2 en nombre: to_number ("0b1" + chaîne) - c'est-à-dire, ajoutez un chiffre binaire à l'extrême gauche et convertissez en binaire (et diminuez de 1, pas nécessaire dans cette instance spécifique).

Expression régulière pour rechercher n'importe quel caractère suivi de {ou }:/[^{}][{}]+/g

Expression régulière pour trouver des caractères répétés: /(.)\1*/g

En utilisant cette expression rationnelle dans replace, le premier paramètre est le caractère "répété" (éventuellement répéter une seule fois), le deuxième paramètre est la chaîne totale répétée, dont la longueur est le nombre que j'ai besoin d'encoder en BB2 déjà incrémenté de 1

... puis mettez tout ensemble ...

edc65
la source