引用:

原帖由 卡斯罗 于 2008-4-28 11:20 发表


很精辟的分析，如果你能看出这些问题，其码能让明您认真看了算法，虽然你和我站在讨论问题相反的立场上，但由于您很仔细的进行分析和出于技术的目的讨论，而不是像其它人总要给别人讲什么高中科普，所以我还是很 ...

下面分析二次压缩的问题，事实上，就是能不能把6位压成5位，5位压成4位，4位压成3位这么依此类推。其实没必要一步一步分析，直接分析6位压成3位的最大压缩能力就可以了，我把一切情况都尽量往利于这种算法的方向分析：
1、分子分母长度不超过3位，前面说了总共有857种，而6位数据的组合有9*10^5种，算算这个比例吧，想把6位压成3位，能压缩的数据只有0.095%，这个比例太小了所以基本等于没压缩。
再简单分析一下6位压5位的情况，6位压5位和4位压3位，能压缩的数据比例差不多，但是压缩能力就不一样了，不再是75%了，而是5/6，只有83.3%。
至此，我想你应该能看出一些规律了，这种压缩算法的缺点在于：
对于多位数据的时候，比如将6位压成5位，缺点是压缩能力低；
如果将6位压成3位或4位，缺点是能被压缩的数据所占的比例太少。
所以此算法的二次压缩并不是不可行，但意义不大，压缩时间倒是成级数增长，不值当。
2、但是对于另一种情况，就是将WINRAR或WINZIP压缩过的文件再用此算法压缩，答案是可行的，算法上基本不冲突。
3、从第一种分析的规律来看，实事上位数越小越有利，也就是如果把随机数据采用3位压2位的算法，这样效果会更好些：
分子分母长度为2位的组合一共有81种，减去分子分母不互质的情况大概是65种，3位随机数据组合一共是900种，这样可压缩的数据所占比例为7.2%，压缩能力为2/3，也就是66.6%，综合起来算压缩能力为97.6%
你可能会问结果怎么和4位压3位的压缩能力一样，因为分析4位压3位的时候我有些数据舍去了，所以4位压3位实际上达不到97.6%，3位压2位倒是可以。

对了，再把最后一个疑问说一下，就是能不能再用别的计算方法，比如开方，平方，乘积等等，答案是你只能选其中一种，而不是哪段数据适合用哪种算法就用哪种算法，因为如果这样，就和记录分子1位还是分母1位一样了，你还需要1个数据来记录到底用的什么算法。
如果只能选一种的话，平方，开方，乘积能组成的最大组合和相除是一样的，决定组合数量的主要是位数。
至此，所有情况应该都已分析过了。

引用:

原帖由 quick 于 2008-4-28 14:32 发表
对了，再把最后一个疑问说一下，就是能不能再用别的计算方法，比如开方，平方，乘积等等，答案是你只能选其中一种，而不是哪段数据适合用哪种算法就用哪种算法，因为如果这样，就和记录分子1位还是分母1位一样了，你 ...

对您的第二次分析结果，我也不得不表示同意，您第二次进行的分析也是很正确的。
对您的整体说法，我没有疑义，我也是对目前这个方法有以下几点疑问，希望您能够在有时间时看一下，并且能够一起研究。
1.您提出的二次压缩的问题，我可能没有把话说清楚，我现在的想法是这样的。
例如源数据中含有1111 2222 3333 这几位数，现在用我的程序来压假设1111可以压，2222和3333都是行不通的，那么我们可能得到这样一个结果就是88622223333，我的想法是可不可以把生成的数字做为第二次压缩。就是形成这样8862 2223 333后，二次压缩，因为考虑到分子分母法不会受到排冗余的那种限制，可以再次压缩得到的结果，但其中后面的333这三位就别想再压了，所以我会有这种想法。不知道这样是否会令算法更优化些。

2.对于您说的:
但是对于另一种情况，就是将WINRAR或WINZIP压缩过的文件再用此算法压缩，答案是可行的，算法上基本不冲突。

对于就点我也表示赞同，完全没有异议，在这里要再次向enthappy前辈致以敬礼 ，您看到了比我能想到更远的东西，如果说我们这次讨论获得了什么价值我想这点是非常大的，起码对我来说，当然我觉得这对其它人也是个思路。

3.对于不采用质的方法，而是采取其它的方法，就像您说的
就是能不能再用别的计算方法，比如开方，平方，乘积等等，答案是你只能选其中一种，而不是哪段数据适合用哪种算法就用哪种算法，因为如果这样，就和记录分子1位还是分母1位一样了，你还需要1个数据来记录到底用的什么算法。

这个非常正确，而且我也想到了这个问题，而且我目前没有能想到有什么好办法，能进行多种方式的取舍来补救这一点，现在据我看来这一点根本就无法补救。

4.我说了采用矩阵的方法，就是说不采用开方，平方，乘积等等，因为就像您说的一样，，还要留一位给它，然后再看用哪个合适，我都觉得不可行。

但如果采用矩阵压缩率可能就会比简单的质或开方平方等高，但我们要在程序中提供大量的模版对应，这样的话会非常复杂，我也是只有个想法，具体实现起来，我不知道会不会实现，所以我现在没办法对这个加以评论，所以对这种想法，我只能做为一个保存意见，但我不排除其它人会实现，在这一点上我仍保留我的观点。

5在对于分子分母法是否能对数据进行压缩的问题上，我想我们目前是应该达成的共识的，它可以，这点您不反对吧，就目前的情况来看，只是它能达到一个什么效率的问题，但目前看来效率是很低的。除非有人实现了我在第四点中提出的观点，或我在第一点中提出的可以进行二次压缩成立。

和您谈话很高兴，希望您有时间时可以回贴。

引用:

原帖由 卡斯罗 于 2008-4-28 16:17 发表


对您的第二次分析结果，我也不得不表示同意，您第二次进行的分析也是很正确的。
对您的整体说法，我没有疑义，我也是对目前这个方法有以下几点疑问，希望您能够在有时间时看一下，并且能够一起研究。
1.您提出 ...

我忽然想起一个严重的问题，对这种算法是致命打击。就是：如何记录哪些数据是被压缩了的？
比如一段数据是1234 5678 9012 3456
假设1234可以压缩，4567不可以压缩，9012可以压缩，3456不可以压缩
那么压缩后如何保存？这次压缩只节省了两位数据，但是保存哪4位被压缩哪4位没被压缩又至少需要3个数据。
我一开始忽略了这个问题是因为考虑到将多位数据压缩时，用来记录的数据所占的比例很小，但现在已经证明，多位数据压缩时可行性非常差，所以这又是一个矛盾!
这可以说是此算法最苛刻的要求，就是需要大量可压缩的数据是连续的!这样才能减少记录解压位置的数据所占的比例。而让可压缩的数据连续，这个概率就非常小了。至此，此压缩算法可以被彻底否定。抱歉我昨天的贴子忘了考虑这一点，以至于做出了压缩率可达到97.6%的错误结论，那是在每4位数据(或者说是后来的3位)都能被压缩的前提下才能达到。如果还有什么问题可以再讨论

引用:

原帖由 quick 于 2008-4-29 00:26 发表

我忽然想起一个严重的问题，对这种算法是致命打击。就是：如何记录哪些数据是被压缩了的？
比如一段数据是1234 5678 9012 3456
假设1234可以压缩，4567不可以压缩，9012可以压缩，3456不可以压缩
那么压缩后如何 ...

是的我一开始也忽略了这个问题，看来用质这种算法是有弊病的，所以可能只有理论上对一个四位数进行压缩，而实际上根本不能应用，但如果换成其它方式有可能解决此问题，但如果这样又会讨论的太多了，也许一时根本不能找出一个正确的结果，我最近一个软件正在收尾，我们以后有时间可以再继续这个话题，谢谢您对这个问题的帮助，

引用:

原帖由 卡斯罗 于 2008-4-29 09:52 发表


是的我一开始也忽略了这个问题，看来用质这种算法是有弊病的，所以可能只有理论上对一个四位数进行压缩，而实际上根本不能应用，但如果换成其它方式有可能解决此问题，但如果这样又会讨论的太多了，也许一时根本 ...

好的，有空再讨论，

我觉着有可行性出于两方面原因：

1）可以用取最大公约数的算法，将一串数取出最大公约数，将 最大公约数 和 这串数中每个数除以最大公约数的结果 存文件，作为压缩结果。这需要两个条件：A）这串数需要优化，较小的数及素数等不利于取最大公约数，要优化或压缩; B) 除法位数越高，越利于压缩，我们常用的是32位运算，最好是64位或更高；

2）一般的压缩算法是将码表存到压缩文件中，从讨论中我们已经知道有很多天然的码表，例如根号2，这些码表的数量无限多，看怎么用了。但是浮点数的精度似乎是个问题，可能需要写新的开方函数之类。

[ 本帖最后由 enthappy 于 2008-4-29 21:55 编辑 ]

引用:

原帖由 enthappy 于 2008-4-29 21:52 发表
我觉着有可行性出于两方面原因：

1）可以用取最大公约数的算法，将一串数取出最大公约数，将 最大公约数 和 这串数中每个数除以最大公约数的结果 存文件，作为压缩结果。这需要两个条件：A）这串数需要优化，较小 ...

精辟，这些是我一直都没有想到的，拓宽了思路，向您学习

盖楼～

太猛了，浑身冒汗，不敢插言