> - есть блок некоторых данных > - нужно составить такую последовательность, которая не > встречается в этих данных
Если покажется фуфлом, прошу сильно не бить ! ;)
Пусть есть блок размером N байт. Предположим худшее - в нем все байты очень хорошо псевдослучайные.
Очевидно, почти наверняка последовательность в 1 байт в нем есть.
Оценим вероятность нахождения последовательности в K байт, K<N.
Начнем с позиции 1: |--------------------------------------(Длина N) |--------(Длина K)
Всего есть последовательностей длиной K с первой позиции 256^K.
Вероятность совпадения в первой позиции - 1/256^K.
Последовательности длиной K могут начинаться с позиций числом N-K,
те всего вариантов (N-K) * 256^K.
Из них заданных последовательностей - (N-K)*(256^(K-1)).
Значит, надо искать с такого K, чтобы число таких последовательностей было очень мало, те
(N-K)*(256^(K-1)) -> 0.
Из общих соображений...02.12.01 13:52 Автор: ggg <ggg> Статус: Elderman
> да это понятно > при достаточно большом К найти послед. не трудно > например при К=N :) > интересно найти при минимальном К
Ну так тогды можно сделать так:
вид функции 256^(K-1) * (N-K+1) - неуклонно возрастающий график от
K = 1 до K= N. (чем больше K, тем больше вероятность встретить нашу последовательность).
Так будем искать, скажем, медианным методом на множестве [1..N]
с весом этой функции:
так можно выбрать наиболее вероятное К, но оно не обязательно будет минимальным
ведь если данные состоят из одних нулей, то невстреч. послед = "1"
даже выбрав К, основная часть задачи не решена - как найти послед. которая не встречается ?
опять возвращаемся к полному перебору послед. длины К
при этом число проходов по файлу = 256^K (если работаем с байтами)
нужно придумать как выстроить данные, чтобы пусть с большими затратами памяти, но быстро найти уникальную послед.
Из общих соображений...02.12.01 17:05 Автор: Chingachguk <Chingachguk> Статус: Member
> нужно придумать как выстроить данные, чтобы пусть с > большими затратами памяти, но быстро найти уникальную > послед.
Слушай ! А пробовал вот так делать:
Пусть, скажем мы имеем некотрое K.
Выискиваем в файле все различные последовательности длиной K.
Различные в любом байте. Если их общее число
не равно 256^K, то мы нашли уровень, на котром есть последовательность,
которой точно нет в файле.
Искать имеет смысл от K=N-1 downto, ибо вероятность не найти последовательность с ростом K возрастает ....
Из общих соображений...02.12.01 17:47 Автор: ggg <ggg> Статус: Elderman
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
