[發(fā)明專(zhuān)利]在正則表達(dá)式代碼上使用最長(zhǎng)通用子序列算法的正則表達(dá)式生成

在審

• 申請(qǐng)?zhí)枺?/td>: 201980037104.0
• 申請(qǐng)日: 2019-06-12
• 公開(kāi)（公告）號(hào): CN112236747A
• 公開(kāi)（公告）日: 2021-01-15
• 發(fā)明（設(shè)計(jì)）人: M·馬拉克;L·E·李瓦斯;M·L·克萊德?tīng)?/a>
• 申請(qǐng)（專(zhuān)利權(quán)）人: 甲骨文國(guó)際公司
• 主分類(lèi)號(hào): G06F8/38
• 分類(lèi)號(hào): G06F8/38;G06F40/194;G06F16/332;G06F3/0482;G06F16/33;G06F40/146;G06F3/14;G06F16/2452;G06F9/451;G06F40/10;G06K9/62;G06F40/177;G06K9/68;G06F1
• 代理公司: 中國(guó)貿(mào)促會(huì)專(zhuān)利商標(biāo)事務(wù)所有限公司 11038
• 代理人: 張?chǎng)?/td>

1.一種使用最長(zhǎng)通用子序列(LCS)算法生成正則表達(dá)式的方法，所述方法包括：

由包括一個(gè)或多個(gè)處理器的正則表達(dá)式生成器接收標(biāo)識(shí)三個(gè)或更多個(gè)字符序列的輸入數(shù)據(jù)；

由所述正則表達(dá)式生成器將所述三個(gè)或更多個(gè)字符序列中的每一個(gè)轉(zhuǎn)換成相應(yīng)的正則表達(dá)式代碼集合，從而產(chǎn)生三個(gè)或更多個(gè)正則表達(dá)式代碼集合；

由所述正則表達(dá)式生成器多次執(zhí)行最長(zhǎng)通用子序列(LCS)算法，并捕獲所述LCS算法的多個(gè)輸出，其中，對(duì)所述三個(gè)或更多個(gè)正則表達(dá)式代碼集合的每一個(gè)唯一兩集合組合執(zhí)行所述LCS算法；

由所述正則表達(dá)式生成器存儲(chǔ)定義全連接圖的數(shù)據(jù)，所述數(shù)據(jù)包括：

多個(gè)節(jié)點(diǎn)，其中所述全連接圖的每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)于所述三個(gè)或更多個(gè)正則表達(dá)式代碼集合中的一個(gè)；以及

多條邊，連接所述多個(gè)節(jié)點(diǎn)中的每一個(gè)唯一節(jié)點(diǎn)對(duì)，其中每一個(gè)唯一節(jié)點(diǎn)對(duì)之間的邊長(zhǎng)由對(duì)與所述唯一節(jié)點(diǎn)對(duì)相對(duì)應(yīng)的正則表達(dá)式代碼執(zhí)行的所述LCS算法的輸出定義；

由所述正則表達(dá)式生成器確定所述全連接圖的最小生成樹(shù)；

由所述正則表達(dá)式生成器遍歷所述全連接圖的最小生成樹(shù)，以確定用于標(biāo)識(shí)所述三個(gè)或更多個(gè)字符序列中的第一最長(zhǎng)通用子序列的順序。

2.如權(quán)利要求1所述的方法，還包括通過(guò)以下方式標(biāo)識(shí)所述三個(gè)或更多個(gè)字符序列中的第一最長(zhǎng)通用子序列：

使用所述LCS算法標(biāo)識(shí)與所述輸入數(shù)據(jù)內(nèi)的第一和第二字符序列相對(duì)應(yīng)的第一和第二正則表達(dá)式代碼集合之間的所述第一最長(zhǎng)通用子序列；

使用所述LCS算法標(biāo)識(shí)與所述輸入數(shù)據(jù)內(nèi)的第一和第三字符序列相對(duì)應(yīng)的第一和第三正則表達(dá)式代碼集合之間的第二最長(zhǎng)通用子序列；

使用所述LCS算法標(biāo)識(shí)與所述輸入數(shù)據(jù)內(nèi)的第二和第三字符序列相對(duì)應(yīng)的第二和第三正則表達(dá)式代碼集合之間的第三最長(zhǎng)通用子序列；

基于通過(guò)遍歷所述全連接圖的最小生成樹(shù)所確定的順序，選擇所述第一最長(zhǎng)通用子序列。

3.如權(quán)利要求1所述的方法，其中遍歷所述全連接圖的最小生成樹(shù)包括在所述最小生成樹(shù)上執(zhí)行深度優(yōu)先遍歷。

4.如權(quán)利要求1所述的方法，還包括：

由所述正則表達(dá)式生成器將作為所述LCS算法的輸入提供的多個(gè)正則表達(dá)式代碼對(duì)以及所述LCS算法的相應(yīng)輸出存儲(chǔ)在存儲(chǔ)器中；

由所述正則表達(dá)式生成器基于所述LCS算法的所述多次執(zhí)行的輸出生成一個(gè)或多個(gè)正則表達(dá)式，

其中，在生成所述一個(gè)或多個(gè)正則表達(dá)式之后，作為所述LCS算法的輸入提供的所述多個(gè)正則表達(dá)式代碼對(duì)和所述LCS算法的相應(yīng)輸出被保留在所述存儲(chǔ)器中。

5.如權(quán)利要求4所述的方法，還包括：

由所述正則表達(dá)式生成器接收標(biāo)識(shí)多個(gè)附加字符序列的輸入數(shù)據(jù)；

由所述正則表達(dá)式生成器將所述多個(gè)附加字符序列中的每一個(gè)轉(zhuǎn)換成相應(yīng)的正則表達(dá)式代碼集合，從而產(chǎn)生多個(gè)附加正則表達(dá)式代碼；

標(biāo)識(shí)所述多個(gè)附加正則表達(dá)式代碼中與被存儲(chǔ)和保留在所述存儲(chǔ)器中的正則表達(dá)式代碼對(duì)相匹配的正則表達(dá)式代碼對(duì)；

響應(yīng)于標(biāo)識(shí)作為所述LCS算法的輸入提供的匹配的正則表達(dá)式代碼對(duì)，從所述存儲(chǔ)器檢索所述LCS算法的相應(yīng)輸出。

6.如權(quán)利要求1所述的方法，還包括基于所述LCS算法的所述多次執(zhí)行來(lái)生成正則表達(dá)式，其中生成所述正則表達(dá)式包括：

基于通過(guò)遍歷最小生成樹(shù)所確定的順序來(lái)確定所述三個(gè)或更多個(gè)正則表達(dá)式代碼集合中的前兩個(gè)正則表達(dá)式代碼集合；

第一次附加執(zhí)行所述LCS算法，其中所述第一次附加執(zhí)行包括提供所述前兩個(gè)正則表達(dá)式代碼集合作為所述LCS算法的執(zhí)行的輸入，以及捕獲所述LCS算法的第一輸出；

基于通過(guò)遍歷最小生成樹(shù)所確定的順序來(lái)確定所述三個(gè)或更多個(gè)正則表達(dá)式代碼集合中的第三正則表達(dá)式代碼集合；以及

第二次附加執(zhí)行所述LCS算法，其中所述第二次附加執(zhí)行包括提供所述LCS算法的第一輸出和第三正則表達(dá)式代碼集合作為所述LCS算法的第二次附加執(zhí)行的輸入，以及捕獲所述LCS算法的第二輸出。