Pythonプレフィックスツリー

私は最近、プレフィックスツリー（ WikipediaまたはHabrを参照）を実装するPythonライブラリdatrieを完成させました。急いで共有します。



要するに、datrie.Trieは、特定の条件下（キー-文字列）でより少ないメモリを消費し、単一の要素を取得する速度に匹敵し、追加の操作をサポートする（特定の文字列のすべてのプレフィックスを取得し、特定の行で始まる行など）は、辞書操作と同程度の速度で機能します。



Python 2.6-3.3で動作し、ユニコード、LGPLライセンスをサポートします。







datrieは、 libdatrieライブラリのCythonラッパーです。 Libdatrieは、ノード間の遷移のステートマシンが特別な2つの配列に格納されるプレフィックスツリーのバリアントを実装し、サフィックス圧縮が実装されます（分岐しないブランチは、「テール」の別の配列に格納されます）。 これは、トライの「最先端」バージョンではありません（HAT-トライなどはより高速である必要があります）が、オプションは非常に高速/効率的で、既成の実装が優れています（そして、実装は実際にアルゴリズムを殺すことができます）。



Pythonのトライ型構造の既存のオプションは私には向いていませんでした。 純粋にpythonicの実装は必然的に多くのメモリを消費し、すぐに一掃されます。 Pythonのトライ型構造の他の実装：

• biopythonのtrie.c。 ユニコードをサポートしていません（それでも構いません）、3.xで動作しません（3.xで動作させるには、ライブラリが「裸の」C拡張として実装されているため、ラッパーを適切に書き換える必要があります）。
• buriyの github.com/buriy/python-chartrieは非常に高速で（__getitem__は最終的にdatrieよりも高速です）、大量のメモリを必要とします（これを修正するには、おそらくデータ構造、つまりライブラリのベースを変更する必要があります）。機能的で、Unicodeをサポートしていません（ただし、これは問題ありません）。
• www.dalkescientific.com/Python/PyJudy.html-古い、複雑な、動作するかどうかは不明です（2.3と2.4をサポートするように書かれています）

他にも何かあるかもしれませんが、いずれにせよ、「うまく機能し、すべての人に効果がある！」オプションが見つからなかったので、Cを覚えて、CythonとPythonで通常の欠如を利用したいという欲求を隠したと思いますPythonのトライ実装。



インストール（通常、拡張機能をインストールする場合のように、コンパイラが必要です）：



pip install datrie







作成：

 import string import datrie trie = datrie.Trie(string.ascii_lowercase)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

作成するとき、このトライで使用できるキーをすぐに言う必要があります（明示的にアルファベットまたは範囲を示します）。 これはlibdatrieの制限です。これにより、ステートマシンを効果的に保存し、Unicodeをサポートできます。まず、有効なUnicode文字の範囲が指定され、次にUnicodeキーがよりコンパクトな内部表現に変換されます。



実際にはcp1251のようなシングルバイトエンコーディングで管理し、ほぼ同じ機能と効率を実現することは可能だと思われますが、文字範囲のアプローチもうまく機能します。それがlibdatrieで行われた方法です。 したがって、「Unicodeをサポートしていません-これで構いません」と書きます。トライの場合、シングルバイトエンコーディングが便利なオプションです。



次に、トライを使用すると、辞書のように作業できます。

 >>> trie[u'foo'] = 5 >>> trie[u'foobar'] = 10 >>> trie[u'bar'] = 'bar value' >>> trie.setdefault(u'foobar', 15) 10 >>> u'foo' in trie True >>> trie[u'foo'] 5
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

キーはユニコードである必要があります:) Python 3.xでは、これは非常に自然です。2.xでは、例に文字uを入れる必要があります、ごめんなさい。 値は任意のPythonオブジェクトにすることができますが、これはトライC実装では一般的ではありません（通常、値として整数があります）。 実際、値の「内部」は実際には整数ですが、datrie.Trieはそれらを「実際の」値の配列のインデックスとして使用します。 この機能を必要としない人（たとえば、値がまったく面白くない）のために、datrieにはdatrie.BaseTrieがあります。これはわずかに高速で、数値のみを保存できます。



速度について少し。 すべての測定はトライで行われました。10万のユニークなロシア語と英語の単語（50/50）とint値「1」を使用して、他の測定（100万URL）をここで確認するか、（さらに良い）独自のデータで実行できます。 速度の測定は、数量の順序について一般的な考えを持ち、ライブラリ内の回帰を追跡するためにのみ行ったので、それに応じて測定しました。 すべてのソースコードとデータはリポジトリにあります。 さらに、さまざまな操作の漸近的な複雑さについてはどこにも書きません。 彼女を探検しませんでした。 理論的には、Wikipediaのトライ（たとえば、要素の取得または接頭辞O（m）、mはキーの長さ）による検索のようにすべきですが、実装の詳細（libdatrieとラッパーの両方）はすべてを変更できます。 誰かが適切なグラフを作成したら、もちろん感謝します。



要素の受信、チェックイン、要素の更新の操作は、標準の辞書より平均で2​​〜3倍遅くなります（つまり、ブナでは、前述のトライでは1秒あたり100〜300万回の操作です）。 例外は、新しい値をトライに挿入することです。これは非常に遅く動作します（ロシア語と英語の単語を使用した同じトライでは、毎秒約5万回の操作）。 同時に、そのようなデータを試してみると、RAMのスペースがはるかに少なくなります：3から5メガバイト（インタープリターに依存）vs通常の辞書で20メガバイト+ （メモリを不器用に測定し、特定の数値を保証できません） 。



つまり datrie.Trieは、dictの代替として使用できます。非常に長くない行（単語やURLなど）が多数ある場合、データは主に読み取り専用モード（または「更新専用」）で使用され、RAMメモリを節約します。アクセス速度が2〜3倍低下します。



この擬似読み取り専用があまり恥ずかしくないように、トライをファイルに保存してファイルからロードできます：

 >>> trie.save('my.trie') >>> trie2 = datrie.Trie.load('my.trie')
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

トライのもう1つの特徴は、ディクテーション（およびその他のハッシュテーブル）で、プレフィクスツリーに追加のインデックスを作成するために完全な列挙または大量のメモリを必要とする一部の操作がほぼ同じ速度で動作することです（さらに高速です） 、値を取得するだけでなく。



キーがこの接頭辞で始まる要素がtrieにあるかどうかを確認できます（これは単純なチェックよりも高速です）。

 >>> trie.has_keys_with_prefix(u'fo') True
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このトライにあるこの行のすべてのプレフィックスを見つけることができます（テストによれば、これはより遅いです-500-600千操作/秒）：

 >>> trie.prefixes(u'foobarbaz') [u'foo', u'foobar'] >>> trie.prefix_items(u'foobarbaz') [(u'foo', 5), (u'foobar', 10)]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この行で始まるキーを持つすべての要素を見つけることができます。

 >>> trie.keys(u'fo') [u'foo', u'foobar'] >>> trie.items(u'fo') [(u'foo', 5), (u'foobar', 10)] >>> trie.values(u'foob') [10]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

最後の例では、ほとんどの時間は検索ではなく結果の構築に費やされていますが、これは最適化できます。 これで、速度は約15万から30万値/秒になりました（たとえば、長さ7のプレフィックスと平均3つの値を使用すると、これは7万操作/秒になります）。



Datrie.Trieにはまださまざまな方法があり、それらに関するヘルプがあり、速度測定の追加の結果はリポジトリのREADMEで見ることができます。



pypyでは、すべてがDebianで起動しました（cpythonの場合よりも10倍遅い）。 pypyの下のケシでは、起動しませんでした（通常のpythonでは、ケシ、Linux、およびWindowsで動作するはずです）。 C API-pypyの拡張は常に遅い cpyext松葉杖を介して動作し、cythonはC拡張APIを生成します。 ctypesでラッパーを書くことはできますが、通常のpythonでは遅くなります（pypyで速くなるという事実ではありません）+ ctypes拡張機能の配布は不便です。 pypyの人たちはcffiを見て、（cpythonとpypyの両方で）高速になると約束しています。 さらに、おそらくCythonはC拡張APIではなくCffi拡張を生成することをいつか学ぶでしょう。 それから、おそらく、幸せが来るでしょう）その間、私はpypyで何をすべきかわかりません。 たぶん私はしません。 どういうわけか、すべてがLinuxで動作し、問題ありません。



実装中に、Pythonで停止したutf_32_leコーデックに遭遇しました。 パッチにバグがあります（ bugs.python.org/issue15027 ）が、パッチはまだコミットされていません。 当初、datrieのすべての操作は10倍遅くなりましたが、1か所で標準のpython utf_32_leで文字列をエンコードせずに実行でき、すべてがうまく機能しました。 このコーデックは、いくつかの「ホットな」場所で使用されるため、加速されると、ダトリ内の一部の操作で最大2倍の速度を得ることができると思います。



ツリーの反復は現在、最も効率的ではなく、libdatrieインターフェース機能と接続されています。 しかし、libdatrieの作者は優秀な人物であり、すべてを修正しようとしているので、見通しは悪くありません。



いつものように、パッチ、バグレポート、アイデア、ベンチマーク、プルリクエストなどは大歓迎です！



github / bitbucket 、 どちらか便利な方 。