информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Портрет посетителяЗа кого нас держат?Сетевые кракеры и правда о деле Левина
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / programming
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Из общих соображений... 02.12.01 13:35  Число просмотров: 982
Автор: Chingachguk <Chingachguk> Статус: Member
<"чистая" ссылка>
> - есть блок некоторых данных
> - нужно составить такую последовательность, которая не
> встречается в этих данных

Если покажется фуфлом, прошу сильно не бить ! ;)

Пусть есть блок размером 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.

<programming>
нужен алгоритм поиска отсутствующей последовательности 02.12.01 12:24  
Автор: ggg <ggg> Статус: Elderman
<"чистая" ссылка>
- есть блок некоторых данных
- нужно составить такую последовательность, которая не встречается в этих данных

и ещё :
- найти самую короткую такую последовательность
- найти все такие последовательности

может это стандартная задача и алгоритм уже давно продуман ?
я не нашёл в инете

полный перебор не устраивает
(атлон всю ночь без результатов проработал) :)
Из общих соображений... 02.12.01 13:35  
Автор: Chingachguk <Chingachguk> Статус: Member
<"чистая" ссылка>
> - есть блок некоторых данных
> - нужно составить такую последовательность, которая не
> встречается в этих данных

Если покажется фуфлом, прошу сильно не бить ! ;)

Пусть есть блок размером 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 :)

интересно найти при минимальном К
Из общих соображений... 02.12.01 14:15  
Автор: Chingachguk <Chingachguk> Статус: Member
<"чистая" ссылка>
> да это понятно
> при достаточно большом К найти послед. не трудно
> например при К=N :)
> интересно найти при минимальном К

Ну так тогды можно сделать так:

вид функции 256^(K-1) * (N-K+1) - неуклонно возрастающий график от
K = 1 до K= N. (чем больше K, тем больше вероятность встретить нашу последовательность).
Так будем искать, скажем, медианным методом на множестве [1..N]
с весом этой функции:

S(K) = 256^(K-1) * (N-K+1);

Kследующее = Kслева + (Kслева - Kсправа)*( S(Kслева) / (S(Kслева)) + S(Kсправа) )
Из общих соображений... 02.12.01 14:41  
Автор: ggg <ggg> Статус: Elderman
<"чистая" ссылка>
так можно выбрать наиболее вероятное К, но оно не обязательно будет минимальным

ведь если данные состоят из одних нулей, то невстреч. послед = "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
<"чистая" ссылка>
да наверно это самое разумное и быстрое:
-собрать все послед. длины К
-отсортировать их
-посмотреть недостающие элементы

сколько же памяти сожрёт :)
но зато наверно должно работать за приемлемое время

спасибо большое за помощь
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach