1class DoubleArray:
2    """
3    ダブルアレイクラス
4
5    Attributes
6    ----------
7    BASE : list
8        ずらす幅を格納するBASE配列
9        
10    CHECK : list
11        遷移元を格納するCHECK配列
12
13    items : list
14        登録された単語の読み方
15        単語終端ノード以外の場合はNone
16
17    """
18
19    def __init__(self, triple):
20        """
21
22        Parameters
23        ----------
24        triple : triple
25            ダブルアレイの元となるトリプルアレイ
26        """
27        # BASEにはずらし幅が入る(ずらし幅は-(VOCAB_SIZE)以下になることはない
28        # 少し余裕をもたせて-(VOCAB_SIZE+10)で初期化する
29        self.BASE = [-(tr.VOCAB_SIZE+10)] * len(triple.OFFSETS)
30        self.CHECK = [None] * len(triple.CHECK)
31        self.items = [None] * len(triple.CHECK)
32
33        self.make_double_array(triple)

1class DoubleArray:
2
3    .
4    .
5    .
6
7    def make_double_array(self, triple):
8        """
9        トリプルアレイクラスからダブルアレイを構築する
10
11        Parameters
12        ----------
13        triple : triple
14            ダブルアレイの元となるトリプルアレイ
15        """
16
17        node_to_index = [-(tr.VOCAB_SIZE+10)] * len(triple.CHECK)
18        # NEXTを1要素ずつループし、BASEとitemsを作成
19        # ついでにCHECK作成の準備をする
20        for i in range(len(triple.NEXT)):
21            N = triple.NEXT[i]
22            if N == -1:
23                # -1の場合は要素が無いということなのでスルー
24                continue
25            self.BASE[i] = triple.OFFSETS[N] # BASEにずらし幅を代入
26            self.items[i] = triple.items[N] # itemsをノードidでなくindexから得られるように位置を変更
27
28            node_to_index[N] = i # 後でcheck配列を作りやすいようにノードidからindexを得られるようにメモしておく
29
30        # CHECKを1要素ずつループし、新しいCHECKを作成する
31        for i in range(len(triple.CHECK)):
32            if triple.CHECK[i] == 0:
33                # triple.CHECK[i]が0のときはルートノードを表すので新しいCHECKでは-1とする
34                self.CHECK[i] = -1
35            else:
36                self.CHECK[i] = node_to_index[triple.CHECK[i]]

1class TripleArray:
2
3    .
4    .
5    .
6
7    def query(self, word):
8        """
9        検索する
10
11        Parameters
12        ----------
13        word : str
14            検索したい単語
15
16        Returns
17        -------
18        item :str or None
19            検索結果
20            見つからなかった場合はNone
21        """
22
23        def get_char_num(c):
24            """
25            文字のidを返す
26            aが0, bが1, ..., zが25となる
27            """
28            return ord(c) - ord('a')
29
30        # ルートノードにいる状況で初期化
31        offset = 0
32        pre_index = -1
33
34        for c in word:
35            char_num = get_char_num(c)
36
37            tmp_index = offset + char_num # indexを計算
38
39            if not(0 <= tmp_index < len(self.CHECK)):
40                # tmp_indexがCHECKのインデックスの範囲に無いっていない場合は遷移できないのでNone
41                return None
42            if self.CHECK[tmp_index] != pre_index:
43                # 正しい遷移でない場合はそのwordは書くのぬされていないのでNoneを返す
44                return None
45
46            offset = self.BASE[tmp_index] # 次のノードのずらし幅をget
47            pre_index = tmp_index
48
49        return self.items[tmp_index]

1import sys
2import trie as tr
3import triple_array as triple
4
5
6class DoubleArray:
7    """
8    ダブルアレイクラス
9
10    Attributes
11    ----------
12    BASE : list
13        ずらす幅を格納するBASE配列
14        
15    CHECK : list
16        遷移元を格納するCHECK配列
17
18    items : list
19        登録された単語の読み方
20        単語終端ノード以外の場合はNone
21
22    """
23
24    def __init__(self, triple):
25        """
26
27        Parameters
28        ----------
29        triple : triple
30            ダブルアレイの元となるトリプルアレイ
31        """
32        # BASEにはずらし幅が入る(ずらし幅は-(VOCAB_SIZE)以下になることはない
33        # 少し余裕をもたせて-(VOCAB_SIZE+10)で初期化する
34        self.BASE = [-(tr.VOCAB_SIZE+10)] * len(triple.OFFSETS)
35        self.CHECK = [None] * len(triple.CHECK)
36        self.items = [None] * len(triple.CHECK)
37
38        self.make_double_array(triple)
39
40    def make_double_array(self, triple):
41        """
42        トリプルアレイクラスからダブルアレイを構築する
43
44        Parameters
45        ----------
46        triple : triple
47            ダブルアレイの元となるトリプルアレイ
48        """
49
50        node_to_index = [-(tr.VOCAB_SIZE+10)] * len(triple.CHECK)
51        # NEXTを1要素ずつループし、BASEとitemsを作成
52        # ついでにCHECK作成の準備をする
53        for i in range(len(triple.NEXT)):
54            N = triple.NEXT[i]
55            if N == -1:
56                # -1の場合は要素が無いということなのでスルー
57                continue
58            self.BASE[i] = triple.OFFSETS[N] # BASEにずらし幅を代入
59            self.items[i] = triple.items[N] # itemsをノードidでなくindexから得られるように位置を変更
60
61            node_to_index[N] = i # 後でcheck配列を作りやすいようにノードidからindexを得られるようにメモしておく
62
63        # CHECKを1要素ずつループし、新しいCHECKを作成する
64        for i in range(len(triple.CHECK)):
65            if triple.CHECK[i] == 0:
66                # triple.CHECK[i]が0のときはルートノードを表すので新しいCHECKでは-1とする
67                self.CHECK[i] = -1
68            else:
69                self.CHECK[i] = node_to_index[triple.CHECK[i]]
70
71
72    def query(self, word):
73        """
74        検索する
75
76        Parameters
77        ----------
78        word : str
79            検索したい単語
80
81        Returns
82        -------
83        item :str or None
84            検索結果
85            見つからなかった場合はNone
86        """
87
88        def get_char_num(c):
89            """
90            文字のidを返す
91            aが0, bが1, ..., zが25となる
92            """
93            return ord(c) - ord('a')
94
95        # ルートノードにいる状況で初期化
96        offset = 0
97        pre_index = -1
98
99        for c in word:
100            char_num = get_char_num(c)
101
102            tmp_index = offset + char_num # indexを計算
103
104            if not(0 <= tmp_index < len(self.CHECK)):
105                # tmp_indexがCHECKのインデックスの範囲に無いっていない場合は遷移できないのでNone
106                return None
107            if self.CHECK[tmp_index] != pre_index:
108                # 正しい遷移でない場合はそのwordは書くのぬされていないのでNoneを返す
109                return None
110
111            offset = self.BASE[tmp_index] # 次のノードのずらし幅をget
112            pre_index = tmp_index
113
114        return self.items[tmp_index]

1trie = tr.Trie()
2
3trie.insert("a", "エー")
4trie.insert("aa", "エーエー")
5trie.insert("ab", "エービー")
6trie.insert("abc", "エービーシー")
7trie.insert("b", "ビー")
8trie.insert("bc", "ビーシー")
9#trie.insert("c", "シー")
10
11## ここまででtrie木を作成
12
13triple_array = triple.TripleArray(trie) 
14
15## ここまででトリプルアレイを構築
16
17
18double_array = DoubleArray(triple_array)
19
20print(double_array.query("a"))
21print(double_array.query("abc"))
22print(double_array.query("bc"))
23print(double_array.query("abcd"))

1エー
2エービーシー
3ビーシー
4None