История изменений
Исправление alysnix, (текущая версия) :
чувак рассуждает так.
если есть битовая строка длиной N - то возможны 2^N вариантов этой строки. мощность множества - 2^N. назовем его множеством A.
однако суммарная мощность суммы множеств {1}, {2}… {N-1} битовых строк есть 2^N-2, (назовем его множество B).
значит мы можем отобразить множество A в множество B, если от A отнять два элемента. отнимем 2 элемента и назовем это множество - AA.
и вот тут содержится прокол, поскольку чтобы отобразить AA -> B, надо не только записать некое число из множества B, но и присовокупить к нему информацию - какому множеству из {1} {2}… это число принадлежит. если их перенумеровать, то получатся числа от 1 до N-1.
то есть строка из первого множества будет отображаться в пару «номер множества в множестве B + строка в этом множестве». и только тогда отображение будет однозначным.
например 5:12 - что гласит - число 12 в в виде битовой строки длиной 5 бит.
итак на каждое отображение надо не менее log основанию 2 от длины в битах данного подмножества в множестве B.
и если он даже применит идеальную упаковку номеров таких множеств - он выигрыша не получит. поскольку это просто изменение битового представления обьектов, вне всякого анализа их контента.
Исходная версия alysnix, :
чувак рассуждает так.
если есть битовая строка длиной N - то возможны 2^N вариантов это строки. мощность множества - 2^N. назовем его множеством A.
однако суммарная мощность суммы множеств {1}, {2}… {N-1} битовых строк есть 2^N-2, (назовем его множество B).
значит мы можем отобразить множество A в множество B, если от A отнять два элемента. отнимем 2 эелемента и назовем это множество - AA.
и вот тут содержится прокол, поскольку чтобы отобразить AA -> B, надо не только записать некое число из множества B, но и присовокупить к нему информацию - какому множеству из {1} {2}… это число принадлежит. если их перенумеровать, то получятся числа от 1 до N-1.
то есть строка из первого множества будет отображаться в пару «номер множества в множестве B + строка в этом множестве». и только тогда отображение будет однозначным.
например 5:12 - что гласит - число 12 в в виде битовой строки длиной 5 бит.
итак на каждое отображание надо не менее log основанию 2 от длины в битах данного подмножества в множестве B.
и если он даже применит идеальную упаковку номеров таких множеств - он выигрыша не получит. поскольку это просто изменение битового представления обьектов, вне всякого анализа их контента.