[發(fā)明專利]一種廣義后綴樹(shù)快速遍歷的方法及系統(tǒng)

在審

• 申請(qǐng)?zhí)枺?/td>: 201310674975.8
• 申請(qǐng)日: 2013-12-11
• 公開(kāi)（公告）號(hào): CN103699593A
• 公開(kāi)（公告）日: 2014-04-02
• 發(fā)明（設(shè)計(jì)）人: 黃鑫;羅軍
• 申請(qǐng)（專利權(quán)）人: 中國(guó)科學(xué)院深圳先進(jìn)技術(shù)研究院
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 深圳中一專利商標(biāo)事務(wù)所 44237
• 代理人: 張全文

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算機(jī)科學(xué)領(lǐng)域，尤其涉及一種廣義后綴樹(shù)快速遍歷的方法及系統(tǒng)。

背景技術(shù)

后綴樹(shù)是一種廣泛使用的數(shù)據(jù)結(jié)構(gòu)，通常用于字符串的處理，能快速解決很多關(guān)于字符串的問(wèn)題。當(dāng)同時(shí)用于多個(gè)字符串，即是說(shuō)把給定的N個(gè)源字符串的所有的后綴建成一顆樹(shù)，這種數(shù)據(jù)結(jié)構(gòu)叫做廣義后綴樹(shù)。

目前，傳統(tǒng)的廣義后綴樹(shù)遍歷采用廣度優(yōu)先遍歷的方法，不過(guò)當(dāng)需要進(jìn)行信息統(tǒng)計(jì)，比如統(tǒng)計(jì)根節(jié)點(diǎn)（Root）到每個(gè)節(jié)點(diǎn)的路徑所代表的子字符串的時(shí)候，傳統(tǒng)的方法會(huì)通過(guò)遞歸多次重復(fù)遍歷底層節(jié)點(diǎn)，需要在遍歷每個(gè)節(jié)點(diǎn)的時(shí)候遞歸調(diào)用方法來(lái)統(tǒng)計(jì)該節(jié)點(diǎn)子節(jié)點(diǎn)里葉子的個(gè)數(shù)和索引數(shù)，使得時(shí)間復(fù)雜度大大提高，并且遞歸嵌套過(guò)多程序容易發(fā)生堆棧溢出，而且運(yùn)行效率降低很多。

因此，亟需設(shè)計(jì)一種廣義后綴樹(shù)快速遍歷的方法及系統(tǒng)，從而可以實(shí)現(xiàn)能極大降低遍歷統(tǒng)計(jì)過(guò)程的時(shí)間復(fù)雜度，進(jìn)而大大提高了運(yùn)行效率。

發(fā)明內(nèi)容

有鑒于此，本發(fā)明實(shí)施例的目的在于提供一種廣義后綴樹(shù)快速遍歷的方法及系統(tǒng)，旨在解決現(xiàn)有技術(shù)中在采用廣度優(yōu)先遍歷的方法時(shí)調(diào)用遞歸統(tǒng)計(jì)會(huì)造成底層節(jié)點(diǎn)的多次訪問(wèn)和底層堆棧負(fù)擔(dān)的加大，進(jìn)而影響運(yùn)行效率的問(wèn)題。

本發(fā)明實(shí)施例是這樣實(shí)現(xiàn)的，一種廣義后綴樹(shù)快速遍歷的方法，包括：

為廣義后綴樹(shù)的數(shù)據(jù)結(jié)構(gòu)添加第一屬性，以更改所述廣義后綴樹(shù)的數(shù)據(jù)結(jié)構(gòu)；

為廣義后綴樹(shù)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)添加第二屬性，以更改所述廣義后綴樹(shù)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)；

利用更改后的所述廣義后綴樹(shù)的數(shù)據(jù)結(jié)構(gòu)以及更改后的所述廣義后綴樹(shù)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，通過(guò)自下而上的方式對(duì)廣義后綴樹(shù)的節(jié)點(diǎn)信息進(jìn)行遍歷統(tǒng)計(jì)。

優(yōu)選的，所述第一屬性為循環(huán)鏈表，用于表示廣義后綴樹(shù)葉子的信息，其中，更后的所述廣義后綴樹(shù)的數(shù)據(jù)結(jié)構(gòu)的屬性包括類型、內(nèi)容、樹(shù)里節(jié)點(diǎn)、根節(jié)點(diǎn)、所述循環(huán)鏈表以及所有葉子循環(huán)鏈表。

優(yōu)選的，所述循環(huán)鏈表中的每一個(gè)節(jié)點(diǎn)的屬性包括類型、內(nèi)容、循環(huán)鏈表里的節(jié)點(diǎn)、樹(shù)里的一個(gè)葉節(jié)點(diǎn)的引用、指針以及指針指向鏈表里的下一個(gè)節(jié)點(diǎn)。

優(yōu)選的，所述第二屬性包括計(jì)數(shù)器計(jì)數(shù)、判斷區(qū)號(hào)以及索引集合，其中，所述計(jì)數(shù)器計(jì)數(shù)用于計(jì)算對(duì)應(yīng)節(jié)點(diǎn)的子節(jié)點(diǎn)里的索引數(shù)量之和，所述判斷區(qū)號(hào)用于表示對(duì)應(yīng)節(jié)點(diǎn)的子節(jié)點(diǎn)里已經(jīng)完成統(tǒng)計(jì)遍歷的個(gè)數(shù)，所述索引集合用于表示對(duì)應(yīng)節(jié)點(diǎn)的子節(jié)點(diǎn)里的所有葉子的索引的集合。

優(yōu)選的，所述通過(guò)自下而上的方式對(duì)廣義后綴樹(shù)的節(jié)點(diǎn)信息進(jìn)行遍歷統(tǒng)計(jì)的步驟具體包括：

對(duì)于所述所有葉子循環(huán)鏈表，設(shè)LNode代表鏈表里的每一個(gè)節(jié)點(diǎn)，對(duì)于每一個(gè)LNode依次遍歷，遍歷完一個(gè)節(jié)點(diǎn)后調(diào)用next指針遍歷對(duì)應(yīng)的下一個(gè)節(jié)點(diǎn)；

重復(fù)上述第一步里對(duì)每一個(gè)節(jié)點(diǎn)的處理，直到循環(huán)鏈表里只有一個(gè)節(jié)點(diǎn)且其LNode為根節(jié)點(diǎn)。

另一方面，本發(fā)明還提供一種廣義后綴樹(shù)快速遍歷的系統(tǒng)，包括：

第一更改模塊，用于為廣義后綴樹(shù)的數(shù)據(jù)結(jié)構(gòu)添加第一屬性，以更改所述廣義后綴樹(shù)的數(shù)據(jù)結(jié)構(gòu)；

第二更改模塊，用于為廣義后綴樹(shù)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)添加第二屬性，以更改所述廣義后綴樹(shù)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)；

遍歷統(tǒng)計(jì)模塊，用于利用更改后的所述廣義后綴樹(shù)的數(shù)據(jù)結(jié)構(gòu)以及更改后的所述廣義后綴樹(shù)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，通過(guò)自下而上的方式對(duì)廣義后綴樹(shù)的節(jié)點(diǎn)信息進(jìn)行遍歷統(tǒng)計(jì)。

優(yōu)選的，所述第一屬性為循環(huán)鏈表，用于表示廣義后綴樹(shù)葉子的信息，其中，更后的所述廣義后綴樹(shù)的數(shù)據(jù)結(jié)構(gòu)的屬性包括類型、內(nèi)容、樹(shù)里節(jié)點(diǎn)、根節(jié)點(diǎn)、所述循環(huán)鏈表以及所有葉子循環(huán)鏈表。

優(yōu)選的，所述循環(huán)鏈表中的每一個(gè)節(jié)點(diǎn)的屬性包括類型、內(nèi)容、循環(huán)鏈表里的節(jié)點(diǎn)、樹(shù)里的一個(gè)葉節(jié)點(diǎn)的引用、指針以及指針指向鏈表里的下一個(gè)節(jié)點(diǎn)。

優(yōu)選的，所述第二屬性包括計(jì)數(shù)器計(jì)數(shù)、判斷區(qū)號(hào)以及索引集合，其中，所述計(jì)數(shù)器計(jì)數(shù)用于計(jì)算對(duì)應(yīng)節(jié)點(diǎn)的子節(jié)點(diǎn)里的索引數(shù)量之和，所述判斷區(qū)號(hào)用于表示對(duì)應(yīng)節(jié)點(diǎn)的子節(jié)點(diǎn)里已經(jīng)完成統(tǒng)計(jì)遍歷的個(gè)數(shù)，所述索引集合用于表示對(duì)應(yīng)節(jié)點(diǎn)的子節(jié)點(diǎn)里的所有葉子的索引的集合。

優(yōu)選的，所述遍歷統(tǒng)計(jì)模塊包括：

遍歷調(diào)用子模塊，用于對(duì)于所述所有葉子循環(huán)鏈表，設(shè)LNode代表鏈表里的每一個(gè)節(jié)點(diǎn)，對(duì)于每一個(gè)LNode依次遍歷，遍歷完一個(gè)節(jié)點(diǎn)后調(diào)用next指針遍歷對(duì)應(yīng)的下一個(gè)節(jié)點(diǎn)；

循環(huán)處理子模塊，用于重復(fù)上述第一步里對(duì)每一個(gè)節(jié)點(diǎn)的處理，直到循環(huán)鏈表里只有一個(gè)節(jié)點(diǎn)且其LNode為根節(jié)點(diǎn)。