w*******x
发帖数: 489 | 1 【 以下文字转载自 Computation 讨论区 】
发信人: woshialex (Qi), 信区: Computation
标 题: 有人知道浮点数的压缩算法吗？有损也没关系
发信站: BBS 未名空间站 (Sat Oct 23 10:12:16 2010, 美东)
我的问题里头内存严重不够用，所以需要把很多浮点数数组（单精度吧）压缩，然后调
用的时候在内存里头一个数组一个数
组的解压缩。
有人知道有效的算法吗？能压缩几倍？即使适当的loss也没关系。数据有大片区域比较
平滑。
谢谢！ |
|
j*t
发帖数: 184 | 2 假如有海量数据如下：
1/15/2010, 3:10:11, AAA, $500,000.00, B
1/15/2010, 3:10:15, BBB, $350,149.00, S
1/15/2010, 3:11:20, AAA, $500,100.00, B
1/15/2010, 3:15:10, CABDE, $1.49, B
如何设计压缩算法得到最大压缩比？ |
|
|
w*******x
发帖数: 489 | 4 我的问题里头内存严重不够用，所以需要把很多浮点数数组（单精度吧）压缩，然后调
用的时候在内存里头一个数组一个数
组的解压缩。
有人知道有效的算法吗？能压缩几倍？即使适当的loss也没关系。数据有大片区域比较
平滑。
谢谢！ |
|
R***a
发帖数: 41892 | 5 4x4像素为一组，14 bits/pixel记录最亮和最暗的四个像素的绝对数值，
10bits/pixel记录其他像素相对最亮和最暗像素的位置。
平均占用11bits
这是利用正常照片里面4x4范围之内不会有极端的明暗变化的
压缩算法。目前还没有人能发现和非压缩算法能够有肉眼可见区别 |
|
h*****u
发帖数: 14 | 6 如果你对数据压缩编程比较熟悉，请与我联系，我有个项目请你帮忙，费用我们一起商
量。
[email protected]/* */ |
|
|
h*****u
发帖数: 14 | 8 如果你对数据压缩编程比较熟悉，请与我联系，我有个项目请你帮忙，费用我们一起商
量。
[email protected]/* */ |
|
h*****u
发帖数: 14 | 9 如果你对数据压缩编程比较熟悉，请与我联系，我有个项目请你帮忙，费用我们一起商
量。
[email protected]/* */ |
|
w*******x
发帖数: 489 | 10 会不会太慢？。。并且data的结构是5唯的小格子。fft估计效果也不好，压缩不了多少
。。
我需要至少4位有效数字吧。。。
放硬盘上反复读取不可行，因为我的是大型并行计算，（数据）内存总量》1000G，io
太慢了 |
|
|
w*******x
发帖数: 489 | 12 我目前跑的程序用4T内存跑。4K node 每个node 1G
并且越多越好。即将出马的机器有16T，我够用了。
所以我这个问题不再是问题了，也不压缩了。谢谢回复。 |
|
a*******8
发帖数: 2299 | 13 有一个terabyte的地图,分辨率相同现在要产生低分辨率的图, (低分辨率再产生更低分
辨率的图) (产生低分辨率图的算法,由你自己决定)一共需要多少存储空间。 |
|
f******h
发帖数: 45 | 14 也找工作了一段时间了，从版上学了很多，上周G家面完了，求个bless。
之前的一些都挂了，还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦！！
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
n*******3
发帖数: 105 | 15 算法是否在工作中经常用，这个和公司和产品关系比较大。拿我们公司来说吧，上个季
度有三个项目涉及到比较繁琐一点的算法。
NETFLOW数据的压缩。我们产品的一个模块需要处理存储大量的NETFLOW数据（一天几个
TB）。用普通的压缩算法（比如GZIP之类），能压缩到30%左右。国内招的一个实习生
在我们一个老年工程师的指导下，针对NETFLOW的特点，实现了一个专门的压缩算法，
能压缩到15%左右。这个算法我们正在申请美国这边的专利。
服务器程序A，因为需要把超过10M的记录存储在类似JAVA HASHMAP的数据结构
中。但如果直接用HASHMAP的话，内存效率太低（不支持primitive types, 里面的
MapEntry更是对象套对象，每个对象什么都不干就是16字节的开销）。所以工程师基于
CUCKOO HASH（这是70
年代发明的一种算法，有很好的CACHE LOCALITY），实现了自己的HASHMAP。
服务器程序B，B负责存储历史时间。每个事件都有一个开始时间与结束时间（比如张三
9
点开始吃早饭，10点才吃完）。所有对这些事件的查询都指定了一个时间范围比如（9
：... 阅读全帖 |
|
发帖数: 1 | 16 联系方式：微信178592880，qq：3369387347，邮a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="cb2f6871f8f8fdf2f8f3fcf8fffc8bbabae5a8a4a6">[email protected]/* */;
本人（工科博士毕业，工作7年）长期从事基于MATLAB、C/C /C#的算法开发，有丰富
处理复杂算法的经验，长期承接来自学生、公司的算法开发，保质保量，不外包。有意
请联系。
主营专业：
计算机程序开发：
C# C C（VS）编程，网站设计，应用程序开发、数据库、数据结构
信号处理：
傅里叶变换 各类滤波器设计 特征提取 频谱分析 信号去噪 信
号压缩 均衡器 心音信号 自适应滤波
语音方向：
识别增强 去噪 变声 压缩 分析 加
解密 采集 合成
通信仿真与设计：
无线通信 信道估计 调制解调
图像处理：
识别融合 滤波 压缩 边缘检测分割
跟踪 采集 加解密 预处理 特征提取
算法：
神经网... 阅读全帖 |
|
发帖数: 1 | 17 联系方式：微信178592880，qq：3369387347，邮a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="1cf8bfa62f2f2a252f242b2f282b5c6d6d327f7371">[email protected]/* */;
本人（工科博士毕业，工作7年）长期从事基于MATLAB、C/C /C#的算法开发，有丰富
处理复杂算法的经验，长期承接来自学生、公司的算法开发，保质保量，不外包。有意
者请联系。
主营专业：
计算机程序开发：
C# C C（VS）编程，网站设计，应用程序开发、数据库、数据结构
信号处理：
傅里叶变换 各类滤波器设计 特征提取 频谱分析 信号去噪 信
号压缩 均衡器 心音信号 自适应滤波
语音方向：
识别增强 去噪 变声 压缩 分析 加
解密 采集 合成
通信仿真与设计：
无线通信 信道估计 调制解调
图像处理：
识别融合 滤波 压缩 边缘检测分割
跟踪 采集 加解密 预处理 特征提取
算法：
神经... 阅读全帖 |
|
发帖数: 1 | 18 联系方式：微信178592880，qq：3369387347，邮a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="d83c7b62ebebeee1ebe0efebecef98a9a9f6bbb7b5">[email protected]/* */;
本人（工科博士毕业，工作7年）长期从事基于MATLAB、C/C /C#的算法开发，有丰富
处理复杂算法的经验，长期承接来自学生、公司的算法开发，保质保量，不外包。有意
者请联系。
主营专业：
计算机程序开发：
C# C C（VS）编程，网站设计，应用程序开发、数据库、数据结构
信号处理：
傅里叶变换 各类滤波器设计 特征提取 频谱分析 信号去噪 信
号压缩 均衡器 心音信号 自适应滤波
语音方向：
识别增强 去噪 变声 压缩 分析 加
解密 采集 合成
通信仿真与设计：
无线通信 信道估计 调制解调
图像处理：
识别融合 滤波 压缩 边缘检测分割
跟踪 采集 加解密 预处理 特征提取
算法：
神经... 阅读全帖 |
|
t*****a
发帖数: 106 | 19 看别人面经，有道题不理解
原帖地址:http://www.mitbbs.com/article_t/JobHunting/32622081.html
为了阅读方便，我把其中用到的部分摘出来，感谢bainikolaus提供面经。
“第四轮
问我知不知道zip文件，我说用过但不知原理。他就说我们来讨论一下
假设一个文件压缩后的表示是
#3, #5, #6, 2 5, #8...
”#k“形式的代表这个数字k，两个数字“i j”形式的代表取前 i 个
数字做 j 长的 circular重复，像上面那个表示，前面3个都是表示单个数字，
然后 2 5表示取前2个数字 （既56），组成5个数字，不够的从头再取，所以就是56565
最后上面解压缩后应该为
3, 5, 6, 5, 6, 5, 6, 5, 8...
要我写的是压缩算法的代码。
我提出从头扫，一边一边用hashtable记下见过的number，每前进一位就检查hashtable
有没有符合当前数字模式的number出现过，然后他说还不错，写代码。一边写一边出现
bug，一边发现很多写代码前没考虑的东西，最后勉强算写完，时间也到了，他说这个... 阅读全帖 |
|
l*****y
发帖数: 337 | 20 AOD肯定会是HD－DVD的介质之一，但是我认为不会是唯一的介质
HD－DVD统一指的更加多的是codec和版权保护的统一，而不一定是介质的统一
700MB的divx当然和dvd有质量差距
divx设计的初衷就是是来backup dvd的，或者
网络传输的，divx采用的内容源就是dvd，
怎么可能压缩后超过dvd呢？最多在80%的人眼中打个平手，700M的话
估计90％的人都可以立即看出高下。
但是如果采用HD 的raw source，大家同样码流会是如何？
DVD用MPEG2的码流压缩成8M/s
divx用xvid，也压缩成为8M/s
你肯定在这个case下面，divx的xvid不如MPEG2么？
提醒一下MPEG4 part10也是替代MPEG2成为HD压缩算法的一个候选
所以说bitrate根本不是everything，高的bitrate要和好的算法在一起才行
说穿了MPEG2，wm9，H.264都是压缩算法，就看谁理论上谁更加有效率
wm9和H.264在7-8M的码流下，体现的1080i/p的图像质量完全超过了MPEG2在同样码流
下的清晰度（480p)
而且wm9或者H.2 |
|
a**a
发帖数: 4 | 21 我理解的过程应该是：
子串和母串的数组/链表表示 ---(转换)---> 更优的数据结构 ---(匹配)---> 子串
在母串中定位
题目要求的时间和空间复杂度，是针对“匹配”算法，不是针对 “目标串转换” 的算
法。
考的是使匹配更优所需的串的数据存储结构。
哈夫曼压缩只是一种转换存储的方式，压缩算法的优劣的确和问题无关，关键是压缩所
得的结果是否有利于匹配，当然，这时候的匹配算法很可能必须在转换域（压缩域）中
直接进行（即不需要解压缩），否则的话，是没有意义的。 |
|
J*********n
发帖数: 6974 | 22 关于 “6D低感画质不如5D2”、“6D低感涂抹严重” 的问题，其实是JPG机内压缩算法
发生了改变。
60D之前，机内压缩算法就相当于DPP中的“锐度”，60D以后，改为DPP中的“非锐化滤
镜”算法，但第二项精细度（相当于Photoshop中“USM锐化”的“半径”，其实USM的
意思就是“非锐化遮罩”）被强制默认为7，而且不可在机内更改。佳能官方说明是，
“精细度”数值越高，图像轮廓越粗。这就是“涂抹”的罪魁祸首。
只要在DPP中把RAW图像的“精细度”数值降低到2以下，细节就全回来了，大家可以在
DPP中用前后比较的方式，看调整前和调整后的差别。非锐化滤镜的“半径”，被佳能
取名为“精细度”，给大家造成错觉，以为精细度数字越高，图像越精细，其实正好相
反。如果不改这个数值，即使拍了RAW，用DPP出JPG，还是和机内一样的“涂抹”感，
当然，用LR和其他第三方RAW软件就不存在这样的问题了。
这个问题不仅在6D中存在，而且存在于60D以后的全部机型，包括5D3、1DX。5D2推出时
，佳能还没有非锐化滤镜算法，机内JPG压缩算法还用的是“锐度”，所以才显得“低
感画质好”。
另... 阅读全帖 |
|
l**p
发帖数: 474 | 23 8.6.3．jpeg文件
1．简介
jpeg(joint photo graphic experts group，发音做jay-peg)文件格式最初由
c-cubemicrosystems推出，是为了提供一种存储深度位象素的有效方法，例如对于照片扫
描，颜色很多而且差别细微(有时也不细微)。jpeg和这里讨论的其他格式的最大区别是
jpeg使用一种有损压缩算法，无损压缩算法能在解压后准确再现压缩前的图象，而有损压
缩则牺牲了一部分的图象数据来达到较高的压缩率。但是这种损失很小以至于人们很难察
觉。
jpeg图象压缩是一个复杂的过程，经常需要专门的硬件来帮助。首先图象以象素为单
位分成8*8的块。然后，每个块分三个步骤被压缩。第一步使用dct(discretecosinetrans
form)离散余弦变换把8*8的象素矩阵变成8*8的频率（也就是颜色改变的速度）矩阵。第
二步对频率矩阵中的值用量化矩阵进行量化，滤掉那些总体上对图象不重要的部分。第三
步，也就是最后一步，对量化后的频率矩阵使用无损压缩。
因为被量化后的频率矩阵缺了许多高频信息，通常能被压缩到一半甚至更 |
|
s********o
发帖数: 3783 | 24 面试遇到的题目有非常多都是leetcode原题
比如我上面提到的2sum，跟leetcode一模一样，一模一样的我就不说了。
下面是一些题，不分先后，不分公司，全混在一起说
1，leetcode 2sum，用O(nlogn)和O(n)怎么做
2，leetcode 2sum，如果是小于不是等于怎么做，3sum怎么做，小于x怎么做
4sum怎么做，小于x怎么做，只输出符合条件（小于x）的总个数但是不需要输出具体数
怎么做，不但输出总个数还要输出具体答案怎么做，k sum 小于x怎么做，
k sum有没有多项式解？证明之
3，一个城市的地图（mxn矩阵），求从左上到右下一共有多少种可能的路线（只能向右
和向下）。先用程序写（利用通项公式递推），然后让我在白板上写close form公式
其实close form非常非常简单，只不过我没见过这道题，当场没有看出来。但是我硬挺
着从通项公式开始用矩阵分解去求解close form，最后在面试官的一点帮助下还是写出
来了公式，最后面试官表示我的数学基本功非常令他吃惊。（我心里想好歹也是学过几
门数学课的）。。。
4，还是数学题，求k个数的最大公约数... 阅读全帖 |
|
p*k
发帖数: 23 | 25 "除了噪声以外，音频压缩算法也是决定声音质量的关键因素之一。实现这个算法可以是
硬件上的（快，但是费电），也可以是软件上的。"
-- 民科暴露了：播放压缩音频文件AAC/MP3的时候，是解码操作，不是编码（压缩）操
作，比编码省电得多。
另外说一句，音质取决于源音频质量，压缩算法，解码算法，以及耳机。苹果的AAC跟
MP3都是差不多的东西，CD比MP3和AAC都要好：
http://www.stereophile.com/features/308mp3cd
但是苹果那种不到10块钱(虽然卖几十块）的耳机太差，你说听着好估计是果粉心理作
用。 |
|
|
b*********s
发帖数: 115 | 27 昨天onsite完的，趁还记得上来写一下，面的不好，求bless。
一轮店面
第一题判断一个string的开头第一个字母是不是大写，两行代码就能写完，没有任何陷
阱。第二题让我用Java（因为我本来用python）写判断binary tree是不是bst。两个题
都很简单，然后还让我说一下自己做过的最challenging的一个project，整个面试不到
二十分钟就说问完了问我还有没有问题，我连忙问他为什么这么快是不是我什么地方做
错了他不愿继续问下去。答曰他在G工作七年多面了不下一百人，十分清楚哪些人去
onsite不是在浪费他们engineer的时间，觉得我没有问题。。。
过了一周果然hr说去onsite，由于我所在的城市有G的office，所以去那里面，早上三
轮然后吃午餐，下午再两轮，一共五轮
第一轮
给一个矩阵，每个格子上有三种可能，空房，阻碍物或者是保安，阻碍物不能进，空房
四个方向都能进，要写代码给每个空房标记其离最近的保安的距离，比如
000
BGG
B00
B表示障碍物，G表示保安，0表示空房，应该标记为
211
BGG
B11
我说扫一遍矩阵，然后遇到每个G就bf... 阅读全帖 |
|
|
g**o
发帖数: 3033 | 29 这个要看压缩算法的原理了，有些摄像头就是打打电话用的，配套压缩算法是针对语音
的，
这类算法去压音乐失真就比较大，音调什么的是可能有变化。不过这种情况应该比较少
见，
多半还是没校准。 |
|
y*********u
发帖数: 2014 | 30 2。
在这种情况下，如何保持3500基本开销再加小孩教育，交通，医疗=6000/月+房呢？
1）吃饭水果零食物等等，全家压缩至2000（可以跟上海比较扣的退休人士相比，比他
们还惨，人家可是没小孩的）；
2）日用，比如洗发水，肥皂，梳子牙膏洗衣粉枕头被褥等等，全家压缩至100（要省着
用啊，东西烂了也别换，一床凉席普通超市都要100，当然你可以去地摊上买50的。）
3）水电煤气电话网等，全部压缩成500（注意省电水电话），网就别上了，手机只接不
打。
4）娱乐玩具书籍游乐等全家压缩至100（小孩可怜啊，每个月出门划个船就好了。平时
家附近晃晃，不要去太远，否则交通什么的也要上）；
5）服装鞋袜皮包化状首饰全家压缩成300（大人别买了，钱只够大人单只皮鞋的，小孩
只能检旧的，破的补补），
6）人情送礼压缩成300（随便别人家里坐坐都要带100多的礼物，老师社会网的都要人
情，比这个再低，大人小孩社会上都不用混了，同学同事朋友都不用见了，过年也不用
过了。）
7）最后只剩下200块机动，比如某次去了超市，一不小心就没了。或者小孩需要交出游
啊，额外保险等的费用。或者1年全家3个人过3生日， |
|
a*f
发帖数: 5682 | 31
和压缩算法有关。原片jpeg压缩的比较大，lr导入后解压，导出重新压缩的时候选择的
压缩率较低。因此出片更大。我觉得扫描最好出tif这样的无损格式进行保存。辛苦拍
出来扫出来，却人工的有损压缩，就好比以前拍出底片却把底片扔了只保存print一样。 |
|
O*******d
发帖数: 20343 | 32 其实focus stack就有这个意思。 可以在最近到最远拍摄128张或256张不同焦点的照片，
后期再把它们合成一张，每张照片只取最清晰的像素。 如果相机可以立即处理，就不需
要同一个拍摄存几百张照片了。 如果真的要存几百张照片，就要研究新的压缩voxel的
技术。 也许可以借鉴video的voxel压缩技术。 HD录像的压缩算法相当牛X，可以把
30帧画面压缩的比一帧未压缩的还小。 |
|
m**********t
发帖数: 385 | 33 北京的一家上市公司，具体职位描述如下，有需要可随时联系我或邮件给我！
l*******[email protected]写明想申请哪方面的岗位；
岗位名称：图像处理算法
工作职责：
1、图像处理算法的研究开发，主要是图像的放大和压缩算法；
2、利用matlab等工具进行算法的实现与验证。
任职资格：
1、图像处理，应用数学或计算机等相关专业硕士及以上学历；
2、3年以上工作经验，有相关算法开发经验；
3、熟悉数字图像处理技术，熟悉super resolution、去噪声、边缘锐化等算法；
4、熟练使用c/c++，matlab，掌握常用图像处理算法的原理及具体实现。
Sputter
岗位描述
负责LTPS制程中的Sputter相关工艺研发
岗位要求：
1.具有在显示领域的工作经验，熟悉TFT工艺流程
2.熟悉LTPS工艺中的Sputter工艺/设备，具有2年以上的LTPS工作经验
3.从事过Sputter相关的工艺开发、优化工作
4.具备良好的沟通、协调能力和团队合作精神
岗位名称：电路设计（FPGA）
工作职责：
1、LTPS AMOLED 模组设计及调试
2、LTPS AMOLED... 阅读全帖 |
|
m**********t
发帖数: 385 | 34 北京的一家上市公司，具体职位描述如下，有需要可随时联系我或邮件给我！
l*******[email protected]写明想申请哪方面的岗位；
岗位名称：图像处理算法
工作职责：
1、图像处理算法的研究开发，主要是图像的放大和压缩算法；
2、利用matlab等工具进行算法的实现与验证。
任职资格：
1、图像处理，应用数学或计算机等相关专业硕士及以上学历；
2、3年以上工作经验，有相关算法开发经验；
3、熟悉数字图像处理技术，熟悉super resolution、去噪声、边缘锐化等算法；
4、熟练使用c/c++，matlab，掌握常用图像处理算法的原理及具体实现。
Sputter
岗位描述
负责LTPS制程中的Sputter相关工艺研发
岗位要求：
1.具有在显示领域的工作经验，熟悉TFT工艺流程
2.熟悉LTPS工艺中的Sputter工艺/设备，具有2年以上的LTPS工作经验
3.从事过Sputter相关的工艺开发、优化工作
4.具备良好的沟通、协调能力和团队合作精神
岗位名称：电路设计（FPGA）
工作职责：
1、LTPS AMOLED 模组设计及调试
2、LTPS AMOLED... 阅读全帖 |
|
e****9
发帖数: 316 | 35 用hash的目的是缩减所需要的存储
比如下面的字串长度可能是1000生成long的hash只要8 bytes.
abcd....
但是同时还要用这些字串来排序，hash之后排序完全没有了。
现在就想要没有一个算法，既可对原来的字串做某种压缩，并且压缩之后的不改变原来
的排序顺序。 |
|
l*********r
发帖数: 136 | 36 背景：中部弱校master，去年五月毕业，刚工作一年（中部小公司），骑驴找马中。
Onsite一共五轮：
--------------------------------------
第一轮（中东人）：
给一个字符串，让压缩并解压，压缩算法类似leetcode中的count and say
输入：aabbbccd 压缩结果：2a3b2cd（注意，'d'前面没有'1'）
引申：输入中如果有数字的话，解压时需要注意歧义问题，例如2a可以解压为'2a'或
者'aa'，问如何解决。答曰用类似ascii码中加反斜杠的做法，或者加个header来标
志压缩过的位，表示同意。
第二轮（老印）：
（leetcode） edit distance，以DP解之，喜。
（leetcode） word ladder，直接给出BFS，不喜，要优化，想了半天给出的答案皆不
喜，最后提示我可以双向BFS，时间不够，没有给出代码。
-----------------午饭-------------------
第三轮（老白）
给一个int的矩阵arr，让返回一个同样大小的result矩阵，每一个result[i][j]... 阅读全帖 |
|
t*******r
发帖数: 22634 | 37 属实，就好比有了“牛鼻压缩算法”，就能更有效的利用硬盘。
“牛鼻压缩算法”其实好比大脑的“符号化”的能力。。。其实大脑所有的能力
都需要靠重复来加强。。。但培养高级点的，比如大脑的“符号化”的能力，
简单型重复练习真不一定靠谱，要复杂型综合型的练习才更有帮助。。。 |
|
w**********5
发帖数: 1741 | 38 程序员的办法
FORTRAN程序员：
01 打开冰箱门
02 把大象放进去
03 关上冰箱门
04 如果还有大象，GO TO 01
APL程序员：
写了仅仅一行代码，不但把大象装进去了，还能控制冰箱在万米高空变形，演算飞行姿
态和火力控制，并和数以万计的外星人飞船战斗。
C 程序员：
将大象编码成二进制文件，然后编译进冰箱的程序代码里。
JAVA程序员：
你还在用面向过程的思维看问题？一个设计良好的冰箱必然封装了相应的方法，所以你
只要调用“冰箱.放入动物(大象)”就行了。
COBOL 程序员：
对和自己一样濒临灭绝的大象寄予了深切的同情。
汇编程序员：
将栈命名为冰箱，然后 PUSH 大象。
算法学家：
用Lempel–Ziv–Welch压缩算法将大象压缩。
网络安全专家：
把大象放进冰箱会使冰箱的冷冻区溢出，这将导致攻击者获得冰箱的系统权限。
硬件工程师：
我可以用随身携带的瑞士军刀把冰箱的各部分拆下来，然后连同大象装在一起。 |
|
w***y
发帖数: 78 | 39 一类函数，输入是若干个整型数（范围都比较小，比如0-16），输出是字符串。
在不同输入下，输出大同小异，比如
f(0)="hello_1_guru"
f(1)="hello_a_guru"
f(2)="hello_a1_guru",
f(3)="hello__guru",
...
请问用那一类算法可以用来压缩此类函数？字符串编辑（如unix diff)的方法可行吗？
另外，如果偶尔可能有例外的情况，比如
f(10)="hello";
又该如何处理呢?
先谢了。 |
|
m********5
发帖数: 17667 | 40 按经验, 大小0.1TB起算
data feeding速度超过100MB/s
一次性需要操作大于内存容量的数据, 比如想在一般的PC上对几十个GB的矩阵进行操作
.
如果传输时间远低于计算时间,那么我认为是典型 computing intensive, 用GPU问题不
大. 这个楼主完全可以用CPU测一下. 但看起来楼主说的计算复杂度似乎不高, 感觉GPU
提升有限, 浪费精力不划算. 即使是8GB-VRAM,只有10GB静态数据,如果不能一次性传入
VRAM, 又需要random access, 上下载是会很频繁的. 得不偿失. 如果楼主的数据可
以用random access性能较好的压缩算法来进行大比例压缩, 可以去偿试一下. GPU和
VRAM之间的带宽只有在数据
能全部upload到VRAM, 或者可顺序读写的时候才能体现优势. 另外楼主认为所有数据包
括中间数据储存在内存(用CPU计算)就没有I/O或者I/O的时间消耗就可忽略不计也是错
误的, 如果是这样我们就不用讨论FFT的算法优化, 当然楼主的case应该不是这种.
关于GPU有很多学术文章已经发过了, 一直很热, ... 阅读全帖 |
|
w**********5
发帖数: 1741 | 41 程序员的办法
FORTRAN程序员：
01 打开冰箱门
02 把大象放进去
03 关上冰箱门
04 如果还有大象，GO TO 01
APL程序员：
写了仅仅一行代码，不但把大象装进去了，还能控制冰箱在万米高空变形，演算飞行姿
态和火力控制，并和数以万计的外星人飞船战斗。
C 程序员：
将大象编码成二进制文件，然后编译进冰箱的程序代码里。
JAVA程序员：
你还在用面向过程的思维看问题？一个设计良好的冰箱必然封装了相应的方法，所以你
只要调用“冰箱.放入动物(大象)”就行了。
COBOL 程序员：
对和自己一样濒临灭绝的大象寄予了深切的同情。
汇编程序员：
将栈命名为冰箱，然后 PUSH 大象。
算法学家：
用Lempel–Ziv–Welch压缩算法将大象压缩。
网络安全专家：
把大象放进冰箱会使冰箱的冷冻区溢出，这将导致攻击者获得冰箱的系统权限。
硬件工程师：
我可以用随身携带的瑞士军刀把冰箱的各部分拆下来，然后连同大象装在一起。 |
|
w**********5
发帖数: 1741 | 42 程序员的办法
FORTRAN程序员：
01 打开冰箱门
02 把大象放进去
03 关上冰箱门
04 如果还有大象，GO TO 01
APL程序员：
写了仅仅一行代码，不但把大象装进去了，还能控制冰箱在万米高空变形，演算飞行姿
态和火力控制，并和数以万计的外星人飞船战斗。
C 程序员：
将大象编码成二进制文件，然后编译进冰箱的程序代码里。
JAVA程序员：
你还在用面向过程的思维看问题？一个设计良好的冰箱必然封装了相应的方法，所以你
只要调用“冰箱.放入动物(大象)”就行了。
COBOL 程序员：
对和自己一样濒临灭绝的大象寄予了深切的同情。
汇编程序员：
将栈命名为冰箱，然后 PUSH 大象。
算法学家：
用Lempel–Ziv–Welch压缩算法将大象压缩。
网络安全专家：
把大象放进冰箱会使冰箱的冷冻区溢出，这将导致攻击者获得冰箱的系统权限。
硬件工程师：
我可以用随身携带的瑞士军刀把冰箱的各部分拆下来，然后连同大象装在一起。 |
|
w**********5
发帖数: 1741 | 43 程序员的办法
FORTRAN程序员：
01 打开冰箱门
02 把大象放进去
03 关上冰箱门
04 如果还有大象，GO TO 01
APL程序员：
写了仅仅一行代码，不但把大象装进去了，还能控制冰箱在万米高空变形，演算飞行姿
态和火力控制，并和数以万计的外星人飞船战斗。
C 程序员：
将大象编码成二进制文件，然后编译进冰箱的程序代码里。
JAVA程序员：
你还在用面向过程的思维看问题？一个设计良好的冰箱必然封装了相应的方法，所以你
只要调用“冰箱.放入动物(大象)”就行了。
COBOL 程序员：
对和自己一样濒临灭绝的大象寄予了深切的同情。
汇编程序员：
将栈命名为冰箱，然后 PUSH 大象。
算法学家：
用Lempel–Ziv–Welch压缩算法将大象压缩。
网络安全专家：
把大象放进冰箱会使冰箱的冷冻区溢出，这将导致攻击者获得冰箱的系统权限。
硬件工程师：
我可以用随身携带的瑞士军刀把冰箱的各部分拆下来，然后连同大象装在一起。 |
|
c******u
发帖数: 739 | 44 我自己设计了一个压缩算法。贡献很小所以没人用没人care。只有我会解压。压缩完把
压缩程序删掉。回头自己再写一个解压程序解压就行。 |
|
z*********n
发帖数: 28 | 45 今天面a家，感觉最后一轮bar raiser凶多吉少。
出了俩题，第一题股票买卖，秒俩
第二题是压缩字符串，比如abcddddd要成为a1b1c1d4。
可以假设压缩后的长度小于压缩前，也保证所有count都在1到9
如果用额外空间，很简单
但要求in place
以前完全没想到过这种要求，所以a->a1的case挺难handle的。 最后在烙印提示下，勉
强想出两遍遍历的方法，
第一次： abcd4
第二次从后往前存，变成 a1b1c1d4
有其它更巧妙解法吗？ |
|
a9
发帖数: 21638 | 46 你还是先去看看现在这些压缩规范的算法再提新的吧。
或许有很多你的想法早就已经实现了。
或许你的一些想法，根本就压缩不了。
可能 |
|
b****g
发帖数: 192 | 47 给定字符串T，然后从后向前扫一遍，能建立T的suffix tree。这一步我会做。
但是从后向前扫描有缺陷，那就是必须知道字符串的结尾，所以不能用于stream相关的
场合及压缩算法。
我知道有方法可以从前向后扫描，建立suffix tree。我从没做过这种算法。面试时有
人问这种算法吗？ |
|
