ЯдроКодаподготовка к экзаменам
Подготавливаем текст, источники и редакционные примечания без изменения разметки страницы.
Автор: Казачкин Даниил Михайлович · Обновлено
DNA Fountain через восстановление потерянных блоков: свой XOR-декодер на Python, фильтрация строк ДНК и разница между потерей и повреждением данных.
Записать нули и единицы четырьмя буквами A, C, G, T можно в несколько строк программы. Но такая перекодировка ещё не создаёт надёжный накопитель. При физической записи и чтении часть последовательностей может отсутствовать, порядок прочтения не сохраняется, а прочитанные буквы иногда содержат ошибки. Научный вопрос DNA Fountain — как согласовать кодирование данных с этим каналом, чтобы восстановить исходные байты.
Этот разбор посвящён алгоритмической стороне хранения. Пример ниже работает с целыми числами и строками и не включает синтез ДНК, лабораторные действия или обработку генетических данных. Его результат — восстановленное учебное слово и проверка границы, после которой простой декодер останавливается.
Yaniv Erlich и Dina Zielinski опубликовали работу в Science 3 марта 2017 года. В DNA Fountain файл делится на блоки; droplet содержит XOR выбранных блоков и seed, позволяющий восстановить их выбор. Двоичные данные переводятся в основания, а неподходящие по GC-составу и длине повторов последовательности отбрасываются до физической записи. Можно создавать новые droplets, пока подходящих не станет достаточно. В опыте использованы 67 088 блоков по 32 байта и 72 000 олигонуклеотидов; служебные данные включали seed и код Reed–Solomon. После чтения исходный файл был восстановлен без ошибок. Полный текст опубликованной статьи в университетском архиве, библиографическая запись.
Ключевая идея для программиста: вместо требования сохранить каждый исходный блок передаются дополнительные уравнения, связывающие блоки. Если некоторые уравнения потеряны, оставшихся может хватить. Но избыток количества сам по себе недостаточен: уравнения должны давать независимую полезную информацию.
Пусть исходные байты обозначены A, B и C. Получив A и A XOR B, можно вычислить B. Если затем приходит B XOR C, восстанавливается C. Потеря отдельного пакета означает отсутствие уравнения. Повреждённый пакет хуже: он может выглядеть как корректное уравнение и привести к неверному восстановлению сразу нескольких байтов.
Поэтому на схеме системы нужно различать обнаружение ошибок внутри прочтённого сообщения и восстановление недостающих сообщений. При объяснении нельзя приписывать обе способности одному XOR. В репозитории авторов отдельно показаны подготовка прочтений, параметры проверки droplets и окончательная сверка восстановленного файла. Авторы также предупреждают, что исходный код относится к старой Python-среде; мы не выдаём его команды за готовую инструкцию для современного Python.
Сначала проверим ограничение алфавита на собственном примере. Каждые два бита отображаются в одно основание. Строка из одних нулей превращается в длинную цепочку A. Функция acceptable отбрасывает длинные повторы и крайний GC-состав по нашим учебным порогам. Это демонстрация отбора строк, а не модель химической пригодности и не полное воспроизведение фильтра статьи.
from functools import reduce
from itertools import groupby
from operator import xor
def to_dna(payload):
alphabet = "ACGT"
return "".join(alphabet[(byte >> shift) & 3]
for byte in payload for shift in (6, 4, 2, 0))
def acceptable(dna):
if not dna:
return False
gc = sum(base in "GC" for base in dna) / len(dna)
longest = max(sum(1 for _ in run) for _, run in groupby(dna))
return 0.25 <= gc <= 0.75 and longest <= 3
assert to_dna(bytes([27])) == "ACGT"
assert acceptable(to_dna(bytes([27]) * 4))
assert not acceptable(to_dna(bytes([0]) * 4))
original = b"KODA"
subsets = [{0}, {0, 1}, {1, 2}, {2, 3}, {0, 3}]
packets = [(indices, reduce(xor, (original[i] for i in indices), 0))
for indices in subsets]
def peel(received):
known = {}
pending = [(set(indices), value) for indices, value in received]
while True:
progress = False
next_pending = []
for indices, value in pending:
unknown = indices - known.keys()
for index in indices & known.keys():
value ^= known[index]
if not unknown:
if value != 0:
raise ValueError("Противоречивое уравнение")
elif len(unknown) == 1:
known[next(iter(unknown))] = value
progress = True
else:
next_pending.append((unknown, value))
if not progress:
return known
pending = next_pending
# Пакет {2, 3} потерян; другой путь уравнений всё ещё восстанавливает байт 3.
received = [packet for i, packet in enumerate(packets) if i != 3]
recovered = peel(list(reversed(received)))
assert bytes(recovered[i] for i in range(len(original))) == original
assert peel(packets[1:]) == {} # Без singleton простой peeling не начинает работу.
print(bytes(recovered[i] for i in range(len(original))).decode("ascii"))Программа печатает KODA, хотя один из пяти пакетов удалён, а остальные пришли в обратном порядке. Индексы здесь переданы явно. В полноценной схеме seed и согласованный генератор выбора позволяют не хранить длинный список индексов в каждом сообщении. Наши маленькие множества подобраны вручную; у них нет вероятностных гарантий fountain-кода.
peel ищет уравнение с одной неизвестной, решает его и подставляет результат в остальные. Если ни одного такого уравнения нет, цикл останавливается. Второе утверждение показывает именно остановку этого метода. В общем случае отсутствие singleton ещё не доказывает невозможность решения: другой алгоритм мог бы выполнить исключение переменных. Для конкретных четырёх оставшихся парных уравнений в нашем примере сохраняется неоднозначность: XOR всех исходных байтов с одной и той же маской не меняет ни одного парного уравнения.
Добавление сотни копий одного уравнения эту неоднозначность не исправит. Полезная избыточность определяется связями, а не только количеством строк. Для случайно выбираемых droplets важны распределение числа участвующих блоков и вероятность успешного восстановления при заданных потерях. Один удачный пример с четырьмя байтами ничего не говорит о проценте потерь, который выдержит большой архив.
Обработка противоречий в коде также ограничена. Она обнаруживает только уже проверяемое несогласованное уравнение. Если повреждённые данные согласуются с другой версией исходного файла, peel может её вернуть. Поэтому в настоящем формате нужна независимая проверка целостности всего результата. Наше сравнение с original доступно только потому, что это учебный опыт; получатель архива обычно исходный файл рядом не имеет.
Наше отображение использует две двоичные цифры на основание, поскольку возможны четыре символа. Это верхний счёт для свободного алфавита. Но файл занимает место вместе с индексами, проверочными данными, избыточными droplets и технологическими участками. Сравнение плотностей без перечисления включённых частей вводит в заблуждение даже при безошибочной арифметике.
Посчитайте собственный условный формат: 16 байт полезных данных, 4 байта заголовка и 4 байта проверки на сообщение, затем 25% дополнительных сообщений. До любых других накладных расходов полезная доля будет 16 / 24 / 1.25, то есть около 0,533. При двух битах на символ получается примерно 1,067 полезного бита на символ. Эти числа придуманы для расчёта и не относятся к результатам DNA Fountain.
Физическая плотность в байтах на массу — ещё одна метрика. Она зависит от числа молекулярных копий и возможности прочитать нужные последовательности. Из информационной плотности нельзя напрямую получить ни скорость доступа, ни цену полного хранилища. В корректном инженерном сравнении отдельно задаются время записи, восстановления, доля потерянных данных и стоимость всей процедуры. Лабораторное подтверждение восстановления файла не является сравнительным тестом готового накопителя.
Самостоятельная задача: удалите каждый пакет по очереди и запишите, в каких случаях peel восстановил все четыре байта. Затем добавьте пакет с единственным индексом 2 и повторите опыт. Объясните изменение через граф зависимостей. Наконец, переверните один бит полезной части пакета и проверьте, когда возникает исключение, а когда только финальное сравнение замечает неверный файл. Так различие потери, повреждения и проверки целостности становится наблюдаемым.
Самостоятельный русскоязычный разбор ЯдроКода. Результаты исследований отделены от авторских учебных данных, вычислительных опытов и выводов. Материал не является переводом или перепечаткой.
Учебные данные, расчёты и программные примеры созданы для этой публикации. Изображения, таблицы и программный код первоисточников не воспроизводятся.