LRC

LRC (сокр. от англ. _Longest Run of Consecutive_ — «самый длинный непрерывный ряд») — это алгоритмическая задача, а также метрика, используемая в теории кодирования, криптографии, анализе данных и проверке целостности информации. В общем смысле LRC обозначает максимальную длину последовательности одинаковых битов, символов или элементов в заданном наборе данных. В контексте коррекции ошибок (например, в RAID-массивах или кодах Рида — Соломона) термин LRC может также обозначать _Local Reconstruction Code_ — локальный код восстановления, используемый для повышения отказоустойчивости распределённых систем хранения данных.

История и происхождение термина

Понятие «самый длинный непрерывный ряд» впервые было формализовано в середине XX века в рамках теории информации и комбинаторики. В 1948 году Клод Шеннон в своей работе «Математическая теория связи» использовал аналогичные метрики для анализа избыточности и энтропии источников сообщений. В 1950-х годах задача LRC стала применяться в криптоанализе для оценки случайности последовательностей (например, в тестах на «рандомность» по критерию «длинных серий»).

В области хранения данных термин LRC как _Local Reconstruction Code_ был предложен в 2010-х годах исследователями из Microsoft Research и Google для повышения эффективности работы с большими распределёнными системами (например, в файловых системах HDFS и Azure). В отличие от классических кодов с максимальным расстоянием (MDS), LRC позволяет восстанавливать потерянные данные с меньшими накладными расходами на чтение.

Классификация

По области применения

1. Алгоритмическая задача LRC — вычисление максимальной длины непрерывной последовательности одинаковых элементов в строке, массиве или потоке данных. Используется в сжатии данных (например, в алгоритме RLE — Run-Length Encoding), в тестировании случайности (тест на серии), в биоинформатике (анализ повторов в ДНК).
2. Метрика LRC в криптографии — критерий оценки качества генераторов псевдослучайных чисел. Чем меньше LRC для заданной длины выборки, тем более случайной считается последовательность.
3. Код LRC (Local Reconstruction Code) — код коррекции ошибок, используемый в системах хранения данных (RAID, распределённые файловые системы). Позволяет восстанавливать один или несколько потерянных блоков данных, обращаясь к меньшему числу узлов, чем при использовании классических кодов (например, кода Рида — Соломона).

По типу данных

• Бинарный LRC — для последовательностей битов (0 и 1).
• Символьный LRC — для строк текста, где элементы могут быть буквами, цифрами или знаками.
• Числовой LRC — для последовательностей чисел (например, в задачах машинного обучения).

Алгоритмы вычисления LRC

Простейший алгоритм для строки

Для нахождения LRC в одномерном массиве (строке) используется линейный проход:

1. Инициализация: max_len = 0, current_len = 1.
2. Для каждого элемента i от 1 до n-1:

• Если array[i] == array[i-1], то current_len++.
• Иначе: max_len = max(max_len, current_len), current_len = 1.

1. После цикла: max_len = max(max_len, current_len).

Сложность: O(n) по времени, O(1) по памяти.

Оптимизированные методы

• Для потоковых данных (бесконечные последовательности) — использование скользящего окна.
• Для многомерных массивов (например, изображений) — поиск LRC по строкам, столбцам или диагоналям.
• В параллельных вычислениях (CUDA, OpenMP) — разделение массива на блоки с последующим слиянием результатов.

Применение

В сжатии данных

LRC лежит в основе алгоритма RLE (Run-Length Encoding), который заменяет повторяющиеся символы на пару «значение — длина серии». Например, строка AAAABBBCC кодируется как A4B3C2. RLE широко применяется в форматах изображений (BMP, PCX) и в факсимильной связи.

В криптографии и тестировании случайности

Тест на серии (англ. _Runs test_) — один из статистических тестов для проверки гипотезы о случайности последовательности. Вычисляется LRC для битовой строки, и если он превышает пороговое значение (например, для 1000 бит — более 20 одинаковых бит подряд), последовательность считается недостаточно случайной. Этот тест входит в набор NIST SP 800-22.

В системах хранения данных (LRC-коды)

В распределённых файловых системах (например, в Windows Azure Storage, Facebook f4) LRC-коды используются для уменьшения накладных расходов на восстановление данных. Принцип работы:

• Данные разбиваются на блоки, к которым добавляются избыточные блоки (паритеты).
• LRC-код делит блоки на локальные группы, внутри которых можно восстановить потерянный блок, обратившись только к блокам этой группы (а не ко всем блокам, как в коде Рида — Соломона).
• Это снижает сетевой трафик и задержки при сбоях.

Пример: для 12 блоков данных и 4 избыточных блоков классический код Рида — Соломона требует чтения 12 блоков для восстановления одного потерянного. LRC-код с двумя локальными группами (по 6 блоков) может восстановить блок, прочитав только 6 блоков.

В биоинформатике

LRC используется для анализа повторов в геномных последовательностях. Например, в геноме человека часто встречаются тандемные повторы (например, CAGCAGCAG), и их максимальная длина может указывать на генетические заболевания (например, синдром ломкой X-хромосомы).

Критика и ограничения

• Алгоритмическая задача LRC тривиальна для одномерных массивов, но для многомерных данных (например, в обработке изображений) поиск LRC по всем направлениям может быть вычислительно затратным.
• LRC-коды в системах хранения данных имеют ограничение: они менее эффективны при большом числе одновременных сбоев (например, при отказе нескольких узлов в распределённой системе). В таких случаях требуется комбинирование с другими кодами (например, с кодами Рида — Соломона).
• Тест на серии может давать ложноположительные результаты для последовательностей, которые на самом деле случайны, но имеют длинные серии из-за особенностей распределения (например, в биномиальном распределении).

Интересные факты

• В 2012 году в файловой системе Windows Azure Storage был внедрён LRC-код, который позволил сократить накладные расходы на восстановление данных на 50–70% по сравнению с классическим кодом Рида — Соломона.
• В криптографии максимальная длина серии (LRC) используется в тесте «Runs Test» из набора NIST SP 800-22, который является обязательным для сертификации генераторов случайных чисел в США.
• В биологии LRC для повторов нуклеотидов может достигать нескольких тысяч для некоторых участков ДНК (например, в теломерах).

Источники

• Shannon, C. E. (1948). «A Mathematical Theory of Communication». _Bell System Technical Journal_.
• NIST Special Publication 800-22 (2010). «A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications».
• Huang, C., et al. (2012). «Erasure Coding in Windows Azure Storage». _USENIX ATC_.
• M. Luby, M. Mitzenmacher, M. A. Shokrollahi, D. A. Spielman (2001). «Efficient Erasure Correcting Codes». _IEEE Transactions on Information Theory_.
• «Run-length encoding». _Encyclopedia of Computer Science_.