[發(fā)明專利]基于散列的串匹配方法及其選擇模式串子窗口的方法

無效

• 申請(qǐng)?zhí)枺?/td>: 201110162453.0
• 申請(qǐng)日: 2011-06-16
• 公開（公告）號(hào): CN102243656A
• 公開（公告）日: 2011-11-16
• 發(fā)明（設(shè)計(jì)）人: 邵妍;劉燕兵;王勇;劉慶云;郭莉;譚建龍;陳訓(xùn)遜;汪立東
• 申請(qǐng)（專利權(quán)）人: 中國科學(xué)院計(jì)算技術(shù)研究所;國家計(jì)算機(jī)網(wǎng)絡(luò)與信息安全管理中心
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 北京泛華偉業(yè)知識(shí)產(chǎn)權(quán)代理有限公司 11280
• 代理人: 王勇

1.一種用于基于散列的串匹配中的選擇模式串子窗口的方法，所述方法包括：

步驟1)求得模式串集合中最短模式串長(zhǎng)度m；

步驟2)對(duì)于模式串集合中的每個(gè)模式串，計(jì)算其所有長(zhǎng)度為m的子串的散列值，組成散列值集合；

步驟3)確定所述模式串集合與所述散列值集合中的元素的一一對(duì)應(yīng)關(guān)系，所述對(duì)應(yīng)關(guān)系應(yīng)滿足模式串所對(duì)應(yīng)的散列值是根據(jù)該模式串的一個(gè)長(zhǎng)度為m的子串計(jì)算出散列值，同時(shí)將這個(gè)子串設(shè)置為該模式串的子窗口。

2.根據(jù)權(quán)利要求1所述的選擇模式串子窗口的方法，所述步驟3)包括以下步驟：

統(tǒng)計(jì)各模式串長(zhǎng)度為m的子串的散列值的出現(xiàn)次數(shù)；

對(duì)于每個(gè)模式串，選擇出現(xiàn)次數(shù)最少的其子串的散列值與該模式串相對(duì)應(yīng)并將該子串設(shè)置為該模式串的子窗口。

3.根據(jù)權(quán)利要求1所述的選擇模式串子窗口的方法，所述步驟3)包括以下步驟：

用數(shù)組Count[h_i]來記錄模式串集合中各模式串長(zhǎng)度為m的子串的散列值h_i的出現(xiàn)次數(shù)；

對(duì)于每個(gè)模式串，逐個(gè)掃描其長(zhǎng)度為m的子串p_i，子串p_i的散列值表示為h_i，選取Count[h_i]最小的子串p_i來作為該模式串的子窗口。

4.根據(jù)權(quán)利要求1所述的選擇模式串子窗口的方法，所述步驟3)中采用最大流法來確定所述模式串集合與所述散列值集合中的元素的一一對(duì)應(yīng)關(guān)系。

5.根據(jù)權(quán)利要求1所述的選擇模式串子窗口的方法，所述步驟3)中采用匈牙利法來確定所述模式串集合與所述散列值集合中的元素的一一對(duì)應(yīng)關(guān)系。

6.一種基于散列的串匹配方法，所述方法包括以下步驟：

步驟1)求得模式串集合中最短模式串長(zhǎng)度m；

步驟2)對(duì)于模式串集合中的每個(gè)模式串，計(jì)算其所有長(zhǎng)度為m的子串的散列值，組成散列值集合；

步驟3)確定所述模式串集合與所述散列值集合中的元素的一一對(duì)應(yīng)關(guān)系，所述對(duì)應(yīng)關(guān)系應(yīng)滿足模式串所對(duì)應(yīng)的散列值是根據(jù)該模式串的一個(gè)長(zhǎng)度為m的子串計(jì)算出散列值，同時(shí)將這個(gè)子串設(shè)置為該模式串的子窗口；

步驟4)對(duì)模式串集合中每個(gè)模式串，截取該模式串的子窗口來計(jì)算該模式串的散列值，并建立散列表。

7.根據(jù)權(quán)利要求6所述的串匹配方法，所述步驟3)包括以下步驟：

統(tǒng)計(jì)各模式串長(zhǎng)度為m的子串的散列值的出現(xiàn)次數(shù)；

對(duì)于每個(gè)模式串，選擇出現(xiàn)次數(shù)最少的其子串的散列值與該模式串相對(duì)應(yīng)并將該子串設(shè)置為該模式串的子窗口。

8.根據(jù)權(quán)利要求6所述的串匹配方法，所述步驟3)包括以下步驟：

用數(shù)組Count[h_i]來記錄模式串集合中各模式串長(zhǎng)度為m的子串的散列值h_i的出現(xiàn)次數(shù)；

對(duì)于每個(gè)模式串，逐個(gè)掃描其長(zhǎng)度為m的子串p_i，子串p_i的散列值表示為h_i，選取Count[h_i]最小的子串p_i來作為該模式串的子窗口。

9.根據(jù)權(quán)利要求6所述的串匹配方法，所述步驟3)中采用最大流法來確定所述模式串集合與所述散列值集合中的元素的一一對(duì)應(yīng)關(guān)系。

10.根據(jù)權(quán)利要求6所述的串匹配方法，所述步驟3)中采用匈牙利法來確定所述模式串集合與所述散列值集合中的元素的一一對(duì)應(yīng)關(guān)系。