[發明專利]一種挖掘最大重復序列的方法及裝置

有效

• 申請號: 201410200896.8
• 申請日: 2014-05-13
• 公開（公告）號: CN105095276B
• 公開（公告）日: 2020-04-21
• 發明（設計）人: 梁辰;范偉
• 申請（專利權）人: 華為技術有限公司
• 主分類號: G06F16/2458
• 分類號: G06F16/2458
• 代理公司: 北京中博世達專利商標代理有限公司 11274
• 代理人: 張娜

1.一種挖掘最大重復序列的方法，其特征在于，包括：

獲取字符；

將所述字符追加到流水線集合中的每個流水線中，分別判斷追加所述字符后的每個流水線中的序列與后綴樹上對應的序列是否相同，其中，所述流水線集合包含至少一個流水線，所述流水線包含序列以及位置指針，所述序列包含與所述字符所在的字符串中所述字符之前的字符相同的字符，所述位置指針指向所述流水線包含的序列的尾字符在所述后綴樹上的位置；

在所述流水線集合中，若存在第一流水線，在追加所述字符后的序列與后綴樹上對應的序列不同，則根據第一預設策略以及所述第一流水線中的序列確定最大重復序列；

其中，所述根據第一預設策略以及所述第一流水線中的序列確定最大重復序列，包括：在所述字符串中，檢測與所述第一流水線中的序列相同的序列相鄰的左邊字符是否為同一種字符，以及，檢測與所述第一流水線中的序列相同的序列相鄰的右邊字符是否為同一種字符；若與所述第一流水線中的序列相同的序列相鄰的左邊字符不為同一種字符，且與所述第一流水線中的序列相同的序列相鄰的右邊字符不為同一種字符，則確定所述第一流水線中的序列為最大重復子序列；若與所述第一流水線中的序列相同的序列相鄰的左邊字符為同一種字符，或者，與所述第一流水線中的序列相同的序列相鄰的右邊字符為同一種字符，或者，與所述第一流水線中的序列相同的序列相鄰的左邊字符為同一種字符以及與所述第一流水線中的序列相同的序列相鄰的右邊字符為同一種字符，則確定所述第一流水線中的序列不是最大重復序列，并銷毀所述第一流水線；同時，在所述流水線集合中，若存在第二流水線，根據所述第二流水線的位置指針以及第二預設策略確定最大非串聯重復序列；以使得所挖掘的最大重復序列為非串聯重復序列；

確定所述第二流水線的參考流水線中的序列為由所述第二流水線中的序列組成的串聯序列，銷毀第二流水線以及第二流水線的參考流水線。

2.根據權利要求1所述的方法，其特征在于，所述在所述字符串中，檢測與所述第一流水線中的序列相同的序列相鄰的左邊字符是否為同一種字符，以及，檢測與所述第一流水線中的序列相同的序列相鄰的右邊字符是否為同一種字符，包括：

在所述字符串中，獲取與所述第一流水線中的序列相同的序列相鄰的左邊字符集；若所述字符集包含同一種字符，則確定與所述第一流水線中的序列相同的序列相鄰的左邊字符為同一種字符；若所述字符集包含至少兩種字符，則確定與所述第一流水線中的序列相同的序列相鄰的左邊字符不為同一種字符；

在所述后綴樹上，判斷所述第一流水線的位置指針所指字符與所述字符是否相同，若相同，則確定與所述第一流水線中的序列相同的序列相鄰的右邊字符為同一種字符，若不同，則確定與所述第一流水線中的序列相同的序列相鄰的右邊字符不為同一種字符。

3.根據權利要求1-2任一項所述的方法，其特征在于，所述分別判斷追加所述字符后的每個流水線中的序列與后綴樹上對應的序列是否相同，包括：

在所述后綴樹上，分別移動每個流水線中的位置指針，使所述位置指針指向與所述流水線包含的序列的尾字符相鄰的下一個字符的位置；

判斷移動后的所述位置指針指向的字符與所述字符是否相同；若不同，則確定追加所述字符后的流水線中的序列與后綴樹上對應的序列不同；若相同，則確定追加所述字符后的流水線中的序列與后綴樹上對應的序列相同。

4.根據權利要求1所述的方法，其特征在于，所述方法還包括：

在所述流水線集合中，若存在第二流水線，在追加所述字符后的序列與后綴樹上對應的序列相同，則將所述字符追加到所述第二流水線中，并將所述第二流水線的位置指針指向追加所述字符后的所述第二流水線包含的序列的尾字符在所述后綴樹上的位置；

根據所述第二流水線的位置指針以及第二預設策略確定最大非串聯重復序列。