[發明專利]壓縮匹配枚舉

有效

• 申請號: 201180071391.0
• 申請日: 2011-10-09
• 公開（公告）號: CN103582880B
• 公開（公告）日: 2017-05-03
• 發明（設計）人: B.A.米克爾
• 申請（專利權）人: 微軟技術許可有限責任公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F17/00
• 代理公司: 中國專利代理(香港)有限公司72001
• 代理人: 李舒,汪揚

1.一種方法，包括：

生成代表存儲在存儲緩沖器中的數據序列的后綴數組，其中所述后綴數組為存儲緩沖器中的緩沖位置的數組，所述緩沖位置通過在相應緩沖位置處開始數據序列的數據串按字母順序排序；

將所述后綴數組轉換成特里結構，由于所述特里結構在所述后綴數組的原地生成，所以其蓋寫存儲緩沖器中的所述后綴數組；以及

枚舉從所述特里結構確定的數據序列匹配。

2.根據權利要求1所述的方法，其中所述后綴數組通過從所述后綴數組的連續后綴步進地更新所述特里結構而被轉換成所述特里結構。

3.根據權利要求1所述的方法，其中所述特里結構包括節點，所述節點的每一個代表所述后綴數組的一個或多個后綴，并且其中每一連續后綴或者與所述特里結構中的現有節點群聚，或者被添加為所述特里結構的新節點。

4.根據權利要求3所述的方法，其中當所述后綴數組的后綴具有如所述特里結構的現有節點的數據序列的共同匹配長度時，所述后綴被與該現有節點群聚。

5.根據權利要求1所述的方法，其中所述特里結構包括節點，所述節點的每一個包括對父節點的引用、用于后代節點的數據序列的共同匹配長度以及最新近遍歷的后代節點的緩沖位置。

6.根據權利要求5所述的方法，其中所述后代節點包括節點的直接子節點，并且其中所述特里結構的生成是基于：

所述特里結構包括一個或多個非葉節點，所述非葉節點的每一個具有至少兩個直接子節點；

用于所述后代節點的數據序列的共同匹配長度是最大的；以及

在所述特里結構中的節點的總數被最小化。

7.根據權利要求1所述的方法，進一步包括在所述特里結構的生成完成之后，搜索所述特里結構以枚舉數據序列匹配。

8.根據權利要求1所述的方法，進一步包括用當前位置更新最新近遍歷的節點的節點字段以指派該最新近遍歷的節點用于將來的數據序列匹配。

9.一種計算設備，包括：

至少存儲器和處理器以實施枚舉服務，所述枚舉服務被配置成：

生成代表存儲在存儲緩沖器中的數據序列的后綴數組；

將所述后綴數組轉換成特里結構，由于所述特里結構在所述后綴數組的原地生成，所以其蓋寫存儲緩沖器中的所述后綴數組，所述特里結構包括節點，所述節點的每一個代表所述后綴數組的一個或多個后綴，其中每一連續后綴或者被與所述特里結構中的現有節點群聚，或者被添加為所述特里結構的新節點；以及

枚舉從所述特里結構確定的數據序列匹配。