アルゴリズム - ハクビシンにもわかる全文検索 - Qiita

2015/07/21 242 users ハクビシン Qiita アルゴリズム FM-Index リニア

高速な全文検索アルゴリズムであるFM-indexについて解説する。理解しがたい点や間違っている点があれば是非コメントで指摘してほしい。 概要 FM-indexはリニアな文字列に対して検索をするアルゴリズムで、主に簡潔データ構造とBWT(およびLF mapping)という二つのアイデアから成り立っている。BWTはBurrows-Wheeler変換のことで、文字列を特殊な並び順に変換するという可逆関数... 続きを読む

完備辞書（簡潔ビットベクトル）の解説 - アスペ日記

2014/02/01 66 users 簡潔ビットベクトル trie LOUDS ウェーブレット行列

以前、「簡潔データ構造 LOUDS の解説」というシリーズの記事を書いたことがあります。LOUDS というのは木構造やtrieを簡潔に表すことができるデータ構造なのですが、この中で「簡潔ビットベクトル」というものについてはブラックボックスとして扱っていました。また、中学生にもわかるウェーブレット行列を書いたときも、その中で出てきた「完備辞書」の実装には触れませんでした。この「簡潔ビットベクトル」「... 続きを読む

「木構造と自然数の重複あり集合は等価だよね」というはなし - EchizenBlog-Zwei

2014/01/30 65 users LOUDS EchizenBlog-Zwei 既知 はなし

計算機科学「木構造と自然数の重複あり集合は等価だよね」というはなしをする。簡潔データ構造な人向けに言うとLOUDSの話。とはいえこの記事は特に簡潔データ構造の知識を要求しない。データ構造とか情報量とかに興味がある人全般を対象としている。※簡潔勢にとっては既知な話のはずなのであえて読む必要はないです。 まず結論から述べる。以下のような幅優先で番号を振った木構造を考える。 親 → 子 ==== (1)... 続きを読む

高速な文字列マッチング - 気ままなブログ

2013/07/26 77 users 文字列マッチング Papers grep ブログ NLP

2013-07-25 高速な文字列マッチング NLP 最近は、簡潔データ構造を中心に調べたりしていたけど、文字列マッチングを考えた場合、別のアプローチもあります。そう、grepのような逐次文字列検索ですね。以下の解説がおもしろいです。http://www.i.kyushu-u.ac.jp/~takeda/papers/IPSJMagazineCPM.pdfCSAとかFM-Indexに隠れてしまって... 続きを読む

LOUDSの基本事項 - Topics Related to Computers and NLP

2013/07/07 10 users LOUDS BFS RANK select index

LOUDSとは木を表現する簡潔データ構造の一つである。 以下のリンクの練習問題を全て解いたらLOUDSについての理解が進んだので、それについて簡単にメモしておく。 情報系修士にもわかるLOUDS ※ノード番号とは、木を根から（左の子優先の）BFSで辿った順番であり、indexとはビット列を配列に例えた際の添字番号の事である。 ※また、rankとselectは簡潔データ構造の基本操作であるが、それら... 続きを読む

"高速文字列解析の世界"を読んだ - 射撃しつつ前転

2013/01/08 67 users 前転 テキストマイニング 概観 高速文字列解析 章題

高速文字列解析の世界というタイトルからは、どんな中身なのかあまり伝わってこないので、どんなことが書いてある本なのか、中身をちょっと紹介してみる。　1章、2章は概観や準備であり、3章からが本番なのだが、Burrows Wheeler Transform、簡潔データ構造、ウェーブレットツリー、データ圧縮、全文検索、テキストマイニングのためのデータ構造、という章題になっている。　何に使うのかという目的ベ... 続きを読む

自然言語処理とか機械学習とかグラフとか簡潔データ構造とか全部入った良書｢日本語入力を支える技術｣がすごい - EchizenBlog-Zwei

2012/02/02 77 users 良書 テキストマイニング グラフ GoogleIME 機械学習

書籍@tkngさんの力作「日本語入力を支える技術」が2/8に発売される。既に秋葉原のヨドバシ有隣堂や池袋のジュンク堂本店では早売りされている様子。ってことで早速購入してきた。本書が扱うテーマはGoogleIMEのような「日本語入力」のシステム。これだけだとさして興味ないや、って人も多いかもしれない。ところがこの日本語入力というのは技術的には形態素解析に非常に近い。自然言語処理やテキストマイニングに... 続きを読む

文書解析のための簡潔データ構造 : Preferred Research

2011/12/02 43 users Preferred Research 要点 高松 進展 岡野原

岡野原です。 12/1〜12/2に高松で開催されたALSIP2011で文書解析のための簡潔データ構造の最近の進展について話をしてきました。 Succinct Data Structure for Analyzing Document Collection View more presentations from PFI Marketing ここの業界の進展は速く毎年様々な方法が出てきますが、要点だ... 続きを読む

私のブックマーク ： 簡潔データ構造

2011/09/18 68 users ブックマーク

田部井靖生（科学技術振興機構 ERATO湊離散構造処理系プロジェクト研究員) はじめに 近年、Web技術や計測技術の発展により言語やゲノムデータは大規模化しています。従来のデータ構造は大規模データを扱うにはサイズが大きくメモリに載らない、 しかし、圧縮するとランダムアクセスをすることができないという欠点があります。 簡潔データ構造とはデータを小さく保存かつ高速な操作が可能なデータ構造です。 近年、... 続きを読む