2012/6/21のPFI全体セミナー, 「文字列データ圧縮ことはじめ」の内容です。データ圧縮の話とそれに纏わる歴史と最近の話を紹介しています。
文字列データ圧縮ことはじめ | SlideShare
2012/6/21のPFI全体セミナー, 「文字列データ圧縮ことはじめ」の内容です。データ圧縮の話とそれに纏わる歴史と最近の話を紹介しています。
[NLP][機械学習] 言語モデル覚え書き - tsubosakaの日記
この文章について 最近言語モデル方面にも少し興味があるので自分の知識を整理する意味で書いてみた。NLPは専門ではないので、おかしなことを書いてある可能性がありますがその場合はご指摘ください。 本文章ではn-gramモデル、単語の出現確率がn-1個前の単語のみに依存するモデルを考える。 問題 who is * という文が与えられたときに*にくる文字の確率を求めることを考える。この場合だと*には例えばheが当てはまるかもしれないが, isが入ることはまずなさそうに思える。このことは文法的にも説明ができると思うが、文法のルールを作るのは大変だし、文法的に正しい単語の中でどれが出やすいかということはできない。 一方で機械学習を使った言語モデルの文脈では文法的知識を余り持たず、与えられたコーパスから自動的に出やすい単語/表現を学習する方針をとる。 最尤推定 一番簡単なモデルとしては最尤推定を使うもの
![[NLP][機械学習] 言語モデル覚え書き - tsubosakaの日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/fd5873fc29a8487ca585cedd187a3197a9282658/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F17680117127124028144%2F17680117127124030005%2F1557332435)
Rabin Karp アルゴリズムでコード重複の検出 blog.bulknews.net
Rabin Karp アルゴリズムでコード重複の検出 YAPC::NA で会った Fotango の Norman Nunley がつくってる Algorithm::RabinKarp モジュールが面白げです。 Rabin Karp 文字列探索アルゴリズム (wikipedia) を使って文字列のハッシュ（ダイジェスト）をチェックし、同一の値を示す部分を重複しているとみなしてレポートしてくれます。つまり、プロジェクト内のコードのコピーペーストを検出するツールとして使えるというわけ。 ためしに Plagger で試してみた結果は rabin.txt のようになりました。プラグインの register_hook や CustomFeed での Feed オブジェクトの生成など、イディオム的に使う部分が大半になってしまっていますが、いくつか実際コピペで再利用しているコードが検出できています。 c
演習３ 今井研 第一回(04/04/28) Compressed Suffix Trees Random-Decodable Compression
演習３ 今井研 第二回 第三回 Compressed Suffix Trees Compressed Suffix Arrays 04/04/28 04/05/12 岡野原 大輔 調べる題材 CST (Compressed Suffix Trees) CSA (Compressed Suffix Arrays) CSA [Grossi, Vitter 00] [Sadakane 03] [Grossi, Guputa, Vitter 03] FM-index [Ferragina, Manzini 00] 括弧木の表現及び操作 rank及びselectに関わる話 全体を並行に調べていく Suffix Trees、Suffix Arraysについて Suffix T[1…n]の時、Tの各部分列Ti = T[i…n]をTのSuffixと呼ぶ。 Suffix Trees Tの全ての
sary: a suffix array library and tools
What is sary? sary is a suffix array library and tools. It provides fast full-text search facilities for text files on the order of 10 to 100 MB using a data structure called a suffix array. It can also search specific fields in a text file by assigning index points to those fields. Table of Contents What's New Characteristics Brief Introduction to Suffix Array libsary Reference Manual Using the I
[を] Suffix Array の解説文書のリンク集
Suffix Array の解説文書のリンク集 2006-04-10-3 [Algorithm] Suffix Array について解説している日本語による文書のうち、 Webで閲覧できるもののリンク集。随時更新予定。 - 用語解説: Suffix Array (PDF) via http://ta2o.net/tools/sufary/ - Suffix Array の解説 in D論 (PDF) via http://ta2o.net/tools/sufary/ - 横着プログラミング 第9回: sary: Suffix Array のライブラリとツール http://0xcc.net/unimag/9/ - Suffix Arrayの簡単な説明 http://sary.sourceforge.net/docs/suffix-array.html - Suffix Trees and
![[を] Suffix Array の解説文書のリンク集](https://cdn-ak-scissors.b.st-hatena.com/image/square/af37977ee866988286b95e74fff98500a190545c/height=288;version=1;width=512/https%3A%2F%2Fchalow.net%2Fimages%2Ftcl-logo-25.png){kind=logo}
横着プログラミング 第9回: sary: Suffix Array のライブラリとツール
最終更新日: 2002-12-18 (公開日: 2002-12-18) Unix Magazine 誌に 2002年1月号から 2003年2月号にかけて連載し ていた記事の元の原稿です。 私にフローチャートだけを見せて、テーブルは見せないとしたら、 私はずっと煙に巻かれたままになるだろう。逆にテーブルが見せて もらえるなら、フローチャートはたいてい必要なくなる。 -- Frederick P. Brooks Jr. *1 プログラミングにおいてはデータ構造が重要であり、正しいデータ 構造を選択すればアルゴリズムは自明なものとなる、という主張が ある。Rob Pike*2 の "Notes on Programming in C" *3 によると、現実的なプログラムに必要なデータ構造は次の 4つであ るという。 配列 (array) 連結リスト (linked list) ハッシュテーブル
クライアント最前線 作って理解するAjax（第3回）
前回は，インクリメンタル検索を実現するAjaxアプリケーションのクライアント・サイドの実装を紹介しました。今回は，サーバーとして稼働するCGIプログラムを作成します。このCGIプログラムは，クライアントから送られてきたクエリーに基づいてテキストを検索し，その結果を返送します。Ajaxアプリケーションは通常のWebアプリケーションに比べて，サーバー・アクセスが増加しがちです。このためサーバーをいかに効率よく実装できるかが，サービスを快適に提供できるかどうかを左右します。サーバー負荷を下げる手法についても考えてみましょう。 テキスト検索にsaryを使用 みなさん，テキスト検索といえばどんな方法を思いつくでしょうか。単純なところではgrepコマンドの利用が考えられますし，データをMySQLやPostgreSQLなどのRDBMSで管理して，そのRDBMSの検索機能を利用する手もあります。また，N
お手軽PerlでSuffixArrayに挑戦
試しにPERLでSuffixArrayついでにソートの勉強 下記のページを参考にしている http://www.namazu.org/~satoru/unimag/9/ ここに記述されているコードは、実験のために書かれているので、 へんなところはご容赦を... インデックスを作ってみる Cで書かれたサンプルをperlでかいてみた。 PERLでもquicksortの関数はあるが、一応PERLでかいてみた。 バイナリー形式でインデックスファイルを書き出している。 テストのためのサンプルプログラムなので、書き出したあとよみだして表示している。 pushを使って配列を拡大しているが、これってスピード的にいいのだろうか？ pack,unpack関数はいろいろ使いでありそう！！ 1: #!/usr/bin/perl 2: 3: #2003/03/14 4: #UNIXマガジン2002 10月号 横着プ
Suffix Array
TopCoder SRM187、 DNAMultiMatcher は、 Stringが3つ(それぞれの長さは最大2500)与えられたとき、 3つ全てに含まれる最長のSubstringの長さを求めなさい。 という問題です。これに対して、 長さをBi...
Java で Suffix Array - odz buffer
なんか Java で Suffix Array なコードというリクエストがあったので簡単に。 とりあえず Suffix Array の構築だけ。効率とか一切無視で。 import java.io.IOException; import java.util.Arrays; import java.util.Comparator; import java.util.regex.Matcher; import java.util.regex.Pattern; public class SuffixArrayBuilder { public void build(String text, Integer[] sa) { Arrays.sort(sa, new SuffixComparator(text)); } private static class SuffixComparator imple
SuffixArray - みずぴー日記
30分プログラム、その580。id:Gemmaさんに借りたWEB+DB PRESS Vol.50に、suffix arrayの解説が載っていたのでやってみた。 解説を読んだときは「ちょう簡単じゃん。さくっと実装してやんよ」と思っていたけど、いざ始めたけど、けっこう大変だった。簡単とか言って、ごめんなさい。 そもそもararyとついてる時点で大変なことに気がつくべきだった。ボク、OCamlでarrayを使ったことなんてほとんどないじゃないか。 使い方 シグネチャはこんな感じ。 type t val make : string -> t val find : t -> string -> int list まず、suffix arrayを作る。 # let s = SuffixArray.make "abracadabra";; val s : SuffixArray.t = <abstr>
JavascriptでSuffixArray - やればできる子の日記
全文検索エンジンを試作してみたよ - やればできる子の日記とJavascriptを組み合わせてもうちょっとなにかできないかなあと思って、JavascriptでSuffixArrayを作ってみました。 上手い具合に組み合わせるアイデアが思いつけなかった(どうせ全文検索用のインデックスを保持しちゃうので、別途SuffixArrayを保持する意味がなさそう)ので、素のまま公開しちゃいます。 ちなみに、Javascriptも自信ないです。僕はJSでのべ2000行程度しか書いたことないはず。 /* Suffix Array構築のアルゴリズムは色々研究されています。 以下のコードはかなり最悪なアルゴリズムなので、実用の際は調査してください。*/ function genSA(text){ var sa = new Array(text.length) for(var i = 0; i < text.l
perlによる大規模データの取扱い
本ページでは，perlでどのようにして大規模なデータを保存するかついて 説明します．主にスタンドアロンで動くもの (クライアント<->サーバ型 でない，いわゆる組込み型) について紹介したいと思います． Menu Berkeley DB BerkeleyDB DB_File SDBM SDBM_File GDBM GDBM_File CDB CDB_File QDBM Depot Curia Villa TDB TDB_File SQLight DBD::SQLite SUFFIX ARRAY SUFARY SARY 複雑なデータ構造 Data::Dumper Storable MLDBM いろいろな比較 ファイルサイズ Benchmark Link サンプルデータについて Berkeley DB Berkeley DBは，組み込み向けデータベースです．通常データベースという とOracl
編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー
昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたものが編集距離です。 例えば 伊藤直哉と伊藤直也 … 編集距離 1 伊藤直と伊藤直也 … 編集距離 1 佐藤直哉と伊藤直也 … 編集距離 2 佐藤B作と伊藤直也 … 編集距離 3 という具合です。 編集距離はスペルミスを修正するプログラムや、近似文字列照合 (検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検索) などで利用されます。 編集距離算出は動的計画法 (Dynamic Programming, DP) で計算することができることが
最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリー
部分列 (Subsequence) は系列のいくつかの要素を取り出してできた系列のことです。二つの系列の共通の部分列を共通部分列 (Common Subsecuence)と言います。共通部分列のうち、もっとも長いものを最長共通部分列 (Longest Common Subsequence, LCS) と言います。 X = <A, B, C, B, D, A, B> Y = <B, D, C, A, B, A> という二つの系列から得られる LCS は <B, C, B, A> で、その長さは 4 です。長さ 2 の<B, D> の長さ 3 の <A, B, A> なども共通部分列ですが、最長ではないのでこれらは LCS ではありません。また、LCS は最長であれば位置はどこでも良いので、この場合 <B, D, A, B> も LCS です。 LCS は動的計画法 (Dynamic Prog
Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
KH Coder
************************************************************ THIS PROJECT IS MOVED. See http://khcoder.net/en for the latest & greatest. You can download this tool from the new home. See you there! ************************************************************
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Perl で自然言語処理
Suffix Arrayを用いたフレーズ抽出 - kuronekonacchan