Pythonで省メモリに大量の文字列を扱う工夫 - MNTSQ Techブログ
たくさんの文字列（や離散的な符号列）をメモリに載せないといけないんだけど、いろんな制約があって通常のList[str]では載らない…ということありませんか？（まぁあんまりなさそうですね） たまたまそういうことがあったので、その際に検討した内容をまとめておきます TL;DR メモリをもっと増やしましょう 富豪的に解決できるならいつでもそれが最高です しかし、世の中それでなんとかならんこともたくさんあります 用途があうのであれば専用のデータ構造を採用する 例えばもし共通のprefixやsuffixが存在し、順序に興味がなければtrie treeなどが使えます 例えば、弊社であれば、法人名をメモリに持ちたいなんてときもあります。そういうときに法人名の辞書をtrieで持ったりすることがあります 「株式会社」「一般財団法人」や「銀行」といった共通語がたくさんでてくるのでtrie treeでごりごり削
トライ木で高速な辞書を作ってみた！ – 株式会社ライトコード
トライ木で高速な辞書を作りたい！ トライ木（英: trie）というデータ構造を知ってますか？ トライ木はテキストを扱う際に良く用いられているデータ構造で、文字列を非常に高速に検索することができるため、辞書の実装などに利用されています。 本記事では、トライ木の特徴の紹介と構築方法の解説・実装を行っていきます。 最終的に単語とその読み方を入力としたトライ木を構築し、単語を入力することでその読み方を出力する辞書システムを作成します。 トライ木とは トライ木とは、上の図のようなデータ構造で、順序付き木の一つです。 この図は、例として「a」「ab」「abc」「ac」「bc」という5単語が入ったトライ木です。 ノードの左上の数字は、ノードidを表します。 id0のノードの <s> というのは先頭文字を表していて、検索の際はここからスタートします。 丸が二重になっているノードは、そのノードが単語の終端文
三分探索木 - Wikipedia
三分探索木（さんぶんたんさくぎ、英: ternary search tree）は、トライ木の各ノードを二分探索木として表現したデータ構造である。各ノードは文字列中の文字と以下の三つの子ノードを持つ。 その文字の代わりに、より小さな文字を指す左ノード その文字の代わりに、より大きな文字を指す右ノード その文字の次の文字を指す中央ノード 他のトライ木構造と同じく、三分探索木の各ノードは格納された文字列の接頭辞に対応している。中央ノードに格納された木は、そこに至るまでのノードを共通接頭辞として持つ。 c / | \ a u h | | | \ t t e u / / | / | s p e i s 上記の三分探索木は "as", "at", "cup", "cute", "he", "i", "us" が値として格納されている。三分探索木から値を取得するには次のような操作を行う。 頂点ノードから
)
トライ (データ構造) - Wikipedia
"A", "to", "tea", "ted", "ten", "i", "in", "inn" というキー群によるトライ木 トライ木（英: trie）やプレフィックス木（英: prefix tree）とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応している。 キーが文字列である連想配列の実装構造としても使われる。右図の例では、ノードを表す丸の中にキーが書かれ、連想される値がその下に書かれている。値が書かれていないノードはキー文字列の途中までにしか対応していない。各英単語
Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - tyler/trie: A super fast, efficiently stored Trie for Ruby. Uses libdatrie.
