Методика статистичного тестування: Технічний звіт ІІТ – 001-2004, страница 14

Тест є тестом на стиск, «заснованим на ідеї Зива про те, що універсальний статистичний тест може бути заснований на універсальному алгоритмі кодування. Генератор може пройти тест, якщо і тільки якщо його вихідна послідовність не може бути значно стиснута». Відповідно до Маурера, алгоритм кодування Лемпеля-Зива “здається менш придатним для застосування в якості статистичного тесту”, оскільки здається важким визначити статистику тесту, чий розподіл може бути детермінованим чи апроксимованим.

Для проходження тесту потрібна довга послідовність (порядку 10∙ 2L + 1000∙ 2L  з 6 ≤ L ≤ 16) біт, що розбивається на два відрізки з L – бітних блоків (6 ≤ L ≤ 16), Q (≥ 10∙ 2L ) ініціалізуючих блоків і К (≈ 1000∙ 2L ) тестових блоки. Вибирають К = max (n / L) – Q для максимізації даної величини. Порядок величини Q повинний бути обраний таким чином, щоб усі можливі L – бітні шаблони зустрічалися в  ініціалізуючих блоках. Тест не придатний для дуже великих значень L, оскільки час ініціалізації L буде рости експоненціально.

Тест . Алгоритм обчислює log2 усіх таких відстаней для всіх L – бітних шаблонів у тестовому сегменті (які дають кількість розрядів у двійковій довжині кожної відстані). Потім він усереднюється над усіма довжинами кількістю тестових блоків.

Алгоритм ефективно працює при індексації динамічної довідкової таблиці, роблячи використання цілочисельного представлення біт складовою частиною блоків шаблонів. Стандартизована версія статистики порівнянна з припустимим рангом стандартної нормальної (Гауссовской) щільністі, що робить використання статистик тесту середньою величиною, представленою формулою (16) у [8]:

Очікуваним значенням статистики тесту fn є випадкова величина , де G = GL – геометрична випадкова величина з параметром 1 – 2-L.

Існує кілька версій емпіричних формул для дисперсії виду

Var(fn) = c(L, K) Var(log2 G) / K,

де c(L, K) – коефіцієнт залежності входжень від шаблонів. Апроксимація має вид:

Вихідна послідовність повинна бути розбита на r (r ≤ 20) підстрок, для кожної з яких розраховується статистика тесту (при тих же самих значеннях параметрів K, L і Q). Розраховується дисперсія вибірки, Р-значення має вид

Приклад.

Вхід: e = 010110100111010101110,

n = 21,

L = 10,

Q = 4.

Тест:

Ініціалізуючий сегмент:

          en = 01011010.

Заповнюємо таблицю:

          Т0 = 0, Т1 = 2, Т2 = 4, Т3 = 0.

Тестовий сегмент:

          eТ = 011101010111,

          і = 5. Значення блоку = 1,

                    sum = log2(5-2) = 1,5849,

                    Т1 = 5;

і = 6. Значення блоку = 1,

                    sum = 1,5849 + log2(6-0) = 4,1699,

                    Т3 = 6;

          і = 7. Значення блоку = 1,

                    sum = 4,1699 + log2(7-5) = 5,1699,

                    Т1 = 7;

і = 8. Значення блоку = 1,

                    sum = 5,1699 + log2(8-7) = 5,1699,

                    Т1 = 8;

          і = 9. Значення блоку = 1,

                    sum = 5,1699 + log2(9-8) = 5,1699,

                    Т1 = 9;

і = 10. Значення блоку = 3,

                    sum = 5,1699 + log2(10-6) = 7,1699,

                    Т1 = 10;

- тест пройдено.

4.10. Тест Лемпеля-Зива

Даний тест стискає випробувані випадкові послідовності, використовуючи алгоритм Лемпеля-Зива [9]. Якщо стиск статистично значний, коли він порівнюється з теоретично очікуваним результатом, послідовність представляється як невипадкова. При тестуванні генераторів багато послідовностей тестуються саме цим способом. Значення імовірностей обчислюється для кожної послідовності і перевіряється гіпотеза того, що значення імовірностей є рівномірно розподіленими, наприклад, тестом Колмогорова-Смірнова.

Тест Лемпеля-Зива до деякої міри схожий  з частотним тестом, спектральним тестом, може перетинатися з тестом перевірки рангу двійкової матриці. Тест схожий з ентропійним тестом і ще більш схожий з тестом Маурера. Однак, тест спрямовано містить евристичний стиск, що обумовлено сучасною теорією інформації.