γ符号、δ符号、ゴロム符号による圧縮効果 - naoyaのはてなダイアリー
通常の整数は 32 ビットは 4 バイトの固定長によるバイナリ符号ですが、小さな数字がたくさん出現し、大きな数字はほとんど出現しないという確率分布のもとでは無駄なビットが目立ちます。 Variable Byte Code (Byte Aligned 符号とも呼ばれます) は整数の符号化手法の一つで、この無駄を幾分解消します。詳しくは Introduction to Information Retrieval (以下 IIR) の第5章に掲載されています。(http://nlp.stanford.edu/IR-book/html/htmledition/variable-byte-codes-1.html で公開されています) Variable Byte Code はその名の通りバイトレベルの可変長符号で、1バイトの先頭1ビットを continuation ビットとして扱い、続く 7 ビット
Perl で Range Coder (再挑戦) - naoyaのはてなダイアリー
以前にも Perl で Range Coder を実装した (http://d.hatena.ne.jp/naoya/20080927/1222512024) のですが、当時は理解も曖昧なまま速度にも気を遣わずに実装していました。 再度改めて、Range Coder を実装してみました。 http://github.com/naoya/perl-RangeCoder/tree/master README に記載した通り、静的 Range Coder*1、Binary Indexed Tree を用いた適応型 Range Coder、それからついでに 1-order の有限文脈モデルをもちいたものを作ってみました。いずれも Algorithms with Python の情報 (1, 2, 3)を参考に実装しています。 Canterbury Corpus の alice29.txt は 0-
アルゴリズムイントロダクション第24章 単一始点最短路問題 - naoyaのはてなダイアリー
アルゴリズムイントロダクションの輪講で、第24章の単一始点最短路問題を担当しました。発表に使った資料を以下にアップロードしました。 http://bloghackers.net/~naoya/ppt/090622_shortest_paths.ppt SlideShare はこちら。フォントの関係でグラフが崩れたりしているので、ppt で参照した方が見やすいかと思います。 Introduction to Algorithms#24 Shortest-Paths ProblemView more OpenOffice presentations from Naoya Ito. 単一始点最短路問題は、重み付き有向グラフの最短路木を求める問題です。各頂点に最短路重みを記録するのですが、はじめに各頂点の重みを∞として、「緩和」と呼ばれる操作により徐々に頂点の重みを最短路重みに近づけていく、というの
404 Blog Not Found:フローチャートがダメな3つの理由
2008年07月19日16:00 カテゴリLightweight Languages フローチャートがダメな3つの理由 というわけで、前世紀の遺物、フローチャートを供養する試み。 フローチャートとFizzBuzz問題 - novtan別館 さて、研修の話だけど、低水準言語ってだけではなく、きちんとフローチャートを書かせて処理の流れを整理し、あるいは効率が悪くないかを考えさせる、ということも重要だと思っています。フローチャートがそんなにいいなら、なんでビジュアルプログラミング言語が現場で使われないの? まずは経験則による終了宣言。ちなみにここで言うビジュアルプログラミング言語の定義は、Wikipediaのそれと同じ。 ビジュアルプログラミング言語 - Wikipedia ビジュアルプログラミング言語（英: Visual programming language、VPL）とは、プログラム要素を
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
ジャンル別ゲームの作り方とアルゴリズムまとめ - ネットサービス研究室
ゲームの作り方とアルゴリズムをジャンル別にまとめてみました。ゲーム制作や、プログラミングの勉強用にご活用ください。言語別ゲームプログラミング制作講座一覧もあわせてお読みください。 リンク切れがおきていたものは、URLを表示しておくので、Internet Archiveなどでキャッシュを表示させてみてください。 RPG ゲームの乱数解析 乱数を利用した敵出現アルゴリズムの解説 各種ゲームプログラム解析 FF、ドラクエ、ロマサガのプログラムの解析。乱数の計算など ダメージ計算あれこれ（http://ysfactory.nobody.jp/ys/prg/calculation_public.html） ダメージの計算式 エンカウントについて考えてみる エンカウント（マップでの敵との遭遇）の処理方法いろいろ RPGの作り方 - ゲームヘル2000 RPGのアルゴリズム ドルアーガの塔 乱数の工夫の
クラスカルのアルゴリズム - naoyaのはてなダイアリー
昨年からはじめたアルゴリズムイントロダクションの輪講も終盤に差し掛かり、残すところ数章となりました。今週は第23章の最小全域木でした。辺に重みのあるグラフで全域木を張るとき、その全域木を構成する辺の合計コストが最小の組み合わせが最小全域木です。 アルゴリズムイントロダクションでは、クラスカルのアルゴリズム、プリムのアルゴリズムの二点が紹介されています。いずれも20世紀半ばに発見された古典的なアルゴリズムです。 二つのうち前者、クラスカルのアルゴリズムは、コスト最小の辺から順番にみていって、その辺を選んだことで閉路が構成されなければ、それは安全な辺であるとみなし、最小全域木を構成する辺のひとつとして選択します。これを繰り返しているうちに最小全域木が構成されるというアルゴリズムです。 今日はクラスカルのアルゴリズムを Python で実装してみました。扱うグラフは書籍の例を使ってみました。以下
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 ...という風に単語を配列で持つことで実現でき
BWT と PPM - naoyaのはてなダイアリー
Burrows Wheeler Transform (BWT, Block-sorting) と Prediction by partial matching (PPM) は本質的に同じ事をやっている、というお話です。 先日 Managing Gigabytes を読んでいたところ、P.69 で "block sorting is very closely related to the PPM* method, which is a variant of PPM that allows arbitrary-length contexts." という記述があり、どうにも気になったので調べてみました。 サマリとしては、BWT と PPM の一種である PPM* はいずれも文脈から次の1文字を一意に決定するという概念で見ると本質的に同じことをやっていると言える、というところです。 BWT のあら
MD5 in ActionScript
ここで使っているswfとソース、連動するランキングCGI一式をダウンロード(9/4 解説を追加, rankingcheck.swfのバグを修正, ranking.cgiの些細なミスを修正) Table of Contents はじめに MD5 hash作成 適当な文字列から、MD5 hashを生成する パスワード管理 swfからパスワードを得ることが限りなく困難なパスワード認証の方法 CGIとの連携 ランキングCGIでMD5を使う意味と基本的な仕組みの解説 文字コードについて Macでのバグ 参考 はじめに まえがき MD5ハッシュを算出するASで書かれたスクリプトは、Flash Experimentsのものがありますが、2バイト以上の文字に対応してないようで、少し他にも探したのですがそれっぽいのが見つかりませんでした。それで自作してみましたが、もし先人の作られたものを知っている方がおりま
龍神録プログラミングの館
管理人の新作ゲーム「四聖龍神録２」公開開始！ ※現在はより適切な設計手法で紹介した龍神録2プログラミングの館があります。 ============================================================================ 龍神録プログラミングの館では、誰にでも龍神録(東方のようなSTG)が作れるような解説を行っています。 難しい構文は使わず、初心者にもわかり易い構文のみで紹介しているので 基本的なC言語の知識と、DXライブラリの知識さえあれば、誰にでも龍神録は作れます！ ゲームプログラミングの館でDXライブラリに慣れたら、今度は本格的なゲームを作ってみましょう！ ↓ゲーム紹介動画↓ ご存じない方は是非四聖龍神録Plusを遊んでみて下さい！ 全ての章のプロジェクトを一括ダウンロードする場合はこちらをクリック ※ 配布しているプロジェクトフ
「解読不能は数学的に証明済み」、RSAを超える新暗号方式とは ― ＠IT
2008/04/11 すべての暗号はいずれ破られる。2000年前のシーザー暗号の時代から高度な暗号技術が一般化したデジタル通信の現代に至るまで、それが暗号通信の歴史が証明し続けた事実であると同時に、もっとも人口に膾炙したクリシェでもあった。例えば、鳴り物入りでリリースされたDVDのコンテンツ暗号技術「CSS」（Content Scramble System）が、リリースからわずか数年で10代のノルウェー人ハッカーに破られたことは記憶に新しい。 【追記】（2008年4月15日） この記事は取材に基づいて執筆したものですが、一部専門家らから「CAB方式暗号は解読不能」というのは誇大表現ではないかとの疑義が呈されています。アルゴリズムの公開や第三者による検証がない現在、この記事に登場するCAB方式が発案者・実装者の主張通り画期的な暗号方式で、本当に解読が不可能であるかどうか分かりません。現在、専
衝突判定のアルゴリズム
2 つの図形の衝突判定 (コリジョン判定) のアルゴリズムをまとめます。 図が用意できておらず見難いですが、ご勘弁を。 太字はベクトルを表します。 線分と三角形 線分を p+tl、 三角形を (1-u-v)q0+uq1+vq2 で表します (t, u, v は媒介変数)。 Tomas Moller のアルゴリズム を Cramer の公式で解きます。 0.0≦t≦1.0, 0.0≦u, 0.0≦v, u+v≦1.0 なら交差と判定します。 半直線と三角形 線分と三角形の場合と同様の計算を行います。 0.0≦t, 0.0≦u, 0.0≦v, u+v≦1.0 なら交差と判定します。 点と球 点と球の中心の距離の 2 乗を求めて、 その長さが球の半径の 2 乗以下なら交差と判定します。 線分と球 線分の始点から終点へのベクトルを v、 線分の始点から球の中心へのベクトルを c とします。 v・c
ゲームのバグにみるアルゴリズム - 衝突判定
何を見てもアルゴリズムを考えてしまうのがプログラマの職業病といったところです。 私は結構ゲーム好きなんですが、ついついアルゴリズムを考えてしまうんですね。 バグを発見したときなどは楽しくてたまりません。 そのほつれからプログラムのコードが透けて見えるのです。 本日のターゲットは2001年、匠から発売されたアーケードゲーム「ナイトレイド」です。 ジャンルはシューティングなのですが、変なシステムを採用した、あまり見栄えのしないゲームでした。 このゲーム、非常にマイナーです。多分、名前を聞いて分かる人の方が少数派ですね。 ちなみにプレイステーションに移植されています。 アーケード版公式ページ PS版公式ページ このゲームには非常に致命的なバグがあり一部界隈では有名です。 自機を画面左上に移動させると敵が弾を撃たなくなるのです！ なぜこんなことが起こるのでしょうか？ 矩形の衝突判定 ところで矩形(
Collision Detection Algorithms - Games++
This article assumes a basic understanding of the geometry and math involved in collision detection, and covers some advanced collision detection techniques. Portal-based engines divide a scene or world into smaller convex polyhedral sections. Convex polyhedra are well-suited for the graphics pipeline because they eliminate overdraw. Unfortunately, for the purpose of collision detection, convex po
自己結合の使い方
はじめに SQLが提供する結合演算には、その特徴に応じて内部結合、外部結合、クロス結合などさまざまな名前が与えられています。普通、これらの結合の多くは、異なるテーブルまたはビューを対象として行われます。しかし、SQLは結合が同一のテーブルまたはビューに適用されることを禁止していません。同一のテーブルを対象に行う結合を「自己結合（self join）」と呼びます。自己結合は、使いこなせば非常に便利な技術ですが、動作がイメージしにくいため敬遠されがちです。そこで本稿では、この自己結合の便利さを例題を通して学び、その動作を分かりやすく解説します。 自己結合を理解することは、実務上のテクニックを身につける以外に、もう一つ利点があります。それは、集合指向（set-oriented）というSQLの重要な特徴を理解できることです。オブジェクト指向言語が世界をオブジェクトとして表現するように、SQLは世界
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
mixi Engineers’ Blog javascript
teacup. byGMO サービス終了のお知らせ｜GMO MEDIA
Amazon.co.jp: 集合知プログラミング: Toby Segaran (著), 當山仁健 (翻訳), 鴨澤眞夫 (翻訳): 本
Code Golf | Home