Contexte

Sur ce site, nous avons occasionnellement des questions demandant que les programmes soient «durcis aux radiations»; cela signifie que le programme doit pouvoir survivre à la suppression d'un ou plusieurs octets, quels que soient les octets supprimés.

Comme cela est courant pour les tâches qui sont souvent définies dans des défis de programmation, il est naturel de vouloir créer un langage particulièrement bon pour ces défis. Étant donné que la façon naturelle de faire cela est d'ajouter des métadonnées qui permettent d'inverser la corruption, ce n'est pas vraiment un langage qui doit être conçu, mais un encodage; l'idée est de transformer chaque entrée en une séquence d'octets, de telle sorte que même si la séquence est légèrement irradiée, il est possible d'extraire l'entrée d'origine.

La tâche

Écrivez deux programmes ou fonctions, E (un encodeur) et D (un décodeur), tels que:

• E prend deux arguments, une séquence d'octets (que nous appellerons " entrée " dans cette spécification) et un entier non négatif " rayonnement ", et sort une séquence d'octets " codage ";
• D prend un argument, une séquence d'octets (" encdng "), et sort une séquence d'octets " reconstruction ";
• Si vous exécutez à la fois E et D (avec encdng , l'entrée de D, choisie en supprimant au plus les éléments de rayonnement de l' encodage (pas nécessairement de manière contiguë)), la reconstruction sera égale à l' entrée , quels que soient les caractères supprimés pour former l' encdng .

Clarifications

• Si vous soumettez des fonctions, vous n'avez pas à les appeler Eet D; vous pouvez choisir le nom qui convient le mieux à votre langue.
• Un "octet" est fondamentalement un entier de 0 à 255 inclus, que vous pouvez encoder comme un entier, un caractère ou tout ce qui est approprié pour votre langue.
• E et D doivent être entièrement déterministes (c'est-à-dire que leur donner les mêmes entrées produira toujours la même sortie, où "entrées" est défini comme entrée et rayonnement pour E, ou encdng pour D). En particulier, E peut ne pas communiquer d'informations à D via un canal latéral.
• Les suppressions sont effectuées en supprimant un élément de la séquence; pensez à ouvrir la seuqence dans un éditeur, à placer le curseur à un point arbitraire et à appuyer sur Retour arrière. Si un élément apparaît plusieurs fois, il est possible qu'une seule copie de l'élément soit supprimée (c'est-à-dire que les autres instances du même octet ne seront pas affectées).
• Bien que le score ne soit calculé que sur la base d'une entrée assez courte , votre programme doit fonctionner en théorie pour toute entrée et rayonnement . En particulier, il doit fonctionner quels que soient les octets qui apparaissent en entrée . (Désolé, les gens qui souhaiteraient pouvoir utiliser des caractères non imprimables qu'ils connaissent n'apparaîtront pas dans l'entrée, mais je dois m'assurer que l'entrée est incompressible afin que le défi concerne le durcissement par rayonnement plutôt que la compression.)
• Vous pouvez soumettre un fichier qui définit deux fonctions; deux fichiers qui définissent chacun une fonction ou qui sont tous deux des programmes complets; ou trois fichiers, dont deux implémentent D et E respectivement (via des programmes complets ou via la définition d'une fonction), et le troisième qui est un fichier d'en-tête ou une bibliothèque commune à D et E. Quelle que soit la forme de soumission que vous utilisez , votre implémentation de langage de programmation doit être capable de comprendre les deux programmes sans autres arguments comme l'emplacement des fichiers (ou bien vous devez payer une pénalité d'octet pour avoir invoqué votre implémentation de manière inhabituelle, conformément à nos règles standard).

Condition de victoire

Pour chaque longueur et rayonnement , soit f ( longueur , rayonnement ) les longueurs totales du codage s qui correspondent à toutes les entrées de longueur de longueur , et le rayonnement donné . (Autrement dit, f ( longueur , rayonnement ) = la somme _{entrée a une longueur longueur} longueur (E ( entrée , rayonnement )).) Soit alors g ( longueur , rayonnement ) égal à f ( longueur ,rayonnement ) ÷ 256 ^longueur . En d'autres termes, g est la longueur moyenne de la sortie codée, pour une longueur d'entrée donnée et une exigence de durcissement par rayonnement donnée. (En théorie, vous pourriez calculer cela par force brute, mais il faudrait probablement peu de temps pour calculer votre score de cette façon. Je m'attends à ce que la plupart des soumissions soient en mesure de faire un argument mathématique quant à leur score. Si vous '' ne savez pas, publiez un score approximatif et vous ou quelqu'un d'autre pouvez le calculer plus en profondeur si une autre entrée affiche un score similaire.)

Votre score est égal à la somme de g ( longueur , rayonnement ) pour tous les rayonnements compris entre 0 et 9 inclus, et toutes les longueurs comprises entre 0 et 99 inclus, plus (principalement pour éviter le codage en dur ou pour maintenir la concurrence si quelqu'un découvre un encodage mathématiquement parfait; cela sera probablement un facteur minimal sinon) le nombre total d'octets dans votre soumission au défi (plus les pénalités standard pour des choses comme nécessiter des indicateurs d'interprète inhabituels ou des noms de fichiers spécifiques). Le gagnant est l'entrée avec le score le plus bas (égalité par la première entrée à soumettre).

CJam, score ≤ 286 516 + 54 + 36 = 286 606

Encodeur

{_{1\+_:e>)_0a+@@b0\{{)_256b_,\e`,-}g}*256b+\)e*}{*}?}

Essayez-le en ligne!

Décodeur

{_{e`1f=(\256b{256b_,\e`,=},,\b1>}&}

Essayez-le en ligne!

Ces deux prennent et renvoient une liste d'entiers. Les liens TIO incluent la conversion de / vers des chaînes pour plus de commodité. Notez que ceux-ci sont incroyablement inefficaces pour les chaînes plus longues. Si vous voulez essayer quelques caractères supplémentaires, je vous recommande d'utiliser des caractères avec de petits codes de caractères.

L'idée de base pour créer un codage durci par rayonnement implique deux étapes:

1. Trouvez un codage qui ne contient jamais deux octets identiques consécutifs.
2. Répétez chaque octet de la chaîne codée r + 1 fois, où r est le niveau de rayonnement.

De cette façon, le rayonnement ne peut pas supprimer complètement une série de caractères identiques, de sorte que nous pouvons décoder la chaîne en prenant un caractère de chaque série, puis décodant l'étape 1.

Donc, la seule partie intéressante est de trouver un encodage qui ne donne jamais d'octets répétés. L'idée de base est d'utiliser quelque chose comme A043096 comme système numérique. Autrement dit, pour coder un entier N , nous comptons simplement dans une base b , en sautant tous les nombres avec des octets répétés. Je crois que la quantité de nombres qui peuvent être représentés de cette façon avec jusqu'à d chiffres est la même que la quantité de nombres qui peuvent être représentés dans la base bijective b-1 (puisque, lorsque vous voulez écrire un tel nombre, vous pouvez choisir entre b-1 chiffre pour chaque position sans violer la contrainte).

Bien sûr, pour obtenir une compression maximale, nous utiliserons b = 256 . Pour transformer l'entrée en un entier, nous pouvons également utiliser la conversion de base. Si je n'étais pas paresseux, j'utiliserais une base bijective pour l'entrée, mais pour l'instant je préfère un 1(pour m'assurer qu'il n'y a pas de zéros de tête) et ensuite utiliser la plus petite base possible telle que tous les octets du les entrées sont inférieures à la base.

Cette base est ensuite ajoutée au codage (pour que le décodeur sache quelle base utiliser) et séparée du nombre restant par un octet 0 (cela fonctionne car le nombre restant ne commencera jamais par un zéro). À titre d'optimisation mineure, la chaîne vide reste une chaîne vide.

La raison pour laquelle je n'ai pas calculé un score exact ci-dessus est que je ne calcule qu'une limite supérieure pour combien de temps chaque entrée sera basée sur sa longueur et son octet maximal. Cependant, pour ces deux paramètres, il y aura souvent deux longueurs de sortie différentes, et je n'ai pas encore pris la peine de déterminer où le point de basculement entre eux se produit. J'ai également utilisé la longueur de la base 255 habituelle au lieu de la base bijective 255 pour estimer cette longueur, qui est encore légèrement plus grande qu'elle ne devrait l'être. Le code Mathematica exact que j'ai utilisé pour le calcul est le suivant:

num[l_, 1] = 0;
num[l_, base_] := num[l, base] = base^l - Sum[num[l, b], {b, base - 1}]
Sum[
  num[l, b]*(r + 1)*(2 + IntegerLength[2*b^l - 1, 255])/256^l, 
  {r, 0, 9}, {l, 1, 99}, {b, 2, 256}
]
N@%

num[l, b]devrait donner le nombre de chaînes de longueur lavec un octet maximum b-1(sauf pour b == 1, où je l'ai codé en dur 0car j'utilise toujours au moins la base 2).

bash + GNU utilities, score 294506 283468

Edit 1: Résout un problème que @Leo a remarqué - merci!

Edit 2: Amélioration de la méthode d'encodage du paramètre de rayonnement, pour un meilleur score.

Encodeur (97 octets):

for((j=0;j<$1;j++)){ p+=p\;;}
(sed 's/\(.\)\1/\1a\1a/g'<<<$1;cat)|xxd -p -c1|sed ${p-;}|xxd -r -p

Décodeur (121 octets):

read n
n=`sed 's/\(.\)\1*/\1/g'<<<$n`
sed -r "s/( ..)\1{0,${n//a}}/\1/g"<<<' 0a '`xxd -p -c1`|sed 's/^ [^ ]*//'|xxd -r -p

Pour l'encodeur: séquence d'octets passée en caractères dans stdin, paramètre de rayonnement r passé en argument.

Pour le décodeur: entrée passée sous forme de caractères dans stdin.

Pour les deux: sortie sur sortie standard.

Le codeur ajoute aux données d'entrée les chiffres de r, avec un caractère «a» inséré entre chaque paire de chiffres identiques consécutifs, suivi d'une seule nouvelle ligne. Il copie ensuite toutes les entrées (en commençant par les caractères ajoutés), en remplaçant chaque caractère par r + 1 copies de ce caractère.

Le décodeur annule cela, en parcourant chacun des caractères restants x dans son entrée, en sautant jusqu'à r copies identiques consécutives de x en suivant x et en imprimant ce qui reste. Les données ajoutées n'ont pas de caractères répétés, elles peuvent donc être décodées avant que r ne soit connu. À ce stade, r est connu et cette valeur est nécessaire pour décoder correctement le reste des données.

Vous pouvez vérifier que cela fonctionne même si l'entrée d'origine a répété des caractères identiques.

Calcul du score:

Supposons que l'entrée ait une longueur L et que le paramètre de rayonnement soit r (qui est au plus 9 pour le calcul du score, donc il tient dans un chiffre et n'a donc pas de caractères répétés consécutifs). Les données ajoutées sont de 2 octets (chiffre, nouvelle ligne), donc la sortie est de (r + 1) (L + 2) octets pour le flux codé.

Donc g (L, r) = (r + 1) (L + 2).

Il s'ensuit que le score total peut être calculé comme

Perl + Math :: {ModInt, Polynomial, Prime :: Util}, score ≤ 92819

$m=Math::Polynomial;sub l{($n,$b,$d)=@_;$n||$d||return;$n%$b,l($n/$b,$b,$d&&$d-1)}sub g{$p=$m->interpolate([grep ref$_[$_],0..$map{$p->evaluate($_)}0..$}sub p{prev_prime(128**$s)}sub e{($_,$r)=@_;length||return'';$s=$r+1;s/^[␀␁]/␁$&/;@l=map{mod($_,p$s)}l(Math::BigInt->from_bytes($_),p$s);$@l+$r>p($s)&&return e($_,$s);$a=0;join'',map{map{chr$_+$a}l($_->residue,128,$s,($a^=128))}g(@l)}sub d{@l=split/([␀-␡]+)/,$_[0];@l||return'';$s=vecmax map length,@l;@l=g map{length==$s&&mod($m->new(map{ord()%128}split//)->evaluate(128),p$s)}@l;$$_=$m->new(map{$_->residue}@l)->evaluate(p$s)->to_bytes;s/^␁//;$_}

Les images de contrôle sont utilisées pour représenter le caractère de contrôle correspondant (par exemple, ␀est un caractère NUL littéral). Ne vous inquiétez pas beaucoup d'essayer de lire le code; il y a une version plus lisible ci-dessous.

Courez avec -Mbigint -MMath::ModInt=mod -MMath::Polynomial -MNtheory=:all. -MMath::Bigint=lib,GMPn'est pas nécessaire (et donc pas inclus dans la partition), mais si vous l'ajoutez avant les autres bibliothèques, le programme s'exécutera un peu plus rapidement.

Calcul du score

L'algorithme ici est quelque peu améliorable, mais serait plus difficile à écrire (car Perl ne possède pas les bibliothèques appropriées). Pour cette raison, j'ai fait quelques compromis taille / efficacité dans le code, en partant du principe que, étant donné que les octets peuvent être enregistrés dans l'encodage, il est inutile d'essayer de raser chaque point du golf.

Le programme se compose de 600 octets de code, plus 78 octets de pénalités pour les options de ligne de commande, ce qui donne une pénalité de 678 points. Le reste du score a été calculé en exécutant le programme sur la chaîne du meilleur et du pire des cas (en termes de longueur de sortie) pour chaque longueur de 0 à 99 et pour chaque niveau de rayonnement de 0 à 9; le cas moyen se situe quelque part entre les deux, ce qui donne des limites sur le score. (Cela ne vaut pas la peine d'essayer de calculer la valeur exacte, sauf si une autre entrée arrive avec un score similaire.)

Cela signifie donc que le score d'efficacité de codage est compris entre 91100 et 92141 inclus, donc le score final est:

91100 + 600 + 78 = 91778 ≤ score ≤ 92819 = 92141 + 600 + 78

Version moins golfée, avec commentaires et code de test

Il s'agit du programme d'origine + nouvelles lignes, indentation et commentaires. (En fait, la version golfée a été produite en supprimant les nouvelles lignes / indentations / commentaires de cette version.)

use 5.010;                    # -M5.010; free
use Math::BigInt lib=>'GMP';  # not necessary, but makes things much faster
use bigint;                   # -Mbigint
use Math::ModInt 'mod';       # -MMath::ModInt=mod
use Math::Polynomial;         # -MMath::Polynomial
use ntheory ':all';           # -Mntheory=:all
use warnings;                 # for testing; clearly not necessary

### Start of program

$m=Math::Polynomial;          # store the module in a variable for golfiness

sub l{ # express a number $n in base $b with at least $d digits, LSdigit first
    # Note: we can't use a builtin for this because the builtins I'm aware of
    # assume that $b fits into an integer, which is not necessarily the case.
    ($n,$b,$d)=@_;
    $n||$d||return;
    $n%$b,l($n/$b,$b,$d&&$d-1)
}

sub g{ # replaces garbled blocks in the input with their actual values
    # The basic idea here is to interpolate a polynomial through all the blocks,
    # of the lowest possible degree. Unknown blocks then get the value that the
    # polynomial evaluates to. (This is a special case of Reed-Solomon coding.)
    # Clearly, if we have at least as many ungarbled blocks as we did original
    # elements, we'll get the same polynomial, thus we can always reconstruct
    # the input.
    # Note (because it's confusing): @_ is the input, $_ is the current element
    # in a loop, but @_ is written as $_ when using the [ or # operator (e.g.
    # $_[0] is the first element of @_.
    # We waste a few bytes of source for efficiency, storing the polynomial
    # in a variable rather than recalculating it each time.
    $p=$m->interpolate([grep ref$_[$_],0..$#_],[grep ref,@_]);
    # Then we just evaluate the polynomial for each element of the input.
    map{$p->evaluate($_)}0..$#_
}

sub p{ # determines maximum value of a block, given (radiation+1)
    # We split the input up into blocks. Each block has a prime number of
    # possibilities, and is stored using the top 7 bits of (radiation+1)
    # consecutive bytes of the output. Work out the largest possible prime that
    # satisfies this property.
    prev_prime(128**$s)
}

sub e{ # encoder; arguments: input (bytestring), radiation (integer)
    ($_,$r)=@_; # Read the arguments into variables, $_ and $r respectively
    length||return''; # special case for empty string
    $s=$r+1; # Also store radiation+1; we use it a lot
    # Ensure that the input doesn't start with NUL, via prepending SOH to it if
    # it starts with NUL or SOH. This means that it can be converted to a number
    # and back, roundtripping correctly.
    s/^[␀␁]/␁$&/; #/# <- unconfuse Stack Exchange's syntax highlighting
    # Convert the input to a bignum, then to digits in base p$s, to split it
    # into blocks.
    @l=map{mod($_,p$s)}l(Math::BigInt->from_bytes($_),p$s);
    # Encoding can reuse code from decoding; we append $r "garbled blocks" to
    # the blocks representing the input, and run the decoder, to figure out what
    # values they should have.
    $#l+=$r;
    # Our degarbling algorithm can only handle at most p$s blocks in total. If
    # that isn't the case, try a higher $r (which will cause a huge increase in
    # $b and a reduction in @l).
    @l+$r>p($s)&&return e($_,$s);
    # Convert each block to a sequence of $s digits in base 128, adding 128 to
    # alternating blocks; this way, deleting up to $r (i.e. less than $s) bytes
    # will preserve the boundaries between each block; then convert that to a
    # string
    $a=0; # we must initialize $a to make this function deterministic
    join'',map{map{chr$_+$a}l($_->residue,128,$s,($a^=128))}g(@l)
}

sub d{ # decoder: arguments; encdng (bytestring)
    # Reconstruct the original blocks by looking at their top bits
    @l=split/([␀-␡]+)/,$_[0];
    @l||return''; # special case for empty string
    # The length of the longest block is the radiation parameter plus 1 (i.e.
    # $s). Use that to reconstruct the value of $s.
    $s=vecmax map length,@l;
    # Convert each block to a number, or to undef if it has the wrong length.
    # Then work out the values for the undefs.
    @l=g map{
        # Convert blocks with the wrong length to undef.
        length==$s&&
            # Convert other blocks to numbers, via removing any +128 and then
            # using Math::Polynomial to convert the digit list to a number.
            mod($m->new(map{ord()%128}split// #/# <- fix syntax highlighting
            )->evaluate(128),p$s)
    }@l;
    # Remove the redundant elements at the end; now that they've reconstructed
    # the garbled elements they have no further use.
    $#l-=$s-1;
    # Convert @l to a single number (reversing the conversion into blocks.)
    $_=$m->new(map{$_->residue}@l)->evaluate(p$s)
        # Convert that number into a string.
        ->to_bytes;
    # Delete a leading SOH.
    s/^␁//;  #/# <- unconfuse Stack Exchange's syntax highlighting
    # Finally, return the string.
    $_
}


### Testing code
use Encode qw/encode decode/;

# Express a string using control pictures + IBM437, to make binary strings
# easier for a human to parse
sub format_string {
    ($_)=@_;
    $_ = decode("Latin-1", $_);
    s/[\0-\x1f]/chr (0x2400 + ord $&)/eag;
    s/\x7f/chr 0x2421/eag;
    s/[ -~\x80-\xff]/decode("IBM437",$&)/eag;
    encode("UTF-8","\x{ff62}$_\x{ff63}")
}

sub test {
    my ($string, $radiation, $samples) = @_;
    say "Input: ", format_string($string);
    my $encoding = e($string, $radiation);
    say "Encoding: ", format_string($encoding);
    say "Input length ", length($string), ", encoding length ", length($encoding), ", radiation $radiation";
    my $decoding = d($encoding);
    $decoding eq $string or die "Mistake in output!";
    say "Decoding: ", format_string($decoding), " from ",
        format_string($encoding);

    # Pseudo-randomly generate $samples radiation-damaged versions.
    srand 1;
    for my $i (1..$samples) {
        my $encdng = $encoding;
        for my $r (1..$radiation) {
            substr $encdng, int(rand(length $encdng)), 1, "";
        }
        my $newdecoding = d($encdng);
        say "Decoding: ", format_string($newdecoding), " from ",
            format_string($encdng);
        $newdecoding eq $string or die "Mistake in output!";
    }

    say "";
    length $encoding;
}

test "abcdefghijklm", 1, 10;
test "abcdefghijklm", 2, 10;
test "abcdefghijklm", 5, 10;
test "abcdefghijklm", 10, 10;
test "\0\0\0\0\0", 1, 10;
test "\5\4\3\2\1", 2, 10;
test "a", 10, 10;

my %minlength = ();
my %maxlength = ();

for my $length (0..99) {
    my ($min, $max) = ("", "");
    $length and ($min, $max) =
        ("\2" . "\0" x ($length - 1), "\1" . "\377" x ($length - 1));
    for my $radiation (0..9) {
        $minlength{"$length-$radiation"} = test $min, $radiation, 1;
        $maxlength{"$length-$radiation"} = test $max, $radiation, 1;
    }
}

say "Minimum score: ", vecsum values %minlength;
say "Maximum score: ", vecsum values %maxlength;

Algorithme

Simplifier le problème

L'idée de base est de réduire ce problème de "codage de suppression" (qui n'est pas largement exploré) en un problème de codage d'effacement (un domaine mathématique exploré en détail). L'idée derrière le codage d'effacement est que vous préparez des données à envoyer sur un "canal d'effacement", un canal qui remplace parfois les caractères qu'il envoie par un caractère "garble" qui indique une position connue d'une erreur. (En d'autres termes, il est toujours clair où la corruption s'est produite, bien que le personnage d'origine soit encore inconnu.) L'idée derrière cela est assez simple: nous divisons l'entrée en blocs de longueur ( rayonnement+ 1), et utilisez sept des huit bits de chaque bloc pour les données, tandis que le bit restant (dans cette construction, le MSB) alterne entre être défini pour un bloc entier, effacé pour tout le bloc suivant, défini pour le bloc après cela, et ainsi de suite. Parce que les blocs sont plus longs que le paramètre de rayonnement, au moins un caractère de chaque bloc survit dans la sortie; donc en prenant des séries de caractères avec le même MSB, nous pouvons déterminer à quel bloc appartenait chaque personnage. Le nombre de blocs est également toujours supérieur au paramètre de rayonnement, nous avons donc toujours au moins un bloc intact dans l'encdng; nous savons donc que tous les blocs les plus longs ou attachés le plus longtemps ne sont pas endommagés, ce qui nous permet de traiter les blocs plus courts comme endommagés (donc un garble). Nous pouvons également déduire le paramètre de rayonnement comme celui-ci (il '

Codage d'effacement

Quant à la partie codage d'effacement du problème, elle utilise un cas spécial simple de la construction Reed-Solomon. Il s'agit d'une construction systématique: la sortie (de l'algorithme de codage d'effacement) est égale à l'entrée plus un certain nombre de blocs supplémentaires, égal au paramètre de rayonnement. Nous pouvons calculer les valeurs nécessaires pour ces blocs de manière simple (et golfique!), En les traitant comme des garbles, puis en exécutant l'algorithme de décodage sur eux pour "reconstruire" leur valeur.

L'idée réelle derrière la construction est également très simple: nous adaptons un polynôme, du degré minimum possible, à tous les blocs de l'encodage (avec des garbles interpolés des autres éléments); si le polynôme est f , le premier bloc est f (0), le second est f (1), et ainsi de suite. Il est clair que le degré du polynôme sera égal au nombre de blocs d'entrée moins 1 (parce que nous ajustons un polynôme à ceux-ci en premier, puis nous l'utilisons pour construire les blocs de «vérification» supplémentaires); et parce que d +1 points définissent uniquement un polynôme de degré d, brouiller n'importe quel nombre de blocs (jusqu'au paramètre de rayonnement) laissera un nombre de blocs non endommagé égal à l'entrée d'origine, ce qui est suffisamment d'informations pour reconstruire le même polynôme. (Il suffit alors d'évaluer le polynôme pour démêler un bloc.)

Conversion de base

La dernière considération laissée ici concerne les valeurs réelles prises par les blocs; si nous effectuons une interpolation polynomiale sur les nombres entiers, les résultats peuvent être des nombres rationnels (plutôt que des nombres entiers), beaucoup plus grands que les valeurs d'entrée, ou autrement indésirables. Ainsi, au lieu d'utiliser les entiers, nous utilisons un champ fini; dans ce programme, le champ fini utilisé est le champ des entiers modulo p , où p est le plus grand premier moins de 128 ^{radiations +1}(c'est-à-dire le plus grand nombre premier pour lequel nous pouvons adapter un nombre de valeurs distinctes égales à ce nombre premier dans la partie données d'un bloc). Le grand avantage des champs finis est que la division (sauf par 0) est définie de manière unique et produira toujours une valeur dans ce champ; ainsi, les valeurs interpolées des polynômes s'intégreront dans un bloc exactement de la même manière que les valeurs d'entrée.

Afin de convertir l'entrée en une série de données de bloc, nous devons alors effectuer une conversion de base: convertir l'entrée de la base 256 en un nombre, puis convertir en la base p (par exemple, pour un paramètre de rayonnement de 1, nous avons p= 16381). Cela était principalement dû au manque de routines de conversion de base de Perl (Math :: Prime :: Util en a, mais elles ne fonctionnent pas pour les bases bignum, et certains des nombres premiers avec lesquels nous travaillons ici sont incroyablement grands). Comme nous utilisons déjà Math :: Polynomial pour l'interpolation polynomiale, j'ai pu la réutiliser comme une fonction "convertir à partir d'une séquence de chiffres" (en visualisant les chiffres comme les coefficients d'un polynôme et en l'évaluant), et cela fonctionne pour les bignums ça va. Dans l'autre sens, cependant, j'ai dû écrire la fonction moi-même. Heureusement, ce n'est pas trop difficile (ou verbeux) à écrire. Malheureusement, cette conversion de base signifie que l'entrée est généralement rendue illisible. Il y a aussi un problème avec les zéros non significatifs;

Il convient de noter que nous ne pouvons pas avoir plus de p blocs dans la sortie (sinon les index de deux blocs deviendraient égaux, et pourtant il faudrait peut-être produire des sorties différentes du polynôme). Cela ne se produit que lorsque l'entrée est extrêmement grande. Ce programme résout le problème d'une manière très simple: l'augmentation du rayonnement (ce qui rend les blocs plus grands et p beaucoup plus grands, ce qui signifie que nous pouvons insérer beaucoup plus de données, et qui conduit clairement à un résultat correct).

Un autre point qui mérite d'être souligné est que nous encodons la chaîne nulle pour lui-même, car le programme tel qu'écrit se planterait autrement. C'est aussi clairement le meilleur encodage possible et fonctionne quel que soit le paramètre de rayonnement.

Améliorations potentielles

L'inefficacité asymptotique principale de ce programme est liée à l'utilisation du modulo-prime comme champs finis en question. Des champs finis de taille 2 ⁿ existent (ce qui est exactement ce que nous voudrions ici, car les tailles de charge utile des blocs sont naturellement une puissance de 128). Malheureusement, ils sont plutôt plus complexes qu'une simple construction modulo, ce qui signifie que Math :: ModInt ne le couperait pas (et je n'ai trouvé aucune bibliothèque sur CPAN pour gérer des champs finis de tailles non-prime); Je devrais écrire une classe entière avec une arithmétique surchargée pour Math :: Polynomial pour pouvoir le gérer, et à ce stade, le coût en octets pourrait potentiellement dépasser la (très petite) perte due à l'utilisation, par exemple, 16381 plutôt que 16384.

Un autre avantage de l'utilisation de tailles de puissance de 2 est que la conversion de base deviendrait beaucoup plus facile. Cependant, dans les deux cas, une meilleure méthode de représentation de la longueur de l'entrée serait utile; la méthode «ajouter un 1 dans les cas ambigus» est simple mais inutile. La conversion de base bijective est une approche plausible ici (l'idée est que vous avez la base sous forme de chiffre, et 0 sous forme de chiffre, de sorte que chaque nombre correspond à une seule chaîne).

Bien que les performances asymptotiques de ce codage soient très bonnes (par exemple, pour une entrée de longueur 99 et un paramètre de rayonnement de 3, le codage a toujours une longueur de 128 octets, plutôt que les ~ 400 octets que les approches basées sur la répétition obtiendraient), ses performances est moins bon sur les entrées courtes; la longueur du codage est toujours au moins le carré de (paramètre de rayonnement + 1). Ainsi, pour des entrées très courtes (longueur 1 à 8) au rayonnement 9, la longueur de la sortie est néanmoins de 100. (En longueur 9, la longueur de la sortie est parfois de 100 et parfois de 110.) Les approches basées sur la répétition ont clairement battu cet effacement - approche basée sur le codage sur de très petites entrées; il peut être utile de basculer entre plusieurs algorithmes en fonction de la taille de l'entrée.

Enfin, cela ne vient pas vraiment dans la notation, mais avec des paramètres de rayonnement très élevés, utiliser un peu de chaque octet (⅛ de la taille de sortie) pour délimiter des blocs est un gaspillage; il serait moins cher d'utiliser à la place des délimiteurs entre les blocs. Reconstruire les blocs à partir des délimiteurs est plutôt plus difficile qu'avec l'approche MSB alternée, mais je pense que c'est possible, au moins si les données sont suffisamment longues (avec des données courtes, il peut être difficile de déduire le paramètre de rayonnement de la sortie) . Ce serait quelque chose à regarder si l'on visait une approche asymptotiquement idéale quels que soient les paramètres.

(Et bien sûr, il pourrait y avoir un algorithme entièrement différent qui produit de meilleurs résultats que celui-ci!)