Algorithms with Python

はじめに

今回は文字列の集合を表すのに都合のよいデータ構造であるトライ (trie) とパトリシア (patricia tree) を紹介します。どちらも木構造の一種で、根 (root) から葉 (leaf) までの経路が一つの文字列に対応します。トライやパトリシアは文字列を高速に探索することができますが、それだけではなく、共通の接頭辞 (common prefix) を持つ文字列、たとえば 'py' で始まる文字列を簡単に見つけることができます。

●トライとは？

最初はトライから説明しましょう。トライは文字列の集合を表すのに都合のよいデータ構造です。トライの語源は、検索 (retrieval) という言葉の真ん中 (trie) に由来しています。次の図を見てください。

            図 1 : 文字列の集合を表したトライ

上図は文字列の集合をトライで表したものです。ここでは葉を $ で表しています。たとえば、葉 $7 までたどると、それは "THEN" という文字列を表しています。また、文字列 "THE" をトライから探す場合は、節を順番にたどっていって、葉 $6 に達した時点で "THE" を見つけることができます。もし、節 E の子に葉 $6 がなければ、"THE" はトライに存在しないことになります。

なお、この例は文字列ですが、配列 [1, 2, 3, 4] などの列型データ (sequence) もトライで表すことができます。

●トライの実装方法

さて、トライの実装方法ですが、二分木と同様に子を格納するインスタンス変数を用意すれば簡単です。たとえば、英大文字と葉を示す $ がデータとすると、一つの節から最大で 27 の子に分岐します。この場合、子を格納する変数を child とし、$ を含めてサイズが 27 の配列を child にセットすればいいでしょう。

ただし、文字の種類が多くなると配列のサイズが大きくなるので、メモリを大量に消費してしまうのが欠点です。このため、トライを二分木のように構成する方法があります。次の図を見てください。

上図に示すように、縦に親子関係が伸びていき、横に兄弟の関係が伸びていくと考えてください。ようするに、二分木の右部分木が兄弟関係を表し、左部分木が親子の関係を表しているわけです。

これを Python でプログラムすると、次のようになります。

リスト : トライの定義

class Trie:
    class Node:
        def __init__(self, x, bros = None, child = None):
            self.data = x
            self.bros = bros
            self.child = child

トライを表すクラスを Trie とし、その中で節を表すクラス Node を定義します。Node のインスタンス変数 bros が兄弟関係のリンケージを、child が子へのリンケージを表します。これを図に示すと次のようになります。

このように、兄弟関係は連結リストと同じ構造になります。したがって、子が多数ある場合は、探索に時間がかかることになります。そのかわり、節の大きさをコンパクトに収めることができます。

●節の操作メソッド

次は節を操作するメソッドを定義します。これらのメソッドはクラス Node のメソッドとして定義します。最初に、新しい子を挿入するメソッド put_child() を作ります。次の図を見てください。

節 p に子 n を追加する場合を考えてみましょう。p に子がない場合は簡単です。上図に示すように、p の child に n をセットするだけです。このとき、子の bros は None に初期化しておきます。

次に、この状態から子 m を追加します。

子 m を追加する場合、兄弟関係のリンケージ bros は連結リストと同じなので、後ろに追加するよりも先頭に追加した方が簡単です。子 m の bros に子 n をセットし、親 p の child を子 m に書き換えます。これで、親 p の子は m と n になります。子 n を探す場合は、親 p の child から先頭の子 m を求め、そのあと兄弟関係のリンケージ bros をたどることで、子 n を求めることができます。

プログラムは次のようになります。

リスト : 子を挿入する

        def set_child(self, x):
            child = Trie.Node(x, self.child)
            self.child = child
            return child

最初に新しい子 child を Node() で生成します。このとき、Node() の第 2 引数に self.child を渡します。これで、親節 self の先頭の子を child の後ろへリンクすることができます。そして、self.child の値を child に書き換えます。self に子がない場合、self.child の値は None なので、新しい子 child だけが追加されます。最後に、新しい子 child を return で返します。

次は、データと等しい子を求めるメソッド get_child() を作ります。

リスト : データと等しい子を求める

        def get_child(self, x):
            child = self.child
            while child:
                if child.data == x: break
                child = child.bros
            return child

get_child() は親節 self の子の中で、引数 x と等しい data を持つ子を求めます。最初に、先頭の子 (self.child) を取り出して変数 child にセットします。あとは、兄弟関係のリンケージ bros をたどって、child.data と x を比較します。見つけた場合は child を返します。見つからない場合は None を返します。

最後に子を削除するメソッド del_child() を作ります。

リスト : 子の削除

        def del_child(self, x):
            child = self.child
            if child.data == x:
                self.child = child.bros
                return True
            else:
                while child.bros:
                    if child.bros.data == x:
                        child.bros = child.bros.bros
                        return True
                    child = child.bros
            return False

del_child() は親節 self の子の中から x と等しい data を持つ子を削除します。最初に、先頭の子を self.child から取り出して変数 child にセットします。child.data が x と等しい場合は先頭の子を削除します。self.child を child.bros に書き換えて、return で True を返します。

そうでなければ、bros をたどって削除する子を探します。この処理は連結リストの削除処理と同じです。child.bros.data が x と等しい場合は節 child.bros を削除します。child.bros の値を child.bros.bros に書き換えて True を返します。見つからない場合は最後で False を返します。

最後に節を巡回するメソッド traverse() を作ります。traverse() は再帰定義を使うと簡単にプログラムできます。巡回した節のデータは配列 (Python のリスト) に格納して返します。次のリストを見てください。

リスト : 節の巡回

        def traverse(self, leaf):
            if self.data == leaf:
                yield []
            else:
                child = self.child
                while child:
                    for x in child.traverse(leaf):
                        yield [self.data] + x
                    child = child.bros

メソッド traverse() はジェネレータとして実装しました。高階関数としても簡単に実装できるので、興味のある方は挑戦してみてください。引数 self が節を表し、leaf が葉の値を表します。self.data と leaf が等しい場合は再帰呼び出しを停止し、yield で空リスト [] を返します。そうでなければ、self の子に対して traverse() を再帰呼び出しします。そして、self.data と traverse() の返り値 x を連結して、それを yield で返します。これで、節 self 以降の部分木に含まれるデータを全て求めることができます。

●トライの操作メソッド

それでは、トライの操作メソッドを作りましょう。最初に Trie を初期化するメソッド __init__() を作ります。

リスト : Trie の初期化

    def __init__(self, x = None):
        self.root = Trie.Node(None)    # header
        self.leaf = x

Trie のインスタンス変数 root にはヘッダを表す節を格納します。この節の data はダミーです。root の子にデータを追加していきます。インスタンス変数 leaf は葉を表すデータを格納します。leaf は Trie を呼び出すときに引数として渡します。省略した場合は None になります。

●データの探索

次はデータを探索するメソッド search() を作成します。次のリストを見てください。

リスト : データの探索

    def search(self, seq):
        node = self.root
        for x in seq:
            node = node.get_child(x)
            if node is None: return False
        # check leaf
        return node.get_child(self.leaf) is not None

引数 seq が探索するデータ (列型データ : sequence) です。for ループで seq の要素を一つずつ取り出して、トライをたどっていきます。最初に、ヘッダの節 self.root の値を変数 node にセットします。そして for ループの中で、節 node にデータ x を持つ子があるか get_child() で調べます。見つからない場合は探索失敗です。return で False を返します。最後に葉 (leaf) があるかチェックします。葉が見つからない場合は探索失敗となります。

●データの挿入

次はデータを挿入するメソッド insert() を作成します。次のリストを見てください。

リスト : データの挿入

    def insert(self, seq):
        node = self.root
        for x in seq:
            child = node.get_child(x)
            if not child:
                child = node.set_child(x)
            node = child
        # check leaf
        if not node.get_child(self.leaf):
            node.set_child(self.leaf)

トライをたどる処理はデータの探索処理と同じです。get_child() で子が見つからない場合は、set_child() で新しい子を挿入します。最後に、get_child() で葉をチェックます。葉が見つからない場合は、新しい葉を set_child() で挿入します。

●データの削除

次はデータを削除するメソッド delete() を作ります。次のリストを見てください。

リスト : データの削除

    def delete(self, seq):
        node = self.root
        for x in seq:
            node = node.get_child(x)
            if not node: return False
        # delete leaf
        return node.del_child(self.leaf)

データの削除は対応する葉を削除するだけです。この場合、不要になった節 (node) が残ったままになるので、メモリを余分に消費する欠点があります。今回はこの対策を行っていません。ご注意ください。興味のある方は不要になった節を取り除くようにプログラムを改造してみてください。

トライをたどる処理は今までと同じです。トライをたどれない場合は、削除するデータがないので False を返します。最後に del_child() で葉を削除するだけです。

●トライの巡回

次はトライを巡回するメソッド traverse() を作ります。

リスト : トライの巡回

    def traverse(self):
        node = self.root.child
        while node:
            for x in node.traverse(self.leaf):
                yield x
            node = node.bros

トライの巡回は Node の traverse() を呼び出すだけです。ヘッダ (self.root) にはダミーデータ (None) があるので、traverse() に self.root を与えて呼び出してはいけません。traverse() にはヘッダの子を渡してください。変数 node に self.root.child をセットし、兄弟関係のリンケージ bros をたどって traverse() を呼び出し、その返り値 x を yield で返します。

●共通接頭辞を持つデータの探索

最後に common prefix を持つデータを求めるメソッド common_prefix() を作ります。

リスト : 共通接頭辞を持つデータを求める

    def common_prefix(self, seq):
        node = self.root
        buff = []
        for x in seq:
            buff.append(x)
            node = node.get_child(x)
            if not node: return
        node = node.child
        while node:
            for x in node.traverse(self.leaf):
                yield buff + x
            node = node.bros

引数 seq に接頭辞 (prefix) を渡します。そして、同じ接頭辞を持つデータを求めます。最初に、接頭辞 seq を探索します。接頭辞が見つからない場合は return で処理を終了します。common_prefix() はジェネレータとして実装するので、return に引数を与えてはいけません。あとは、接頭辞から下の部分木にあるデータをメソッド traverse() で求めるだけです。接頭辞 buff と traverse() の返り値を連結して yield で返します。

• プログラムリスト１

●実行例

それでは、簡単な実行例として suffix trie を作成してみましょう。サフィックス (suffix : 接尾辞) とは、文字列のある位置から末尾までの文字列のことです。たとえば、文字列 "abcd" のサフィックスは abcd, bcd, cd, d の 4 つになります。

このサフィックスをトライで表したものが suffix trie で、文字列の照合などに用いられるデータ構造です。このほかに、サフィックスを辞書順に並べた配列 suffix array や、suffix trie を改良した suffix tree というデータ構造もあります。

suffix trie は、サフィックスを順番にトライに追加していくだけで作成できます。次のリストを見てください。

リスト : 簡単なテスト

if __name__ == '__main__':
    # suffix trie
    def make_suffix_trie(seq):
        a = Trie()
        for x in range(len(seq)):
            a.insert(seq[x:])
        return a

    s = make_suffix_trie('abcabbca')
    for x in s.traverse():
        print(x)
    for x in ['a', 'bc']:
        print(x)
        for y in s.common_prefix(x):
            print(y)

関数 make_suffix_trie は引数 seq の suffix trie を生成します。seq[x:] で seq の接尾辞を作り、メソッド insert でトライに追加します。とても簡単な方法ですが、データが多くなると時間がかかるのが欠点です。データ数を N とすると、実行時間は N² に比例します。とても遅いので実用的ではありません。ご注意くださいませ。

それでは実行例を示します。

$ python3 trie.py
['c', 'a']
['c', 'a', 'b', 'b', 'c', 'a']
['b', 'b', 'c', 'a']
['b', 'c', 'a']
['b', 'c', 'a', 'b', 'b', 'c', 'a']
['a']
['a', 'b', 'b', 'c', 'a']
['a', 'b', 'c', 'a', 'b', 'b', 'c', 'a']
a
['a']
['a', 'b', 'b', 'c', 'a']
['a', 'b', 'c', 'a', 'b', 'b', 'c', 'a']
bc
['b', 'c', 'a']
['b', 'c', 'a', 'b', 'b', 'c', 'a']

●パトリシア

トライは便利なデータ構造ですが、節には一つの文字 (要素) しか格納できないため、文字列 (列型データ) が長くなるとメモリを大量に消費してしまいます。このため、文字ではなく文字列を節に格納する方法があります。次の図を見てください。

          図 6 : 文字列の集合を表したパトリシア

"TAIL" をトライで表すと T - A - I - L となりますが、I の子は L しかありませんね。この部分は "IL" とまとめることができます。つまり、節には部分文字列を格納するわけです。このように、トライにおいて分岐していない節を一つにまとめたものをパトリシア (patricia tree) と呼ぶことがあります。

パトリシアの場合、データの探索は節の部分文字列を比較していくだけなので、簡単に実現できます。ところが、データの挿入はちょっとだけ複雑になります。たとえば、パトリシアが "ab" - "cdef" という状態で、ここに文字列 "abcdgh" を挿入してみましょう。

挿入する文字列の先頭 2 文字と最初の節 "ab" は一致するので、次の節 "cdef" と残りの文字列 "cdgh" を比較します。"cd" は一致しますが、それ以降で不一致になりますね。この場合、節 "cdef" を不一致の位置で分割します。つまり、節 "cdef" を "cd" - "ef" と分割し、節 "cd" に新しい節 "gh" を追加するのです。このあと、終端を表す葉を追加すれば、パトリシアに "abcdgh" を挿入することができます。

このように、パトリシアにデータを挿入する場合、節の分割が必要になるためプログラムは複雑になります。そのかわり、パトリシアはトライに比べて節の個数を少なくすることができるので、トライよりも少ないメモリで文字列の集合を表すことができます。

●プログラムの作成

それではプログラムを作りましょう。最初にパトリシアを表すクラスを定義します。

リスト : パトリシアの定義

class Patricia:
    class Node:
        def __init__(self, x, bros = None, child = None):
            self.data = x
            self.bros = bros
            self.child = child

        # 子を求める
        def get_child(self, x):
            child = self.child
            while child:
                if child.data[0] == x: break
                child = child.bros
            return child

        # 子を挿入する
        def set_child(self, x):
            child = Patricia.Node(x, self.child)
            self.child = child
            return child

        # 子を削除する
        def del_child(self, x):
            child = self.child
            if child.data[0] == x:
                self.child = child.bros
                return True
            else:
                while child.bros:
                    if child.bros.data[0] == x:
                        child.bros = child.bros.bros
                        return True
                    child = child.bros
            return False

        # 節を巡回する
        def traverse(self, leaf):
            if self.data[0] == leaf:
                yield []
            else:
                child = self.child
                while child:
                    for x in child.traverse(leaf):
                        yield [self.data] + x
                    child = child.bros

クラス名は Patricia とし、その中で節を表すクラス Node を定義します。節を操作するメソッドは Trie とほとんど同じですが、一つだけ注意点があります。Patricia の場合、Node のインスタンス変数 data には列 (sequence) を格納します。このため、get_child(), del_child(), traverse() は、self.data の先頭の要素 (self.data[0]) と引数 x を比較するように修正します。

次は、パトリシアをたどるためのメソッドを作ります。次のリストを見てください。

リスト : パトリシアのメソッド

    # 初期化
    def __init__(self, x = None):
        self.root = Patricia.Node(None)  # header
        self.leaf = x
        self.leaf_data = [x]

    # 最長一致を求める
    def longest_match(self, seq):
        node = self.root
        k = len(seq)
        i = 0
        while i < k:
            child = node.get_child(seq[i])
            if not child: break
            j = 1
            k1 = len(child.data)
            while j < k1:
                if i + j == k or seq[i + j] != child.data[j]:
                    return child, i + j, j
                j += 1
            i += j
            node = child
        return node, i, 0

葉を表すデータも列型データに格納する必要があるので、メソッド __init__() で Patricia のインスタンス変数 leaf_data に、leaf を格納した配列を用意しておきます。そして、葉を挿入するときは set_child() に leaf_data を渡します。

メソッド longest_match() はパトリシアをたどって、引数 seq と最も長く一致する位置を求めます。longest_match() は、最後に一致した節 (node)、seq と一致した長さ (match)、節のデータ (node.data) と一致した長さ (sub_match) を返します。節のデータと全て一致した場合、sub_match の値は 0 とします。このメソッドはパトリシアを操作するメソッド search(), insert(), delete(), traverse(), common_prefix() から呼び出されます。

最初にヘッダ (self.root) を変数 node にセットします。それから、while ループでパトリシアをたどります。次に、メソッド get_child() で seq[i] と等しい子を求めます。見つからない場合は、break で while ループを脱出します。

見つかった場合は child.data と照合します。変数 j が child.data の位置を、i + j が seq の位置を示します。したがって、i + j が一致長 (match)、j が node.data との一致長 (sub_match) になります。seq と最後まで一致した場合 (i + j == k)、または seq と node.data が一致しない場合は、return で node, i + j, j を返します。

node.data と全て一致した場合は、i の値に j を加算し、node の値を child に更新して、次の子を探索します。seq と最後まで一致した場合、または、子が見つからない場合は、while ループを脱出して return で node, i, 0 を返します。この場合は node のデータと全て一致し、その一致長が i となります。

●データの探索

longest_match() を使うとデータの探索は簡単です。次のリストを見てください。

リスト : データの探索

    def search(self, seq):
        node, match, sub_match = self.longest_match(seq)
        if len(seq) == match and sub_match == 0:
            # 葉をチェックする
            return node.get_child(self.leaf)
        return False

longest_match() の返り値を変数 node, match, sub_match で受け取ります。match が seq と同じ長さであれば、seq と全て一致しました。ただし、それだけでは節 node の途中で終わっている場合もあるので、sub_match が 0 かチェックします。node.data と全て一致しているならば、node の子に葉があるかチェックします。

●データの挿入

次はデータの挿入するメソッド insert() を作ります。insert() は節を分割する場合があるので、その処理はちょっと複雑になります。

リスト : データの挿入

    def insert(self, seq):
        node, match, sub_match = self.longest_match(seq)
        if sub_match > 0:
            # node を node - node1 に分割する
            node1 = Patricia.Node(node.data[sub_match:], None, node.child)
            node.data = node.data[:sub_match]
            node.child = node1
            if match < len(seq):
                # node に残りのデータを追加する
                new_node = node.set_child(seq[match:])
                new_node.set_child(self.leaf_data)
            else:
                # 葉を追加するだけ
                node.set_child(self.leaf_data)
        else:
            # node にデータを追加
            if match == len(seq):
                # 葉を追加するだけ
                if not node.get_child(self.leaf):
                    node.set_child(self.leaf_data)
            else:
                # node に残りのデータを追加する
                new_node = node.set_child(seq[match:])
                new_node.set_child(self.leaf_data)

longest_match() の返り値を変数 node, match, sub_match にセットします。sub_match が 0 ならば、節 node の後ろにデータを追加するだけです。sub_match が 0 より大きい場合は node を分割します。節を分割しない場合は簡単です。match が len(seq) と等しい場合は葉を追加するだけです。そうでなければ、seq[match:] を node の子に挿入して、new_node に葉を挿入します。

node を分割する場合はちょっと複雑です。次の図を見てください。

node.data が "abcd" で、これを "ab" - "cd" に分割することにします。この場合、node を "ab" に書き換え、その後ろに "cd" を保持する新しい子 node1 を挿入すると簡単です。node の bros は兄弟関係のリンケージなので、node.bros の値 (P) はそのまま保持します。node1 は node とその子 Q の間に挿入されるので、node1.child の値が Q になり、node.child の値が node1 になります。node1.bros の値は None のままです。

それでは、プログラムに戻りましょう。最初に node1 を生成します。このとき、node.data[sub_match:] で後半部分（不一致部分）のデータと、node の子 (node.child) を渡します。それから、node.data を前半部分 (一致部分) に書き換えて、node.child を node1 に書き換えます。

そして、match が len(seq) よりも短い場合は、残りのデータ seq[match:] を node の子に挿入します。新しい子 new_node には葉を挿入することをお忘れなく。seq と全てマッチングした場合は、node に葉を追加するだけです。

●データの削除

次はデータの削除を行うメソッド delete() を作ります。

リスト : データの削除

    def delete(self, seq):
        node, match, sub_match = self.longest_match(seq)
        if match == len(seq) and sub_match == 0:
            # delete leaf
            return node.del_child(self.leaf)
        return False

delete() はデータの探索 search() とほとんど同じです。longest_match() で最長一致を求め、seq と全てマッチングしたら葉を削除するだけです。delete() はトライと同様に葉を削除するだけで、不要になった節を削除していないことに注意してください。

●パトリシアの巡回

次はパトリシアを巡回するメソッド traverse() を作ります。

リスト : パトリシアの巡回

    def traverse(self):
        node = self.root.child
        while node:
            for x in node.traverse(self.leaf):
                yield x
            node = node.bros

traverse() はジェネレータとして実装しています。これは Node のメソッド traverse() を呼び出すだけです。

●共通接頭辞の探索

最後に common prefix を探索するメソッド common_prefix() を作ります。

リスト : 共通接頭辞を持つデータを求める

    def common_prefix(self, seq):
        node, match, sub_match = self.longest_match(seq)
        if len(seq) == match:
            buff = [seq]
            if sub_match > 0: buff.append(node.data[sub_match:])
            node = node.child
            while node:
                for x in node.traverse(self.leaf):
                    yield buff + x
                node = node.bros

longest_match() で接頭辞 seq の最長一致を求めます。seq が全てマッチングしたら、traverse() で seq で始まるデータをすべて求めます。sub_match が 0 より大きい場合は、node.data の途中でマッチングが終了しているので、残りのデータ node.data[sub_match:] をバッファ buff に追加しておきます。

• プログラムリスト２

●実行例

それでは、簡単な実行例として suffix tree を作ってみましょう。suffix tree は suffix trie の改良したもので、サフィックスを順番にパトリシアに追加していくだけで作成できます。次のリストを見てください。

# 簡単なテスト
if __name__ == '__main__':
    # suffix tree
    def make_suffix_tree(seq):
        a = Patricia()
        for x in range(len(seq)):
            a.insert(seq[x:])
        return a

    s = make_suffix_tree('abcabbca')
    for x in s.traverse():
        print(x)
    for x in ['a', 'bc']:
        print(x)
        for y in s.common_prefix(x):
            print(y)
    print(s.delete('a'))
    print(s.delete('ca'))
    print(s.delete('bca'))
    for x in s.traverse():
        print(x)

とても簡単な方法ですが、データが多くなると時間がかかるのが欠点です。データ数を N とすると、実行時間は N² に比例します。とても遅いので実用的ではありません。ご注意くださいませ。

それでは実行例を示します。

$ python3 patricia.py
['ca']
['ca', 'bbca']
['b', 'bca']
['b', 'ca']
['b', 'ca', 'bbca']
['a']
['a', 'b', 'bca']
['a', 'b', 'cabbca']
a
['a']
['a', 'b', 'bca']
['a', 'b', 'cabbca']
bc
['bc', 'a']
['bc', 'a', 'bbca']
True
True
True
['ca', 'bbca']
['b', 'bca']
['b', 'ca', 'bbca']
['a', 'b', 'bca']
['a', 'b', 'cabbca']

正常に動作していますね。suffix trie を構成する場合、データ数を N とすると N² に比例するメモリが必要になりますが、suffix tree は N に比例するメモリで構成することができます。また、データ数 N に比例する時間で suffix tree を構築する方法 (Ukkonen のアルゴリズムなど) もあります。suffix tree は suffix trie よりも省メモリなので、いろいろなデータ処理の高速化に利用することができます。最近は suffix tree よりも省メモリのデータ構造である suffix array も注目されています。

●プログラムリスト１

#
# trie.py : トライ
#
#           Copyright (C) 2007-2022 Makoto Hiroi
#
class Trie:
    class Node:
        def __init__(self, x, bros = None, child = None):
            self.data = x
            self.bros = bros
            self.child = child

        # 子を求める
        def get_child(self, x):
            child = self.child
            while child:
                if child.data == x: break
                child = child.bros
            return child

        # 子を挿入する
        def set_child(self, x):
            child = Trie.Node(x, self.child)
            self.child = child
            return child

        # 子を削除する
        def del_child(self, x):
            child = self.child
            if child.data == x:
                self.child = child.bros
                return True
            else:
                while child.bros:
                    if child.bros.data == x:
                        child.bros = child.bros.bros
                        return True
                    child = child.bros
            return False

        # 節を巡回する (ジェネレータ)
        def traverse(self, leaf):
            if self.data == leaf:
                yield []
            else:
                child = self.child
                while child:
                    for x in child.traverse(leaf):
                        yield [self.data] + x
                    child = child.bros

    def __init__(self, x = None):
        self.root = Trie.Node(None)  # header
        self.leaf = x

    # 探索
    def search(self, seq):
        node = self.root
        for x in seq:
            node = node.get_child(x)
            if not node: return False
        # check leaf
        return node.get_child(self.leaf) is not None

    # 挿入
    def insert(self, seq):
        node = self.root
        for x in seq:
            child = node.get_child(x)
            if not child:
                child = node.set_child(x)
            node = child
        # check leaf
        if not node.get_child(self.leaf):
            node.set_child(self.leaf)

    # 削除
    def delete(self, seq):
        node = self.root
        for x in seq:
            node = node.get_child(x)
            if not node: return False
        # delete leaf
        return node.del_child(self.leaf)

    # 巡回 (高階関数版)
    def traverse_h(self, func):
        def traverse_node(node, buff):
            if node.data == self.leaf:
                func(buff)
            else:
                child = node.child
                while child:
                    traverse_node(child, buff + [node.data])
                    child = child.bros
        #
        node = self.root.child
        while node:
            traverse_node(node, [])
            node = node.bros

    # 巡回 (ジェネレータ版)
    def traverse(self):
        node = self.root.child
        while node:
            for x in node.traverse(self.leaf):
                yield x
            node = node.bros

    # 共通接頭辞を持つデータを求める
    def common_prefix(self, seq):
        node = self.root
        buff = []
        for x in seq:
            buff.append(x)
            node = node.get_child(x)
            if not node: return
        node = node.child
        while node:
            for x in node.traverse(self.leaf):
                yield buff + x
            node = node.bros

# 簡単なテスト
if __name__ == '__main__':
    # suffix trie
    def make_suffix_trie(seq):
        a = Trie()
        for x in range(len(seq)):
            a.insert(seq[x:])
        return a

    s = make_suffix_trie('abcabbca')
    for x in s.traverse():
        print(x)
    for x in ['a', 'bc']:
        print(x)
        for y in s.common_prefix(x):
            print(y)

●プログラムリスト２

#
# patricia.py : パトリシア (patricia tree)
#
#               Copyright (C) 2007-2022 Makoto Hiroi
#
class Patricia:
    class Node:
        def __init__(self, x, bros = None, child = None):
            self.data = x
            self.bros = bros
            self.child = child

        # 子を求める
        def get_child(self, x):
            child = self.child
            while child:
                if child.data[0] == x: break
                child = child.bros
            return child

        # 子を挿入する
        def set_child(self, x):
            child = Patricia.Node(x, self.child)
            self.child = child
            return child

        # 子を削除する
        def del_child(self, x):
            child = self.child
            if child.data[0] == x:
                self.child = child.bros
                return True
            else:
                while child.bros:
                    if child.bros.data[0] == x:
                        child.bros = child.bros.bros
                        return True
                    child = child.bros
            return False

        # 節を巡回する
        def traverse(self, leaf):
            if self.data[0] == leaf:
                yield []
            else:
                child = self.child
                while child:
                    for x in child.traverse(leaf):
                        yield [self.data] + x
                    child = child.bros

    def __init__(self, x = None):
        self.root = Patricia.Node(None)  # header
        self.leaf = x
        self.leaf_data = [x]

    #
    # 最長一致を求める
    # 返り値 (node, match, sub_match)
    # sub_match = 0 : node のデータと全て一致
    #
    def longest_match(self, seq):
        node = self.root
        k = len(seq)
        i = 0
        while i < k:
            child = node.get_child(seq[i])
            if not child: break
            j = 1
            k1 = len(child.data)
            while j < k1:
                if i + j == k or seq[i + j] != child.data[j]:
                    return child, i + j, j
                j += 1
            i += j
            node = child
        return node, i, 0

    # 探索
    def search(self, seq):
        node, match, sub_match = self.longest_match(seq)
        if len(seq) == match and sub_match == 0:
            # 葉をチェックする
            return node.get_child(self.leaf)
        return False

    # 挿入
    def insert(self, seq):
        node, match, sub_match = self.longest_match(seq)
        if sub_match > 0:
            # node を node - node1 に分割する
            node1 = Patricia.Node(node.data[sub_match:], None, node.child)
            node.data = node.data[:sub_match]
            node.child = node1
            if match < len(seq):
                # node に残りのデータを追加する
                new_node = node.set_child(seq[match:])
                new_node.set_child(self.leaf_data)
            else:
                # 葉を追加するだけ
                node.set_child(self.leaf_data)
        else:
            # node にデータを追加
            if match == len(seq):
                # 葉を追加するだけ
                if not node.get_child(self.leaf):
                    node.set_child(self.leaf_data)
            else:
                # node に残りのデータを追加する
                new_node = node.set_child(seq[match:])
                new_node.set_child(self.leaf_data)

    # 削除
    def delete(self, seq):
        node, match, sub_match = self.longest_match(seq)
        if match == len(seq) and sub_match == 0:
            # delete leaf
            return node.del_child(self.leaf)
        return False

    # 巡回
    def traverse(self):
        node = self.root.child
        while node:
            for x in node.traverse(self.leaf):
                yield x
            node = node.bros

    # 共通接頭辞を持つデータを求める
    def common_prefix(self, seq):
        node, match, sub_match = self.longest_match(seq)
        if len(seq) == match:
            buff = [seq]
            if sub_match > 0: buff.append(node.data[sub_match:])
            node = node.child
            while node:
                for x in node.traverse(self.leaf):
                    yield buff + x
                node = node.bros

# 簡単なテスト
if __name__ == '__main__':
    # suffix tree
    def make_suffix_tree(seq):
        a = Patricia()
        for x in range(len(seq)):
            a.insert(seq[x:])
        return a

    s = make_suffix_tree('abcabbca')
    for x in s.traverse():
        print(x)
    for x in ['a', 'bc']:
        print(x)
        for y in s.common_prefix(x):
            print(y)
    print(s.delete('a'))
    print(s.delete('ca'))
    print(s.delete('bca'))
    for x in s.traverse():
        print(x)