Blog Archives

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

Tagged with: ,
Posted in algorithm, nlp, Uncategorized

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

Tagged with: , ,
Posted in algorithm, database
Archives