【计概】有关于LZW算法

楼主: loveyou999 (lovelovelove)   2015-08-11 22:59:58
网络查到的演算步骤如下~
步骤一
使用资料源的输入符号集合A中的所有符号字符来建立一本初始的字典,其中每一个符号
被当成字典中的一个字。
步骤二
找出目前待编码资料中和字典的字相同(相匹配)之最长子序列(符号串)。将此匹配子序
列编码,送出一个字段的编码结果[index],其中index:最长匹配子序列在字典中的索
引位置。此匹配子序列与其后的一个符号连结成一个新子序列,将此新序列加入字典中
成为一个新字。
步骤三
重复步骤二直到待编码资料都处理完毕才停止。
我按照上面方法要求【xyx xyx xyx】的LZW编码如下图
http://i.imgur.com/NAhePO7.jpg
但这题的答案是1213434,说明如下~
先作成初始字典:1=x,2=y,3= (空格)
将xyx编码成121,接着再加上空格,成为1213,因为有了空格,我们知道前面的字串
已形成一个单字,故将xyz加到字典内,即4=xyz,故其编码为~1213434
请问~我的作法是不是有问题呢?谢谢
作者: emstarbucks (花榭清风)   2015-08-11 23:10:00
哇现在计概连这都考喔@@ 看来改天连lz78 77都会考
作者: oklp1415 (天生我材)   2015-08-11 23:17:00
如果LZ都能考LZ77、LZ78、LZW、LZO下次考出来也不例外了
作者: emstarbucks (花榭清风)   2015-08-11 23:19:00
对阿 我好讶异.. 请问这哪一年的考题?我想哪天突然不考huffman跑去考算数编码都不意外了国考考题真是处处充满惊奇(!?) 囧
楼主: loveyou999 (lovelovelove)   2015-08-11 23:29:00
哈哈~我不知国考有没有考过,但课本有写,就看了啊但课本写的方式看不懂
作者: oklp1415 (天生我材)   2015-08-11 23:48:00
拿来考资讯类的不为过,因为资讯类的考生都异于常人!!
作者: youarestupid (ptt卒仔很多)   2015-08-11 23:53:00
有 这国考考过
作者: emstarbucks (花榭清风)   2015-08-12 00:14:00
课本错了另外 你少编了"空白"X你题目说空白在初始字典里的符号所以你既然编了X"空白" 那"空白"X你也应该加入字典题目解法空白是一个断点 如果是这样他不该编码"3"可以请问是哪一本书写的吗? 他解法很有问题吧@@
作者: carterdunk (妳能听到我的心吗)   2015-08-12 08:35:00
去年资讯技师的计概考题 会不会不影响上榜
楼主: loveyou999 (lovelovelove)   2015-08-12 19:38:00
computer science an overview 这一本书写的刚看了一下去年技师,真的有考哦~题目差不多上网查了一下,对几乎是写课本内的解法,但说明很简略所以~到底那个才是正确的呢?回em兄~确实少编了一个,谢谢提醒
作者: emstarbucks (花榭清风)   2015-08-12 21:11:00
他原始算法就是你的解法阿 如果你要处理那种断点你就必须在程式里做手脚阿 你懂我的意思吗通常"默认"的字典会是ascii code 不在里面的就要编如果你今天碰到空白不想处理 那你绝对要特别写出来的但事实上字典大小我们会限制 所以有些符号会特别处理oh 我要更正一下我认为他空白特别处理编3错是因为 我一直记space是32XD" SORRY 用太习惯 看到不是32就觉得他错了简单说 原始的算法精神不在字典就要编但是我上面有说 字典大小我们会限制如果都编进去是一件很蠢的事情 所以我们真的在压缩的时候 通常0跟32我们会保留起来所以课本那样没错 他有处理SPACE 是我用习惯ASCII= =你的一定没错 你只是没特别处理空白 都编进去而已喔然后他这题也没说是变动长度还是固定长度总之你的解法是没有问题的 别担心
楼主: loveyou999 (lovelovelove)   2015-08-12 22:25:00
谢谢EM兄的回答~总之土法炼钢的方法不会有错就对了 3Q
作者: emstarbucks (花榭清风)   2015-08-12 22:38:00
http://imgur.com/bBjaWnN 给你安心一下原文书里不考虑效率/SIZE的原始做法 编进去就对了
楼主: loveyou999 (lovelovelove)   2015-08-12 22:51:00
看懂了 谢谢 Orz

Links booklink

Contact Us: admin [ a t ] ucptt.com