[發(fā)明專利]一種基于分區(qū)雙數(shù)組Trie的字符串檢索方法及裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 201810179880.1
• 申請(qǐng)日: 2018-03-05
• 公開(kāi)（公告）號(hào): CN108509505B
• 公開(kāi)（公告）日: 2022-04-12
• 發(fā)明（設(shè)計(jì)）人: 陳文焰;賈連印;丁家滿;李孟娟;游進(jìn)國(guó);章露露;呂曉偉
• 申請(qǐng)（專利權(quán)）人: 昆明理工大學(xué)
• 主分類號(hào): G06F16/9032
• 分類號(hào): G06F16/9032;G06F16/901
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

1.一種基于分區(qū)雙數(shù)組Trie的字符串檢索方法，其特征在于包括以下步驟：

數(shù)據(jù)預(yù)處理步驟：對(duì)字符串?dāng)?shù)據(jù)集進(jìn)行排序并統(tǒng)計(jì)不同首字符的字符串?dāng)?shù)量；

索引創(chuàng)建步驟：根據(jù)輸入的分區(qū)數(shù)量N，進(jìn)行分區(qū)的劃分，再生成分區(qū)映射表，簡(jiǎn)稱PMT，并為每個(gè)分區(qū)創(chuàng)建獨(dú)立的雙數(shù)組Trie索引結(jié)構(gòu)，簡(jiǎn)稱DAT索引結(jié)構(gòu)；

其索引創(chuàng)建步驟按如下步驟執(zhí)行：

步驟210：分區(qū)的劃分；

步驟220：生成PMT；

步驟230：分區(qū)DAT索引結(jié)構(gòu)的創(chuàng)建；

所述步驟230，按如下步驟執(zhí)行：

步驟231：對(duì)要插入分區(qū)DAT中的一個(gè)字符串，根據(jù)其首字符在PMT中進(jìn)行映射，獲取其要插入的分區(qū)；

步驟232：根據(jù)創(chuàng)建DAT索引的公式將字符串插入到相應(yīng)的分區(qū)中，對(duì)于插入字符“c”，從狀態(tài)s轉(zhuǎn)換到狀態(tài)t，其公式為：

BASE[s]+CODE[c]＝t (1)

CHECK[t]＝s (2)

其中CODE[c]表示字符c的數(shù)值編碼，對(duì)英文字符而言，字符“#”，“a”，“b”，“c”···“z”的編碼值分別對(duì)應(yīng)1，2，3，4···27；

分區(qū)DAT索引結(jié)構(gòu)的創(chuàng)建，取待插入的字符串與PMT進(jìn)行映射，以其中一個(gè)集合K1＝{“baby#”，“bachelor#”，“badge#”}插入到1號(hào)分區(qū)，即其雙數(shù)組Trie的創(chuàng)建過(guò)程為例：

雙數(shù)組Trie初始化，其中POS的值表明當(dāng)前向TAIL數(shù)組插入字符的位置，

插入字符串“baby#”到1號(hào)分區(qū)，分為以下幾個(gè)步驟：

步驟A1：從雙數(shù)組BASE數(shù)組位置1處開(kāi)始進(jìn)行索引的創(chuàng)建，“b”的編碼值為3，那么就有：

BASE[1]+“b”＝BASE[1]+3＝1+3＝4，并且CHECK[4]＝0≠1

步驟A2：CHECK值為0表明應(yīng)要插入剩余的字符串到TAIL數(shù)組當(dāng)中，此時(shí)插入“b”可唯一識(shí)別“baby#”，則將剩余的部分“aby#”從POS＝1處依次插入到TAIL數(shù)組中；

步驟A3：設(shè)置

BASE[4]←-POS＝-1

表明剩下的字符串在TAIL數(shù)組開(kāi)始讀取的位置即BASE[4]的絕對(duì)值；

更新

POS＝1+length(“aby#”)＝1+4＝5

再更新

CHECK[4]＝1

表明結(jié)點(diǎn)4是從結(jié)點(diǎn)1跳轉(zhuǎn)過(guò)來(lái)的即結(jié)點(diǎn)4是結(jié)點(diǎn)1的孩子結(jié)點(diǎn)；

插入字符串“bachelor#”到1號(hào)分區(qū)：

步驟B1：從雙數(shù)組BASE數(shù)組位置1處開(kāi)始進(jìn)行索引的創(chuàng)建，“b”的編碼值為3，則有：

BASE[1]+“b”＝BASE[1]+3＝1+3＝4，并且CHECK[4]＝1

非0的CHECK值表明已經(jīng)存在從結(jié)點(diǎn)1到結(jié)點(diǎn)4的邊；

步驟B2：需要索引更多的字符到雙數(shù)組中以區(qū)分這兩個(gè)字符串，那么結(jié)點(diǎn)4就要作為狀態(tài)轉(zhuǎn)移的基值，而此時(shí)BASE[4]＝-1，表明查詢已經(jīng)結(jié)束，將當(dāng)前BASE[4]的值存在一個(gè)臨時(shí)變量TEMP中，訪問(wèn)X_CHECK(LIST)函數(shù)并為BASE[4]尋找一個(gè)新的基值，X_CHECK(LIST)函數(shù)是返回最小的整數(shù)q，q滿足q0并且CHECK[q+c]＝0即找到一個(gè)空位置，c是LIST里的字符，q的值總是從1開(kāi)始遞增；

TEMP←BASE[4]＝-1

步驟B3：為BASE[4]尋找一個(gè)新的基值，新的基值要滿足將字符“a”插入到一個(gè)空的位置，“a”的編碼值為2，所以訪問(wèn)X_CHECK(LIST)函數(shù)并為BASE[4]尋找一個(gè)新的基值，X_CHECK(LIST)函數(shù)是返回最小的整數(shù)q，q滿足q0并且CHECK[q+c]＝0即找到一個(gè)空位置，c是LIST里的字符即需要索引到雙數(shù)組中的字符，q的值總是從1開(kāi)始遞增；

CHECK[q+“a”]＝CHECK[1+2]＝CHECK[3]＝BASE[3]＝0

找到一個(gè)空的位置，返回的q值為1即

BASE[4]＝1

步驟B4：將字符“b”，“c”索引到雙數(shù)組中以區(qū)分“baby#”，“bachelor#”，訪問(wèn)X_CHECK(LIST)函數(shù)找到合適的空位置插入字符“b”，“c”，即為BASE[3]尋找一個(gè)合適的基值進(jìn)行狀態(tài)的轉(zhuǎn)移：

CHECK[q+“b”]＝CHECK[1+3]＝CHECK[4]≠0，q＝1不可用

CHECK[q+“b”]＝CHECK[2+3]＝CHECK[5]＝0，q＝2可用

CHECK[2+“c”]＝CHECK[2+4]＝CHECK[6]＝0，q＝2可用，則

BASE[3]＝2；

步驟B5：索引“b”到雙數(shù)組中：

BASE[3]+“b”＝2+3＝5

令

CHECK[5]＝3

BASE[5]←TEMP＝-1

索引“c”到雙數(shù)組中：

BASE[3]+“c”＝2+4＝6

令

BASE[6]←-POS＝-5

CHECK[6]＝3

步驟B6：再更新

POS＝5+length(“helor#”)＝5+6＝11；

插入字符串“badge#”到1號(hào)分區(qū)中：

步驟C1：從雙數(shù)組BASE數(shù)組位置1處開(kāi)始進(jìn)行索引的創(chuàng)建，“b”的編碼值為3，則有：

BASE[1]+“b”＝1+3＝4且CHECK[4]＝1

BASE[4]+“a”＝1+2＝3且CHECK[3]＝4

BASE[3]+“d”＝2+5＝7且CHECK[7]＝0≠3

步驟C2：CHECK值為0表明應(yīng)要插入剩余的字符串到TAIL數(shù)組當(dāng)中，從POS＝11處依次插入“ge#”到TAIL數(shù)組中；

步驟C3：令

BASE[7]←-POS＝-11

CHECK[7]＝3

步驟C4：再更新

POS＝11+length(“ge#”)＝11+3＝14；

檢索步驟：輸入檢索的字符串，在分區(qū)DAT索引結(jié)構(gòu)上進(jìn)行檢索。