タグ LOUDS
人気順 10 users 50 users 100 users 500 users 1000 users完備辞書(簡潔ビットベクトル)の解説 - アスペ日記
以前、「簡潔データ構造 LOUDS の解説」というシリーズの記事を書いたことがあります。LOUDS というのは木構造やtrieを簡潔に表すことができるデータ構造なのですが、この中で「簡潔ビットベクトル」というものについてはブラックボックスとして扱っていました。また、中学生にもわかるウェーブレット行列を書いたときも、その中で出てきた「完備辞書」の実装には触れませんでした。この「簡潔ビットベクトル」「... 続きを読む
「木構造と自然数の重複あり集合は等価だよね」というはなし - EchizenBlog-Zwei
計算機科学「木構造と自然数の重複あり集合は等価だよね」というはなしをする。簡潔データ構造な人向けに言うとLOUDSの話。とはいえこの記事は特に簡潔データ構造の知識を要求しない。データ構造とか情報量とかに興味がある人全般を対象としている。※簡潔勢にとっては既知な話のはずなのであえて読む必要はないです。 まず結論から述べる。以下のような幅優先で番号を振った木構造を考える。 親 → 子 ==== (1)... 続きを読む
LOUDSの基本事項 - Topics Related to Computers and NLP
LOUDSとは木を表現する簡潔データ構造の一つである。 以下のリンクの練習問題を全て解いたらLOUDSについての理解が進んだので、それについて簡単にメモしておく。 情報系修士にもわかるLOUDS ※ノード番号とは、木を根から(左の子優先の)BFSで辿った順番であり、indexとはビット列を配列に例えた際の添字番号の事である。 ※また、rankとselectは簡潔データ構造の基本操作であるが、それら... 続きを読む
LOUDS を普通のプログラマにもわかるように解説してみた - アスペ日記
以前「日本語入力を支える技術」(通称「IME本」「徳永本」)を読んで「ダブル配列」「LOUDS」の解説のわかりやすさに感動したので、友達(情報系大学院の修士課程での同級生)との勉強会ネタに使ってみたところ、いろいろひっかかるところがあって難しいようだった。それで、より直感的な説明をしようと情報系修士にもわかるダブル配列 を書いた。幸い、その時はすぐにわかってもらえた。その後、LOUDS も同じよう... 続きを読む
情報系修士にもわかるLOUDS - アスペ日記
「情報系修士にもわかるダブル配列」が好評だったので、二匹目のどじょうを狙って、「日本語入力を支える技術」でダブル配列と並べて解説されていた LOUDS についても書いてみる。注意点。LOUDS は本質的に難しい。流し読みではまずわからない。ダブル配列の「ずらしてガッチャンコ」のようなわかりやすいキーワードはない。ここでは簡潔ビットベクターはブラックボックスとして扱い、中には踏み込まない。trie ... 続きを読む
情報系修士にもわかるダブル配列 - アスペ日記
最近話題の「日本語入力を支える技術」を途中まで読んだ。3章がものすごく気合いが入っている。trie(トライ)というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、この本の説明を読むことで理解ができた。ありがたい。 感銘を受けたので、この本を教材に友... 続きを読む
erika-trie(実用版)とキーワード抽出ツールerika_extractを作ったよ - EchizenBlog-Zwei
erika先日まで勉強のためにerika-trieというLOUDSを用いたトライ木を作っていた。ある程度考えがまとまったので実用版を作り始めた。erika-trie(実用版)はmarisa-trieやtx/ux/rx等と同等の操作を備えたトライ木。またerika-trieを用いてテキストからキーワードを高速に抽出するためのツールerika_extractが付属している。DSIRNLP#1で発表しま... 続きを読む