bmf-tech.com - Golangでトライ木を実装する
概要トライ木のアルゴリズムと実装についてかく。 bmf-san/road-to-algorithm-master トライ木とはトライ木（プレフィックス木ともいう。英語はそれぞれ、trie、prefix tree）は文字列の集合を扱う木構造の一種。 各ノードは単一または複数の文字列あるいは数値を持ち（ノードは必ずしも値を持つ必要はない）、根ノードから葉に向かって探索して値をつなげていくことで単語を表現する。 ネットワークのレイヤーならIPアドレスの探索、アプリケーションレイヤーならhttpのルーティングに、機械学習とかの文脈であれば形態素解析といったところでトライ木の応用が見受けられる。 言葉で説明するよりもビジュアルのほうが頭に入りやすい。 Algorithm Visualizations - Trie (Prefix Tree) メモリ効率が悪いので、メモリ効率がボトルネックとなるような
GolangでTrie木を車輪の再発明した話 - KAYAC engineers' blog
こんにちは! Tech KAYAC Advent Calendar 2020 4日目を担当する荒賀(@ken39arg) です。 近況報告 毎年このアドベントカレンダーの場をかりて、趣味の長距離スポーツの結果を報告して承認欲求を満たしていたのですが、 昨年サブスリーを達成して今年はサブエガ1を目指していたフルマラソンの大会は中止となり、夏の趣味であるOWS2の大会も軒並み中止となってしまいました。 その代わりに今年は2018年に買って未クリアだったゼルダをプレイし、ハイラルの平和をなんとか今年中に取り戻せるように努力をしております。 Trie木が必要になった経緯 さて、アドベントカレンダーだからツリー → ツリーといえば我々の世界では木構造 → 木構造といえばトライ木ということではなく、 今年した仕事でTrie木を実装する機会があったので、その時の気づきを書いてみようかと思います。 今年ユ
Suffix Automatonの作り方と使い方 - uwicoder
この記事はCompetitive Programming Advent Calendar Div2013の13日目の記事です。 競プロにおいて、文字列関連の問題への解法は、ローリングハッシュだのManacherだのKMPだのZだのTrieだのSuffix Arrayだの、色々なアルゴリズム・データ構造を使います。今回はその中でSuffix Automatonを取り上げたいと思います。 Suffix AutomatonはSuffix AutomataとかDAWG(Directed Acyclic Word Graph)とかの名前で呼ばれることもあるデータ構造です。一言で言ってしまえば、"Suffix Treeのノードをまとめたもの", "文字列Tのすべての連続部分文字列を受理するオートマトン"ですが、色々便利な性質を持っています。ですが、Suffix Automatonそのものについてほとん
Darts clone のデータ構造 - やた＠はてな日記
トライをダブル配列で表現する Darts に対して，Darts clone は，基礎のデータ構造として Directed Acyclic Word Graph (DAWG) というグラフ構造を採用し，DAWG をダブル配列で表現するようになっています． Directed Acyclic Word Graph (DAWG) トライの共通部分木を併合することで得られるグラフ構造が DAWG です．トライからDAWG への変換では，登録するキーの末尾に共通性があるほど，多くのノードを取り除くことができます．これまでの実験により，日本語や英語の単語をたくさん登録する場合であれば，全体の 60 〜 70% 程度のノードを取り除けることが分かっています．特に有効なデータの例として，日本の郵便番号を DAWG に登録すると，そのサイズはトライの約 1/10 になります． DAWG はトライを圧縮したデー
Luceneで使われてるFSTを実装してみた（正規表現マッチ：VMアプローチへの招待） - Qiita
入力と出力のペアに対して，上のようなグラフを作るのが目標です．テーブルの出力のとこは数字が書いてありますが，文字列だと思ってとらえて下さい．map だと出力は1つに限られちゃいますが，ひとつの入力に対して出力が複数あってもいいです．たとえば入力 "feb" に対して，出力は "28" と "29" があります．（2月は28日と29日のときがありますね）． ノードの部分が状態で，そこから出ている矢印が状態遷移になります．矢印には a/b というラベルがついていますが，a の部分が入力とのマッチを意味し，b の部分がそのときの出力を意味します． 上の例で示すFSTで，"aug"を処理するには，"aug"を頭から読んで，入力"a"に対応するの(9)から(3)への矢印を選択します．そのとき，出力として"3"を記録しておきます．そのあと，"u"に対して(3)から(2)への矢印を選択し，"1"を先ほど
Denco 技術解説
今回は Golang 用の URL ルーターである Denco の技術解説をしていきます。 その前にひとつ、お知らせがあります。Denco はこのたび URL ルーターから URL ルーター兼 HTTP request multiplexer となりました。つまり、http.ServeMux の代わりとして使えるようになりました。 詳しくは README を参照してください。 基本戦略まず始めに、Denco のルーティングは静的パス（/user/alice みたいなの）とパラメーター付きパス（/user/:name みたいなの）で使用するアルゴリズムを変えています。 静的パスの場合は Go の map を使い、パラメーター付きパスの場合はパラメーターを扱えるように拡張したダブル配列を使います。これは、静的パスの場合、ダブル配列で処理するより Go の map を使ったほうが速いからです。
発表資料（Prefix/Patricia Trie の入れ子による辞書圧縮） - やた＠はてな日記
言語処理学会の発表で用いた資料に少しノートを加えたファイルです．もう少し詳しいものを用意できればよいのですが，優先順位は低めなので，あまり期待しないでください． PowerPoint http://sites.google.com/site/headdythehero/cabine/2011/0311/NLP2011-F2-6.pptx?attredirects=0&d=1 PDF ノートなし http://sites.google.com/site/headdythehero/cabine/2011/0311/NLP2011-F2-6.pdf?attredirects=0&d=1 PDF ノートあり http://sites.google.com/site/headdythehero/cabine/2011/0311/NLP2011-F2-6-notes.pdf?attredirects
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Lecture 25 | Programming Abstractions (Stanford) - YouTube