Researcher finds optimal fix-free codes
http://www.physorg.com/news157987290.html
April 3rd, 2009
※ 譯註：若一編碼同時為前綴碼（prefix code）與後綴碼（suffix code），則此編碼為 fix-free code。以 fix-free code 編碼的資料可同時從前、後端解碼，增加解碼速度。若從前端解碼有誤的資料，可從後端開始解碼直到資料錯誤位置。
(PhysOrg.com) -- 在 David Huffman 發展 Huffman coding（霍夫曼編碼），一種 entropy encoding（熵編碼，一種無失真資料壓縮方案，固定長度的輸入符號會被相關的、唯一的可變長度前綴碼編碼字 (codeword) 取代。在此，資訊量越大，體系愈有規則、完善，熵就越小，反之亦然），之後 50 年，一位 Texas A&M 大學電機與電腦工程系成員發現了一種方法來建構最有效率的 fix-free 編碼。
Huffman coding 使用一可變長度編碼表以便為每一個符號選擇代表物，結果產生一前綴碼（亦即代表某些特定符號的位元字串 (bit string) 都是唯一的），而最常見之字元（characters）以短於「較不常見之來源符號的位元字串」的位元字串來表現。Huffman 之所以能夠設計此類型最有效的壓縮方式，因為沒有與其他唯一「位元字串」映射的個別來源符號，將產生較小的平均輸出大小，這時實際符號的頻率將與那些用來創造此編碼的一致。
Dr. Serap Savari，該校電機與電腦工程系副教授，已發展出尋找最佳化 fix-free code 的第一種方法。該方法是可變長度編碼，其中沒有任何一個編碼字為其他編碼字的前綴或後綴（譯註：即 minimum-redundancy）。
"我尋找最佳化 fix-free codes 的方法為高運算需求，但在這之前沒人解決這個問題，即使它首度在 1990 年被貼出來，" Savari 說。"較早的演算法以合理的有效方法（指時間上）產生良好的 fix-free codes，但沒有最佳性（optimality）的保證。"
雖然 fix-free codes 有相當多的應用，不過最重要的應用還是在通訊中。Fix-free codes 已經在 joint source-channel coding（聯合來源通道編碼）中被研究過，而且因為它能有效的同時進行前向與後向解碼的特性，加上發生錯誤時的復原能力，所以被應用在 H.263+ 與 MPEG-4 等影像標準中。在資訊檢索（information retrieval）的問題中它們也引起關注，例如直接在已壓縮文字中尋找模式。Savari 並不確定她的發現會如何影響這種於其他的 fix-free codes 應用，不過希望她的研究能為研究者與人們所用以實作出實用的系統。
"我的研究如同 Huffman 的，是基礎研究，其動機都是實際上的重要問題，而且那對於資料壓縮的理論有所貢獻，" 她說。
Savari 已獲邀前往全美許多大學的研究班討論她的發現。
※ 相關報導：
＊ 非破壞壓縮與 AI 獎金？
＊ 以電腦挖掘數百萬種隱喻
＊ 發現科學新知的電腦與機器人
＊ 「鹵莽」軟體更新 更快發現「對稱」
＊ 可即時產生高品質 3D 電玩材質的演算法
＊ 新演算法顯著提升路由效率
＊ 破記錄的解多工：640 Gbps
＊ 數位通訊技術協助釐清個人化治療途徑
＊ 新計算技術讓基因組的比對更加容易
＊ 基因的「選擇特徵」協助偵測細菌的天擇
＊ 新模型證明蛋白質如何找到正確的 DNA 序列
沒有留言:
張貼留言