Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | | |
Из общих соображений... 02.12.01 14:41 Число просмотров: 1000
Автор: ggg <ggg> Статус: Elderman
|
так можно выбрать наиболее вероятное К, но оно не обязательно будет минимальным
ведь если данные состоят из одних нулей, то невстреч. послед = "1"
даже выбрав К, основная часть задачи не решена - как найти послед. которая не встречается ?
опять возвращаемся к полному перебору послед. длины К
при этом число проходов по файлу = 256^K (если работаем с байтами)
нужно придумать как выстроить данные, чтобы пусть с большими затратами памяти, но быстро найти уникальную послед.
|
|
<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
|
да наверно это самое разумное и быстрое:
-собрать все послед. длины К
-отсортировать их
-посмотреть недостающие элементы
сколько же памяти сожрёт :)
но зато наверно должно работать за приемлемое время
спасибо большое за помощь
|
|
|
подробно о проекте
Анализ криптографических сетевых...
