Latar Belakang

Di situs ini, kami kadang-kadang memiliki pertanyaan yang memerlukan program untuk "radiasi diperkeras"; ini berarti bahwa program tersebut harus mampu bertahan dari penghapusan satu atau lebih byte, tidak peduli byte mana yang dihapus.

Seperti biasa untuk tugas-tugas yang sering diatur dalam tantangan pemrograman, itu wajar untuk ingin membuat bahasa yang sangat baik pada tantangan ini. Mengingat bahwa cara alami untuk membuat ini adalah dengan menambahkan beberapa metadata yang memungkinkan untuk membalikkan korupsi, itu sebenarnya bukan bahasa yang perlu dirancang, tetapi suatu pengkodean; idenya adalah untuk mengubah setiap input ke urutan byte, sedemikian rupa sehingga bahkan jika urutannya sedikit diiradiasi, dimungkinkan untuk mengekstrak input asli.

Tugas

Tulis dua program atau fungsi, E (sebuah encoder) dan D (sebuah decoder), sehingga:

• E mengambil dua argumen, urutan oktet (yang akan kita sebut " input " dalam spesifikasi ini) dan integer non-negatif " radiasi ", dan menghasilkan urutan oktet " encoding ";
• D mengambil satu argumen, urutan oktet (" encdng "), dan menghasilkan urutan oktet " rekonstruksi ";
• Jika Anda menjalankan E dan D (dengan encdng , input ke D, dipilih dengan menghapus tidak lebih dari elemen radiasi dari encoding (tidak harus bersamaan)), maka rekonstruksi akan sama dengan input tidak peduli karakter mana yang dihapus untuk membentuk encdng .

Klarifikasi

• Jika Anda mengirim fungsi, Anda tidak harus memanggilnya Edan D; Anda dapat memilih nama apa pun yang paling cocok untuk bahasa Anda.
• "Oktet" pada dasarnya adalah bilangan bulat dari 0 hingga 255 inklusif, yang dapat Anda enkode sebagai bilangan bulat, karakter, atau apa pun yang sesuai untuk bahasa Anda.
• E dan D harus sepenuhnya deterministik (yaitu memberi mereka input yang sama akan selalu menghasilkan output yang sama, di mana "input" didefinisikan sebagai input dan radiasi untuk E, atau encdng untuk D). Secara khusus, E mungkin tidak mengkomunikasikan informasi ke D melalui saluran samping.
• Penghapusan dilakukan dengan menghapus satu elemen dari urutan; pikirkan membuka seuqence dalam editor, menempatkan kursor pada titik arbitrer, dan menekan Backspace. Jika suatu elemen muncul beberapa kali, mungkin saja hanya satu salinan elemen yang akan dihapus (contoh lain dari oktet yang sama tidak akan terpengaruh).
• Meskipun skor hanya dihitung berdasarkan input yang cukup pendek , program Anda harus bekerja secara teori untuk setiap input dan radiasi . Secara khusus, ia harus bekerja tidak peduli oktet mana yang muncul pada input . (Maaf, orang-orang yang menginginkan kemampuan untuk menggunakan karakter yang tidak diinginkan yang mereka tahu tidak akan muncul di input, tapi saya perlu memastikan bahwa inputnya tidak dapat dimampatkan sehingga tantangannya adalah tentang pengerasan radiasi daripada kompresi.)
• Anda dapat mengirim salah satu file yang mendefinisikan dua fungsi; dua file yang masing-masing mendefinisikan suatu fungsi atau yang keduanya merupakan program penuh; atau tiga file, dua di antaranya mengimplementasikan D dan E masing-masing (baik melalui program penuh atau melalui mendefinisikan fungsi), dan yang ketiga merupakan file header atau pustaka yang umum untuk D dan E. Terlepas dari bentuk pengajuan yang Anda gunakan , implementasi bahasa pemrograman Anda harus dapat memahami kedua program tanpa argumen lebih lanjut seperti lokasi file (atau Anda harus membayar penalti byte untuk meminta implementasi Anda dengan cara yang tidak biasa, sesuai aturan standar kami).

Kondisi kemenangan

Untuk setiap panjang dan radiasi , misalkan f ( panjang , radiasi ) menjadi panjang total enkode yang sesuai dengan semua input dengan panjang panjang , dan radiasi yang diberikan . (Yaitu, f ( panjang , radiasi ) = jumlah _{input memiliki panjang panjang} panjang (E ( input , radiasi )).) Kemudian biarkan g ( panjang , radiasi ) sama dengan f ( radiasi panjang ,) ÷ 256 ^panjang . Dengan kata lain, g adalah panjang rata-rata dari output yang dikodekan, untuk panjang input yang diberikan dan persyaratan pengerasan radiasi yang diberikan. (Secara teori Anda dapat menghitung ini dengan kekerasan, tetapi kemungkinan akan memakan waktu lama untuk menghitung skor Anda dengan cara itu. Saya berharap sebagian besar pengiriman akan dapat membuat argumen matematis tentang berapa skor mereka. Jika Anda ' tidak yakin, memposting skor perkiraan dan Anda atau orang lain dapat menghitungnya lebih mendalam jika entri lain memposting skor yang sama.)

Skor Anda sama dengan jumlah g ( panjang , radiasi ) untuk semua radiasi dalam rentang 0 hingga 9 inklusif, dan semua panjang dalam kisaran 0 hingga 99 inklusif, plus (kebanyakan untuk menghindari hardcoding, atau untuk menjaga agar kompetisi tetap berjalan jika seseorang menemukan penyandian yang sempurna secara matematis; ini mungkin merupakan faktor minimal jika tidak) total jumlah byte dalam pengiriman Anda ke tantangan (ditambah hukuman standar untuk hal-hal seperti memerlukan bendera juru bahasa yang tidak biasa atau nama file tertentu). Pemenangnya adalah entri dengan skor terendah (tiebroken oleh entri pertama yang dikirimkan).

CJam, skor ≤ 286.516 + 54 + 36 = 286.606

Encoder

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

Cobalah online!

Dekoder

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

Cobalah online!

Keduanya mengambil dan mengembalikan daftar bilangan bulat. TIO Link menyertakan konversi dari / ke string untuk kenyamanan. Perhatikan bahwa ini sangat tidak efisien untuk string yang lebih lama. Jika Anda ingin mencoba beberapa karakter lagi, saya sarankan menggunakan karakter dengan kode karakter kecil.

Gagasan dasar untuk membuat pengkodean yang diperkuat radiasi melibatkan dua langkah:

1. Temukan penyandian yang tidak pernah berisi dua oktet identik berturut-turut.
2. Ulangi setiap oktet dalam string yang disandikan r + 1 kali, di mana r adalah tingkat radiasi.

Dengan cara ini, radiasi tidak dapat sepenuhnya menghapus satu run karakter yang identik, sehingga kita dapat mendekode string dengan mengambil satu karakter dari setiap run dan kemudian mendekode langkah 1.

Jadi satu-satunya bagian yang menarik adalah menemukan pengkodean yang tidak pernah menghasilkan oktet berulang. Ide dasarnya adalah menggunakan sesuatu seperti A043096 sebagai sistem angka. Artinya, untuk menyandikan bilangan bulat N , kita cukup menghitung dalam beberapa basis b , melewatkan semua angka dengan oktet berulang. Saya percaya jumlah angka yang dapat direpresentasikan dengan cara ini dengan hingga d digit sama dengan jumlah angka yang dapat direpresentasikan dalam basis bijektif b-1 (karena, ketika Anda ingin menulis angka seperti itu, Anda dapat pilih antara b-1 digit untuk setiap posisi tanpa melanggar batasan).

Tentu saja, untuk mendapatkan kompresi maksimal kita akan menggunakan b = 256 . Untuk mengubah input menjadi bilangan bulat, kita dapat menggunakan konversi basis juga. Jika saya tidak malas, saya akan menggunakan basis kata sifat untuk input, tetapi untuk sekarang saya hanya menambahkan a1 (untuk memastikan tidak ada nol di depan) dan kemudian menggunakan basis terkecil yang mungkin sehingga semua oktet di input kurang dari basis.

Basis ini kemudian didahului dengan pengkodean (sehingga decoder mengetahui basis mana yang digunakan) dan dipisahkan dari angka yang tersisa dengan 0-oktet (ini bekerja karena angka yang tersisa tidak akan pernah mulai dengan nol). Sebagai optimasi kecil, string kosong tetap merupakan string kosong.

Alasan saya belum menghitung skor tepat di atas adalah bahwa saya hanya menghitung batas atas untuk berapa lama setiap input akan didasarkan pada panjang dan oktet maksimalnya. Namun, untuk dua parameter ini, sering kali akan ada dua panjang output yang berbeda, dan saya belum repot mencari tahu di mana titik kritis di antara mereka terjadi. Saya juga menggunakan panjang basis biasa 255 daripada basis bijektif 255 untuk memperkirakan panjang itu, yang lagi-lagi sedikit lebih besar dari yang seharusnya. Kode Mathematica persis yang saya gunakan untuk perhitungan adalah sebagai berikut:

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]harus memberikan jumlah string panjang ldengan oktet maksimum b-1(kecuali untuk b == 1, di mana saya telah hardcode 0karena saya selalu menggunakan setidaknya pangkalan 2).

bash + Utilitas GNU, skor 294506 283468

Sunting 1: Memperbaiki masalah yang diperhatikan oleh @Leo - terima kasih!

Sunting 2: Memperbaiki metode pengkodean untuk parameter radiasi, untuk skor yang lebih baik.

Pengkode (97 byte):

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 byte):

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

Untuk pembuat enkode: Urutan oktet dilewatkan sebagai karakter dalam stdin, parameter radiasi r dilewatkan sebagai argumen.

Untuk dekoder: Input diberikan sebagai karakter di stdin.

Untuk keduanya: Output pada stdout.

Pembuat enkode menambahkan ke dalam data input digit r, dengan karakter 'a' dimasukkan di antara setiap pasangan digit identik berturut-turut, diikuti oleh satu baris baru. Kemudian salin semua input (dimulai dengan karakter yang diawali), mengganti setiap karakter dengan r +1 salinan karakter itu.

Decoder membatalkan ini, melalui masing-masing karakter yang tersisa x dalam inputnya, melompati hingga r salinan identik berturut-turut dari x berikut x, dan mencetak yang tersisa. Data yang digantung sebelumnya tidak memiliki karakter yang diulang, sehingga dapat didekodekan sebelum r diketahui. Pada titik itu, r diketahui, dan nilai itu diperlukan untuk memecahkan kode sisa data dengan benar.

Anda dapat memeriksa apakah ini berfungsi bahkan jika input asli telah mengulangi karakter yang sama.

Perhitungan skor:

Misalkan input memiliki panjang L dan parameter radiasi adalah r (yang paling banyak 9 untuk perhitungan skor, sehingga cocok dalam satu digit dan karenanya tidak memiliki karakter yang diulang berturut-turut). Data yang ditambahkan adalah 2 byte (digit, baris baru), sehingga outputnya adalah (r + 1) (L + 2) byte untuk aliran yang disandikan.

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

Oleh karena itu skor total dapat dihitung sebagai

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

Gambar kontrol digunakan untuk mewakili karakter kontrol yang sesuai (mis ␀ Adalah karakter NUL literal). Jangan terlalu khawatir tentang mencoba membaca kode; ada versi yang lebih mudah dibaca di bawah ini.

Jalankan dengan -Mbigint -MMath::ModInt=mod -MMath::Polynomial -MNtheory=:all.-MMath::Bigint=lib,GMPtidak perlu (dan dengan demikian tidak termasuk dalam skor), tetapi jika Anda menambahkannya sebelum perpustakaan lain itu akan membuat program berjalan agak lebih cepat.

Perhitungan skor

Algoritme di sini agak dapat diperbaiki, tetapi akan lebih sulit untuk menulis (karena Perl tidak memiliki perpustakaan yang sesuai). Karena itu, saya membuat beberapa ukuran / efisiensi pengorbanan dalam kode, dengan dasar bahwa mengingat byte dapat disimpan dalam pengkodean, tidak ada gunanya mencoba mencukur setiap titik dari golf.

Program ini terdiri dari 600 byte kode, ditambah 78 byte hukuman untuk opsi baris perintah, memberikan hukuman 678 poin. Sisa skor dihitung dengan menjalankan program pada string kasus terbaik dan terburuk (dalam hal panjang output) untuk setiap panjang dari 0 hingga 99 dan setiap tingkat radiasi dari 0 hingga 9; kasus rata-rata ada di antara keduanya, dan ini memberi batasan pada skor. (Tidak ada gunanya mencoba menghitung nilai yang tepat kecuali entri lain masuk dengan skor yang sama.)

Oleh karena itu, ini berarti bahwa skor dari efisiensi pengkodean berada dalam kisaran 91100 hingga 92141 inklusif, sehingga skor akhirnya adalah:

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

Versi kurang golf, dengan komentar dan kode uji

Ini adalah program asli + baris baru, lekukan, dan komentar. (Sebenarnya, versi golf diproduksi dengan menghapus baris baru / lekukan / komentar dari versi ini.)

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;

Algoritma

Menyederhanakan masalah

Ide dasarnya adalah untuk mengurangi masalah "penghapusan kode" ini (yang bukan merupakan masalah yang banyak dieksplorasi) menjadi masalah pengkodean penghapusan (area matematika yang dieksplorasi secara komprehensif). Gagasan di balik pengkodean penghapusan adalah bahwa Anda menyiapkan data untuk dikirim melalui "saluran penghapusan", saluran yang terkadang menggantikan karakter yang dikirim dengan karakter "memutarbalikkan" yang menunjukkan posisi kesalahan yang diketahui. (Dengan kata lain, selalu jelas di mana korupsi telah terjadi, meskipun karakter aslinya masih belum diketahui.) Gagasan di balik itu cukup sederhana: kami membagi input menjadi beberapa blok panjang ( radiasi+1, dan menggunakan tujuh dari delapan bit di setiap blok untuk data, sedangkan bit yang tersisa (dalam konstruksi ini, MSB) bergantian antara ditetapkan untuk seluruh blok, kosong untuk seluruh blok berikutnya, ditetapkan untuk blok setelah itu, dan seterusnya. Karena blok lebih panjang dari parameter radiasi, setidaknya satu karakter dari setiap blok bertahan ke output; jadi dengan menjalankan karakter dengan MSB yang sama, kita dapat mengetahui blok mana yang dimiliki masing-masing karakter. Jumlah blok juga selalu lebih besar dari parameter radiasi, jadi kami selalu memiliki setidaknya satu blok tidak rusak di encdng; kita dengan demikian tahu bahwa semua blok yang terpanjang atau terikat paling lama tidak rusak, memungkinkan kita untuk memperlakukan blok yang lebih pendek sebagai yang rusak (sehingga menjadi puing-puing). Kami juga dapat menyimpulkan parameter radiasi seperti ini (itu '

Penghapusan coding

Adapun bagian pengkodean penghapusan masalah, ini menggunakan kasus khusus sederhana dari konstruksi Reed-Solomon. Ini adalah konstruksi yang sistematis: output (dari algoritma pengkodean penghapusan) sama dengan input ditambah sejumlah blok tambahan, sama dengan parameter radiasi. Kita dapat menghitung nilai-nilai yang diperlukan untuk blok ini dengan cara yang sederhana (dan golf!), Dengan memperlakukannya sebagai kerusakan, kemudian menjalankan algoritma penguraian kode pada mereka untuk "merekonstruksi" nilai mereka.

Gagasan sebenarnya di balik konstruksi juga sangat sederhana: kami memuat polinomial, dengan derajat minimum yang mungkin, untuk semua blok dalam pengkodean (dengan krik yang diinterpolasi dari elemen lain); jika polinomialnya adalah f , blok pertama adalah f (0), yang kedua adalah f (1), dan seterusnya. Jelas bahwa derajat polinomial akan sama dengan jumlah blok input minus 1 (karena kami memasukkan polinomial dengan yang pertama, kemudian menggunakannya untuk membangun blok "periksa" tambahan); dan karena d +1 poin secara unik mendefinisikan polinomial derajat d, memutarbalikkan sejumlah blok (hingga parameter radiasi) akan meninggalkan sejumlah blok yang tidak rusak sama dengan input asli, yang merupakan informasi yang cukup untuk merekonstruksi polinomial yang sama. (Kemudian kita hanya perlu mengevaluasi polinomial untuk memisahkan blok.)

Konversi basis

Pertimbangan terakhir yang tersisa di sini adalah berkaitan dengan nilai aktual yang diambil oleh blok; jika kita melakukan interpolasi polinomial pada bilangan bulat, hasilnya mungkin bilangan rasional (bukan bilangan bulat), jauh lebih besar dari nilai input, atau sebaliknya tidak diinginkan. Karena itu, alih-alih menggunakan bilangan bulat, kami menggunakan bidang terbatas; dalam program ini, bidang hingga yang digunakan adalah bidang bilangan bulat modulo p , di mana p adalah bilangan prima terbesar kurang dari 128 ^{radiasi +1}(Yaitu prime terbesar yang kami dapat mencocokkan sejumlah nilai berbeda sama dengan prime itu ke dalam bagian data blok). Keuntungan besar bidang hingga adalah pembagian itu (kecuali 0) didefinisikan secara unik dan akan selalu menghasilkan nilai di dalam bidang itu; dengan demikian, nilai interpolasi polinomial akan masuk ke dalam blok sama seperti yang dilakukan oleh nilai input.

Untuk mengubah input menjadi serangkaian data blok, maka, kita perlu melakukan konversi basis: mengkonversi input dari basis 256 menjadi angka, kemudian mengkonversi menjadi basis p (misalnya untuk parameter radiasi 1, kita harus p= 16381). Ini sebagian besar ditangguhkan oleh kurangnya rutinitas konversi basis (Math :: Prime :: Util memiliki beberapa, tetapi mereka tidak bekerja untuk basis bignum, dan beberapa bilangan prima yang bekerja dengan kami di sini sangat besar). Karena kita sudah menggunakan Math :: Polynomial untuk interpolasi polinomial, saya dapat menggunakannya kembali sebagai fungsi "convert from digit sequence" (melalui melihat angka sebagai koefisien dari polinomial dan mengevaluasinya), dan ini berfungsi untuk bignum baik baik saja. Akan tetapi, saya harus menulis sendiri fungsinya. Untungnya, tidak terlalu sulit (atau bertele-tele) untuk menulis. Sayangnya, konversi basis ini berarti bahwa input biasanya tidak dapat dibaca. Ada juga masalah dengan nol terkemuka;

Perlu dicatat bahwa kita tidak dapat memiliki lebih dari p blok dalam output (jika tidak, indeks dua blok akan menjadi sama, namun mungkin perlu menghasilkan output yang berbeda dari polinomial). Ini hanya terjadi ketika input sangat besar. Program ini memecahkan masalah dengan cara yang sangat sederhana: meningkatkan radiasi (yang membuat blok lebih besar dan p jauh lebih besar, artinya kita dapat memasukkan lebih banyak data, dan yang jelas mengarah pada hasil yang benar).

Satu hal lagi yang layak untuk dibuat adalah bahwa kita menyandikan string nol ke dirinya sendiri, karena program seperti yang tertulis akan menabraknya. Ini juga jelas pengkodean terbaik, dan bekerja tidak peduli apa parameter radiasi.

Peningkatan potensial

Inefisiensi asimtotik utama dalam program ini adalah berkaitan dengan penggunaan modulo-prime sebagai bidang hingga yang dimaksud. Hingga bidang ukuran 2 ⁿ ada (yang persis apa yang kita inginkan di sini, karena ukuran muatan blok 'secara alami kekuatan 128). Sayangnya, mereka agak lebih kompleks daripada konstruksi modulo sederhana, artinya Math :: ModInt tidak akan memotongnya (dan saya tidak bisa menemukan perpustakaan di CPAN untuk menangani bidang terbatas ukuran non-prime); Saya harus menulis seluruh kelas dengan aritmatika kelebihan muatan untuk Matematika :: Polinomial untuk dapat menanganinya, dan pada saat itu biaya byte mungkin berpotensi melebihi kerugian (sangat kecil) dari penggunaan, misalnya, 16381 daripada 16384.

Keuntungan lain menggunakan ukuran power-of-2 adalah bahwa konversi basis akan menjadi lebih mudah. Namun, dalam kedua kasus tersebut, metode yang lebih baik untuk merepresentasikan panjang input akan bermanfaat; metode "tambahkan 1 dalam kasus ganda" sederhana namun boros. Konversi basis bijektif adalah salah satu pendekatan yang masuk akal di sini (idenya adalah Anda memiliki basis sebagai digit, dan 0 sebagai bukan digit, sehingga setiap angka berhubungan dengan satu string).

Meskipun kinerja asimptotik dari pengkodean ini sangat baik (misalnya untuk input dengan panjang 99 dan parameter radiasi 3, pengkodean selalu panjang 128 byte, daripada ~ 400 byte yang didapat dari pendekatan berbasis pengulangan), kinerjanya kurang baik pada input pendek; panjang encoding selalu setidaknya kuadrat dari (parameter radiasi + 1). Jadi untuk input yang sangat pendek (panjang 1 hingga 8) pada radiasi 9, panjang output tetap 100. (Pada panjang 9, panjang output kadang-kadang 100 dan kadang-kadang 110.) Pendekatan berbasis pengulangan jelas mengalahkan penghapusan ini. pendekatan berbasis-kode pada input yang sangat kecil; mungkin perlu diubah di antara beberapa algoritma berdasarkan ukuran input.

Akhirnya, itu tidak benar-benar muncul dalam penilaian, tetapi dengan parameter radiasi yang sangat tinggi, menggunakan sedikit setiap byte (⅛ dari ukuran output) untuk membatasi blok boros; akan lebih murah untuk menggunakan pembatas antar blok saja. Merekonstruksi blok dari pembatas agak lebih sulit daripada dengan pendekatan bolak-MSB, tapi saya percaya itu mungkin, setidaknya jika datanya cukup panjang (dengan data pendek, bisa sulit untuk menyimpulkan parameter radiasi dari output) . Itu akan menjadi sesuatu untuk dilihat jika bertujuan untuk pendekatan ideal asimptotik terlepas dari parameter.

(Dan tentu saja, mungkin ada algoritma yang sama sekali berbeda yang menghasilkan hasil yang lebih baik daripada yang ini!)