[發(fā)明專利]哈希編碼方法和裝置

有效

• 申請?zhí)枺?/td>: 201410364922.0
• 申請日: 2014-07-29
• 公開（公告）號: CN105320685B
• 公開（公告）日: 2019-03-19
• 發(fā)明（設計）人: 劉汝杰;劉曦
• 申請（專利權）人: 富士通株式會社
• 主分類號: G06F16/22
• 分類號: G06F16/22
• 代理公司: 北京三友知識產權代理有限公司 11127
• 代理人: 樊一槿

本發(fā)明實施例提供一種哈希編碼方法和裝置，其中，所述方法包括：首先利用多個投影對數據投影得到多維數據投影值，然后在每維數據下通過k?means聚類得到k個聚類中心，假定兩兩相鄰聚類中心存在一個閾值，根據熵最大化原則求得(k?1)個閾值并利用這些閾值及預設的編碼方案對每維數據進行編碼，最后拼合所有投影下的編碼得到最終的二值編碼。通過在每個投影方向下使用多個閾值，克服了單閾值量化中無法有效對數據劃分問題且可以選擇使用任意多個閾值；通過使用多個自適應學習的閾值來對每維數據進行量化，有效地保持了近鄰結構，從而為大規(guī)模數據索引及近鄰查詢提供良好基礎。

技術領域

本發(fā)明涉及數據檢索領域，尤其涉及一種哈希編碼方法和裝置。

背景技術

隨著互聯網上的數據如文本、圖像及視頻等呈爆炸式增長，對大規(guī)模數據的索引和近鄰查詢已經越來越引起人們的關注。

哈希編碼是一種常用的將任意實值多維數據轉換成0-1二值串的技術。它具有低存儲及高速查詢的優(yōu)點，因此非常適于大規(guī)模數據索引及查找。

傳統的哈希編碼技術首先生成若干投影，然后對每個投影方向下的投影數據進行單閾值量化，從而得到0-1二值編碼串。單閾值量化方法往往無法很好地分辨數據，這使得相鄰的數據可能具有不同編碼，進而影響基于哈希編碼的大規(guī)模數據索引和近鄰查詢效果。雙閾值哈希方法是最近提出的一種多閾值哈希編碼方法，它先利用多個投影對數據投影得到多維數據投影值，然后在每維數據中使用自適應學習的雙閾值對數據進行量化和編碼，最后拼合所有投影下的編碼生成最終的二值編碼。

應該注意，上面對技術背景的介紹只是為了方便對本發(fā)明的技術方案進行清楚、完整的說明，并方便本領域技術人員的理解而闡述的。不能僅僅因為這些方案在本發(fā)明的背景技術部分進行了闡述而認為上述技術方案為本領域技術人員所公知。

發(fā)明內容

上述方法在每個投影下只使用兩個閾值量化且其中的閾值學習算法只針對兩個閾值，因此無法擴展到多個閾值量化。

本發(fā)明實施例提供一種哈希編碼方法和裝置，以解決背景技術指出的問題。

根據本發(fā)明實施例的一個方面，提供一種哈希編碼裝置，其中，所述裝置包括：

投影單元，其基于給定的訓練數據集生成多個投影方向；

聚類單元，其將所述訓練數據集中的所有訓練數據在每一個所述投影方向上進行投影，得到對應每一個投影方向的一組投影值，利用預先設定的聚類算法對每一個投影方向對應的投影值進行聚類，得到對應每一個投影方向的預定數量的聚類中心；

閾值確定單元，其根據每一個投影方向對應的預定數量的聚類中心，根據熵最大化原則確定對應每一個投影方向的多個閾值，包括：對于每一個投影方向，根據所述投影方向對應的聚類中心的個數確定所述閾值的個數，其中，所述閾值的個數為所述聚類中心的個數減1；對每個閾值賦予候選值；迭代所有閾值的所有候選值，分別計算出相應的熵值；將熵值最大所對應的一組閾值的候選值作為所述多個閾值；

編碼單元，其利用對應每一個投影方向的多個閾值，對輸入數據在所述每一個投影方向的投影值進行編碼，得到所述輸入數據的編碼。

根據本發(fā)明實施例的第二方面，提供一種哈希編碼裝置，其中，所述裝置包括：

投影單元，其基于給定的訓練數據集生成多個投影方向；

聚類單元，其將所述訓練數據集中的所有訓練數據在每一個所述投影方向上進行投影，得到對應每一個投影方向的一組投影值，利用預先設定的聚類算法對每一個投影方向對應的投影值進行聚類，得到對應每一個投影方向的預定數量的聚類中心；