• トップ
  • ブログ一覧
  • トライ木で高速な辞書を作ってみた!
  • トライ木で高速な辞書を作ってみた!

    広告メディア事業部広告メディア事業部
    2019.08.08

    IT技術

    トライ木で高速な辞書を作りたい!

    トライ木(英: trie)というデータ構造を知ってますか?

    トライ木はテキストを扱う際に良く用いられているデータ構造で、文字列を非常に高速に検索することができるため、辞書の実装などに利用されています。

    本記事では、トライ木の特徴の紹介構築方法の解説・実装を行っていきます。

    最終的に単語とその読み方を入力としたトライ木を構築し、単語を入力することでその読み方を出力する辞書システムを作成します。

    トライ木とは

    トライ木とは、上の図のようなデータ構造で、順序付き木の一つです。

    この図は、例として「a」「ab」「abc」「ac」「bc」という5単語が入ったトライ木です。

    ノードの左上の数字は、ノードidを表します。

    id0のノードの <s> というのは先頭文字を表していて、検索の際はここからスタートします。

    丸が二重になっているノードは、そのノードが単語の終端文字を表していることを示します。

    検索の際は、先頭ノードから入力文字に対応するエッジをたどります。

    手順

    例えば、「ab」という単語を検索する際には、以下のような手順をたどります。

    1先頭ノードからでているエッジに「ab」の1文字めである「a」があるかを探す
    2ノード1に伸びるエッジが「a」なので、ノード1に遷移
    3ノード1のエッジに「ab」の2文字目である「b」があるかを探す
    4ノード3に伸びるエッジが「b」なので、ノード2に遷移
    5入力文字が最後まで行ったので現在のノードが終端文字を表すノードか確認
    6ノード3は終端文字を表すノードなので辞書に「ab」が存在することがわかる

    トライ木の特徴

    トライ木には、以下のような特徴があります。

    検索が高速[計算量O(M)]で、構築が高速[単語1つにつきO(L)]

    検索が高速という点は、トライ木を用いる際の最も大きな利点といえるでしょう。

    検索単語の長さがMのとき、計算量はO(M)となります。

    これは辞書に格納されている単語数によらず、検索単語の長さにのみ比例した時間で検索できることを表しています。

    つまり、数百万単語(あるいは数億、数兆)の中から「トライ木」という単語を抜き出してくる処理を、2単語の中から「トライ木」という単語を抜き出す処理と同じくらい高速にできるということです。

    同様に、構築の際も長さLの1単語を挿入するのにかかる計算量はO(L)となり、辞書の大きさによらず、挿入単語の長さに比例した時間で挿入できます。

    一度の探索でキーのprefixの検索もできる

    一度の探索でキーのprefixの検索もできるというのもトライ木特有の優れた点です。

    例えば、「情報処理技術者」という単語を検索することを考えます。

    このとき、辞書には「情報」「情報処理」「情報処理技術」という3つの単語も登録されていたとします。

    この辞書がトライ木で実装されていたとしたら、「情報処理技術者」という単語を検索する1回の処理で、他の3単語の情報も得ることができます。

    この特徴は、日本語の形態素解析をする際に非常によく利用されています。

    また、オートコンプリートシステムの構築にも用いることができます。

    サイズが大きくなることがある

    次は、欠点です。

    トライ木においては、登録されている単語によっては、サイズが大きくなることがあります。

    そのため、なるべくサイズが小さくなるような実装方法や工夫が研究されています。

    トライ木の実装方法

    トライ木には、LOUDSダブルアレイなどの様々な実装方法があります。

    しかし、今回は(おそらく)最も素直で単純な実装である配列を用いた実装を行います。

    この実装では、1つのノードを1つの配列として表現します。

    図で表すと

    次の図は、先ほど例として示した図を配列表現したものです。

    各行各ノードを表す
    WORDの列格納される単語を表す
    abc...zのどの文字でどのノードに遷移するか、つまり木の表現におけるエッジを表す
    ENDの列そのノードが単語の終端文字であるかどうか、木の表現における二重丸かどうかを表す

    検索を行う際のノードの巡り方

    実際に検索を行う際のノードの巡り方の例は以下の図のようになります。


    図の、木の表現と列の表現の赤い矢印は、同じ「ab」という単語を検索した際のノードの巡り方を示しています。

    トライ木の実装(準備)

    それでは、いよいよ実際にトライ木を実装し、辞書システムを作っていきましょう!

    今回の言語は、Python(パイソン)を用いたいと思います。

    要件

    要件は以下のようなものです。

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

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

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

    さて、まずは準備段階として、トライ木実装の際に用いる構造体(クラス)を作っていきます。

    今回は、TrieNodeクラスTrieクラスという2種類のクラスを用います。

    TrieNodeクラス

    TrieNodeクラスは、トライ木の1つのノードを表すクラスで、itemchildrenという2つの変数を持ちます。

    itemは、辞書引きを行った際に取得したい情報です。

    今回は単語を入力し、その読み方を得るシステムなので、itemには単語の読み方が入ります。

    単語の終端ノードでない場合には、Noneが入ります。

    今回は、このitemを単語の終端ノードかどうかの判定にも利用します。

    childrenは、どの文字でどのノードに遷移するかのリストです。

    先のトライ木の配列の例の図におけるabc...zの列を表します。

    Trieクラス

    Trieクラスは、トライ木の実態を表すクラスで、nodesという変数を持ちます。

    nodesは、TrieNodeのリストになります。

    コード

    1VOCAB_SIZE = 128 # 語彙数(今回はasciiのみの対応なので128)
    2
    3class TrieNode:
    4    """
    5    Trie木の1ノードを表すクラス
    6
    7    Attributes
    8    ----------
    9    item : str
    10        登録された単語の読み方
    11        単語終端ノード以外の場合はNone
    12
    13    children : list
    14      遷移先のリスト
    15    """
    16
    17
    18    def __init__(self, item = None):
    19        self.item = item
    20        self.children = [-1 for i in range(VOCAB_SIZE)]
    21
    22    def __str__(self):
    23        ret = ""
    24        ret = ret + "item = {}\n".format(self.item)
    25        ret = ret + "children = \n{}".format(self.children)
    26        return ret
    27
    28class Trie:
    29    """
    30    Trie木を表すクラス
    31
    32    Attributes
    33    ----------
    34    nodes : TrieNode
    35        ノードのリスト
    36    """
    37
    38    def __init__(self):
    39        root = TrieNode()
    40        self.nodes = [root]

    トライ木の実装(構築部分)

    前章で作ったTrieクラスに単語を登録し、トライ木を構築するためのinsertメソッドを実装します。

    1class Trie:
    2    """
    3    Trie木を表すクラス
    4
    5    Attributes
    6    ----------
    7    nodes : TrieNode
    8        ノードのリスト
    9    """
    10
    11    def __init__(self):
    12        root = TrieNode()
    13        self.nodes = [root]
    14
    15
    16    def __add_node(self, node):
    17        """
    18        nodesにノードを追加する
    19        追加したノードのインデックスを返す
    20
    21        Parameters
    22        ----------
    23        node : TrieNode
    24            追加するノード
    25
    26        Returns
    27        -------
    28        index : int
    29            追加したノードのインデックス
    30        """
    31        self.nodes.append(node)
    32        return len(self.nodes) - 1
    33
    34    def __get_char_num(self, c):
    35        """
    36        文字のidを返す
    37        aが1, bが2, ..., zが26となる
    38
    39        Parameters
    40        ----------
    41        c : char
    42          idを取得したいしたい文字
    43
    44        Returns
    45        -------
    46        id : int
    47          文字のid
    48        """
    49
    50        return ord(c) - ord('a')
    51
    52    def insert(self ,word, item, char_index=0, node_index=0):
    53        """
    54        Trieに新しい単語を登録する
    55
    56        Parameters
    57        ----------
    58        word : str
    59            登録する単語
    60
    61        item : str
    62            wordに対応する読み方
    63
    64        char_index : int
    65            現在着目している文字の位置
    66
    67        node_index : int
    68            現在着目しているノードの位置
    69        """
    70
    71        char_num = self.__get_char_num(word[char_index])
    72        next_node_index = self.nodes[node_index].children[char_num]
    73        if next_node_index == -1:
    74            # 現在のノードにword[char_index]での遷移がなかった場合
    75            new_node = TrieNode()
    76            next_node_index = self.__add_node(new_node)
    77            self.nodes[node_index].children[char_num] = next_node_index
    78
    79        if char_index == len(word) - 1:
    80            # 最後の文字だった場合
    81            self.nodes[next_node_index].item = item
    82        else:
    83            self.insert(word, item, char_index+1, next_node_index)

    insertを実装するために__add_node()__get_char_num() というメソッドを作りました。

    それぞれ、nodesにnodeを追加し、追加したノードのインデックスを返すメソッドと、文字のidを返すメソッドになります。

    詳しくは実装とコメントを参考にしてください。

    insertメソッド

    insertメソッドを見ていきます。

    insertメソッドは、再帰的に呼び出され、すでにあるトライ木を辿っていき、その過程で対応するノードがなかった場合に追加していくことで、トライ木を構築するメソッドです。

    一度、insertメソッドが呼び出されるたびに登録単語の1文字分のノードをたどります。

    例えば、「ab」という単語を登録する際には、「a」の分と「b」の分の2回のinsertメソッドが呼び出されます。

    まず、1,2行目で、現在の文字で遷移すべきノード(next_node_index)を取得します。

    このときに遷移すべきノードがまだなかった場合、3行目からの分岐で新たなノードを作成します。

    9行目のif char_index == len(word) - 1: の分岐は、現在見ている文字が単語の最後の文字かどうかを判定する分岐です。

    最後の文字だった場合、対応するノードに item (今回は読み方)を保存します。

    そうでなかった場合は、文字を1つ進めて、もう一度 insert を呼び出します。

    トライ木の実装(検索部分)

    続いて、検索を行うqueryメソッドを実装します。

    1class Trie:
    2    """
    3    Trie木を表すクラス
    4
    5    Attributes
    6    ----------
    7    nodes : TrieNode
    8        ノードのリスト
    9    """
    10
    11    def __init__(self):
    12        root = TrieNode()
    13        self.nodes = [root]
    14
    15    #    -
    16    #    - 中略
    17    #    -
    18
    19    def query(self, word):
    20        """
    21        作ったTrieを検索する
    22
    23        Parameters
    24        ----------
    25        word : str
    26            検索したい単語
    27
    28        Returns
    29        -------
    30        item : str or None
    31            検索結果
    32            見つからなかった場合はNone
    33        """
    34        node_index = 0
    35
    36        for c in word:
    37            char_num = self.__get_char_num(c)
    38            tmp_node = self.nodes[node_index]
    39            
    40            node_index = tmp_node.children[char_num]
    41            if node_index == -1:
    42                return None
    43
    44        return self.nodes[node_index].item

    queryメソッドは、入力された単語を一文字ずつ見て、トライ木を辿っていきます。

    最終的に、単語の終端となるノードのインデックスを取得し、そのノードに保存された item を返します。

    コード解説

    まず、1行目で現在着目しているノードを表すnode_indexを先頭文字のノードである0に初期化します。

    次に、3行目から始まるループで、単語を1文字ずつ見ていきます。

    5行目では、現在着目している文字に対応するノードである tmp_node を取得しています。

    7行目で、次に遷移するべきノードの index を取得します。

    このとき、遷移すべきノードがなかった場合は、その単語が辞書に登録されていないことになるので、Noneを返します。(8行目の分岐)

    トライ木の実装(全体)

    ここまでで、トライ木を用いた辞書の実装が終わりました

    構築部分と検索部分をまとめたコードは以下のようになります。

    1import sys
    2
    3VOCAB_SIZE = 128 # 語彙数(今回はasciiのみの対応なので128)
    4
    5class TrieNode:
    6    """
    7    Trie木の1ノードを表すクラス
    8
    9    Attributes
    10    ----------
    11    item : str
    12        登録された単語の読み方
    13        単語終端ノード以外の場合はNone
    14
    15    children : list
    16        子ノードのリスト
    17    """
    18
    19
    20    def __init__(self, item = None):
    21        self.item = item
    22        self.children = [-1 for i in range(VOCAB_SIZE)]
    23
    24    def __str__(self):
    25        ret = ""
    26        ret = ret + "item = {}\n".format(self.item)
    27        ret = ret + "children = \n{}".format(self.children)
    28        return ret
    29
    30class Trie:
    31    """
    32    Trie木を表すクラス
    33
    34    Attributes
    35    ----------
    36    nodes : TrieNode
    37        ノードのリスト
    38    """
    39
    40    def __init__(self):
    41        root = TrieNode()
    42        self.nodes = [root]
    43
    44
    45    def __add_node(self, node):
    46        """
    47        nodesにノードを追加する
    48        追加したノードのインデックスを返す
    49
    50        Parameters
    51        ----------
    52        node : TrieNode
    53            追加するノード
    54
    55        Returns
    56        -------
    57        index : int
    58            追加したノードのインデックス
    59        """
    60        self.nodes.append(node)
    61        return len(self.nodes) - 1
    62
    63    def __get_char_num(self, c):
    64        """
    65        文字のidを返す
    66        aが1, bが2, ..., zが26となる
    67
    68        Parameters
    69        ----------
    70        c : char
    71          idを取得したいしたい文字
    72
    73        Returns
    74        -------
    75        id : int
    76          文字のid
    77        """
    78
    79        return ord(c) - ord('a')
    80
    81    def insert(self ,word, item, char_index=0, node_index=0):
    82        """
    83        Trieに新しい単語を登録する
    84
    85        Parameters
    86        ----------
    87        word : str
    88            登録する単語
    89
    90        item : str
    91            wordに対応する読み方
    92
    93        char_index : int
    94            現在着目している文字の位置
    95
    96        node_index : int
    97            現在着目しているノードの位置
    98        """
    99
    100        char_num = self.__get_char_num(word[char_index])
    101        next_node_index = self.nodes[node_index].children[char_num]
    102        if next_node_index == -1:
    103            # 現在のノードにword[char_index]での遷移がなかった場合
    104            new_node = TrieNode()
    105            next_node_index = self.__add_node(new_node)
    106            self.nodes[node_index].children[char_num] = next_node_index
    107
    108        if char_index == len(word) - 1:
    109            # 最後の文字だった場合
    110            self.nodes[next_node_index].item = item
    111        else:
    112            self.insert(word, item, char_index+1, next_node_index)
    113
    114    def query(self, word):
    115        """
    116        作ったTrieを検索する
    117
    118        Parameters
    119        ----------
    120        word : str
    121            検索したい単語
    122
    123        Returns
    124        -------
    125        item : str or None
    126            検索結果
    127            見つからなかった場合はNone
    128        """
    129        node_index = 0
    130
    131        for c in word:
    132            char_num = self.__get_char_num(c)
    133            tmp_node = self.nodes[node_index]
    134            
    135            node_index = tmp_node.children[char_num]
    136            if node_index == -1:
    137                return None
    138
    139        return self.nodes[node_index].item

    登録・検索

    最後に、Trieクラスを利用して単語の登録、検索を行います。

    1trie = Trie()
    2
    3trie.insert("a", "エー")
    4trie.insert("ab", "エービー")
    5trie.insert("abc", "エービーシー")
    6trie.insert("b", "ビー")
    7trie.insert("bc", "ビーシー")
    8trie.insert("c", "シー")
    9
    10
    11print(trie.query("a"))
    12print(trie.query("abc"))
    13print(trie.query("bc"))
    14print(trie.query("abcd"))

    実行

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

    エー
    エービーシー
    ビーシー
    None

    辞書に登録した3単語はきちんと読み方が返ってきて、登録していない「abcd」という単語はNoneが返ることがわかります。

    さいごに

    トライ木は一見難しそうですが、一度理解してしまえば実装は、さほど難しくなかったと思います。

    トライ木を用いると今回のような辞書だけでなく、「形態素解析機」「オートコンプリート」など、様々な分野に応用がきく便利なデータ構造です。

    この期にぜひマスターしてみてください。

    また、今回の実装では配列を用いた実装ということで、サイズがとても大きくなっています。

    実際に使う際には「パトリシア木」「LOUDS」「ダブルアレイ」といった、サイズを小さくする工夫、実装を行います。

    これについても、近いうちに記事にできたらと思います!

    この記事の続き

    featureImg2019.08.08トライ木で高速な辞書を作ってみた!トライ木で高速な辞書を作りたい!トライ木(英: trie)というデータ構造を知ってますか?トライ木はテキストを扱う際に...

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

    featureImg2020.07.17ライトコード的「やってみた!」シリーズ「やってみた!」を集めました!(株)ライトコードが今まで作ってきた「やってみた!」記事を集めてみました!※作成日が新し...
    featureImg2020.07.30Python 特集実装編※最新記事順Responder + Firestore でモダンかつサーバーレスなブログシステムを作ってみた!P...

    関連記事

    featureImg2019.08.08トライ木で高速な辞書を作ってみた!トライ木で高速な辞書を作りたい!トライ木(英: trie)というデータ構造を知ってますか?トライ木はテキストを扱う際に...

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

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

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

    広告メディア事業部

    広告メディア事業部

    おすすめ記事