Ruby で Double-Array を実装して Common-Prefix Search を試してみる - P A R A G R A P H S
lib/trie/double_array.rb at master from tily's ruby-gardening - GitHub Double-Array (ダブル配列) は トライ木を実装するためのアルゴリズムの 1 つで、他の実装よりも高速に TRIE から文字列を検索できるらしい。ChaSen や MeCab で、形態素解析を行うために必要な Common-Prefix Search (共通接頭辞探索) を行うために使われている。これを理解のために Ruby で実装してみた。 基本的な動作確認 ここに書いてある bird, bison, cat の 3 単語で構築した Double-Array の例。 コード： require 'trie/double_array' da = Trie::DoubleArray.new da.build(%w|bird bison cat
連想配列の進化 - DO++
キーに対して値を結びつける連想配列は多くのアプリケーションの肝であり、コンパクトかつ高速な処理が可能な連想配列を追い求め日夜研究が進められています。 特に非常に巨大な連想配列を高速に処理するというのが重要な課題となっています。例えば、音声認識・文字認識・機械翻訳などで使われている言語モデルでは、非常に大量のN個の単語列の情報（特に頻度）を格納することが重要になります。 この場合、キーが単語列であり、値が単語列のコーパス中での頻度に対応します。 例えばGoogle N-gram Corpusからは数十億種類ものN-gramのキーとその頻度などが取得できます。これらを主記憶上に格納し、それに関する情報（頻度や特徴情報）を操作することが必要になります。 そのほかにも大規模なデータを扱う問題の多くが巨大な連想配列を必要とします。 ここではこのような連想配列の中でも、キーの情報を格納することすら難し
軽量データクラスタリングツールbayon - mixi engineer blog
逆転検事を先日クリアして、久しぶりに逆転裁判1〜3をやり直そうか迷い中のfujisawaです。シンプルなデータクラスタリングツールを作成しましたので、そのご紹介をさせていただきます。 クラスタリングとは クラスタリングとは、対象のデータ集合中で似ているもの同士をまとめて、いくつかのグループにデータ集合を分割することです。データマイニングや統計分析などでよく利用され、データ集合の傾向を調べたいときなどに役に立ちます。 例えば下図の例ですと、当初はデータがゴチャゴチャと混ざっていてよく分からなかったのですが、クラスタリングすることで、実際は3つのグループのデータのみから構成されていることが分かります。 様々なクラスタリング手法がこれまでに提案されていますが、有名なところではK-means法などが挙げられます。ここでは詳細については触れませんが、クラスタリングについてより詳しく知りたい方は以下の
String::Dictionary - naoyaのはてなダイアリー
String::Dictionary という Perl のライブラリを作ってみました。 http://github.com/naoya/perl-String-Dictionary/tree/master String::Dictionary は検索エンジンその他を作る時に必要になる「辞書」のためのデータ構造 + API です。辞書は単語の集まりですが、これを配列やハッシュなどで持つのではなく、単語をすべて繋げた一つの大きな文字列として保持することでメモリ領域を節約したものです。単語は単に文字列連結で持つだけでなく、Front Coding で圧縮しています。以下簡単な解説です。 辞書は例えば [0] ･･･ jezebel [1] ･･･ jezer [2] ･･･ jezerit [3] ･･･ jeziah [4] ･･･ jeziel ...という風に単語を配列で持つことで実現でき
手軽に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
「日本語テキストを分類するベイジアンフィルタ」を簡単につくるyo - download_takeshi’s diary
数週間前の話になりますが、「はてブのリニューアル会見」の記事を読んでいたところ、はてブにも「自動カテゴライズによる記事分類」の機能が搭載されるとか。。。 同じようなタイミングで「似たようなモノ」というか「ほぼ同じようなモノ」を作っていたので、すごーくインスパイアされてしまいました。ジュワ〜。（アドレナリンの放出音） 数週間たってもいまだ興奮冷めやらぬ状態なので、今日はその件について書いてみようと思います。 Lingua::JA::Categorize - a Naive Bayes Classifier for Japanese document. http://search.cpan.org/~miki/Lingua-JA-Categorize-0.00001/ 「はてブのパクリ」ではありません。「ベイジアンによる日本語テキスト分類器」を「簡単に作る」ことを目的としたモジュールです。 も
新はてなブックマークでも使われてるComplement Naive Bayesを解説するよ - 射撃しつつ前転 改
新はてブ正式リリース記念ということで。もうリリースから何週間も経っちゃったけど。 新はてなブックマークではブックマークエントリをカテゴリへと自動で分類しているが、このカテゴリ分類に使われているアルゴリズムはComplement Naive Bayesらしい。今日はこのアルゴリズムについて紹介してみる。 Complement Naive Bayesは2003年のICMLでJ. Rennieらが提案した手法である。ICMLというのは、機械学習に関する（たぶん）最難関の学会で、採択率はここ数年は30%を切っている。2003は119/371で、32.1%の採択率だったようだ。 Complement Naive Bayesの位置づけは 実装が簡単 学習時間が短い 性能もそこそこよい という感じで、2003年段階にあっても、絶対的な性能ではSVMに負けていた。しかし、学習が早いというのは実アプリケーシ
GC - GCアルゴリズム詳細解説 - livedoor Wiki（ウィキ）
GC¥¢¥ë¥´¥ê¥º¥à¾ÜºÙ²òÀâ ÆüËܸì¤Î»ñÎÁ¤¬¤¹¤¯¤Ê¤¤GC¥¢¥ë¥´¥ê¥º¥à¤Ë¤Ä¤¤¤Æ¾ÜºÙ¤Ë²òÀ⤷¤Þ¤¹ ¥È¥Ã¥×¥Ú¡¼¥¸¥Ú¡¼¥¸°ìÍ÷¥á¥ó¥Ð¡¼ÊÔ½¸ GC ºÇ½ª¹¹¿·¡§ author_nari 2010ǯ03·î14Æü(Æü) 20:47:11ÍúÎò Tweet ¤³¤ÎWiki¤¬Ìܻؤ¹½ê GC¤È¤Ï¡© GC¤ò³Ø¤ÖÁ°¤ËÃΤäƤª¤¯»ö ¼Â¹Ô»þ¥á¥â¥ê¹½Â¤ ´ðËÜ¥¢¥ë¥´¥ê¥º¥àÊÔ Reference Counter Mark&Sweep Copying ±þÍÑ¥¢¥ë¥´¥ê¥º¥àÊÔ IncrementalGC À¤ÂåÊÌGC ¥¹¥Ê¥Ã¥×¥·¥ç¥Ã¥È·¿GC LazySweep TwoFinger Lisp2 Pa
Não Aqui! » DASTrie 1.0 released
Static Double Array Trie (DASTrie) という静的ダブル配列のライブラリをリリースしました．ダブル配列の実装はいろいろありますが，このライブラリの特徴を以下に挙げます． C++テンプレートを利用して，std::mapのような連想配列，std::setのような集合を簡単に実装できる． ダブル配列の要素を４バイト，もしくは５バイトで表現し，データベースをコンパクトにする（通常の実装では要素サイズは８バイト）． 最小接頭辞トライを実装し，データベースのサイズをコンパクトにする． よくあるダブル配列の実装では，レコードのキーとユニークなIDがトライの中に格納され，レコードのデータは配列などで独自に管理する必要があります．DASTrieはC++のテンプレートで，任意のデータ型をレコードとして使い，レコードをトライの中に格納するので，連想配列として簡単に利用できます．もち
"comb sort" Motoyuki's Diary:2000年5月下旬
昨日から延々とサーバ構築。 SCSI HDD の騒音に耐えかねて再インストール決行。 旧おうちサーバで使っていた 20GB IDE HDD を入れて IDE 10GB + 20GB 体制にする。 データの転送に時間をとられた *1ため、ほぼ二日間の間メールの読み書きができなかった。
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' __ /:::::::/｀ヽ /'
OBB vs AABB - Radium Software Development
iPhoneの一般修理店は予約なしでも来店できる？ 基本的には飛び込みで修理に行ってもOK iPhoneを置いていたソファにうっかりと腰かけてしまい、パネルを割ってしまった、こんな時はスマホの一般修理店へ行きましょう。画面割れは、スマホやタブレットの故障原因として非常に多いものです。予約なしで突然お店に行っても平気かしらと、不安に思う方々もいらっしゃるかもしれません。結論としては特に問題はなく、予約なしで訪問しても画面割れの修理はお願いできます。 ただし他のサービス業のお店同様、予約なしの場合、お店が混雑していると順番待ちをしなければいけないです。特に繁盛しているスマホ修理のお店だと、行列が店内で出来ており、予約なしだと、自分の順番が巡ってくるまで長時間待たされる可能性があります。平日の朝、昼なら利用客が少ない場合が多く、飛び込みでも比較スムーズに修理が頼めます。 予約は入れた方が時短に、
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
M.Hiroi's Home Page / Lightweight Language
white page