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
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
横着プログラミング 第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>
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
Zinnia: 機械学習ベースのポータブルな手書き文字認識エンジン
Zinnia: 機械学習ベースのポータブルなオンライン手書き文字認識エンジン [日本語][英語] Zinniaは機械学習アルゴリズム SVM を用いたポータブルで汎用的な オンライン手書き文字認識エンジンです。Zinniaは組み込みの容易さと汎用性を高めるために、 文字のレンダリング機能は持っていません。Zinniaは文字のストローク情報を座標の連続として受け取り、 確からしい順にスコア付きでN文字の認識結果を返すだけに機能を限定しています。 また、認識エンジンは完全に機械学習ベースであるために、文字のみならずユーザの任意のマウス・ペンストロークに対して任意の文字列をマッピングするような認識エンジンを小コスト作成することができます。 主な特徴 機械学習アルゴリズムSVMによる高い認識精度 ポータブルでコンパクトな設計 -- POSIX/Windows (C++ STLのみに依存) リエント
レーベンシュタイン距離 - Wikipedia
レーベンシュタイン距離（レーベンシュタインきょり、英: Levenshtein distance）は、二つの文字列がどの程度異なっているかを示す距離の一種である。編集距離（へんしゅうきょり、英: edit distance）とも呼ばれる。具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される[1]。名称は、1965年にこれを考案したロシアの学者ウラジーミル・レーベンシュタイン (露: Влади́мир Левенште́йн) にちなむ。 レーベンシュタイン距離は、同じ文字数の単語に対する置換編集に使われているハミング距離の一般化であると見なすことが可能である。レーベンシュタイン距離の更なる一般化として、例えば一回の操作で二文字を変換する等の方法が考えられる。 実際的な距離の求め方を例示すれば、「kitten」を「s
レーベンシュタイン距離を求める - 主にアルゴリズムの実験日誌
【内部主要記事】 【Abstruct的？】 【ToDoもしくは目次】 【参考文献】 【本文】 レーベンシュタイン距離を使って個体の適合度を求めます。 gaucheの配列に関する資料 http://www.shiro.dreamhost.com/scheme/gauche/man/gauche-refj_71.html レーベンシュタイン距離に関する資料 http://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2 http://www-06.ibm.com/jp/developerworks/java/041217/j_j-jazzy.html#figure1 ; 以下の2つのリストのレーベンシュ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Perl で自然言語処理
Suffix Arrayを用いたフレーズ抽出 - kuronekonacchan