Hintergrund

Auf dieser Site haben wir gelegentlich Fragen, bei denen Programme "strahlungsgehärtet" werden müssen. Dies bedeutet, dass das Programm in der Lage sein muss, das Löschen eines oder mehrerer Bytes zu überstehen, unabhängig davon, welche Bytes gelöscht werden.

Wie es bei Aufgaben üblich ist, die bei Programmierherausforderungen häufig vorkommen, ist es selbstverständlich, eine Sprache zu erstellen, die bei diesen Herausforderungen besonders gut ist. Angesichts der Tatsache, dass der natürliche Weg, dies zu tun, darin besteht, einige Metadaten hinzuzufügen, mit denen Korruption rückgängig gemacht werden kann, handelt es sich eigentlich nicht wirklich um eine zu entwerfende Sprache, sondern um eine Kodierung. Die Idee ist, jede Eingabe in eine Folge von Bytes umzuwandeln, so dass es möglich ist, die ursprüngliche Eingabe zu extrahieren, selbst wenn die Folge leicht bestrahlt wird.

Die Aufgabe

Schreiben Sie zwei Programme oder Funktionen, E (ein Encoder) und D (ein Decoder), so dass:

• E nimmt zwei Argumente, eine Folge von Oktetten (die wir in dieser Beschreibung " Eingabe " nennen ) und eine nichtnegative ganze Zahl " Strahlung ", und gibt eine Folge von Oktetten " Codierung " aus;
• D nimmt ein Argument, eine Folge von Oktetten (" encdng ") und gibt eine Folge von Oktetten " reconstruction " aus;
• Wenn Sie sowohl E als auch D ausführen (mit encdng , die Eingabe in D, ausgewählt durch Löschen von nicht mehr als Strahlungselementen aus der Codierung (nicht unbedingt zusammenhängend)), entspricht die Rekonstruktion der Eingabe, unabhängig davon, welche Zeichen zur Codierung gelöscht wurden .

Klarstellungen

• Wenn Sie Funktionen einreichen, müssen Sie sie nicht aufrufen Eund D; Sie können wählen, welcher Name für Ihre Sprache am besten geeignet ist.
• Ein "Oktett" ist im Grunde genommen eine Ganzzahl von 0 bis einschließlich 255, die Sie als Ganzzahl, Zeichen oder was auch immer für Ihre Sprache geeignet ist, codieren können.
• E und D müssen vollständig deterministisch sein (dh die Angabe derselben Eingaben führt immer zu derselben Ausgabe, wobei "Eingaben" als Eingabe und Strahlung für E oder Kodierung für D definiert sind). Insbesondere darf E keine Informationen über einen Seitenkanal an D übermitteln.
• Die Löschvorgänge werden ausgeführt, indem ein Element der Sequenz gelöscht wird. Stellen Sie sich vor, Sie öffnen die Sequenz in einem Editor, platzieren den Cursor an einer beliebigen Stelle und drücken die Rücktaste. Wenn ein Element mehrmals vorkommt, wird möglicherweise nur eine Kopie des Elements gelöscht (dh andere Instanzen desselben Oktetts sind nicht betroffen).
• Obwohl die Punktzahl nur auf der Grundlage einer relativ kurzen Eingabe berechnet wird , muss Ihr Programm theoretisch für jede Eingabe und Strahlung funktionieren . Insbesondere muss es funktionieren, egal welche Oktette in der Eingabe erscheinen . (Sorry, Leute, die nicht druckbare Zeichen verwenden möchten, die sie kennen, werden in der Eingabe nicht angezeigt, aber ich muss sicherstellen, dass die Eingabe inkompressibel ist, damit es bei der Herausforderung nicht um Komprimierung, sondern um Strahlungshärtung geht.)
• Sie können eine der beiden Dateien einreichen, in denen zwei Funktionen definiert sind. zwei Dateien, die jeweils eine Funktion definieren oder beide vollständige Programme sind; oder drei Dateien, von denen zwei D und E implementieren (entweder als vollständige Programme oder durch Definieren einer Funktion), und die dritte Datei ist eine Header-Datei oder Bibliothek, die D und E gemeinsam ist. Unabhängig davon, welche Form der Übermittlung Sie verwenden muss Ihre Programmiersprachenimplementierung in der Lage sein, beide Programme ohne weitere Argumente wie Dateispeicherorte zu verstehen (oder Sie müssen eine Byte-Strafe zahlen, wenn Sie Ihre Implementierung gemäß unseren Standardregeln auf ungewöhnliche Weise aufrufen).

Siegbedingung

Für jede Länge und Strahlung , lassen f ( Länge , Strahlung ) sein , die Gesamtlängen der Codierung diese entsprechen alle S - Eingang mit Längenlänge und der gegebenen Strahlung . (Das heißt, f ( Länge , Strahlung ) = Summe _{Eingang hat Länge Länge} Länge (E ( Eingang , Strahlung )).) Dann lassen Sie g ( Länge , Strahlung ) gleich f ( Länge ,Strahlung ) ÷ 256 ^Länge . Mit anderen Worten ist g die durchschnittliche Länge der codierten Ausgabe für eine gegebene Länge der Eingabe und eine gegebene Strahlungshärtungsanforderung. (Theoretisch könnten Sie dies mit brachialer Gewalt berechnen, aber es würde wahrscheinlich unplausibel lange dauern, Ihre Punktzahl auf diese Weise zu berechnen. Ich gehe davon aus, dass die meisten Einsendungen in der Lage sind, ein mathematisches Argument für die Punktzahl zu liefern. Wenn Sie Wenn Sie sich nicht sicher sind, geben Sie eine ungefähre Punktzahl an, und Sie oder eine andere Person können diese genauer berechnen, wenn ein anderer Eintrag eine ähnliche Punktzahl veröffentlicht.)

Ihre Punktzahl entspricht der Summe von g ( Länge , Strahlung ) für alle Strahlungen im Bereich von 0 bis einschließlich 9 und für alle Längen im Bereich von 0 bis einschließlich 99 plus (hauptsächlich, um Hardcodierung zu vermeiden oder die Konkurrenz am Laufen zu halten, wenn Jemand entdeckt eine mathematisch perfekte Kodierung, dies ist wahrscheinlich ein minimaler Faktor, andernfalls) die Gesamtzahl der Bytes, die Sie bei der Challenge eingereicht haben (zuzüglich der Standardstrafen für Dinge, die ungewöhnliche Interpreter-Flags oder bestimmte Dateinamen erfordern). Der Gewinner ist der Eintrag mit der niedrigsten Punktzahl (gebrochen durch den ersten einzureichenden Eintrag).

CJam, Score ≤ 286.516 + 54 + 36 = 286.606

Encoder

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

Probieren Sie es online!

Decoder

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

Probieren Sie es online!

Beide nehmen und geben eine Liste von ganzen Zahlen zurück. Die TIO-Links enthalten aus Bequemlichkeitsgründen die Konvertierung von / in Zeichenfolgen. Beachten Sie, dass diese für längere Saiten unglaublich ineffizient sind. Wenn Sie noch ein paar Zeichen ausprobieren möchten, empfehle ich die Verwendung von Zeichen mit kleinen Zeichencodes.

Die Grundidee zum Erstellen einer strahlungsgehärteten Codierung besteht aus zwei Schritten:

1. Suchen Sie eine Kodierung, die niemals zwei aufeinanderfolgende identische Oktette enthält.
2. Wiederholen Sie jedes Oktett in der codierten Zeichenfolge r + 1 Mal, wobei r der Strahlungspegel ist.

Auf diese Weise kann die Strahlung einen Lauf identischer Zeichen nicht vollständig löschen, sodass wir den String entschlüsseln können, indem wir aus jedem Lauf ein Zeichen nehmen und dann Schritt 1 entschlüsseln.

Der einzig interessante Teil ist es also, eine Kodierung zu finden, die niemals wiederholte Oktette liefert. Die Grundidee ist, so etwas wie A043096 als Zahlensystem zu verwenden. Das heißt, um eine ganze Zahl N zu codieren , zählen wir einfach in einer Basis b hoch und überspringen alle Zahlen mit wiederholten Oktetten. Ich glaube, die Anzahl der Zahlen, die auf diese Weise mit bis zu d Ziffern dargestellt werden können, entspricht der Anzahl der Zahlen, die in der bijektiven Basis b-1 dargestellt werden können (da Sie, wenn Sie eine solche Zahl schreiben möchten, dies können) Wählen Sie für jede Position eine Ziffer zwischen b und 1 aus, ohne die Einschränkung zu verletzen.

Um eine maximale Komprimierung zu erzielen, verwenden wir natürlich b = 256 . Um die Eingabe in eine Ganzzahl umzuwandeln, können wir auch die Basiskonvertierung verwenden. Wenn ich nicht faul wäre, würde ich eine bijektive Basis für die Eingabe verwenden, aber im Moment stelle ich nur eine voran 1(um sicherzustellen, dass keine führenden Nullen vorhanden sind) und verwende dann die kleinstmögliche Basis, sodass alle Oktette in der Eingang sind weniger als die Basis.

Diese Basis wird dann der Codierung vorangestellt (damit der Decoder weiß, welche Basis er verwenden soll) und durch ein 0-Oktett von der verbleibenden Zahl getrennt (dies funktioniert, weil die verbleibende Zahl niemals mit einer Null beginnt). Als Nebenoptimierung bleibt die leere Zeichenfolge eine leere Zeichenfolge.

Der Grund, warum ich oben keine exakte Punktzahl berechnet habe, ist, dass ich nur eine Obergrenze für die Länge jeder Eingabe auf der Grundlage ihrer Länge und ihres maximalen Oktetts berechne. Für diese beiden Parameter gibt es jedoch häufig zwei unterschiedliche Ausgabelängen, und ich habe mich noch nicht darum gekümmert, herauszufinden, wo der Kipppunkt zwischen ihnen liegt. Ich habe auch die Länge der gewöhnlichen Basis 255 anstelle der bijektiven Basis 255 verwendet, um diese Länge zu schätzen, die wiederum etwas größer ist, als sie sein muss. Der genaue Mathematica-Code, den ich für die Berechnung verwendet habe, ist der folgende:

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]sollte die Anzahl der Zeichenketten lmit maximalem Oktett angeben b-1(außer b == 1, wo ich es fest codiert habe, 0weil ich immer mindestens base verwende 2).

Bash + GNU-Dienstprogramme, Score 294506 283468

Edit 1: Behebt ein Problem, das @Leo bemerkt hat - danke!

Edit 2: Die Kodierungsmethode für den Strahlungsparameter wurde verbessert, um eine bessere Punktzahl zu erzielen.

Encoder (97 Bytes):

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

Decoder (121 Bytes):

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

Für den Encoder: Oktettsequenz als Zeichen in stdin übergeben, Strahlungsparameter r als Argument übergeben.

Für den Decoder: Eingabe als Zeichen in stdin übergeben.

Für beide: Ausgabe auf Standardausgabe.

Der Codierer stellt den Eingabedaten die Ziffern von r voran, wobei ein Zeichen 'a' zwischen jedes Paar aufeinanderfolgender identischer Ziffern eingefügt wird, gefolgt von einer einzelnen neuen Zeile. Es kopiert dann alle Eingaben (beginnend mit den vorangestellten Zeichen) und ersetzt jedes Zeichen durch r + 1 Kopien dieses Zeichens.

Der Decoder macht dies rückgängig, indem er jedes der verbleibenden Zeichen x in seiner Eingabe durchläuft, bis zu r aufeinanderfolgenden identischen Kopien von x nach x überspringt und druckt, was übrig bleibt. Die vorangestellten Daten enthalten keine wiederholten Zeichen und können daher dekodiert werden, bevor r bekannt ist. Zu diesem Zeitpunkt ist r bekannt und dieser Wert wird benötigt, um den Rest der Daten korrekt zu decodieren.

Sie können überprüfen, ob dies auch dann funktioniert, wenn die ursprüngliche Eingabe identische Zeichen wiederholt hat.

Punktzahlberechnung:

Angenommen, die Eingabe hat die Länge L und der Strahlungsparameter ist r (der für die Bewertungsberechnung höchstens 9 beträgt, sodass er in eine Ziffer passt und daher keine aufeinanderfolgenden wiederholten Zeichen enthält). Die vorangestellten Daten bestehen aus 2 Bytes (Ziffer, Zeilenvorschub), sodass die Ausgabe (r + 1) (L + 2) Bytes für den codierten Datenstrom beträgt.

Also ist g (L, r) = (r + 1) (L + 2).

Daraus folgt, dass die Gesamtpunktzahl berechnet werden kann als

Perl + Math :: {ModInt, Polynom, Prime :: Util}, Ergebnis ≤ 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/^␁//;$_}

Kontrollbilder werden verwendet, um das entsprechende Kontrollzeichen darzustellen (z. B. ␀ein wörtliches NUL-Zeichen). Mach dir keine Sorgen, wenn du versuchst, den Code zu lesen. Es gibt unten eine besser lesbare Version.

Laufen Sie mit -Mbigint -MMath::ModInt=mod -MMath::Polynomial -MNtheory=:all. -MMath::Bigint=lib,GMPist nicht notwendig (und daher nicht in der Partitur enthalten), aber wenn Sie es vor den anderen Bibliotheken hinzufügen, wird das Programm etwas schneller ausgeführt.

Ergebnisberechnung

Der Algorithmus hier ist etwas verbesserungsfähig, aber schwieriger zu schreiben (da Perl nicht über die entsprechenden Bibliotheken verfügt). Aus diesem Grund habe ich einige Kompromisse in Bezug auf Größe und Effizienz im Code gemacht, da es keinen Grund gibt, zu versuchen, jeden Punkt vom Golfspielen abzuhalten, da Bytes in der Codierung gespeichert werden können.

Das Programm besteht aus 600 Byte Code und 78 Byte Strafen für Befehlszeilenoptionen, was eine Strafe von 678 Punkten ergibt. Der Rest der Punktzahl wurde berechnet, indem das Programm für jede Länge von 0 bis 99 und jede Strahlungsstufe von 0 bis 9 mit der Zeichenfolge für den besten und den schlechtesten Fall (in Bezug auf die Ausgabelänge) ausgeführt wurde. Der durchschnittliche Fall liegt irgendwo dazwischen, und dies gibt Grenzen für die Punktzahl. (Es lohnt sich nicht, den genauen Wert zu berechnen, es sei denn, ein anderer Eintrag kommt mit einer ähnlichen Punktzahl.)

Dies bedeutet, dass die Bewertung der Kodierungseffizienz im Bereich von 91100 bis einschließlich 92141 liegt. Die endgültige Bewertung lautet daher:

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

Weniger Golf-Version mit Kommentaren und Testcode

Dies ist das ursprüngliche Programm + Zeilenumbrüche, Einrückungen und Kommentare. (Tatsächlich wurde die Golfversion durch Entfernen von Zeilenumbrüchen / Einrückungen / Kommentaren aus dieser Version erstellt.)

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;

Algorithmus

Das Problem vereinfachen

Die Grundidee besteht darin, dieses Problem der "Löschkodierung" (das nicht weit verbreitet ist) in ein Löschkodierungsproblem (ein umfassend erforschtes Gebiet der Mathematik) zu reduzieren. Die Idee hinter der Löschcodierung ist, dass Sie Daten vorbereiten, die über einen "Löschkanal" gesendet werden. Dieser Kanal ersetzt manchmal die gesendeten Zeichen durch ein "Garble" -Zeichen, das auf eine bekannte Fehlerposition hinweist. (Mit anderen Worten, es ist immer klar, wo Korruption aufgetreten ist, obwohl der ursprüngliche Charakter noch unbekannt ist.) Die Idee dahinter ist ziemlich einfach: Wir teilen die Eingabe in Längenblöcke ( Strahlung) auf+ 1) und verwenden Sie sieben der acht Bits in jedem Block für Daten, während das verbleibende Bit (bei dieser Konstruktion das MSB) abwechselnd für einen gesamten Block gesetzt, für den gesamten nächsten Block gelöscht und für den Block gesetzt wird danach und so weiter. Da die Blöcke länger als der Strahlungsparameter sind, bleibt mindestens ein Zeichen von jedem Block in der Ausgabe erhalten. Wenn wir also eine Reihe von Zeichen mit demselben MSB ausführen, können wir herausfinden, zu welchem ​​Block jedes Zeichen gehört. Die Anzahl der Blöcke ist auch immer größer als der Strahlungsparameter, so dass wir immer mindestens einen unbeschädigten Block in der Kodierung haben; Wir wissen also, dass alle Blöcke, die am längsten oder am längsten gebunden sind, unbeschädigt sind, so dass wir kürzere Blöcke als beschädigt behandeln können (also als eine Unlesbarkeit). Wir können den Strahlungsparameter auch so ableiten (es '

Löschcodierung

Für den Löschcodierungsteil des Problems wird ein einfacher Spezialfall der Reed-Solomon-Konstruktion verwendet. Dies ist eine systematische Konstruktion: Die Ausgabe (des Löschcodierungsalgorithmus) entspricht der Eingabe plus einer Anzahl zusätzlicher Blöcke, die dem Strahlungsparameter entsprechen. Wir können die Werte, die für diese Blöcke benötigt werden, auf einfache (und golferische) Weise berechnen, indem wir sie als Störsignale behandeln und dann den Decodierungsalgorithmus ausführen, um ihren Wert zu "rekonstruieren".

Die eigentliche Idee hinter der Konstruktion ist ebenfalls sehr einfach: Wir passen ein Polynom mit dem kleinstmöglichen Grad an alle Blöcke in der Codierung an (mit Verzerrungen, die von den anderen Elementen interpoliert werden); Wenn das Polynom f ist , ist der erste Block f (0), der zweite ist f (1) und so weiter. Es ist klar, dass der Grad des Polynoms der Anzahl der Eingabeblöcke minus 1 entspricht (da wir zuerst ein Polynom an diese anpassen und dann die zusätzlichen "Check" -Blöcke daraus konstruieren); und weil d + 1 Punkte ein Polynom des Grades d eindeutig definierenWenn eine beliebige Anzahl von Blöcken (bis zum Strahlungsparameter) verstümmelt wird, bleibt eine Anzahl von unbeschädigten Blöcken gleich der ursprünglichen Eingabe, was ausreicht, um dasselbe Polynom zu rekonstruieren. (Dann müssen wir nur noch das Polynom auswerten, um einen Block freizugeben.)

Basisumwandlung

Die letzte Überlegung betrifft die tatsächlichen Werte der Blöcke. Wenn wir eine Polynominterpolation für die ganzen Zahlen durchführen, können die Ergebnisse rationale Zahlen (und nicht ganze Zahlen) sein, die viel größer als die Eingabewerte sind oder auf andere Weise unerwünscht sind. Anstatt die ganzen Zahlen zu verwenden, verwenden wir daher ein endliches Feld. In diesem Programm wird als endliches Feld das Feld der ganzen Zahlen modulo p verwendet , wobei p die größte Primzahl unter 128 ^{Strahlung +1 ist}(dh die größte Primzahl, für die wir eine Anzahl unterschiedlicher Werte, die dieser Primzahl entsprechen, in den Datenteil eines Blocks einfügen können). Der große Vorteil von endlichen Feldern besteht darin, dass die Division (außer durch 0) eindeutig definiert ist und immer einen Wert in diesem Feld erzeugt. Daher passen die interpolierten Werte der Polynome genauso in einen Block wie die Eingabewerte.

Um die Eingabe in eine Reihe von Blockdaten umzuwandeln, müssen wir eine Basiskonvertierung durchführen: Konvertieren Sie die Eingabe von der Basis 256 in eine Zahl und konvertieren Sie sie dann in die Basis p (z. B. für einen Strahlungsparameter von 1 haben wir p= 16381). Dies wurde größtenteils durch das Fehlen von Basenkonvertierungsroutinen in Perl aufgehalten (Math :: Prime :: Util hat einige, aber sie funktionieren nicht für Bignum-Basen, und einige der Primzahlen, mit denen wir hier arbeiten, sind unglaublich groß). Da wir Math :: Polynomial bereits für die Polynominterpolation verwenden, konnte ich es als Funktion "Konvertieren aus Ziffernfolge" wiederverwenden (indem ich die Ziffern als Koeffizienten eines Polynoms betrachtete und es auswertete). Dies funktioniert für Bignome Alles gut. Umgekehrt musste ich die Funktion selbst schreiben. Zum Glück ist es nicht zu schwer (oder wortreich) zu schreiben. Leider bedeutet diese Basiskonvertierung, dass die Eingabe normalerweise nicht lesbar ist. Es gibt auch ein Problem mit führenden Nullen.

Es sollte beachtet werden, dass wir nicht mehr als p Blöcke in der Ausgabe haben können (andernfalls würden die Indizes von zwei Blöcken gleich werden und müssen möglicherweise unterschiedliche Ausgaben aus dem Polynom erzeugen). Dies geschieht nur, wenn die Eingabe extrem groß ist. Dieses Programm löst das Problem auf sehr einfache Weise: Erhöhung der Strahlung (wodurch die Blöcke größer und p viel größer werden, was bedeutet, dass wir viel mehr Daten einpassen können, und was eindeutig zu einem korrekten Ergebnis führt).

Ein weiterer Punkt, den es sich zu machen lohnt, ist, dass wir den Null-String in sich selbst kodieren, da das geschriebene Programm andernfalls darauf abstürzen würde. Es ist auch eindeutig die bestmögliche Kodierung und funktioniert unabhängig von den Strahlungsparametern.

Mögliche Verbesserungen

Die hauptsächliche asymptotische Ineffizienz in diesem Programm liegt in der Verwendung von Modulo-Prime als die fraglichen endlichen Felder. Es existieren endliche Felder der Größe 2 ⁿ (was wir hier genau wollen, da die Nutzlastgrößen der Blöcke natürlich eine Potenz von 128 sind). Leider sind sie komplexer als eine einfache Modulo-Konstruktion, was bedeutet, dass Math :: ModInt sie nicht schneiden würde (und ich konnte keine Bibliotheken im CPAN finden, um endliche Felder von Nicht-Prim-Größen zu verarbeiten). Ich müsste eine ganze Klasse mit überladener Arithmetik schreiben, damit Math :: Polynomial damit umgehen kann, und zu diesem Zeitpunkt können die Bytekosten möglicherweise den (sehr geringen) Verlust aus der Verwendung von z. B. 16381 anstelle von 16384 überwiegen.

Ein weiterer Vorteil der Verwendung von Potenz-2-Größen besteht darin, dass die Basisumwandlung viel einfacher wird. In beiden Fällen wäre jedoch eine bessere Methode zur Darstellung der Länge der Eingabe nützlich. Die Methode "Voranstellen einer 1 in mehrdeutigen Fällen" ist einfach, aber verschwenderisch. Die bijektive Basiskonvertierung ist hier ein plausibler Ansatz (die Idee ist, dass Sie die Basis als Ziffer und 0 als keine Ziffer haben, sodass jede Zahl einer einzelnen Zeichenfolge entspricht).

Obwohl die asymptotische Leistung dieser Codierung sehr gut ist (z. B. bei einer Eingabe von Länge 99 und einem Strahlungsparameter von 3, ist die Codierung immer 128 Bytes lang, anstatt der ~ 400 Bytes, die wiederholungsbasierte Ansätze erhalten würden), ist ihre Leistung sehr gut ist bei kurzen Eingaben weniger gut; Die Länge der Kodierung ist immer mindestens das Quadrat von (Strahlungsparameter + 1). Für sehr kurze Eingaben (Länge 1 bis 8) bei Strahlung 9 beträgt die Länge der Ausgabe dennoch 100. (Bei Länge 9 beträgt die Länge der Ausgabe manchmal 100 und manchmal 110.) Wiederholungsbasierte Ansätze schlagen diese Löschung deutlich -codierungsbasierter Ansatz für sehr kleine Eingaben; Möglicherweise lohnt es sich, je nach Größe der Eingabe zwischen mehreren Algorithmen zu wechseln.

Schließlich kommt es in der Wertung nicht wirklich vor, aber bei sehr hohen Strahlungsparametern ist es verschwenderisch, ein bisschen von jedem Byte (⅛ der Ausgabegröße) zur Begrenzung von Blöcken zu verwenden. Es wäre billiger, stattdessen Trennzeichen zwischen den Blöcken zu verwenden. Die Rekonstruktion der Blöcke aus Begrenzern ist schwieriger als mit dem Alternating-MSB-Ansatz, aber ich halte es für möglich, zumindest wenn die Daten ausreichend lang sind (bei kurzen Daten kann es schwierig sein, den Strahlungsparameter aus der Ausgabe abzuleiten). . Dies ist zu prüfen, wenn unabhängig von den Parametern ein asymptotisch idealer Ansatz angestrebt wird.

(Und natürlich könnte es einen völlig anderen Algorithmus geben, der bessere Ergebnisse liefert als dieser!)