[發明專利]數據處理裝置和為值串形式索引值建立索引的方法

有效

• 申請號: 201010124847.2
• 申請日: 2010-03-12
• 公開（公告）號: CN102193941A
• 公開（公告）日: 2011-09-21
• 發明（設計）人: 王主龍;葛付江;于浩;賈文杰;何楠;王新文;賈曉建
• 申請（專利權）人: 富士通株式會社
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 杜誠;陳煒

技術領域

本發明涉及信息、數據處理領域，尤其涉及一種數據處理裝置和為值串形式索引值建立索引的方法。

背景技術

隨著網絡技術的發展，數據信息量呈指數增長。如何快速對數據信息進行有效的檢索和查詢成為關注焦點。在這樣的背景下，建立便于查詢的高效索引是解決該問題的有效途徑。在各種數據類型中，對于特定應用，需要對某一范圍內的值串形式的數據進行檢索。值串形式的數據例如：數字串、時間數據以及字符串等。

作為值串形式的數據索引，以日期時間索引為例。在現有技術中，信息檢索系統中對于日期、時間等類型數據的索引通常以最小時間粒度為單位作為索引值選擇的依據。因此，檢索系統在對日期數據進行索引之前，需要在年、月、日、時、分的單位內建立該范圍的秒級索引項，以便檢索查詢。然而這會導致大量索引項，通常會使得檢索系統需要遍歷的索引項數過多，從而降低系統的效率。

對數字串或字符串的范圍檢索同樣存在這樣的問題。例如，對abc、abb...abx范圍內的字符串進行檢索，同樣存在磁盤訪問次數過多，系統檢索效率低的問題。

發明內容

本發明的一個目的是提供一種數據處理裝置，其能夠減少范圍檢索中的磁盤訪問次數，從而提高值串形式數據的檢索效率。

本發明的另一個目的是提供一種在數據處理裝置中用于為值串形式的索引值建立前綴樹索引的方法，其能夠減少范圍檢索中的磁盤訪問次數，從而提高值串形式數據的檢索效率。

本發明的一個實施例是一種數據處理裝置，包括為值串形式的索引值建立前綴樹索引的索引部分，索引部分包括：中間索引值獲取單元，用于將索引值補位到預定長度，并基于補位后的各索引值的相應位以及相應位的組合來獲取中間索引值；中間索引項產生單元，用于產生針對中間索引值的索引數據作為中間索引數據，并建立中間索引值與中間索引數據之間的對應關系，中間索引數據是中間索引值覆蓋的各索引值的索引數據或這些索引數據的變形的集合；其中，在該集合中，索引數據或這些索引數據的變形按照與索引值的各位相關的預定順序排列，并且，每一個索引值的索引數據或索引數據的變形各自包含表示本身在何處結束的結束標志。

在本發明的一個實施例中，在每一個文檔具有一個索引值的應用中，中間索引數據是中間索引值覆蓋的各索引值的相應索引數據的集合。

在本發明的一個實施例中，在文檔的至少之一具有多于一個索引值的應用中，中間索引數據是中間索引值覆蓋的各索引值的相應索引數據的變形的集合。

在本發明的一個實施例中，中間索引項產生單元還包括：前向索引產生單元，用于產生中間索引值的前向索引數據，并建立中間索引值與其前向索引數據之間的對應關系；后向索引產生單元，用于產生中間索引值的后向索引數據，并建立中間索引值與其后向索引數據之間的對應關系。

在本發明的一個實施例中，在前向索引產生單元中，對于每一個中間索引值，將該中間索引值覆蓋的索引值按照與索引值的各位相關的預定順序排列，并從前向后遍歷這些索引值，利用等式(1)來獲得中間索引值的前向索引數據：

Fn=Cn-Cn∩(∪i=1n-1Ci)---(1)]]>

其中，F_n是中間索引值的前向索引數據中與按所述順序排列的第n個索引值相對應的項，C_i是第i個索引值的索引數據，i和n為正整數，i≤n，且n≤每個中間索引值所覆蓋的索引值的項數。