这是一个创建于 2606 天前的主题，其中的信息可能已经有所发展或是发生改变。
FPGA 能实现这样的功能吗？ 三排二进制存储位，第一、第二排做 与非 运算，得到第三排。第三排相当于并联的电阻，1 电阻小，0 电阻大，加电压后，能测试出电流的大小。1 多则电流大，0 多则电流小。 第一排放 1G 的压缩过的文件（ 1 与 0 差不多一样多），圆周率从第二排排队经过，第三排产生比照数据。第三排的传感器达到一定阀值，则记录圆周率的位置。将这个位置的值放在第三排数据前，然后压缩并存入第一排。重复以上过程，直到获得极短的数据。
 |
1
churchmice 2017-09-22 09:13:41 +08:00 via Android
可以实现，但是你这玩意要找到 1G 匹配的圆周率数据考虑过花多少时间吗？而且理论上存在这个解吗？我一直以为这压缩算法是来搞笑的
|
 |
2
ZUYI OP @churchmice 并不是完全匹配呀。仔细看，只要是达到一定 阀值 就可以。比如说，90%。
|
|
3
churchmice 2017-09-22 09:22:06 +08:00 via Android  1
@ZUYI 仔细一想，不现实，硬件里面你要计算 1G 比特的 A 是不是等于 1G 比特的 B，需要花费的时间很大，我怎么估计都需要 0.1 秒了，然后你这个还要迭代，就算你迭代个 1G 次吧，自己算算需要花费多少时间
|
|
4
churchmice 2017-09-22 09:24:13 +08:00 via Android
@ZUYI 而且 90%匹配比 100%匹配硬件上的开销提升的不是一点半点，你要加一堆 mux 一堆比较强，这时钟频率就更上不去了
|
|
5
ZUYI OP @churchmice 不是等于，不是等于，不是等于。。。是相似，是相似，是相似。。。另外，%90 的 100 次方就是很大的压缩比例了，用不了迭代 1G 次呀？
|
 |
6
nutting 2017-09-22 09:28:58 +08:00
看不懂，抛开硬件详细说说算法，有啥优点
|
 |
7
roychan 2017-09-22 09:29:24 +08:00 3
|
|
8
nutting 2017-09-22 09:31:03 +08:00
0123456789，这串和圆周率运算，得到什么？怎么实现压缩
|
|
9
ZUYI OP 为啥“ 90%匹配比 100%匹配硬件上的开销提升的不是一点半点”呀？我是要通过第三排的 电阻 来进行 比较，按理说 开销 应该一样呀？
|
 |
10
whileFalse 2017-09-22 09:33:34 +08:00 via iPhone
容易证明，设有字典 D （ n ），任意长度为 n 的串都可以在其中找到。则最好情况下，串的起始位置 K （ n ）的平均长度是 n，即压缩无意义。
|
|
11
churchmice 2017-09-22 09:36:01 +08:00 via Android
@ZUYI
1 ）你产生 100bit 的随机数，去圆周率里面匹配匹配看究竟需要多少次？按你说的 90%的相似度再去计算下 2 ）硬件上 10 比特里面有 9bit 相似怎么做？很简单啊，每一个比特相加看看结果是不是 9，但是这样会用到 10 个进位加法器。如果是 1G 比特呢？要实现 90%相似度检测需要 0.9G 个加法器，这一方面是巨大的硬件开销，一方面会导致时钟频率很低很低很低，几乎不可行。当然会有一些算法可以稍微优化下，但是数量级不会改变。不要说什么电流相加这种方法，最后转化到数字电路里面还是 0/1 的操作，电流你能无限相加吗？加到后来是不是都能电死恐龙了“ |
|
12
churchmice 2017-09-22 09:37:19 +08:00 via Android 3
@nutting 「圆周率(Pi)压缩法」就是一个例子，常被用来开压缩算法的玩笑 —— 但不止是玩笑而已，理论上确实管用。方法是你把想要的压缩文件二进制化，然后在二进制化的 Pi 序列里找这段数据。由于 Pi 是无限不循环小数，所以任何你所选择的二进制数据最终都会在 Pi 里被找。这是个疯狂的但是尚未被彻底推翻的理论上可行的算法。但是如果我们只是要对单个文件进行压缩，而不是多个，这个方法一定管用。
于是你只需要标记 Pi 的起始位置和你文件的大小，压缩过程就愉快地完成了。这可以把任意的文件压缩到非常小的地步，而且可能会用掉你海量的时间来找到对应的二进制串，完全是拼人品的算法。 不过，理论上，如果你人品不够，找到的数据位于非常遥远的地方，那用这逗比算法得到的压缩包也可能会非常大。但是最近有一些逗比孩子对此还发表了论文，指出你可能得到比你要压缩的数据还大的压缩包。github 上就有一个这样的玩意儿叫 PIFS(Pi 文件系统)，这个开源项目声称不管怎么说，100% 的压缩率在数学上是不可能的。 |
 |
13
BOYPT 2017-09-22 09:39:29 +08:00
从信息熵角度直接就知道不可能的。
|
|
14
nutting 2017-09-22 09:47:32 +08:00
哦，哈哈，真是逗比的想法啊
|
 |
15
lovestudykid 2017-09-22 09:48:14 +08:00
感觉像在造永动机
|
 |
16
twilight 2017-09-22 09:54:48 +08:00 3
楼主，那个字应该是“阈” ， 阈值，不是阀值。
======================================= 继空穴来风含义颠倒之后，阀值是否会取代阈值？ 阀值是不是更贴近群众，更好理解----到了这个值，阀门就开了或关上 |
 |
17
sennes 2017-09-22 09:56:50 +08:00
因为是涉及硬件的 所以我其实从你发的 /t/390354 这一篇开始就有在想了
不过 这么多天过去了 我还是不太理解你说的「第三排相当于并联的电阻」到底是什么意思。 |
|
18
churchmice 2017-09-22 10:04:03 +08:00 via Android
@sennes 电阻并联，电流相加，我猜是这个意思
根据最终电流的大小判断到底匹配了几个 |
 |
19
Xs0ul 2017-09-22 10:16:14 +08:00
建议看看信息论
|
 |
20
shuax 2017-09-22 10:22:36 +08:00 1
我要保存“ 123 ”，在 pi 的第“ 1926 ”位，长度为“ 3 ”，仅仅是“ 1926 ”已经比我要保存的东西大了。
|
|
21
ZUYI OP @churchmice @sennes @Xs0ul @twilight @lovestudykid @BOYPT @whileFalse @roychan 其实你想想，只要有 50%以上匹配就可以了，不用达到 90%相似（我太着急了，把意思搞混淆了，对不起）。因为，经过压缩的文件 1 和 0 的比例是一样的，圆周率中 1 和 0 的比例也是一样的。那么根据概率，只要有 50%以上匹配，就会有 25%以上的 1 匹配，与非运算后就会实现将原来的压缩文件中 1 的比率（ 50%）降低（存入第三排进行判断是否降低），从而再次压缩（获得原压缩文件 90%左右的大小）并存入第一排。 另外，不是电流相加，只是把第三排所有的二进制位（应该类似并联的二极管吧，）统一加上个电压，测电压下降的幅度，来判定比率是否下降。
|
 |
22
LU35 2017-09-22 11:10:41 +08:00 via Android
@shuax 你可能没理解这个理论，有可能你的整个数据都可以在 pi 中顺序保存。
唯一的问题是 pi 的数据有多大，还有检索这个数据所花的时间。 |
|
23
Xs0ul 2017-09-22 11:23:05 +08:00
@LU35 #22 其实和 pi 没有关系，你完全可以把 pi 换成 0.0 1 00 01 10 11 000 001 ... 这样有规律的无限小数，这样根本不需要检索，可以直接获得位置。然而这样压缩还是没意义的。
|
|
25
churchmice 2017-09-22 12:10:15 +08:00 via Android 1
@ZUYI 首先 FPGA 里面没有分离式的电阻，用电阻这些就是无稽之谈，其次你这种测电压下降的方法考虑过精度没有？你 9999 个电阻并联跟 10000 个电阻并联你算算这电压表的精度得达到多少才能帮你区分出来？有没有考虑过最后电阻本身的误差就已经超过你想要实现的精度了？
|
|
26
ZUYI OP @churchmice 0.0001 的差异，确实太小了，测不准。但如果是 0.01 呢？ 0.05 呢？ FPGA 里有没有其它可以达到这个目的的结构呢？或者别的什么硬件能实现这个功能？
|
|
27
twilight 2017-09-22 12:35:57 +08:00
|
 |
28
gzgz8080 2017-09-22 12:40:12 +08:00
看了 GitHub 上的 pifs 项目，原理就是用时间换取空间。
因为理论上所有的数值组合都可能出现在 pi 的其中一段，但有可能在非常后面才出现。 思路是不错的，但是限于当前的 cpu 计算能力，只能将文件分成多个小段，再对每个小段进行 pi 压缩。 至于最终性能，github 上也说了，压缩 400 行的文本文件花了 5 分钟。 就像以前蒸汽机车刚发明时跑得比马车还慢，还被不少人骂没前途吗？ 随着并行计算的发展，每段都可以并发处理；甚至用量子计算机来计算 pi，那能力可就杠杠的。 以后就可以用一个偏移量加长度来表示任意文件内容了。 以后此算法的潜力还真的无法估量。 |
|
31
gzgz8080 2017-09-22 14:42:01 +08:00 via Android
|
 |
33
UncleRiver 2017-09-22 15:21:21 +08:00
pi 的小数部分是无限不循环的，但是能否由此推论出任意一个数字序列都会出现在 pi 的小数部分里？
举例来说，一个无限不循环的序列可以完全不出现“ 123 ”。 或者放宽要求来说，我们能否证明，在 pi 的小数部分，一定可以找到与任意一个数字序列相似度 90%的那一段？ |
 |
34
jedihy 2017-09-22 15:28:20 +08:00
这样字典也就是 pi 会占无穷大的空间的。
|
|
35
gzgz8080 2017-09-22 15:45:05 +08:00 2
@noe132 这肯定会通过一定的统计值来确定最佳的分段长度。
因为越短的分段，越容易在前面匹配到。 我测试了一下： 999999 出现在 pi 的 762 位：压缩率有 50%； 9999999 出现在第 1722776 位：压缩率只有 0 ； 99999999 出现在第 66780105 位：压缩率也为 0 ； 999999999 的话已经搜索很久都没找到了。 所以设置合适的分段长度确实可以提高压缩率的。 |
 |
36
hahastudio 2017-09-22 15:51:49 +08:00
pi 认为是 normal number 但还没被证明
|
 |
37
chuanqirenwu 2017-09-22 15:55:44 +08:00
talk is cheap, show me the code.
|
 |
38
Luckyray 2017-09-22 15:58:25 +08:00
想起来一个段子，就是说外星人来到地球，收集了所有信息，然后在飞船上一个特点的地方点了个点，就把信息带回去了，因为这个点到飞船头部的距离是个非常长的数字.....可以解码成信息...
楼主的概念是不是跟这个有点像？ |
 |
40
mhycy 2017-09-22 16:28:12 +08:00
一排电阻？楼主该看看 R2R DAC 电路。。。。
先把电源稳定性解决了再说 |
 |
41
popkara 2017-09-22 17:05:24 +08:00
计算圆周率相当消耗处理器性能，而且越算到后面计算量越大，不具有普适性。
你说加个字典？那不就是现在这些算法吗？ |
 |
43
neoblackcap 2017-09-22 23:16:40 +08:00
压缩了，然后没法解压。或者我每次解压都要产生大于原数据源的信息，那我压缩来干嘛？还不如直接传送或者保存原数据，根本没有意义。
|
 |
44
zhicheng 2017-09-23 03:00:34 +08:00
压缩算法是根据内容计算出字典， 现在拿内容去匹配一个固定的随机字典。计算的浪费就不说了，一个固定的字典怎么可能会比一个根据内容计算出来的字典压缩比高。
|
 |
45
zmj1316 2017-09-23 05:53:59 +08:00 via Android 1
所以说本科教育还是很重要的......
|
 |
46
rozbo 2017-09-23 14:42:30 +08:00
1 是计算机计算不确定的数值所要花费的时间要远大于确定的
2 抛去计算时间不计，这样做的压缩比也没有现在压缩算法高 |
|
47
ZUYI OP |
|
49
ZUYI OP @sennes
@rozbo @zmj1316 @zhicheng @popkara @chuanqirenwu @gzgz8080 @noe132 @LU35 @Xs0ul @lovestudykid @BOYPT @churchmice @whileFalse @roychan 我想自己编程，用 2kb 以内的文件尝试一下。我觉得这个压缩过程本质上是一种不断向 解 收敛的过程。有一个问题，希望能得到帮助。怎样才能在 C 语言中实现 LZH 压缩算法？ |
Select Language