Фон

На этом сайте иногда возникают вопросы, требующие, чтобы программы были «радиационно-стойкими»; это означает, что программа должна выдерживать удаление одного или нескольких байтов, независимо от того, какие байты удалены.

Как это часто бывает для задач, которые часто задаются в задачах программирования, естественно, хочется создать язык, который особенно хорош в этих задачах. Учитывая, что естественным способом сделать это является добавление метаданных, позволяющих обратить вспять коррупцию, на самом деле это не язык, требующий проектирования, а кодирование; Идея состоит в том, чтобы преобразовать каждый вход в последовательность байтов таким образом, чтобы, даже если последовательность была слегка облучена, можно было извлечь исходный ввод.

Задание

Напишите две программы или функции, E (кодер) и D (декодер), такие, что:

• E принимает два аргумента, последовательность октетов (которые мы будем называть « вход » в этой спецификации) и неотрицательное целое число « излучение », и выводит последовательность октетов « кодирование »;
• D принимает один аргумент, последовательность октетов (« encdng ») и выводит последовательность октетов « реконструкция »;
• Если вы запустите и E, и D (с encdng , вход для D, выбранный путем удаления не более чем элементов излучения из кодирования (не обязательно непрерывно)), тогда восстановление будет равно вводу независимо от того, какие символы были удалены для формирования encdng .

Разъяснения

• Если вы отправляете функции, вам не нужно вызывать их Eи D; Вы можете выбрать любое имя, наиболее подходящее для вашего языка.
• «Октет» - это, по сути, целое число от 0 до 255 включительно, которое вы можете кодировать как целое число, символ или все, что подходит для вашего языка.
• E и D должны быть полностью детерминированными (т. Е. Предоставление им одинаковых входных данных всегда будет давать один и тот же выходной сигнал, где «входные данные» определены как входные данные и излучение для E или encdng для D). В частности, E может не передавать информацию D через побочный канал.
• Удаление выполняется путем удаления одного элемента последовательности; Подумайте об открытии последовательности в редакторе, расположении курсора в произвольной точке и нажатии Backspace. Если элемент появляется несколько раз, возможно, будет удалена только одна копия элемента (т. Е. Другие экземпляры того же октета не будут затронуты).
• Хотя оценка рассчитывается только на основе довольно короткого ввода , ваша программа должна работать теоретически для любого ввода и излучения . В частности, он должен работать независимо от того, какие октеты появляются при вводе . (Извините, люди, которые хотели бы иметь возможность использовать непечатаемые символы, которые, как они знают, не появятся на входе, но я должен убедиться, что вход несжимаемый, так что проблема заключается в радиационном упрочнении, а не в сжатии.)
• Вы можете отправить либо один файл, который определяет две функции; два файла, каждый из которых определяет функцию или оба являются полными программами; или три файла, два из которых реализуют D и E соответственно (либо через полные программы, либо через определение функции), а третий - файл заголовка или библиотека, общие для D и E. Независимо от того, какую форму представления вы используете Ваша реализация на языке программирования должна понимать обе программы без дополнительных аргументов, таких как расположение файлов (иначе вы должны заплатить штраф за байты за необычный вызов вашей реализации в соответствии с нашими стандартными правилами).

Состояние победы

Для каждой длины и излучения пусть f ( длина , излучение ) будет полной длиной кодирования s, которая соответствует всем входным данным с длиной длины и данному излучению . (То есть f ( длина , излучение ) = сумма _{ввода имеет длину длина} длина (E ( вход , излучение )).) Тогда пусть g ( длина , излучение ) будет равно f ( длина ,излучение ) ÷ 256 ^длина . Другими словами, g - это средняя длина кодированного выхода для заданной длины ввода и заданного требования радиационной стойкости. (Теоретически вы можете рассчитать это методом грубой силы, но, скорее всего, это займет невероятно много времени, чтобы рассчитать ваш счет таким образом. Я ожидаю, что большинство представлений смогут сделать математический аргумент относительно их оценки. Если вы ' Если вы не уверены, опубликуйте приблизительный балл, и вы или кто-то еще можете рассчитать его более подробно, если в другой записи будет аналогичный балл.)

Ваша оценка равна сумме g ( длина , излучение ) для всех излучений в диапазоне от 0 до 9 включительно и для всей длины в диапазоне от 0 до 99 включительно, плюс (в основном, чтобы избежать жесткого кодирования или для продолжения соревнования, если кто-то обнаружит математически совершенную кодировку (в противном случае это, вероятно, будет минимальный фактор) общее количество байтов в вашей подаче на вызов (плюс стандартные штрафы за такие вещи, как требование необычных флагов интерпретатора или конкретных имен файлов). Победителем становится запись с наименьшим количеством баллов (разбитая на первую запись для подачи).

CJam, оценка ≤ 286 516 + 54 + 36 = 286 606

кодировщик

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

Попробуйте онлайн!

дешифратор

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

Попробуйте онлайн!

Оба они берут и возвращают список целых чисел. Ссылки TIO включают преобразование из / в строки для удобства. Обратите внимание, что они невероятно неэффективны для длинных строк. Если вы хотите попробовать еще несколько символов, я рекомендую использовать символы с маленькими кодами символов.

Основная идея создания радиационно-стойкой кодировки состоит из двух этапов:

1. Найдите кодировку, которая никогда не содержит двух последовательных идентичных октетов.
2. Повторите каждый октет в кодированной строке r + 1 раз, где r - уровень излучения.

Таким образом, излучение не может полностью удалить один цикл идентичных символов, поэтому мы можем декодировать строку, беря один символ из каждого цикла, а затем декодировать шаг 1.

Таким образом, единственная интересная часть - это найти кодировку, которая никогда не даст повторяющихся октетов. Основная идея - использовать что-то вроде A043096 в качестве системы счисления. То есть, чтобы закодировать целое число N , мы просто считаем в некоторой базе b , пропуская все числа с повторяющимися октетами. Я полагаю, что количество чисел, которое может быть представлено таким образом с помощью до d цифр, равно количеству чисел, которое может быть представлено в биективном основании b-1 (поскольку, когда вы хотите написать такое число, вы можете выбирайте между цифрами b-1 для каждой позиции, не нарушая ограничения).

Конечно, чтобы получить максимальное сжатие, мы будем использовать b = 256 . Чтобы превратить ввод в целое число, мы также можем использовать базовое преобразование. Если бы я не был ленивым, я бы использовал биективную основу для ввода, но сейчас я просто добавляю 1(чтобы убедиться, что нет ведущих нулей), а затем использую наименьшую возможную базу, чтобы все октеты в вход меньше базового.

Эта база затем добавляется к кодированию (чтобы декодер знал, какую базу использовать) и отделяется от оставшегося числа 0-октетом (это работает, потому что оставшееся число никогда не начинается с нуля). В качестве незначительной оптимизации пустая строка остается пустой строкой.

Причина, по которой я не вычислил точную оценку выше, состоит в том, что я вычисляю только верхнюю границу того, как долго каждый вход будет основан на его длине и максимальном октете. Тем не менее, для этих двух параметров часто будут две разные выходные длины, и я пока не удосужился выяснить, где происходит переломный момент между ними. Я также использовал длину обычного основания 255 вместо биективного основания 255, чтобы оценить эту длину, которая снова немного больше, чем должна быть. Точный код Mathematica, который я использовал для вычисления, следующий:

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]должен дать количество строк длины lс максимальным октетом b-1(за исключением того b == 1, где я жестко запрограммировал его, 0потому что я всегда использую хотя бы основание 2).

утилиты bash + GNU, оценка 294506 283468

Редактировать 1: исправляет проблему, замеченную @Leo - спасибо!

Редактировать 2: Улучшен метод кодирования для параметра излучения, для лучшей оценки.

Кодировщик (97 байт):

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

Декодер (121 байт):

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

Для кодера: последовательность октетов, переданная в виде символов в stdin, параметр излучения r, переданный в качестве аргумента.

Для декодера: ввод передается как символы в stdin.

Для обоих: вывод на стандартный вывод.

Кодировщик добавляет к входным данным цифры r, причем между каждой парой последовательных идентичных цифр вставляется символ «a», за которым следует одна новая строка. Затем он копирует все введенные данные (начиная с предварительно добавленных символов), заменяя каждый символ на r + 1 копию этого символа.

Декодер отменяет это, просматривая каждый из оставшихся символов x на своем входе, пропуская до r последовательных идентичных копий x после x и печатая то, что осталось. Предварительно добавленные данные не имеют повторяющихся символов, поэтому их можно декодировать до того, как станет известно r. В этот момент r известно, и это значение необходимо для правильного декодирования остальных данных.

Вы можете проверить, что это работает, даже если исходный ввод повторял одинаковые символы.

Расчет баллов:

Предположим, что вход имеет длину L и параметр излучения равен r (что не более 9 для вычисления оценки, поэтому он умещается в одну цифру и поэтому не имеет последовательных повторяющихся символов). Предварительно добавленные данные имеют размер 2 байта (цифра, новая строка), поэтому выходные данные для кодированного потока (r + 1) (L + 2) байта.

Итак, g (L, r) = (r + 1) (L + 2).

Отсюда следует, что общий балл может быть рассчитан как

Perl + Math :: {ModInt, Polynomial, Prime :: Util}, оценка ≤ 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/^␁//;$_}

Управляющие изображения используются для представления соответствующего управляющего символа (например ␀, это буквенный символ NUL). Не беспокойтесь о попытке прочитать код; Ниже приведена более читаемая версия.

Беги с -Mbigint -MMath::ModInt=mod -MMath::Polynomial -MNtheory=:all. -MMath::Bigint=lib,GMPне является необходимым (и поэтому не включается в счет), но если вы добавите его раньше других библиотек, это заставит программу работать несколько быстрее.

Расчет балла

Алгоритм здесь несколько улучшен, но его будет сложнее написать (из-за того, что в Perl нет соответствующих библиотек). Из-за этого я сделал пару компромиссов между размером и эффективностью в коде, исходя из того, что, учитывая, что байты могут быть сохранены в кодировке, нет смысла пытаться сбить каждую точку с игры в гольф.

Программа состоит из 600 байтов кода плюс 78 байтов штрафов за параметры командной строки, что дает штраф в 678 баллов. Оставшаяся часть балла была рассчитана путем запуска программы для строки наилучшего и наихудшего (с точки зрения длины вывода) значений для каждой длины от 0 до 99 и каждого уровня излучения от 0 до 9; средний случай находится где-то посередине, и это дает оценки на счет. (Не стоит пытаться вычислить точное значение, если не появится другая запись с аналогичным счетом.)

Следовательно, это означает, что оценка эффективности кодирования находится в диапазоне от 91100 до 92141 включительно, поэтому окончательная оценка составляет:

91100 + 600 + 78 = 91778 ≤ оценка ≤ 92819 = 92141 + 600 + 78

Версия для гольфа с комментариями и тестовым кодом

Это оригинальная программа + переводы строк, отступы и комментарии. (На самом деле, версия для гольфа была создана путем удаления новых строк / отступов / комментариев из этой версии.)

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;

Алгоритм

Упрощение проблемы

Основная идея состоит в том, чтобы свести эту проблему «кодирования удаления» (которая не является широко исследованной) к проблеме кодирования стирания (всесторонне изученной области математики). Идея кодирования стирания заключается в том, что вы готовите данные для отправки по «каналу стирания», каналу, который иногда заменяет отправляемые символы «искаженным» символом, который указывает на известную позицию ошибки. (Другими словами, всегда ясно, где произошло искажение, хотя первоначальный персонаж все еще неизвестен.) Идея, лежащая в основе этого, довольно проста: мы разделяем входные данные на блоки длины ( излучение+ 1) и использовать семь из восьми битов в каждом блоке для данных, в то время как оставшийся бит (в этой конструкции, MSB) чередуется между установленным для всего блока, очищенным для всего следующего блока, установленным для блока после этого и так далее. Поскольку блоки длиннее, чем параметр излучения, по крайней мере один символ из каждого блока остается на выходе; поэтому, взяв серии символов с одним и тем же MSB, мы можем определить, к какому блоку принадлежит каждый символ. Количество блоков также всегда больше, чем параметр излучения, поэтому у нас всегда есть хотя бы один неповрежденный блок в encdng; таким образом, мы знаем, что все блоки, которые являются самыми длинными или связаны с самыми длинными, не имеют повреждений, что позволяет нам рассматривать любые более короткие блоки как поврежденные (таким образом, мусор). Мы также можем вывести параметр излучения следующим образом:

Стирание кодирования

Что касается части проблемы, связанной с кодированием стирания, то здесь используется простой частный случай конструкции Рида-Соломона. Это систематическая конструкция: выходной сигнал (алгоритма кодирования стирания) равен входному значению плюс количество дополнительных блоков, равных параметру излучения. Мы можем вычислить значения, необходимые для этих блоков, простым (и гольфистским!) Способом, обрабатывая их как искаженные объекты, а затем запуская алгоритм декодирования для них, чтобы «восстановить» их значение.

Реальная идея построения также очень проста: мы подгоняем полином минимально возможной степени ко всем блокам кодирования (с искажением, интерполированным из других элементов); если многочлен f , первый блок f (0), второй f (1) и т. д. Понятно, что степень многочлена будет равна количеству входных блоков минус 1 (потому что сначала мы подгоняем полином к ним, а затем используем его для построения дополнительных «проверочных» блоков); и потому, что d +1 баллов однозначно определяют многочлен степени dпри искажении любого количества блоков (вплоть до параметра излучения) количество неповрежденных блоков останется равным исходному вводу, что достаточно для восстановления одного и того же полинома. (Тогда мы просто должны оценить многочлен, чтобы разгрузить блок.)

Базовая конверсия

Последнее оставленное здесь соображение связано с фактическими значениями, взятыми блоками; если мы выполняем полиномиальную интерполяцию по целым числам, результаты могут быть рациональными числами (а не целыми числами), намного большими, чем входные значения, или иным образом нежелательными. Таким образом, вместо использования целых чисел мы используем конечное поле; в этой программе используемое конечное поле представляет собой поле целых чисел по модулю p , где p - наибольшее простое число, меньшее 128 ^{излучения +1}(т. е. наибольшее простое число, для которого мы можем поместить несколько различных значений, равных этому простому числу, в часть данных блока). Большим преимуществом конечных полей является то, что деление (кроме 0) определяется однозначно и всегда будет давать значение в этом поле; таким образом, интерполированные значения полиномов будут помещаться в блок точно так же, как и входные значения.

Чтобы преобразовать входные данные в серию блочных данных, нам нужно выполнить базовое преобразование: преобразовать входные данные из базового 256 в число, а затем преобразовать в базовое p (например, для параметра излучения 1 мы имеем p= 16381). В основном это было вызвано отсутствием в Perl подпрограмм преобразования баз (у Math :: Prime :: Util есть некоторые, но они не работают для баз bignum, и некоторые простые числа, с которыми мы здесь работаем, невероятно велики). Поскольку мы уже используем Math :: Polynomial для полиномиальной интерполяции, я смог использовать его как функцию «преобразования из последовательности цифр» (просматривая цифры как коэффициенты полинома и оценивая его), и это работает для больших чисел просто хорошо. Если пойти по другому пути, мне пришлось написать эту функцию самому. К счастью, это не слишком сложно (или многословно), чтобы написать. К сожалению, это базовое преобразование означает, что входные данные обычно отображаются нечитаемыми. Есть также проблема с ведущими нулями;

Следует отметить, что у нас не может быть более p блоков в выходных данных (в противном случае индексы двух блоков станут равными, и, тем не менее, возможно, потребуется создать различные выходные данные из полинома). Это происходит только тогда, когда ввод очень велик. Эта программа решает проблему очень простым способом: увеличивая излучение (что делает блоки больше и p намного больше, что означает, что мы можем разместить гораздо больше данных, и которое явно приводит к правильному результату).

Еще одно замечание, которое стоит отметить, - это то, что мы кодируем пустую строку для себя, потому что написанная программа в противном случае вылетит на ней. Это также, несомненно, наилучшее из возможных кодировок, и оно работает независимо от того, какой параметр излучения используется.

Потенциальные улучшения

Основная асимптотическая неэффективность в этой программе связана с использованием по модулю простого числа в качестве рассматриваемых конечных полей. Существуют конечные поля размером 2 ⁿ (это именно то, что мы хотели бы здесь, потому что размеры полезной нагрузки блоков, естественно, имеют степень 128). К сожалению, они скорее более сложны, чем простая конструкция по модулю, а это означает, что Math :: ModInt не будет его резать (и я не смог найти никаких библиотек на CPAN для обработки конечных полей не простых размеров); Мне нужно было бы написать целый класс с перегруженной арифметикой для Math :: Polynomial, чтобы иметь возможность его обрабатывать, и в этот момент стоимость байтов может потенциально перевесить (очень малую) потерю от использования, например, 16381, а не 16384.

Другое преимущество использования размеров степени 2 состоит в том, что базовое преобразование станет намного проще. Однако в любом случае был бы полезен лучший способ представления длины входных данных; метод «добавить 1 в неоднозначных случаях» прост, но расточителен. Биективное преобразование базы - один из возможных подходов (идея состоит в том, что у вас есть база в виде цифры, а 0 - не цифра, так что каждое число соответствует одной строке).

Хотя асимптотическая производительность этого кодирования очень хорошая (например, для входа длиной 99 и параметра излучения 3, кодирование всегда имеет длину 128 байтов, а не ~ 400 байтов, которые могут получить подходы, основанные на повторениях), его производительность менее хорош на коротких входах; длина кодирования всегда равна как минимум квадрату (параметр излучения + 1). Таким образом, для очень коротких входов (длина от 1 до 8) в излучении 9 длина выхода, тем не менее, равна 100. (При длине 9 длина выходного сигнала иногда составляет 100, а иногда и 110.) Подходы, основанные на повторениях, явно превосходят это стирание. -подход на основе кодирования на очень маленьких входах; возможно, стоило бы переключаться между несколькими алгоритмами в зависимости от размера ввода.

Наконец, это не совсем подходит для оценки, но при очень высоких параметрах излучения использование каждого байта (size выходного размера) для разделения блоков является расточительным; вместо этого было бы дешевле использовать разделители между блоками. Реконструировать блоки из разделителей довольно сложно, чем при использовании метода чередующихся MSB, но я считаю, что это возможно, по крайней мере, если данные достаточно длинные (при коротких данных может быть сложно вывести параметр излучения из выходного сигнала) , Это было бы на что посмотреть, если мы стремимся к асимптотически идеальному подходу независимо от параметров.

(И, конечно, может быть совершенно другой алгоритм, который дает лучшие результаты, чем этот!)