[發(fā)明專利]基于字典的并行壓縮編碼器

有效

• 申請?zhí)枺?/td>: 201580057220.0
• 申請日: 2015-10-21
• 公開（公告）號: CN106852185B
• 公開（公告）日: 2019-10-25
• 發(fā)明（設(shè)計）人: 巴納比·道爾頓;扎赫拉·臘克;曼努埃爾·薩爾達(dá)納;布萊恩·穆迪
• 申請（專利權(quán)）人: 華為技術(shù)有限公司
• 主分類號: H03M7/30
• 分類號: H03M7/30;H04L29/06
• 代理公司: 廣州三環(huán)專利商標(biāo)代理有限公司 44202
• 代理人: 郝傳鑫;熊永強(qiáng)

本發(fā)明公開了利用歷史搜索進(jìn)行基于字典的壓縮的數(shù)據(jù)壓縮系統(tǒng)、設(shè)備和方法。所述系統(tǒng)、設(shè)備和方法可以使用并行處理技術(shù)進(jìn)行數(shù)據(jù)壓縮和編碼。所述系統(tǒng)、設(shè)備和方法可以為硬件提供內(nèi)存搜索技術(shù)。

相關(guān)申請案交叉申請

本申請要求于2014年10月21日遞交的發(fā)明名稱為“數(shù)據(jù)壓縮系統(tǒng)、設(shè)備和方法”的第62/066,572號美國臨時專利申請案的在先申請優(yōu)先權(quán)，以及于2015年10月20日遞交的發(fā)明名稱為“基于字典的并行壓縮編碼器”的第14/887,908號美國申請案的在先申請優(yōu)先權(quán)，這些在先申請的內(nèi)容以引入的方式并入本文。

技術(shù)領(lǐng)域

本文描述的實施例通常涉及數(shù)據(jù)壓縮系統(tǒng)、設(shè)備和方法，尤其涉及無損數(shù)據(jù)壓縮系統(tǒng)、設(shè)備和方法。

背景技術(shù)

數(shù)據(jù)壓縮涉及對作為輸入的符號序列進(jìn)行處理，并嘗試生成作為輸出的較短的序列。無損數(shù)據(jù)壓縮嘗試在不丟失信息的情況下，通過標(biāo)識并消除輸入數(shù)據(jù)中的統(tǒng)計冗余以減少輸出。

附圖說明

圖1是一些實施例中提供的數(shù)據(jù)壓縮系統(tǒng)的示例的示意圖；

圖2是壓縮處理的說明示例性輸入的示意圖；

圖3是壓縮處理的說明示例性輸入的可替代示意圖；

圖4是一些實施例提供的示例性數(shù)據(jù)壓縮方法的流程圖；

圖5是一些實施例提供的用于數(shù)據(jù)壓縮的比較器網(wǎng)絡(luò)的示意圖；

圖6是一些實施例提供的用于數(shù)據(jù)壓縮的時序圖的示意圖；

圖7是一些實施例提供的示例性數(shù)據(jù)壓縮方法的可替代流程圖；

圖8是一些實施例提供的數(shù)據(jù)壓縮系統(tǒng)的示例的可替代示意圖；

圖9是壓縮處理的說明示例性輸入的可替代示意圖；

圖10和圖11是一些實施例提供的說明編碼過程的表格。

為了進(jìn)行說明，這些附圖描述了示例性實施例。可以對這些示例性實施例進(jìn)行變型、選擇配置、選擇組件以及作出修改。

發(fā)明內(nèi)容

在第一方面，提供了一種用于對輸入數(shù)據(jù)流進(jìn)行編碼以生成壓縮輸出流的電路。所述電路包括：輸入單元，用于接收傳入的輸入數(shù)據(jù)流，所述輸入數(shù)據(jù)流包括：一系列令牌，其中每個令牌定義所述輸入數(shù)據(jù)流中的位置、長度和類型，所述類型為文字令牌或者復(fù)制令牌，每個文字令牌定義文字符號，每個復(fù)制令牌具有與所述數(shù)據(jù)流中一系列令牌中的另一令牌的位置的偏置；內(nèi)存設(shè)備，用于將所述輸入數(shù)據(jù)流的所述一系列令牌存儲在存儲位置。

所述電路包括：并行處理器，用于在參考所述輸入數(shù)據(jù)流的一系列令牌中各自令牌的位置之前的其他令牌時，利用對內(nèi)存設(shè)備中的所述輸入數(shù)據(jù)流的并行掃描對所述令牌進(jìn)行編碼以同時處理所述輸入數(shù)據(jù)流中的各個令牌，所述并行處理器通過基于所述并行掃描的結(jié)果消除所述輸入數(shù)據(jù)流中的一部分令牌來生成所述壓縮輸出流。

所述電路包括：多個比較器，用于對來自并行掃描的存儲器中存儲位置的一系列令牌進(jìn)行比較；內(nèi)存選擇器，用于為每個復(fù)制令牌選擇對應(yīng)于偏置的位置的存儲位置。所述電路包括：輸出單元，用于連接接收設(shè)備以輸出所述壓縮輸出流。

在一些實施例中，所述并行處理器采用反向計算、清除計算、正向計算的并行掃描以同時處理所述輸入數(shù)據(jù)流的令牌，以便更新用于生成所述壓縮輸出流的所述輸入數(shù)據(jù)流。

在一些實施例中，在生成所述壓縮輸出流時，所述并行處理器利用前導(dǎo)計算和布局計算消除所述輸入數(shù)據(jù)流的一部分令牌。