[發明專利]信息處理裝置、數據存取方法以及程序

在審

• 申請號: 201280052433.0
• 申請日: 2012-08-24
• 公開（公告）號: CN103890763A
• 公開（公告）日: 2014-06-25
• 發明（設計）人: 小柳光生;R.H.P.魯迪;海野裕也;今道貴司
• 申請（專利權）人: 國際商業機器公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F12/00;G06F17/28
• 代理公司: 北京市柳沈律師事務所 11105
• 代理人: 金景花

1.一種信息處理裝置，實現數據存儲器，包括：

最上位存儲器，構成所述數據存儲器，具有符號的每個條目的計數器；

一個以上的層次存儲器，分別構成所述數據存儲器，對每個層次定義了與頻度有關的代表值；以及

分配部，在所述最上位存儲器內對要存取的符號進行計數，根據計數器值而對所述最上位存儲器以及所述一個以上的層次存儲器進行分配，

所述分配部與對于從所述最上位存儲器移動的符號的存取對應地，使用對包含該符號的層次存儲器定義的與頻度有關的代表值，在所述最上位存儲器中復原該符號的條目。

2.如權利要求1所述的信息處理裝置，

所述計數器值保持符號的出現頻度值，所述復原包含根據所述代表值而設定反映了符號丟失的過去的出現頻度值、或者表示在出現頻度值中能夠包含的誤差的誤差值，

所述分配部設定所述誤差值而在所述最上位存儲器中追加條目，且在對于輸入數據的規定寬度的桶的邊界根據出現頻度值、誤差值以及輸入數據數的關系而判定在所述最上位存儲器中殘留的條目和從所述最上位存儲器移動到各個所述層次存儲器的條目。

3.如權利要求2所述的信息處理裝置，

所述代表值是所述層次存儲器內的符號平均出現頻度或者最大出現頻度。

4.如權利要求3所述的信息處理裝置，

所述代表值是根據對每個層次存儲器計數的符號的合計出現頻度和符號數而算出的所述符號平均出現頻度。

5.如權利要求1所述的信息處理裝置，

所述一個以上的層次存儲器至少具有兩個層次存儲器，

所述分配部在規定寬度的桶的邊界，將符號平均出現頻度比下位的層次存儲器低規定以上的上位的層次存儲器內的全部條目編入該下位的層次存儲器。

6.如權利要求1所述的信息處理裝置，

所述一個以上的層次存儲器至少包含基于鏈接結構的動態的樹以及基于簡潔數據結構的靜態的樹或者基于其中任一個結構的樹作為層次存儲器。

7.如權利要求1所述的信息處理裝置，

所述最上位存儲器是散列圖，所述一個以上的層次存儲器中的一個是基于鏈接結構的動態的樹，所述一個以上的層次存儲器中的另一個是基于LOUDS(Level?Order?Unary?Degree?Sequence，一級階一元等級序列)的靜態的樹。

8.如權利要求1所述的信息處理裝置，

所述分配部與對于所述最上位存儲器內的條目的存取對應地，增加所述計數器，且與對于在所述最上位存儲器以及所述一個以上的層次存儲器中的任一個中都不包含的符號的存取對應地，將該符號的條目在計數器中設定初始值并新追加到所述最上位存儲器。

9.如權利要求2所述的信息處理裝置，

用于判定要從最上位存儲器D移動到層次存儲器D_i的條目的出現頻度值f、誤差值Δ以及輸入數據數N的關系通過下述式(1)表現，其中，桶寬度通過1/e表示、桶識別值通過B(＝eN)表示、對層次存儲器D_i以及D_i+1設定的表示出現頻度的上限的閾值因子通過θ_i以及θ_i+1表示。

[數9]

θ_i+1(B-Δ)≤θ_i(B-Δ)···(1)

10.一種數據存取方法，由信息處理裝置執行以便對數據存儲器進行存取，信息處理裝置包括：

接受對于符號的存取的步驟；

在構成所述數據存儲器且對符號的每個條目設置了計數器的最上位存儲器內，對進行了存取的符號進行計數的步驟；

根據計數器值，分配到所述最上位存儲器和分別構成所述數據存儲器的一個以上的層次存儲器的步驟；以及

與對于從所述最上位存儲器移動的符號的存取對應地，使用對包含該符號的層次存儲器定義的代表值，在所述最上位存儲器中復原該符號的條目的步驟。