tło

Na tej stronie czasami pojawiają się pytania wymagające, aby programy były „utwardzane promieniowaniem”; oznacza to, że program musi być w stanie przetrwać usunięcie jednego lub więcej bajtów, bez względu na to, które bajty zostaną usunięte.

Jak to często bywa w zadaniach, które często ustawiają się w wyzwaniach programistycznych, naturalne jest, że chcemy stworzyć język, który jest szczególnie dobry w tych wyzwaniach. Biorąc pod uwagę, że naturalnym sposobem na to jest dodanie metadanych, które umożliwiają odwrócenie korupcji, tak naprawdę nie jest to język, który wymaga projektowania, ale kodowanie; pomysł polega na przekształceniu każdego wejścia w sekwencję bajtów, w taki sposób, że nawet jeśli sekwencja jest lekko naświetlona, ​​możliwe jest wyodrębnienie pierwotnego wejścia.

Zadanie

Napisz dwa programy lub funkcje, E (koder) i D (dekoder), tak aby:

• E przyjmuje dwa argumenty, sekwencję oktetów (które w tej specyfikacji nazywamy „ wejściem ”) i nieujemną liczbę całkowitą „ promieniowanie ”, i wysyła sekwencję oktetów „ kodującą ”;
• D przyjmuje jeden argument, sekwencję oktetów („ encdng ”) i wysyła sekwencję „ rekonstrukcji ” oktetów ;
• Jeśli uruchomisz zarówno E, jak i D (z encdng , wejście do D, wybrane przez usunięcie nie więcej niż elementów promieniowania z kodowania (niekoniecznie w sposób ciągły)), to rekonstrukcja będzie równa wejściowi bez względu na to, które znaki zostały usunięte, aby utworzyć encdng .

Wyjaśnienia

• Jeśli prześlesz funkcje, nie musisz do nich dzwonić Ei D; możesz wybrać dowolną nazwę odpowiednią dla twojego języka.
• „Oktet” jest w zasadzie liczbą całkowitą od 0 do 255 włącznie, którą możesz zakodować jako liczbę całkowitą, znak lub cokolwiek odpowiedniego dla twojego języka.
• E i D muszą być całkowicie deterministyczne (tj. Nadanie im tych samych danych wejściowych zawsze będzie dawało tę samą moc wyjściową, przy czym „dane wejściowe” są zdefiniowane jako dane wejściowe i promieniowanie dla E lub encdng dla D). W szczególności E może nie przekazywać informacji D do kanału bocznego.
• Usunięcia wykonuje się przez usunięcie jednego elementu sekwencji; pomyśl o otwarciu sekwencji w edytorze, umieszczeniu kursora w dowolnym punkcie i naciśnięciu klawisza Backspace. Jeśli element pojawia się wiele razy, możliwe jest, że zostanie usunięta tylko jedna kopia elementu (tj. Nie wpłynie to na inne wystąpienia tego samego oktetu).
• Chociaż wynik jest obliczany tylko na podstawie dość krótkich danych wejściowych , twój program musi działać teoretycznie dla każdego sygnału wejściowego i promieniowania . W szczególności musi działać niezależnie od tego, które oktety pojawiają się na wejściu . (Niestety, ludzie, którzy chcieliby mieć możliwość używania znaków, które nie mogą zostać wydrukowane, nie pojawią się w danych wejściowych, ale muszę upewnić się, że dane wejściowe są nieściśliwe, aby wyzwanie dotyczyło utwardzania promieniowaniem, a nie kompresji.)
• Możesz przesłać jeden plik, który definiuje dwie funkcje; dwa pliki, z których każdy definiuje funkcję lub które są pełnymi programami; lub trzy pliki, z których dwa implementują odpowiednio D i E (albo jako pełne programy, albo przez zdefiniowanie funkcji), a trzeci to plik nagłówkowy lub biblioteka wspólna dla D i E. Bez względu na to, jakiego rodzaju przesłania używasz , implementacja języka programowania musi być w stanie zrozumieć oba programy bez dalszych argumentów, takich jak lokalizacje plików (w przeciwnym razie musisz zapłacić karę bajtową za wywołanie implementacji w nietypowy sposób, zgodnie z naszymi standardowymi zasadami).

Warunek zwycięstwa

Dla każdej długości i promieni , niech C ( długość , promieniowanie ) będzie całkowite Długości kodowania S, która spełnia wszystkich wejściowych o długości długości i danego promieniowania . (To znaczy, f ( długość , promieniowanie ) = suma _{wejściowa ma długość długość} długość (E ( wejście , promieniowanie )).) Następnie niech g ( długość , promieniowanie ) równa się f ( długość ,promieniowanie ) ÷ 256 ^długości . Innymi słowy, g jest średnią długością zakodowanego sygnału wyjściowego dla danej długości sygnału wejściowego i danego wymogu utwardzania promieniowaniem. (Teoretycznie można to obliczyć za pomocą brutalnej siły, ale prawdopodobnie zajęłoby to nieprawdopodobnie dużo czasu w ten sposób. Oczekuję, że większość zgłoszeń będzie w stanie przedstawić matematyczny argument na temat ich wyniku. Jeśli „ nie jesteś pewien, opublikuj przybliżony wynik, a Ty lub ktoś inny możesz go obliczyć bardziej szczegółowo, jeśli inny wpis opublikuje podobny wynik).

Twój wynik jest równy sumie g ( długość , promieniowanie ) dla całego promieniowania w zakresie od 0 do 9 włącznie i dla całej długości w zakresie od 0 do 99 włącznie, plus (głównie w celu uniknięcia zakodowania na stałe lub utrzymania konkurencji, jeśli ktoś odkrywa matematycznie doskonałe kodowanie; w przeciwnym razie prawdopodobnie będzie to minimalny czynnik) całkowita liczba bajtów w zgłoszeniu do wyzwania (plus standardowe kary za takie rzeczy, jak wymaganie nietypowych flag tłumacza lub konkretnych nazw plików). Zwycięzcą jest zgłoszenie o najniższym wyniku (remis rozstrzygany przy pierwszym zgłoszeniu do przesłania).

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

Enkoder

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

Wypróbuj online!

Dekoder

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

Wypróbuj online!

Oba pobierają i zwracają liczby całkowite listy. Linki TIO zawierają dla wygody konwersję z / na ciągi. Zauważ, że są one niezwykle nieefektywne w przypadku dłuższych ciągów. Jeśli chcesz wypróbować jeszcze kilka znaków, zalecamy używanie znaków z kodami małych znaków.

Podstawowy pomysł stworzenia kodowania utwardzanego promieniowaniem obejmuje dwa etapy:

1. Znajdź kodowanie, które nigdy nie zawiera dwóch kolejnych identycznych oktetów.
2. Powtórz każdy oktet w zakodowanym ciągu r + 1 razy, gdzie r jest poziomem promieniowania.

W ten sposób promieniowanie nie może całkowicie usunąć jednego ciągu identycznych znaków, dzięki czemu możemy dekodować ciąg, pobierając jeden znak z każdego przebiegu, a następnie dekodując krok 1.

Więc jedyną interesującą częścią jest znalezienie kodowania, które nigdy nie daje powtarzających się oktetów. Podstawową ideą jest użycie czegoś takiego jak A043096 jako systemu liczbowego. To znaczy, aby zakodować liczbę całkowitą N , po prostu zliczamy w jakiejś bazie b , pomijając wszystkie liczby z powtarzającymi się oktetami. Uważam, że liczba cyfr, które mogą być reprezentowane w ten sposób maksymalnie cyframi d, jest taka sama, jak liczba liczb, które mogą być reprezentowane w bazie bijective b-1 (ponieważ, jeśli chcesz zapisać taką liczbę, możesz wybierz cyfrę b-1 dla każdej pozycji bez naruszenia ograniczenia).

Oczywiście, aby uzyskać maksymalną kompresję, użyjemy b = 256 . Aby przekształcić dane wejściowe w liczbę całkowitą, możemy również użyć konwersji bazowej. Gdybym nie był leniwy, użyłbym bijective base jako danych wejściowych, ale na razie przygotowuję tylko 1(aby upewnić się, że nie ma zer wiodących), a następnie używam najmniejszej możliwej podstawy, aby wszystkie oktety w dane wejściowe są mniejsze niż podstawa.

Ta baza jest następnie dodawana do kodowania (aby dekoder wiedział, z której bazy należy skorzystać) i oddzielana od pozostałej liczby przez 0-oktet (to działa, ponieważ pozostała liczba nigdy nie rozpocznie się od zera). W ramach drobnej optymalizacji pusty ciąg pozostaje pustym ciągiem.

Powodem, dla którego nie wyliczyłem dokładnego wyniku powyżej, jest to, że obliczam jedynie górną granicę dla tego, jak długo każde wejście będzie oparte na jego długości i maksymalnym oktecie. Jednak dla tych dwóch parametrów często występują dwie różne długości wyjściowe, a ja nie zastanawiałem się jeszcze, gdzie występuje punkt krytyczny między nimi. Użyłem również długości zwykłej podstawy 255 zamiast bijective base 255, aby oszacować tę długość, która jest znowu nieco większa niż powinna. Dokładny kod Mathematica, którego użyłem do obliczeń, jest następujący:

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]powinienem podać liczbę łańcuchów długości lo maksymalnej liczbie oktetów b-1(z wyjątkiem tego b == 1, gdzie to zakodowałem, 0ponieważ zawsze używam przynajmniej bazy 2).

bash + narzędzia GNU, wynik 294506 283468

Edycja 1: Naprawiono problem, który zauważył @Leo - dziękuję!

Edycja 2: Ulepszono metodę kodowania parametru promieniowania, aby uzyskać lepszy wynik.

Koder (97 bajtów):

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

Dekoder (121 bajtów):

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

Dla enkodera: Sekwencja oktetów przekazana jako znaki w standardzie, parametr promieniowania r przekazany jako argument.

Dla dekodera: Dane wejściowe przekazywane jako znaki w standardzie.

Dla obu: Wyjście na standardowe wyjście.

Koder wstawia do danych wejściowych cyfry r, ze znakiem „a” wstawionym między każdą parę kolejnych identycznych cyfr, a następnie pojedynczą nową linię. Następnie kopiuje wszystkie dane wejściowe (zaczynając od poprzedzających znaków), zastępując każdy znak r + 1 kopiami tego znaku.

Dekoder cofa to, przechodząc przez każdy z pozostałych znaków x na wejściu, przeskakując do r kolejnych identycznych kopii x po x i drukując to, co pozostało. Dodane dane nie mają powtarzających się znaków, więc można je zdekodować, zanim r będzie znane. W tym momencie r jest znany i ta wartość jest potrzebna do prawidłowego dekodowania reszty danych.

Możesz sprawdzić, czy to działa, nawet jeśli oryginalne wejście ma powtarzające się identyczne znaki.

Obliczanie wyniku:

Załóżmy, że dane wejściowe mają długość L, a parametr promieniowania wynosi r (co najwyżej 9 w przypadku obliczenia punktacji, więc mieści się w jednej cyfrze, a zatem nie ma kolejnych powtarzających się znaków). Dane poprzedzone to 2 bajty (cyfra, nowa linia), więc wyjściem jest (r + 1) (L + 2) bajty dla zakodowanego strumienia.

Więc g (L, r) = (r + 1) (L + 2).

Wynika z tego, że całkowity wynik można obliczyć jako

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

Obrazy kontrolne są używane do reprezentowania odpowiedniego znaku kontrolnego (np. ␀Jest dosłowny znak NUL). Nie przejmuj się zbytnio próbą odczytania kodu; poniżej znajduje się bardziej czytelna wersja.

Uruchom z -Mbigint -MMath::ModInt=mod -MMath::Polynomial -MNtheory=:all. -MMath::Bigint=lib,GMPnie jest konieczne (i dlatego nie jest uwzględnione w partyturze), ale jeśli dodasz go przed innymi bibliotekami, spowoduje to, że program będzie działał nieco szybciej.

Obliczanie wyniku

Algorytm jest tutaj nieco poprawialny, ale trudniej go napisać (ponieważ Perl nie ma odpowiednich bibliotek). Z tego powodu dokonałem kilku kompromisów między rozmiarem a wydajnością w kodzie, na tej podstawie, że biorąc pod uwagę, że bajty można zapisać w kodowaniu, nie ma sensu próbować zgrywać każdego punktu z gry w golfa.

Program składa się z 600 bajtów kodu oraz 78 bajtów kar za opcje wiersza poleceń, co daje karę w wysokości 678 punktów. Resztę wyniku obliczono, uruchamiając program na łańcuchu najlepszych i najgorszych (pod względem długości wyjściowej) dla każdej długości od 0 do 99 i dla każdego poziomu promieniowania od 0 do 9; średni przypadek jest gdzieś pośrodku, a to wyznacza granice wyniku. (Nie warto próbować obliczyć dokładnej wartości, chyba że pojawi się inny wpis z podobnym wynikiem).

Oznacza to zatem, że wynik ze skuteczności kodowania mieści się w zakresie od 91100 do 92141 włącznie, więc wynik końcowy wynosi:

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

Wersja mniej golfowa, z komentarzami i kodem testowym

To jest oryginalny program + nowe linie, wcięcia i komentarze. (W rzeczywistości wersja w golfa została wyprodukowana przez usunięcie nowych linii / wcięć / komentarzy z tej wersji.)

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;

Algorytm

Uproszczenie problemu

Podstawową ideą jest zredukowanie problemu „kodowania kasowania” (który nie jest szeroko badany) do problemu kodowania kasowania (obszernie zbadany obszar matematyki). Kodowanie wymazywania polega na tym, że przygotowujesz dane do wysłania przez „kanał kasowania”, kanał, który czasami zastępuje wysyłane przez siebie znaki znakiem „pomieszania”, który wskazuje znaną pozycję błędu. (Innymi słowy, zawsze jest jasne, gdzie nastąpiło uszkodzenie, chociaż pierwotna postać jest nadal nieznana). Idea tego jest dość prosta: dzielimy dane wejściowe na bloki długości ( promieniowanie+ 1) i użyj siedmiu z ośmiu bitów w każdym bloku na dane, podczas gdy pozostały bit (w tej konstrukcji MSB) na przemian jest ustawiony dla całego bloku, wyczyść dla całego następnego bloku, ustawiony dla bloku potem i tak dalej. Ponieważ bloki są dłuższe niż parametr promieniowania, co najmniej jeden znak z każdego bloku przetrwa na wyjściu; więc, biorąc ciąg znaków z tym samym MSB, możemy ustalić, do którego bloku należała każda postać. Liczba bloków jest również zawsze większa niż parametr promieniowania, więc zawsze mamy co najmniej jeden nieuszkodzony blok w encdng; wiemy zatem, że wszystkie najdłuższe bloki lub najdłuższe remisy są nieuszkodzone, co pozwala traktować wszelkie bloki krótsze jako uszkodzone (a więc pomyłkę). Możemy również wydedukować taki parametr promieniowania (

Usuń kod

Jeśli chodzi o część problemu polegającą na kodowaniu skasowania, wykorzystuje się prosty specjalny przypadek konstrukcji Reeda-Solomona. Jest to konstrukcja systematyczna: wynik (algorytmu kodowania kasowania) jest równy wejściowi plus pewna liczba dodatkowych bloków, równych parametrowi promieniowania. Możemy obliczyć wartości potrzebne dla tych bloków w prosty (i golfistyczny!) Sposób, traktując je jak elementy, a następnie uruchamiając na nich algorytm dekodujący w celu „odtworzenia” ich wartości.

Sam pomysł konstrukcji jest również bardzo prosty: dopasowujemy wielomian, w możliwie najmniejszym stopniu, do wszystkich bloków w kodowaniu (z interpolacjami interpolowanymi z innych elementów); jeśli wielomianem jest f , pierwszy blok to f (0), drugi to f (1) i tak dalej. Oczywiste jest, że stopień wielomianu będzie równy liczbie bloków wejściowych minus 1 (ponieważ najpierw dopasowujemy wielomian do tych bloków, a następnie wykorzystujemy go do budowy dodatkowych bloków „kontrolnych”); a ponieważ punkty d +1 jednoznacznie definiują wielomian stopnia d, wykasowanie dowolnej liczby bloków (do parametru promieniowania) pozostawi liczbę nieuszkodzonych bloków równą pierwotnemu wejściowi, co jest wystarczającą informacją do odtworzenia tego samego wielomianu. (Musimy wtedy tylko ocenić wielomian, aby odblokować blok.)

Konwersja bazy

Ostatnią kwestią pozostawioną tutaj jest faktyczne wartości przyjęte przez bloki; jeśli wykonamy interpolację wielomianową na liczbach całkowitych, wynikiem mogą być liczby wymierne (zamiast liczb całkowitych), znacznie większe niż wartości wejściowe lub w inny sposób niepożądane. Dlatego zamiast liczb całkowitych używamy pola skończonego; w tym programie zastosowanym polem skończonym jest pole liczb całkowitych modulo p , gdzie p jest największą liczbą pierwszą mniejszą niż 128 ^{promieniowania +1}(tj. największa liczba pierwsza, dla której możemy dopasować wiele odrębnych wartości równych tej liczbie pierwszej do części danych bloku). Dużą zaletą pól skończonych jest to, że podział (z wyjątkiem 0) jest jednoznacznie zdefiniowany i zawsze będzie generował wartość w tym polu; dlatego interpolowane wartości wielomianów zmieszczą się w bloku w taki sam sposób jak wartości wejściowe.

Aby przekonwertować dane wejściowe na szereg danych blokowych, musimy wykonać konwersję bazy: przekonwertować dane wejściowe z bazy 256 na liczbę, a następnie przekonwertować na bazę p (np. Dla parametru promieniowania 1 mamy p= 16381). Było to głównie powstrzymywane przez brak podstawowych procedur konwersji Perla (Math :: Prime :: Util ma kilka, ale nie działają one na bazy bignum, a niektóre liczby pierwsze, z którymi pracujemy, są niewiarygodnie duże). Ponieważ już używamy Math :: Polynomial do interpolacji wielomianowej, byłem w stanie użyć go ponownie jako funkcji „przekształć z sekwencji cyfr” (przeglądając cyfry jako współczynniki wielomianu i oceniając go), i to działa na bignum w porządku. Idąc w drugą stronę, musiałem sam napisać tę funkcję. Na szczęście pisanie nie jest zbyt trudne (lub pełne). Niestety ta podstawowa konwersja oznacza, że ​​dane wejściowe są zwykle nieczytelne. Istnieje również problem z wiodącymi zerami;

Należy zauważyć, że nie możemy mieć więcej niż p bloków na wyjściu (w przeciwnym razie indeksy dwóch bloków stałyby się równe, a jednak prawdopodobnie musiałyby wytwarzać różne wyniki z wielomianu). Dzieje się tak tylko wtedy, gdy dane wejściowe są bardzo duże. Ten program rozwiązuje problem w bardzo prosty sposób: zwiększenie promieniowania (co sprawia, że ​​bloki są większe, a p znacznie większe, co oznacza, że ​​możemy zmieścić znacznie więcej danych i co wyraźnie prowadzi do prawidłowego wyniku).

Inną kwestią wartą uwagi jest to, że kodujemy łańcuch zerowy do siebie, ponieważ program tak jak napisałby zawiesiłby się na nim inaczej. Jest to oczywiście najlepsze możliwe kodowanie i działa bez względu na parametr promieniowania.

Potencjalne ulepszenia

Główną asymptotyczną nieefektywnością w tym programie jest wykorzystanie modulo-prime jako omawianych pól skończonych. Istnieją pola skończone o wielkości 2 ⁿ (dokładnie tego tutaj chcielibyśmy, ponieważ rozmiary bloków mają naturalnie potęgę 128). Niestety, są one bardziej złożone niż prosta konstrukcja modulo, co oznacza, że ​​Math :: ModInt by tego nie wyciął (i nie mogłem znaleźć żadnych bibliotek na CPAN do obsługi skończonych pól o rozmiarach innych niż podstawowe); Musiałbym napisać całą klasę z przeciążoną arytmetyką dla Math :: Polynomial, aby móc sobie z tym poradzić, a w tym momencie koszt bajtu może potencjalnie przewyższyć (bardzo małą) stratę wynikającą z użycia np. 16381 zamiast 16384.

Kolejną zaletą korzystania z potęgi 2 rozmiarów jest to, że podstawowa konwersja stałaby się znacznie łatwiejsza. W obu przypadkach przydatna byłaby lepsza metoda reprezentowania długości danych wejściowych; metoda „przedkładaj 1 w niejednoznacznych przypadkach” jest prosta, ale marnotrawiona. Dwusuwowa konwersja bazy jest tutaj jednym z możliwych podejść (chodzi o to, że masz bazę jako cyfrę, a 0 jako nie cyfrę, tak aby każda liczba odpowiadała jednemu ciągowi znaków).

Chociaż asymptotyczna wydajność tego kodowania jest bardzo dobra (np. Dla wejścia o długości 99 i parametru promieniowania 3, kodowanie ma zawsze długość 128 bajtów, a nie ~ 400 bajtów, które uzyskałyby podejścia oparte na powtarzaniu), jego wydajność jest mniej dobry przy krótkich nakładach; długość kodowania jest zawsze co najmniej kwadratem (parametr promieniowania + 1). Tak więc dla bardzo krótkich sygnałów wejściowych (długość 1 do 8) przy promieniowaniu 9 długość wyjściowa wynosi jednak 100. (Przy długości 9 długość wyjściowa wynosi czasami 100, a czasem 110.) Podejścia oparte na powtarzaniu wyraźnie pokonują to wymazanie - podejście oparte na kodowaniu na bardzo małych nakładach; warto zmieniać różne algorytmy na podstawie wielkości danych wejściowych.

Wreszcie, tak naprawdę nie pojawia się w punktacji, ale przy bardzo wysokich parametrach promieniowania, użycie odrobiny każdego bajtu (⅛ wielkości wyjściowej) do rozgraniczenia bloków jest marnotrawstwem; taniej byłoby użyć zamiast tego ograniczników między blokami. Rekonstrukcja bloków z ograniczników jest raczej trudniejsza niż w przypadku metody naprzemiennego MSB, ale uważam, że jest to możliwe, przynajmniej jeśli dane są wystarczająco długie (przy krótkich danych może być trudno wydedukować parametr promieniowania z wyjścia) . Można by na to spojrzeć, jeśli dąży się do asymptotycznie idealnego podejścia niezależnie od parametrów.

(I oczywiście może istnieć zupełnie inny algorytm, który daje lepsze wyniki niż ten!)