Является ли следующий алгоритм сжатия данных без потерь теоретически верным?

Question

Мне интересно, является ли следующий алгоритм допустимым алгоритмом сжатия данных без потерь (хотя это не практично для традиционных компьютеров, может быть, квантовых компьютеров?).

На высоком и упрощенном уровне этапы сжатия:

1. Вычисление частоты символов несжатого текста.
2. Вычисление SHA3-512 (или другой хэш-функции) несжатого текста.
3. Объединение SHA3-512и частота символов (теперь это сжатый текст, который будет записан в файл).

А на высоком и упрощенном уровне шаги декомпрессии:

1. Используя частоту символов в сжатом файле, сгенерируйте перестановку несжатого текста (отследите, какой именно).
2. Рассчитайте SHA3-512 сгенерированной перестановки на шаге 1.
3. Если SHA3-512, вычисленный на шаге 2, совпадает с SHA3-512 в сжатом файле, распаковка завершена.Иначе, перейдите к шагу 1.

Возможно ли столкновение SHA3-512 с перестановкой несжатого текста (т. Е. Могут ли две перестановки данной частоты символов иметь один и тот же SHA3-512?)?Если да, то когда это может начаться (т. Е. Через сколько символов несжатого текста?)?

Один упрощенный пример выглядит следующим образом:

• Несжатый текст: «Lorem ipsum dolor sit amet, consitteur adipiscing elit. Maecenas et enim vitae ligula ultricies molestie at ac libero. Duis dui erat, mollis nec metus nec, porttitor scelerisque enim.Fusce et nisl porta, aliquam quam eget, mollis sapien. Sed purus est, efficitur elementum quam quis, congue rutrum libero. Etiam metus leo, hendrerit ac dui in, hendrerit blandit sem. Etiam pellentesque enim dapibutus et al.mauris pulvinar, et pharetra leo semper. Nulla a mauris Tellus. Пеллетентный обитатель morbi tristique senectus et netus и malesuada славится ac turpis egestas.В конкурсе пеллеттеск. Cras malesuada enim est est vehicleula pretium. Phasellus scelerisque imperdiet lorem, eu euismod lectus convallis Продолжение. Nam vitae euismod est, vitae.Lacinia Arcu.Прейсент ферментум сит амет эрат феугиат курс.Pellentesque magna felis, euismod vel Vehicleula eu, tincidunt ac ex.Vestibulum viverra justo nec orci semper, nec следуют за justo faucibus.Curabitur dignissim feugiat nulla, в cursus nunc facilisis id.Потенциал Suspendisse.Etiam Commodo Turpis без Фрингилла Semper.Vivamus aliquam ex lorem tincidunt и др. Sagittis Tellus Placerat.Proin malesuada tortor eu viverra faucibus.Curabitur euismod orci lorem, ut fermentum velit contectetur vel.Nullam sodales cursus maximus.Curabitur nec turpis erat.Vestibulum Eget Lorem Nunc.Morbi laoreet massa vel nulla feugiat gravida.Nulla Rutrum Neque.Phasellus maximus tempus neque, eu sagittis ex volutpat ac.Duis malesuada sem vitae lacus suscipit, eu dictum elit euismod.Sed ID Сагиттис Лео.Sed convallis nisi nisl, vel pretium elit cursus vel.Duis Quis Accumsan Odio.Ut arcu ex, iaculis a lectus sit amet, lacinia pellentesque enim.Donec maximus ante odio, porta odio luctus at.Nullam dapibus aliquet sollicitudin.Sed ultrices iaculis blandit.Suspendisse dapibus, odio non venenatis faucibus, justo urna euismod neque, non finibus ante ante in massa.Sed sit amet nunc vel lacus dictum euismod.Пеллетентный обитатель Morbi Tristique Senectus et netus и malesuada славится ac turpis egestas.Interdum et malesuada прославляет первобытную приманку у фоцибуса.Fusce Varius Lacus Velit, Venenatis Conquat Justo Rutrum NEC.Nunc cursus odio arcu, nec egestas purus feugiat nec.Aliquam efficitur ornare ullamcorper.Mauris Concectetur, qua vitae ultricies ullamcorper, nulla nulla tempus risus, аликвит euismod urna erat gravida neque.Suspendisse et viverra enim, ut facilisis enim.Quisque Quis Elit Diam.Morbi quis nulla bibendum, molestie risus egestas, pharetra nisl.Aliquam Sed Massa dictum, Scelerisque Odio vel, Finibus Tellus.Nam Tristique Commodo Sem, Dictum Risus Euismod Sed.Morbi vel urc nec sem seccectetur auctor quis ac augue.Donec ac pellentesque tortor.В хендрерите ультриции конквата.Pellentesque non metus vitae elit euismod efficitur in in leo.Nulla ac pulvinar nunc.Donec porttitor nunc ante, et congue augue laoreet ac.Vivamus Bibendum является Eleifend Efficitur.Lorem Ipsum Dolor Sit Amet, Concetetur Adipiscing Elit.Lorem Ipsum Dolor Sit Amet, Concetetur Adipiscing Elit.Nunc arcu neque, molestie ac lorem id, feugiat efficitur erat.Vestibulum vel condimentum lectus, eu euismod turpis. "r: 147 м: 132 c: 128 o: 117 d: 79.: 64 p: 54,: 47 v: 40 q: 39 f: 35 g: 31 b: 31 ч: ​​11 P: 9 N: 9 S:8 x: 7 D: 6 V: 6 M: 5 I: 4 C: 4 j: 4 L: 3 A: 3 E: 3 F: 2 U: 1 Q: 1 ".
• SHA3-512 это: "45ebde65cf667d1bfdcf779baab84301c1d4abe60448be821adda9cf7b99b36a61c53233db4a0eda93a04c75201be13bbb638b5e78f5047560fffc97f1c95ad * 1 1033 * Содержимое сжатого файла: «45ebde65cf667d1bfdcf779baab84301c1d4abe60448be821adda9cf7b99b36a61c53233db4a0eda93a04c75201be13bbb638b5e78: 504: 23: 236: 256: 236: 235: 235: 236: 236: 235: 235: 235: 235: 235: 235: 235: 235: 236: 235: 235: 235: 235: 235: 235: 235: 235: 235: 235: 235: 235: 235: 235: 235: 235: 235: 235: 236: 235: 235: 235: 235: 235: 235: 236: 235: 235: 235: 235: 232: 23: 25: 232: 23: 25: 23: 23: 23: 23: 79.: 64 стр .: 54,: 47 v: 40 q: 39 f: 35 g: 31 b: 31 h: 11 P: 9 N: 9 S: 8 x: 7 D: 6 V: 6 M: 5I: 4 C: 4 j: 4 L: 3 A: 3 E: 3 F: 2 U: 1 Q: 1 ".

Answer 1

Ваш метод сжатия предполагает, что существует только одна перестановка данной таблицы частот символов, которая будет генерировать данный хэш-код.Это ложное доказательство.

512-битный хеш может представлять порядка 1,34E + 154 уникальных значения.Число перестановок в 100-символьном файле равно 100 !, или 9,33E + 157.

При наличии 100-символьного файла для каждого возможного 512-битового хэш-кода существует более 6900 различных перестановок.

Использование большего хэш-кода не поможет.Количество хеш-кодов удваивается с каждым добавляемым вами битом, но число возможных перестановок увеличивается с каждым добавляемым в файл символом.