以下无损数据压缩算法在理论上是否有效?
Is the following lossless data compression algorithm theoretically valid?
我想知道下面的算法是否是一个有效的无损数据压缩算法(虽然对传统计算机不实用,也许是量子计算机?)。
在较高的简化级别上,压缩步骤为:
- 计算未压缩文本的字符频率。
- 计算未压缩文本的 SHA3-512(或其他哈希函数)。
- 连接 SHA3-512 和字符频率(这是现在将写入文件的压缩文本)。
并且在高度和简化的层次上,解压步骤是:
- 使用压缩文件中的字符频率,生成未压缩文本的排列(记录是哪一个)。
- 计算步骤 1 中生成的排列的 SHA3-512。
- 如果步骤2计算出的SHA3-512与压缩文件中的SHA3-512匹配,则解压完成。否则,转到步骤 1。
是否有可能与未压缩文本的排列发生 SHA3-512 冲突(即给定字符频率的两个排列是否可以具有相同的 SHA3-512?)?如果是这样,什么时候开始发生(即在多少个未压缩的文本字符之后?)?
一个简化的例子如下:
- 未压缩的文本为:"Lorem ipsum dolor sit amet, consectetur adipiscing elit. Maecenas et enim vitae ligula ultricies molestie at ac libero. Duis dui erat, mollis nec metus nec, porttitor scelerisque enim. Aenean feugiat tellus sit amet facilisis imperdiet. 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 dapibus luctus volutpat. Praesent aliquet ipsum vitae mauris pulvinar, et pharetra leo semper. Nulla a mauris tellus. Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Integer sollicitudin dui sapien, in tempus arcu facilisis in. Vivamus dui dolor, faucibus eu accumsan eu, porttitor id risus. In auctor congue pellentesque. Cras malesuada enim eget est vehicula pretium. Phasellus scelerisque imperdiet lorem, eu euismod lectus convallis consequat. Nam vitae euismod est, vitae lacinia arcu. Praesent fermentum sit amet erat feugiat cursus. Pellentesque magna felis, euismod vel vehicula eu, tincidunt ac ex. Vestibulum viverra justo nec orci semper, nec consequat justo faucibus. Curabitur dignissim feugiat nulla, in cursus nunc facilisis id. Suspendisse potenti. Etiam commodo turpis non fringilla semper. Vivamus aliquam ex non lorem tincidunt, et sagittis tellus placerat. Proin malesuada tortor eu viverra faucibus. Curabitur euismod orci lorem, ut fermentum velit consectetur vel. Nullam sodales cursus maximus. Curabitur nec turpis erat. Vestibulum eget lorem nunc. Morbi laoreet massa vel nulla feugiat gravida. Nulla a rutrum neque. Phasellus maximus tempus neque, eu sagittis ex volutpat ac. Duis malesuada sem vitae lacus suscipit, eu dictum elit euismod. Sed id sagittis leo. 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, a 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. Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Interdum et malesuada fames ac ante ipsum primis in faucibus. Fusce varius lacus velit, venenatis consequat justo rutrum nec. Nunc cursus odio arcu, nec egestas purus feugiat nec. Aliquam efficitur ornare ullamcorper. Mauris consectetur, quam vitae ultricies ullamcorper, nulla nulla tempus risus, aliquet 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, a dictum risus euismod sed. Morbi vel urna nec sem consectetur auctor quis ac augue. Donec ac pellentesque tortor. In hendrerit ultricies consequat. 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 id est eleifend efficitur. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nunc arcu neque, molestie ac lorem id, feugiat efficitur erat. Vestibulum vel condimentum lectus, eu euismod turpis.".
- 字符频率为:"⎵:501e:345i:277u:266s:240t:226a:219l:161n:154 r:147 m:132 c:128 o:117 d:79 .:64 p: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:5 I:4 C:4 j:4 L:3 A:3 E:3 F:2 U:1 Q:1 ".
- SHA3-512 是:“45ebde65cf667d1bfdcf779baab84301c1d4abe60448be821adda9cf7b99b36a61c53233db4a0eda93a04c75201be13bbb638b5e78f5047560fffc=933b]f1”。
- The compressed file contents are: "45ebde65cf667d1bfdcf779baab84301c1d4abe60448be821adda9cf7b99b36a61c53233db4a0eda93a04c75201be13bbb638b5e78f5047560fffc97f1c95adb⎵:501 e:345 i:277 u:266 s:240 t:226 a:219 l:161 n:154 r:147 m:132 c:128 o:117 d:79 .:64 p: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:5 I:4 C:4 j:4 L:3 A:3 E:3 F:2 U:1 Q:1".
您的压缩方法假定给定字符频率 table 只有一种排列会生成给定的哈希码。事实证明这是错误的。
一个 512 位哈希可以表示 1.34E+154 个唯一值的数量级。 100个字符的文件中的排列数为100!,即9.33E+157。
给定一个 100 个字符的文件,每个可能的 512 位哈希码有超过 6,900 种不同的排列。
使用更大的哈希码也无济于事。每添加一位,哈希码的数量就会翻倍,但可能的排列数量会随着添加到文件中的每个字符而增加。
我想知道下面的算法是否是一个有效的无损数据压缩算法(虽然对传统计算机不实用,也许是量子计算机?)。
在较高的简化级别上,压缩步骤为:
- 计算未压缩文本的字符频率。
- 计算未压缩文本的 SHA3-512(或其他哈希函数)。
- 连接 SHA3-512 和字符频率(这是现在将写入文件的压缩文本)。
并且在高度和简化的层次上,解压步骤是:
- 使用压缩文件中的字符频率,生成未压缩文本的排列(记录是哪一个)。
- 计算步骤 1 中生成的排列的 SHA3-512。
- 如果步骤2计算出的SHA3-512与压缩文件中的SHA3-512匹配,则解压完成。否则,转到步骤 1。
是否有可能与未压缩文本的排列发生 SHA3-512 冲突(即给定字符频率的两个排列是否可以具有相同的 SHA3-512?)?如果是这样,什么时候开始发生(即在多少个未压缩的文本字符之后?)?
一个简化的例子如下:
- 未压缩的文本为:"Lorem ipsum dolor sit amet, consectetur adipiscing elit. Maecenas et enim vitae ligula ultricies molestie at ac libero. Duis dui erat, mollis nec metus nec, porttitor scelerisque enim. Aenean feugiat tellus sit amet facilisis imperdiet. 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 dapibus luctus volutpat. Praesent aliquet ipsum vitae mauris pulvinar, et pharetra leo semper. Nulla a mauris tellus. Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Integer sollicitudin dui sapien, in tempus arcu facilisis in. Vivamus dui dolor, faucibus eu accumsan eu, porttitor id risus. In auctor congue pellentesque. Cras malesuada enim eget est vehicula pretium. Phasellus scelerisque imperdiet lorem, eu euismod lectus convallis consequat. Nam vitae euismod est, vitae lacinia arcu. Praesent fermentum sit amet erat feugiat cursus. Pellentesque magna felis, euismod vel vehicula eu, tincidunt ac ex. Vestibulum viverra justo nec orci semper, nec consequat justo faucibus. Curabitur dignissim feugiat nulla, in cursus nunc facilisis id. Suspendisse potenti. Etiam commodo turpis non fringilla semper. Vivamus aliquam ex non lorem tincidunt, et sagittis tellus placerat. Proin malesuada tortor eu viverra faucibus. Curabitur euismod orci lorem, ut fermentum velit consectetur vel. Nullam sodales cursus maximus. Curabitur nec turpis erat. Vestibulum eget lorem nunc. Morbi laoreet massa vel nulla feugiat gravida. Nulla a rutrum neque. Phasellus maximus tempus neque, eu sagittis ex volutpat ac. Duis malesuada sem vitae lacus suscipit, eu dictum elit euismod. Sed id sagittis leo. 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, a 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. Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Interdum et malesuada fames ac ante ipsum primis in faucibus. Fusce varius lacus velit, venenatis consequat justo rutrum nec. Nunc cursus odio arcu, nec egestas purus feugiat nec. Aliquam efficitur ornare ullamcorper. Mauris consectetur, quam vitae ultricies ullamcorper, nulla nulla tempus risus, aliquet 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, a dictum risus euismod sed. Morbi vel urna nec sem consectetur auctor quis ac augue. Donec ac pellentesque tortor. In hendrerit ultricies consequat. 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 id est eleifend efficitur. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nunc arcu neque, molestie ac lorem id, feugiat efficitur erat. Vestibulum vel condimentum lectus, eu euismod turpis.".
- 字符频率为:"⎵:501e:345i:277u:266s:240t:226a:219l:161n:154 r:147 m:132 c:128 o:117 d:79 .:64 p: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:5 I:4 C:4 j:4 L:3 A:3 E:3 F:2 U:1 Q:1 ".
- SHA3-512 是:“45ebde65cf667d1bfdcf779baab84301c1d4abe60448be821adda9cf7b99b36a61c53233db4a0eda93a04c75201be13bbb638b5e78f5047560fffc=933b]f1”。
- The compressed file contents are: "45ebde65cf667d1bfdcf779baab84301c1d4abe60448be821adda9cf7b99b36a61c53233db4a0eda93a04c75201be13bbb638b5e78f5047560fffc97f1c95adb⎵:501 e:345 i:277 u:266 s:240 t:226 a:219 l:161 n:154 r:147 m:132 c:128 o:117 d:79 .:64 p: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:5 I:4 C:4 j:4 L:3 A:3 E:3 F:2 U:1 Q:1".
您的压缩方法假定给定字符频率 table 只有一种排列会生成给定的哈希码。事实证明这是错误的。
一个 512 位哈希可以表示 1.34E+154 个唯一值的数量级。 100个字符的文件中的排列数为100!,即9.33E+157。
给定一个 100 个字符的文件,每个可能的 512 位哈希码有超过 6,900 种不同的排列。
使用更大的哈希码也无济于事。每添加一位,哈希码的数量就会翻倍,但可能的排列数量会随着添加到文件中的每个字符而增加。