[發明專利]一種改進的BWT數據壓縮方法及其硬件實現系統

有效

• 申請號: 201410571262.3
• 申請日: 2014-10-23
• 公開（公告）號: CN104284189B
• 公開（公告）日: 2017-06-16
• 發明（設計）人: 李冰;陳帥;董乾;劉勇;趙霞;王剛
• 申請（專利權）人: 東南大學
• 主分類號: H04N19/13
• 分類號: H04N19/13;H04N19/85;H04N19/91;H04N19/96
• 代理公司: 江蘇永衡昭輝律師事務所32250
• 代理人: 王斌

1.一種改進的BWT數據壓縮方法的硬件實現系統，其特征在于，包括：

輸入緩存模塊，用于暫存待處理字符串，并同步數據輸入和數據處理，處理完后將字符串輸出至Lyndon Word查找模塊；

Lyndon Word查找模塊，用于查找來自于輸入緩存模塊字符串中的最長Lyndon Word，并將查找到的最長Lyndon Word輸出至Lyndon Word緩存模塊，將各個最長Lyndon Word的長度輸出至Lyndon Word長度緩存模塊；

Lyndon Word緩存模塊，用于暫存輸出自Lyndon Word查找模塊的Lyndon Word供轉置模塊使用；

Lyndon Word長度緩存模塊，用于暫存Lyndon Word查找模塊中找到的所有Lyndon Word的長度和個數供排序模塊使用；

轉置模塊，用于完成Lyndon Word查找模塊中所有Lyndon Word的轉置并將轉置結果暫存至轉置緩存模塊；

轉置緩存模塊，用于暫存轉置模塊輸出的轉置結果供排序模塊使用；

排序模塊，用于將轉置緩存模塊中的所有字符串按字典序排序，并取最后一列作為BWTS方法的輸出，并暫存在輸出緩存模塊；

輸出緩存模塊，用于暫存輸出的字符串，供后續模塊使用。

2.根據權利要求1所述的系統，其特征在于，所述Lyndon Word查找模塊進一步包括：

取字符串子模塊，用于從輸入緩存模塊取字符，并記錄此時所取字符串的長度，自字符串首字符開始逐位讀入，每增加一位便將其輸入后續模塊進行Lyndon Word判斷，若出現Lyndon Word，則將字符串長度輸入Lyndon Word長度緩存模塊、長度置零，下次取字符串則自該次取字符串的最后一個字符開始；

移位子模塊，用于將取字符串子模塊的字符串輸入Lyndon Word判斷子模塊以及將該字符串進行逐次移位，并將所有移位字符串輸入N*N寄存器；

N*N寄存器，用于存儲來自于移位子模塊的待判斷字符串的所有移位字符串供Lyndon Word判斷子模塊處理；

Lyndon Word判斷子模塊，用于逐次從N*N寄存器中取出移位字符串并與原字符串對比，其中：對比個數是待判斷字符串的長度，若對比結果顯示原符串字典排序最小，則該字符串為Lyndon Word，將各個最長Lyndon Word的長度輸出至Lyndon Word長度緩存模塊。

3.根據權利要求1所述的系統，其特征在于，所述轉置模塊進一步包括：

最長Lyndon Word長度判別子模塊，用于通過Lyndon Word長度暫存模塊中的內容判別被處理字符串的最長Lyndon Word的長度，并將該長度傳送至字符串擴展子模塊；

字符串擴展子模塊，用于將Lyndon Word緩存模塊中的所有Lyndon Word都擴展至最長Lyndon Word的長度供循環移位子模塊使用；

循環移位子模塊，用于將來自于字符串擴展子模塊的Lyndon Word依次循環移位，并儲存至轉置緩存模塊。

4.根據權利要求1所述的系統，其特征在于，所述排序模塊包括：

排序子模塊，用于將轉置緩存模塊中的字符串按照字典序排序供BWTS結果獲取模塊使用；

BWTS結果獲取模塊，用于將排序子模塊的排序結果的最后一列讀出，作為BWTS方法的輸出，并暫存至輸出緩存模塊。