[發明專利]支持集束搜索的運算裝置和方法

有效

• 申請號: 201710279655.0
• 申請日: 2017-04-25
• 公開（公告）號: CN108733739B
• 公開（公告）日: 2021-09-07
• 發明（設計）人: 不公告發明人
• 申請（專利權）人: 上海寒武紀信息科技有限公司
• 主分類號: G06F8/30
• 分類號: G06F8/30;G06F16/903
• 代理公司: 中科專利商標代理有限責任公司 11021
• 代理人: 任巖

1.一種支持集束搜索的裝置，應用于人工智能領域中的機器翻譯系統或語音識別系統，包括數據轉換模塊、數據運算模塊和整合結果模塊，其中

數據轉換模塊，用于從裝置外獲取指令，以及獲取圖形結構中的部分節點并進行格式轉換；

數據運算模塊，獲取尚未被運算的節點數據，計算從源節點到對應節點路徑的總代價值，將總代價值最小的前k個節點選出作為候選節點，k為裝置允許的最大候選節點數，根據總代價值最小的節點判斷是否得到近似最優路徑，如果沒有，則繼續獲取未被運算的節點數據進行計算和判斷，如果有，將總代價最小節點和其前驅節點寫入到整合結果模塊中；

整合結果模塊，根據從數據運算模塊得到的近似最優路徑的尾節點不斷尋找前驅節點，直至回溯至源節點，獲得最優路徑；

其中，所述數據運算模塊包括：多個代價計算子模塊，用于計算從源節點到對應路徑的代價值，得到節點號-路徑代價值對；所述源節點到對應節點路徑的總代價值為多個代價計算子模塊中的對應節點的路徑代價值與該對應節點的前驅節點的路徑代價值的總和。

2.根據權利要求1所述的裝置，其特征在于，還包括：

存儲模塊，用于從數據轉換模塊中獲取指令和格式轉換后的節點數據，存儲整合結果模塊獲得的最優路徑。

3.根據權利要求1所述的裝置，其特征在于，還包括：

控制器，用于執行指令，分別對數據轉換模塊、數據運算模塊和整合結果模塊進行控制。

4.根據權利要求1所述的裝置，其特征在于，所述格式轉換具體包括：

將從裝置外獲取的圖的節點n轉化為如下的格式：

(Addr(before(n))，F(n)，n，vis)

其中，before(n)表示節點n的前驅節點，Addr(before(n))表示節點n的前驅節點在存儲模塊中的地址，F(n)表示從源節點s到節點n的路徑上產生的總代價，vis表示此節點是否被訪問過，是為1，否則為0。

5.根據權利要求3所述的裝置，其特征在于，所述數據運算模塊包括：節點分發子模塊、排序子模塊和終止判斷子模塊，其中

節點分發子模塊，用于將數據運算模塊獲取的節點數據分配給代價計算子模塊；

排序子模塊，用于接收所述節點號-路徑代價值對，并根據路徑代價值從小到大排序，并傳送到終止判斷模塊；

終止判斷子模塊，用于從排序子模塊中獲取排序后的節點號-路徑代價值對，判斷是否已經取得近似最優路徑，如果已經取得近似最優路徑，則終止判斷子模塊對控制器發送運算終止指令，并將最小代價值對應的節點數據傳送到整合結果模塊；否則，若排序的節點數m≤k，則將對應的m個節點數據都作為候選節點寫回到存儲模塊，若m＞k，將排序后的從小到大k個節點數據寫回到存儲模塊。

6.根據權利要求1所述的裝置，其特征在于，所述圖形結構為鄰接表、鄰接矩陣或頂點對形式。

7.根據權利要求2所述的裝置，其特征在于，所述存儲模塊還用于將所述最優路徑輸入裝置外部。

8.一種支持集束搜索的方法，應用于如權利要求1所述的支持集束搜索的裝置，包括步驟：

獲取指令，經由一數據轉換模塊存儲到一存儲模塊中；

將原始圖形結構中部分節點傳送到數據轉換模塊中，數據轉換模塊將傳入的節點進行格式轉換后，然后送至存儲模塊中；

數據運算模塊從存儲模塊獲取尚未被運算的節點數據，計算從源節點到對應節點路徑的總代價值，將總代價值最小的前k個節點選出作為候選節點，k為裝置允許的最大候選節點數，根據總代價值最小的節點判斷是否得到近似最優路徑，如果沒有，則繼續從存儲模塊獲取未被運算的節點數據進行計算和判斷；如果有，將總代價最小節點和其前驅節點寫入到一整合結果模塊中；

根據從數據運算模塊得到的近似最優路徑的尾節點從存儲模塊中不斷尋找前驅節點，直至回溯至源節點，獲得最優路徑存入存儲模塊；

存儲模塊獲得最優路徑存入，并將其傳輸到裝置外部。