手軽にTF/IDFを計算するモジュール - download_takeshi’s diary
情報検索の分野でよく使われるアルゴリズムで「TF/IDF」というものがあります。 ドキュメントの中から「特徴語」を抽出する、といったような用途でよく使われています。 TF/IDFアルゴリズムのくわしい解説はこことかここを見てください。 今回はこのTF/IDFの計算を「簡単」に実現するためのperlモジュールをCPANに上げましたので、ご紹介します。なまえはLingua::JA::TFIDFといいます。 Lingua::JA::TFIDF - TF/IDF calculator based on MeCab. http://search.cpan.org/~miki/Lingua-JA-TFIDF TF/IDF実装の困りどころ TF/IDFの実装を試みた方であればわかると思うのですが、実際にやろうとすると、TF（Term Frequency）の計算はなんら難しくありませんが、IDF（Inve
Integer::Elias - Elias gamma/delta coder - naoyaのはてなダイアリー
Perl でγ符号、δ符号で整数を符号化するためのモジュールを作りました。(ω符号はまだサポートしていませんが) Elias 整数符号のモジュールなので Integer::Elias という名前にしています。 http://github.com/naoya/perl-integer-elias/tree/master γ符号、δ符号は整数の可変長符号です。バイト単位での可変長符号は ASN.1 BER (id:naoya:20080906:1220685978 参照) がありますが、γ符号、δ符号はビット単位での可変長符号で、より短いビット数で小さな整数を符号化することができます。 例えば 6 という数字があったとします。 6 の二進数での表現は 110 で 3 ビットです。110 の先頭ビットを除いたビット 10 で 2ビットあります。このビット数 2 を α符号 (Unary code
Algorithm::MTF / BWT → MTF → Range Coder によるデータ圧縮 - naoyaのはてなダイアリー
先日言及した Burrows Wheeler Transform (id:naoya:20081016:1224173077) による変換後のテキストは圧縮に使えたり、全文索引に利用できたりと応用範囲は広いです。 BWT により変換したテキストを圧縮するには、そのまま圧縮するのではなく先頭移動法 (Move-To-Front http://ja.wikipedia.org/wiki/Move_To_Front) を適用することでより情報に偏りを持たせてから圧縮するのがセオリーです。 今日は先頭移動法の Perl 実装を作ってみました。Algoritm::MTF です。 http://github.com/naoya/perl-algorithm-mtf/tree/master に置いています。 use Algorithm::MTF; my $encoder = Algorithm::MTF
Burrows Wheeler Transform と Suffix Array - naoyaのはてなダイアリー
,. -‐'''''""¨¨¨ヽ (.＿＿_,,,... -ｧァﾌ| あ…ありのまま 今日 起こった事を話すぜ！ |i i| }! }} /／| |l､{ j} /,,ｨ//｜ 『BWT について調べていたら Suffix Array のライブラリができていた』 i|:!ヾ､_ﾉ／ u {:}//ﾍ |ﾘ u' } ,ﾉ _,!V,ﾊ | ／´fト､_{ﾙ{,ィ'ｅﾗ , ﾀ人 な… 何を言ってるのか わからねーと思うが /' ヾ|宀| {´,)⌒`/ |<ヽﾄiゝ おれも何をされたのかわからなかった… ,ﾞ ／ )ヽ iLﾚ u' | | ヾｌﾄﾊ〉 |／_／ ﾊ !ニ⊇ '／:} V:::::ヽ 頭がどうにかなりそうだった… /／ 二二二7'T'' ／u' __ /:::::::/｀ヽ /'
List::FrontCode - naoyaのはてなダイアリー
先日 Array::Gap という Variable Byte Codes による整列済み整数の圧縮の実装を作りました。(id:naoya:20080906:1220685978) 今日は Front Coding を使った同じような圧縮リストクラス、List::FrontCode を作ってみました。Front Coding は辞書式順に整列済みの文字列リストなどを圧縮する手法です。WEB+DB PRESS Vol.42 のアルゴリズム&データ構造の記事で PFI の岡野原さんによる解説があったので、それを参考に実装しました。 Front Coding Front Coding は http://www.hoge.jp http://www.hoge.jp/a.htm http://www.hoge.jp/index.htm http://www.fuga.com/ http://www.
[を] 転置インデックスによる検索システムを作ってみよう！
転置インデックスによる検索システムを作ってみよう！ 2007-11-26-5 [Algorithm][Programming] 転置インデックス[2007-06-17-6]による検索システムの実装は パフォーマンスを無視すれば意外と簡単です。 それを示すために Perl で簡単な検索システムを作ってみました。 検索方式は転置インデックス(Inverted Index)、 ランキングには TF-IDF[2005-10-12-1] を用いました。 検索対象ファイルは一行一記事で以下のフォーマットとします。 [記事ID][SPC][記事内容]\n 記事IDは数字、記事内容は UTF-8 の文字で構成されるものとします。 以下のようなサンプル test.txt を用意しました。 1 これはペンです 2 最近はどうですか？ 3 ペンギン大好き 4 こんにちは。いかがおすごしですか？ 5 ここ最近疲れ
![[を] 転置インデックスによる検索システムを作ってみよう！](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}
Dynamic Programming による類似文字列マッチの実装例
Dynamic Programming による類似文字列マッチの実装例 2007-01-22-4 [Programming][Algorithm] 「Modern Information Retrieval」(8.6.1 p.216) での Dynamic Programming (DP) の解説のところのアルゴリズムを 素直に Perl で実装したみた。 さらにマッチ箇所取り出しロジックも実装してみた。 # DP はいわゆる「類似文字列検索（あいまい検索）」に使うと 便利なalgorithm。 実は、大学院でも前の会社でも、PerlやらC++やらで実装して使ってた。 単純ながら使い勝手もよく、まさに現場向きかと。 grep 式に頭から見ていくので計算量的にはイマイチなのだが、 転置インデックス検索などで範囲を絞ってから適用すれば実用上問題ない。 ■定義みたいなの Q1. 二つの文字列 "
イケてないプログラム（使えない成果物）に見られる３つの共通点
クイックソートの話で書いたとおり、相変わらず Excel - VBA と格闘する日々が続いております・・・orz 「大企業にありがちな問題。委託開発の甘い罠・・・」でも書いたとおり、今まで外注して作ったソフトウェアってほぼ 100% の確率でイケていないものが完成してます。年末に納品されたソフトウェアのできも酷いの何のって・・・ さて、いままで見てきたイケてないプログラムのダメソースに共通して言えることが３点ありまして、 DRY ( Don’t Repeat Yourself ) でない。同じもしくは似たソースのコピペが至る所に散在する。 ロジックに無駄が多すぎ。行き当たりばったりで作った感、満点。 アルゴリズム知らなさすぎ。馬鹿ループ処理で時間かかりすぎ。 のいずれか、もしくは全部が当てはまります。大抵は全部ですね。こういったソースが納品されると、センス無いなぁ〜と思っちゃうわけ。こうい
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
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
