MARISA-TrieをコマンドラインとPythonから使う

概要 Matching Algorithm with Recursively Implemented StorAge (MARISA) という Trie に対する高い空間効率とそれなりの時間効率を実現するデータ構造があります。 動的な更新には対応していませんが 辞書引き（Lookup） : 入力文字列が登録されているかどうかを確認 逆引き（Reverse Lookup） : 入力された ID から登録文字列を復元 Common Prefix Search : 入力文字列の前半部分に一致する登録文字列を検索 Predictive Search : 入力文字列で始まる登録文字列を検索 といった操作が可能です。 今回は marisa-trie 0.2.4 をベースに コマンドラインプログラム Python バインディング から MARISA を触ってみます。  Install MARISA 環境は Amazon Linux とします。 まずはC++のプログラムビルドに必要なツール群をインストールします。 次に C++ プログラムのよくある手順でインストールします。 最後に Python バインディングをインストールします。 marisa-trie には SWIG ベースのバインディングもありますが、今回は pip ベースでインストールできるサードパーティーの

Redisでオートコンプリート(4)Trie

Redisを使ったいろいろな autocomplete のアルゴリズムをメモ。 前方一致 zrange 範囲指定 @antirez trie inverted index trie(トライ木) 3つ目の @antirez アルゴリズムでは、登録後 bar に対して b, ba, bar というように各部分文字列だけをキーとして保存した。 これを拡張して、 b の次は a, ba の次は r というように接頭する文字列とその次に来る文字の対応関係を木構造で持つと、トライ木(trie)というデータ構造になる。 登録語が inn の場合 root -> i i -> n in -> n inn -> + # 終端文字 というようになる。 検索の場合も同じようにルートから辿り、検索文字列を接頭語としてもつノードより下のノードを、終端文字にたどり着くまで辿る。 キーの追加 wikipedia の例を題材にする。 データ型は再び Sorted Set を利用。 候補となるキー(下の例では