トリプルアレイで軽量で高速な辞書を作ってみた！

メディアチーム

トリプルアレイで軽量で高速な辞書を作ってみた！

メディアチーム

2020.01.15

IT技術

Python

軽量で高速に検索できる辞書システムをつくる

トリプルアレイというデータ構造をご存知でしょうか？

「ダブルアレイ」は聞いたことがあっても、「トリプルアレイ」は知らないという方も多いのではないかと思います。

トリプルアレイは、ダブルアレイの元となったデータ構造で、ダブルアレイ同様トライ木を表現することができます。

基本的なアイデアは、トリプルアレイもダブルアレイも一緒です。

ただ、性能はダブルアレイのほうが良いです。

しかし、実装の簡単さから、トリプルアレイが適当な場合もあるかと思います。

そこで、今回は、トリプルアレイを用いて、軽量で高速に検索できる辞書システムを実装してみたいと思います。

トリプルアレイとダブルアレイ

元々、トリプルアレイは「YACC」や「LEX」といったツールで使われていた技術です。

これを検索に特化し改良したものとして、「ダブルアレイ」が生まれました。

※詳しくは『An Efficient Digital Search Algorithm by Using a Double-Array Structure(JI-Aoe.1989)』という論文に書かれています。

ただ、トリプルアレイも、Trie木を表現できるデータ構造なので、辞書検索に利用することができます。

ダブルアレイ

ダブルアレイの方がメモリ効率が良く、検索速度もトリプルアレイと同等であるため、できればダブルアレイを用いたほうが良いです。

しかし、その分、仕組みがやや複雑になるため、理解、実装するのがやや難しいという面があります。

トリプルアレイ

一方、トリプルアレイは、メモリ効率はダブルアレイに劣りますが、仕組みはダブルアレイほど複雑でないため、理解、実装が比較的簡単にできます。

トリプルアレイでは、その名の通り3本の配列を利用することでトライ木を表現します。

下記図の左側、配列で表現されたトライ木では無駄な要素が多く、メモリ効率が非常に悪いです。

右側のトリプルアレイでは、この隙間を無くし、よりコンパクトにトライ木を格納することができます。

以前の記事はこちら

トライ木の配列表現がよく分からない方は、以前の記事を参照してください。

2019.08.08トライ木で高速な辞書を作ってみた！トライ木で高速な辞書を作りたい！トライ木（英: trie）というデータ構造を知ってますか？トライ木はテキストを扱う際に...

2019.10.01トライ木をビットスライスとパトリシア木でコンパクトにしてみた！「ビットスライス」「パトリシア木」を用いて、トライ木の問題点を解決したい！前回の記事では、トライ木というデータ構造を紹...

トリプルアレイ構築方法

それでは、トリプルアレイの構築方法について解説していきます。

トリプルアレイは、トライ木の配列表現を利用して構築していきます。

まず、トライ木の配列表現の各行を、要素がぶつからないようにずらし、潰して一本の配列にします。

この配列が、トリプルアレイの一本目の配列、NEXT配列になります。

また、この際に各行のずらし幅を2本目の配列、OFFSET配列として記録しておきます。

ここで、このトライ木において、ノード1 にいる状態で「c」を入力し、ノード3 に遷移する場合を考えます。

配列表現においては、まずノード1 の行をみます。

このノード1 の配列を TRIE[1] と表すことにします。

入力される文字「c」の単語idは「2」です。

ここから、遷移先は TRIE[1][2] に格納されていることが分かります。

ここにある数字が3なので、ノード3 の行に遷移する となります。

NEXT配列とOFFSET配列を用いて、同様の遷移をすることを考える

まずは、NEXT配列のなかで、ノード1 に対応する場所を見つける必要があります。

NEXT配列は、配列表現の各行をずらして潰した配列ですので、ノード1 の行のずらし幅が分かれば、ノード1 が NEXT配列においてどこから始まるのかが分かります。

ノード1 のずらし幅は、OFFSET配列の1の位置（OFFSET[1]）に入っています。

OFFSET[1] をみると、ずらし幅は「-1」です。

ここから、ノード1 は NEXT[-1] から始まることがわかります。

(ノード1 の配列が-1の位置からはじまるというだけで、実際には NEXT[-1] に要素は保存されていません。)

次に、ノード1 において「c」が入力された場合に対応する位置を探します。

NEXT配列を作成する際に各行をずらしましたが、各行内での要素の位置関係は変わっていません。

そのため、「c」の単語idである「2」をずらし幅に足した NEXT[-1+2] に遷移先が格納されています。

NEXT[1] の要素は「3」ですので、ノード3 に遷移することがわかります。

このように、「NEXT配列」と「OFFSET配列」があれば、トライ木を遷移していくことが可能です。

問題点

しかし、この2本だけでは1つ問題点があります。

例）
ノード1において、今度はこのトライ木格納されていない「d」が入力された場合を考えます。
先程と同様に、OFFSET配列からずらし幅が「-1」であることがわかり、これに「d」の単語idである「3」を足した NEXT[2] に遷移先の情報が入っていることがわかります。
NEXT[2] は、「2」となっています。

これはおかしいです。

ノード1 における「d」、は本来格納されていない単語なので、どこにも遷移できないはずですが、ノード2 に遷移することになっています。

この「2」というのは実は、ノード0 において「c」が入力された際に遷移する先です。

このように、NEXT配列と OFFSET配列だけで遷移すると、NEXT配列の要素がどのノードからの遷移情報であるかが分からないため、誤った場所に遷移してしまいます。

この問題を解決するために、CHECK配列を導入します。

CHECK配列

CHECK配列には、NEXT配列の同じ位置にある要素が、どのノードからの遷移情報を表しているかを格納しておきます。

CHECK配列を導入した状態でもう一度、ノード1 で「d」が入力された場合を考えます。

先程同様、OFFSETと「d」のidから、NEXT[2] に遷移先の情報が入っていることが分かります。

ここで、CHECK[2] をみると、「0」となっています。

いまは、ノード1 からの遷移をしようとしており、ノード0ではありません。

ここから、ノード1 から「d」では遷移できない。

つまり、この単語は格納されていないということが分かります。

以上、「NEXT配列」「OFFSET配列」「 CHECK配列」でトリプルアレイの構築は完了です。

トリプルアレイの実装(準備)

いよいよ、実際にトリプルアレイを実装し、辞書システムを作っていきましょう！

言語は、Python を用います。

要件

要件は、トライ木、パトリシア木のときと同様です。

単語とその読み方のペアを登録する
単語を入力することで読み方を出力する
単語に使える文字はasciiのみ

単語とその読み方のペアとして、以下のデータを用います。

単語	読み方
a	エー
ab	エービー
ac	エーシー
abc	エービーシー
bc	ビーシー

構造体を作る

まずは、準備段階として、構造体から作っていきます。

TripleArrayクラス

今回は、TripleArray というクラスを作成します。

なお、トリプルアレイは、トライ木を元に作成するため、以前の記事で作成したTrieクラスを用いています。

TripleArrayクラスは、「NEXT配列」「CHECK配列」「OFFSETS配列」と「items」「 trie」の5つの変数を持ちます。

NEXT配列とCHECK配列

NEXT配列と CHECK配列は、構築するまでどのくらいの長さになるのか分かりません。

そのため、まずは長さ2 で初期化し、構築中に長さが足りなくなったら伸ばすというようにします。

OFFSETS配列

OFFSETS（ずらし幅）は、負の値になることもあるので、要素が入っているかどうかを判断するために十分小さな値で初期化します。

実装

__init__() 関数の最後の行で、後に説明するmake_triple_array() を呼び出し、trie を元にトリプルアレイを構築します。

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

トリプルアレイ実装(構築部分)

Trieクラスからトリプルアレイを構築するmake_triple_array() を実装していきます。

このメソッドは、trieのノードに一つずつ以下の処理を適応することで、3つの配列を構築していきます。

要素がぶつからないずらし幅を見つける(find_offset)
見つかったずらし幅で、3つの配列に挿入する(update_arraies)
NEXTの長さが足りない場合は、倍に増やす(resize_arraies)

コード

1class TripleArray:
2
3    .
4    .
5    .
6
7    def make_triple_array(self):
8        """
9        トリプルアレイを構築する
10        """
11        def is_have_child(node):
12            """
13            nodeが子ノードを持っているかを調べる
14            """
15            tmp = [i for i in node.children if i != -1]
16            if len(tmp) > 0:
17                return True
18            else:
19                return False
20
21        node_id = 0
22        for node in self.trie.nodes:
23            self.items[node_id] = node.item # itemの登録
24            if is_have_child(node):
25                # 子ノードを持ってるノードだったら
26                offset = self.find_offset(node)
27                self.update_arraies(offset, node_id, node)
28            node_id = node_id + 1
29
30    def resize_arraies(self, new_size):
31        """
32        CHECKとNEXTのサイズをnew_sizeにする
33        """
34        now_size = len(self.CHECK)
35        add_size = new_size - now_size
36        new_CHECK = [-1] * add_size
37        new_NEXT = [-1] * add_size
38        self.CHECK.extend(new_CHECK)
39        self.NEXT.extend(new_NEXT)
40
41
42    def find_offset(self, node):
43        """
44        nodeを格納できるずらし幅を見つける
45
46        Parameters
47        ----------
48        node : TrieNode
49            格納するnode
50
51        Returns
52        -------
53        offsets : int
54            見つけたずらし幅
55        """
56        def find_left_node():
57            """
58            nodeの一番左側の要素のindexを返す
59            """
60            for i in range(len(node.children)):
61                if node.children[i] != -1:
62                    return i
63            return -1
64
65        def find_right_node():
66            """
67            nodeの一番右側の要素のindexを返す
68            なかったら-1
69            """
70            for i in range(len(node.children)-1, 0, -1):
71                if node.children[i] != -1:
72                    return i
73            return -1
74
75        def check(tmp_offset, node):
76            """
77            tmp_offsetでnodeを挿入可能かたしかめる
78            """
79            for i in range(len(node.children)):
80                # nodeの全部のに対して一つずつNEXTのすでにある要素とぶつからないかを調べる
81                if node.children[i] != -1 and self.NEXT[i+tmp_offset] != -1:
82                    return False
83
84            return True
85
86        def update_tmp_offset(tmp_offset):
87            """
88            tmp_offsetを更新する
89            """
90            # 今回は+1するだけだが、NEXTの空の位置を記録したりすることで構築時間を短縮することができる
91            return tmp_offset + 1
92
93
94
95
96        tmp_offset = - find_left_node()
97        inserted = False
98        node_last = find_right_node() + 1
99        while inserted == False:
100            # ぶつからないところが見つかるまでずらしていく
101
102            if node_last + tmp_offset > len(self.NEXT):
103                # もしNEXTのサイズが足りなかったら増やす
104                self.resize_arraies(len(self.NEXT) * 2)
105                continue
106
107            if check(tmp_offset, node): # 挿入可能かどうかをcheck
108                # tmp_offsetで挿入可能ならreturn
109                return tmp_offset
110
111            tmp_offset = update_tmp_offset(tmp_offset)
112
113    def update_arraies(self, offset, parent_id, node):
114        """
115        CHECK, NEXT, OFFSETS配列を更新する
116
117        Parameters
118        ----------
119        offset : int
120            ずらし幅
121
122        parent_id : int
123            挿入するノードのid
124
125        node : TrieNode
126            挿入するノード
127        """
128
129        for i in range(len(node.children)):
130            insert_index = i + offset
131            if node.children[i] != -1:
132                # ちゃんと挿入できるか一応再チェック
133                if self.NEXT[insert_index] != -1:
134                    print("ERROR:NEXT[{}] is not empty".format(insert_index), file=sys.stderr)
135                    exit(1)
136                if self.CHECK[insert_index] != -1:
137                    print("ERROR:CHECK[{}] is not empty".format(insert_index), file=sys.stderr)
138                    exit(1)
139                # 挿入
140                self.NEXT[insert_index] = node.children[i]
141                self.CHECK[insert_index] = parent_id
142        self.OFFSETS[parent_id] = offset

基本的には、1ノードずつずらし幅を見つけて（find_offset）、挿入する（update_arraies）だけなので、トリプルアレイの仕組みが理解できていれば問題ないと思います。

コード中にかなり詳しくコメントを書いたので参考にしてください。

トリプルアレイ実装(検索部分)

続いて、検索を行うquery() を実装していきます。

こちらは、検索文字列を一文字ずつループすることで、トリプルアレイを遷移していきます。

最後のノードにたどり着いたら、items に格納されているそのノードに対応する要素を返します。

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        tmp_index = 0
31        tmp_node = 0
32        tmp_offset = 0
33        for c in word:
34            char_num = get_char_num(c)
35
36            offset = self.OFFSETS[tmp_node] # ずらし幅をget
37            tmp_index = offset + char_num # NEXT, CHECKのindexを計算
38            if not(0 <= tmp_index < len(self.CHECK)):
39                # tmp_indexがCHECKのインデックスの範囲に無いっていない場合はただ遷移でないのでNone
40                return None
41
42            if self.CHECK[tmp_index] != tmp_node:
43                # 正しい遷移でない場合そのwordは格納されていないのでNoneを返す
44                return None
45
46            tmp_node = self.NEXT[tmp_index] # 遷移先のノードをget
47
48        return self.items[tmp_node]

トリプルアレイの実装(全体)

ここまでで、トリプルアレイを用いた辞書の実装が完了です。

すべてのコードをまとめたものが以下になります。

コード

1import sys
2import trie as tr # 以前の記事で作成したTRIEクラス
3
4
5class TripleArray:
6    """
7    トリプルアレイクラス
8
9    Attributes
10    ----------
11    NEXT : list
12        遷移先を格納するNEXT配列
13
14    CHECK : list
15        遷移元を格納するCHECK配列
16
17    OFFSETS : list
18        ずらし幅を格納するOFFSETS配列
19
20    items : list
21        登録された単語の読み方
22        単語終端ノード以外の場合はNone
23
24    trie : Trie
25        トリプルアレイの元となるTrie木
26
27    """
28
29    def __init__(self, trie):
30        self.CHECK = [-1] * 2
31        self.NEXT = [-1] * 2
32        # オフセットは-(VOCAB_SIZE)以下になることはない
33        # 少し余裕をもたせて-(VOCAB_SIZE+10)で初期化する
34        self.OFFSETS = [-(tr.VOCAB_SIZE+10)] * len(trie.nodes)
35        self.items = [None] * len(trie.nodes)
36
37        self.trie = trie
38        self.make_triple_array()
39
40
41
42    def make_triple_array(self):
43        """
44        トリプルアレイを構築する
45        """
46        def is_have_child(node):
47            """
48            nodeが子ノードを持っているかを調べる
49            """
50            tmp = [i for i in node.children if i != -1]
51            if len(tmp) > 0:
52                return True
53            else:
54                return False
55
56        node_id = 0
57        for node in self.trie.nodes:
58            self.items[node_id] = node.item # itemの登録
59            if is_have_child(node):
60                # 子ノードを持ってるノードだったら
61                offset = self.find_offset(node)
62                self.update_arraies(offset, node_id, node)
63            node_id = node_id + 1
64
65    def resize_arraies(self, new_size):
66        """
67        CHECKとNEXTのサイズをnew_sizeにする
68        """
69        now_size = len(self.CHECK)
70        add_size = new_size - now_size
71        new_CHECK = [-1] * add_size
72        new_NEXT = [-1] * add_size
73        self.CHECK.extend(new_CHECK)
74        self.NEXT.extend(new_NEXT)
75
76
77    def find_offset(self, node):
78        """
79        nodeを格納できるずらし幅を見つける
80
81        Parameters
82        ----------
83        node : TrieNode
84            格納するnode
85
86        Returns
87        -------
88        offsets : int
89            見つけたずらし幅
90        """
91        def find_left_node():
92            """
93            nodeの一番左側の要素のindexを返す
94            """
95            for i in range(len(node.children)):
96                if node.children[i] != -1:
97                    return i
98            return -1
99
100        def find_right_node():
101            """
102            nodeの一番右側の要素のindexを返す
103            なかったら-1
104            """
105            for i in range(len(node.children)-1, 0, -1):
106                if node.children[i] != -1:
107                    return i
108            return -1
109
110        def check(tmp_offset, node):
111            """
112            tmp_offsetでnodeを挿入可能かたしかめる
113            """
114            for i in range(len(node.children)):
115                # nodeの全部のに対して一つずつNEXTのすでにある要素とぶつからないかを調べる
116                if node.children[i] != -1 and self.NEXT[i+tmp_offset] != -1:
117                    return False
118
119            return True
120
121        def update_tmp_offset(tmp_offset):
122            """
123            tmp_offsetを更新する
124            """
125            # 今回は+1するだけだが、NEXTの空の位置を記録したりすることで構築時間を短縮することができる
126            return tmp_offset + 1
127
128
129
130
131        tmp_offset = - find_left_node()
132        inserted = False
133        node_last = find_right_node() + 1
134        while inserted == False:
135            # ぶつからないところが見つかるまでずらしていく
136
137            if node_last + tmp_offset > len(self.NEXT):
138                # もしNEXTのサイズが足りなかったら増やす
139                self.resize_arraies(len(self.NEXT) * 2)
140                continue
141
142            if check(tmp_offset, node): # 挿入可能かどうかをcheck
143                # tmp_offsetで挿入可能ならreturn
144                return tmp_offset
145
146            tmp_offset = update_tmp_offset(tmp_offset)
147
148    def update_arraies(self, offset, parent_id, node):
149        """
150        CHECK, NEXT, OFFSETS配列を更新する
151
152        Parameters
153        ----------
154        offset : int
155            ずらし幅
156
157        parent_id : int
158            挿入するノードのid
159
160        node : TrieNode
161            挿入するノード
162        """
163
164        for i in range(len(node.children)):
165            insert_index = i + offset
166            if node.children[i] != -1:
167                # ちゃんと挿入できるか一応再チェック
168                if self.NEXT[insert_index] != -1:
169                    print("ERROR:NEXT[{}] is not empty".format(insert_index), file=sys.stderr)
170                    exit(1)
171                if self.CHECK[insert_index] != -1:
172                    print("ERROR:CHECK[{}] is not empty".format(insert_index), file=sys.stderr)
173                    exit(1)
174                # 挿入
175                self.NEXT[insert_index] = node.children[i]
176                self.CHECK[insert_index] = parent_id
177        self.OFFSETS[parent_id] = offset
178
179    def query(self, word):
180        """
181        検索する
182
183        Parameters
184        ----------
185        word : str
186            検索したい単語
187
188        Returns
189        -------
190        item :str or None
191            検索結果
192            見つからなかった場合はNone
193        """
194
195        def get_char_num(c):
196            """
197            文字のidを返す
198            aが0, bが1, ..., zが25となる
199            """
200            return ord(c) - ord('a')
201
202        tmp_index = 0
203        tmp_node = 0
204        tmp_offset = 0
205        for c in word:
206            char_num = get_char_num(c)
207
208            offset = self.OFFSETS[tmp_node] # ずらし幅をget
209            tmp_index = offset + char_num # NEXT, CHECKのindexを計算
210            if not(0 <= tmp_index < len(self.CHECK)):
211                # tmp_indexがCHECKのインデックスの範囲に無いっていない場合はただ遷移でないのでNone
212                return None
213
214            if self.CHECK[tmp_index] != tmp_node:
215                # 正しい遷移でない場合そのwordは格納されていないのでNoneを返す
216                return None
217
218            tmp_node = self.NEXT[tmp_index] # 遷移先のノードをget
219
220        return self.items[tmp_node]

トリプルアレイの構築、検索

最後に、トリプルアレイの構築、検索を行います。

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

結果

これを実行すると、以下のような結果になります。

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

辞書に insert した単語は、きちんと読み方が表示され、そうでない単語は None となっていることがわかります。

さいごに

お疲れさまでした！

トリプルアレイは、ダブルアレイに比べると簡単ですが、それでもきちんと理解するのは難しいかもしれません。

それでも、一度きちんと実装してみれば、必ず理解できるはずです。

また、トリプルアレイさえ理解できれば、ダブルアレイの理解も簡単になるので、ぜひチャレンジしてみてください！

こちらの記事もオススメ！

2020.01.15トリプルアレイで軽量で高速な辞書を作ってみた！軽量で高速に検索できる辞書システムをつくるトリプルアレイというデータ構造をご存知でしょうか？「ダブルアレイ」は聞いたこ...

2020.01.28ダブルアレイで高速でコンパクトな辞書を実装してみた！ダブルアレイを使って辞書を実装してみるダブルアレイは、トライ木を表現することができるデータ構造で、コンパクトで高速に辞...

ITフリーランスのエンジニア専門エージェント

技術力で世の中をもっと面白くエンジニア積極採用中！

ライトコードでは、エンジニアを積極採用中！

ライトコードでは、エンジニアを積極採用しています！社長と一杯しながらお話しする機会もご用意しております。そのほかカジュアル面談等もございますので、くわしくは採用情報をご確認ください。

採用情報へ

メディアチーム

「好きを仕事にするエンジニア集団」の（株）ライトコードです！ライトコードは、福岡、東京、大阪、名古屋の４拠点で事業展開するIT企業です。現在は、国内を代表する大手IT企業を取引先にもち、ITシステムの受託事業が中心。いずれも直取引で、月間PV数1億を超えるWebサービスのシステム開発・運営、インフラの構築・運用に携わっています。システム開発依頼・お見積もり大歓迎！また、現在「WEBエンジニア」「モバイルエンジニア」「営業」「WEBデザイナー」を積極採用中です！インターンや新卒採用も行っております。以下よりご応募をお待ちしております！ https://rightcode.co.jp/recruit