PythonによるTRIE実装 ～ダブル配列（Tailあり）～

概要

　Python上でダブル配列を実装し、そのメモリ使用量、検索時間を測定します。
　性能評価をするにあたって、いろいろと検索してみたのですが、今一つ納得のいく実装が見当たらなかったので、自作することにしました。
　なお、本来なら、ダブル配列の作成過程の効率も考えるべきですが、今回はそこは重視しません。あくまでも、出来上がったダブル配列の性能を評価することを目的としています。（したがって、動的な追加についても対象外です。）
　また、ファイルでの運用も考慮していません。メモリ上で作成し、そこで性能測定を行います。

TRIE構造

　文字列データを管理する方法のひとつで、効果的な速度で検索を実現することができます。
　理論的にはシンプルな構造なのですが、実装方法によってはさほど効果が出ない場合もあります。

• トライ木 (Wikipedia)

　「ダブル配列」はそのTRIE構造の実装方法の一つで高速な検索が実現できます。

ダブル配列

　ダブル配列については、各所にわかりやすい説明が載っているのでそれを参照してください。

• 情報系修士にもわかるダブル配列
• ダブル配列の実装方法 (slideshare)
• ダブル配列の豆知識 (slideshare)
• 文字列アルゴリズムの学びかた
• 人生で何度目かのダブル配列TRIEを書いた (Qiita)
• ダブル配列法によるトライ検索の実現法 （青江順一教授による論文）

Pythonでの実装

　これまで、他のプログラミング言語（C、C++、Javaなど）で「ダブル配列」を実装したことはありましたが、Pythonでの実装は初めてです。Python特有の効率化手法があるかと思いますが、基本的なアルゴリズムに従って実装することにします。
　基本的なデータ構造（ListやArrayなど）は言語に備わっているものを使いますが、アルゴリズム実装はフルスクラッチで作成しました。

　1ノードにおけるリンクの全体像が見えないと、配列のどこに格納可能かを確認できないので、まず、簡易的な（速度を考えない）TRIE実装を行い、リンクの全体が見渡せるようにして、それをダブル配列に格納するようにします。

　今回のダブル配列の実装では、Tailを考慮したつくりになっています。
　すべての文字列をTRIE構造で表現することは可能です。そうすることでアルゴリズム的にはシンプルになります。しかし、終端に近い文字列では分岐がなく、ひとつながりのノードとリンクが出来上がってしまい、その結果として、メモリや時間のコストが大きくなります。そこで分岐がない終端文字列をTailとして管理することでこれを改善します。
　すなわち、性能評価においてより良い性能の実装という観点でTailありのダブル配列を実装しました。

• プログラムソース(Github)

性能評価

• 性能測定の方法

  • 完全一致検索を測定する 100回試行してその平均値を結果とする

• 実行環境

  • Windows 10 Pro
  • Intel(R) Core(TM)i7-75600U CPU @ 2.40GHz
  • RAM 16GB
  • Python 3.7.1

• 検索対象単語

  • wordnetから取得した英単語 87,379件

• 実行時間＆使用メモリ

  • 検索単語数
    • 50,000件
  • 結果：実行時間
    • 0.281秒
  • 結果：使用メモリ
    • 7.5MB

今後の改良

• 前方一致検索の追加
  • 今回は、文字列と一致するレコードを検索するだけですが、他への応用を考えた場合には前方一致検索が必要な局面が出てきます。
• 性能アップ
  • 「とりあえず作ってみた」レベルの実装なので、Python特有の効率化の余地があると思っています。さらなる性能アップを目指したいと思います。