[發明專利]一種字符串詞典的索引方法及系統

有效

• 申請號: 201310731193.3
• 申請日: 2013-12-26
• 公開（公告）號: CN103699647B
• 公開（公告）日: 2017-02-15
• 發明（設計）人: 張廣泉;張國清;戎玫;顧玉磊
• 申請（專利權）人: 蘇州大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京集佳知識產權代理有限公司11227
• 代理人: 常亮

1.一種字符串詞典的索引方法，其特征在于，包括：

獲取待測字符串鍵P；

查詢預先建立的包括索引Trie和標簽Trie的索引模型；

其中：所述索引Trie由多個節點，及節點之間路徑上的字符串標簽首字母組成，各節點中攜帶字符串鍵的值及字符串標簽的尾字符串在標簽Trie中的節點編號，所述尾字符串為字符串標簽除首字母外剩余的字符串；所述標簽Trie上的各節點具有唯一編號，且每個節點到根節點之間的路徑上存儲的字符串，為所述索引Trie上攜帶當前節點編號的節點對應的字符串標簽的尾字符串。

2.根據權利要求1所述的方法，其特征在于，所述索引Trie和所述標簽Trie為通過LOUDS表示法進行存儲的。

3.根據權利要求1所述的方法，其特征在于，所述索引Trie和所述標簽Trie的建立過程如下：

將多個字符串鍵值對進行排序，該排序與字符串在詞典中的順序一致；

將所有字符串鍵值對分成若干組，每組具有若干按照上述順序排列的字符串鍵值對；

為上述每個組建立一個第一Patricia?Trie；

從每個第一Patricia?Trie中選取最大鍵作為新鍵，每個第一Patricia?Trie的標識作為對應新鍵的值；

使用所有的新鍵及新鍵的值構造一個第二Patricia?Trie，該第二Patricia?Trie作為根節點，與作為葉子節點的所述第一Patricia?Trie形成樹狀結構；

將第一Patricia?Trie和第二Patricia?Trie中的每個Patricia?Trie，分解成一個標簽Trie和一個索引Trie；

其中：將所述第一Patricia?Trie分解成的索引Trie確定為第一索引Trie，將所述第二Patricia?Trie分解成的索引Trie確定為第二索引Trie，所述索引Trie由多個節點及節點之間路徑上的字符串標簽首字母組成，各節點中攜帶字符串鍵的值及字符串標簽的尾字符串在標簽Trie中的節點編號；所述標簽Trie上的各節點具有唯一編號，且每個節點到根節點之間的路徑上存儲的字符串，為所述索引Trie上攜帶當前節點編號的節點對應的字符串標簽的尾字符串。

4.根據權利要求3所述的方法，其特征在于，還包括：將所有的標簽Trie以疊加的方式合并為一個統一標簽Trie，則所述索引模型中包括的標簽Trie為所述統一標簽Trie。