ロスレス圧縮アルゴリズムの歴史
江添亮 自由ソフトウェア主義者 C++ Evangelist C++標準化委員会の委員 ドワンゴ社員 C++11本を執筆した。 株式会社ドワンゴで働いている。 Mail:boostcpp@gmail.com Twitter:@EzoeRyou GitHub: https://github.com/EzoeRyou 江添亮のマストドン@EzoeRyou 筆者にブログのネタを提供するために、品物をアマゾンお気に入りリスト経由で送りたい場合： Amazon.co.jp: 江添亮: 江添のほしい物リスト 筆者にブログのネタを提供するために、直接に品物を送りたい場合、住所をメールで質問してください。 View my complete profile ► 2020 (31) ► December (2) ► November (2) ► September (2) ► August (4) ► Jul
RSA鍵の生成時に確率的素数判定法を使って問題ないのか - hnwの日記
前回記事「RSA公開鍵から素数の積を取り出す方法」でも紹介しましたが、RSA鍵の生成には巨大な2つの素数p,qが必要です。近年一般的に使われている2048bit RSA鍵の場合、p,qの大きさは1024bit、10進で約308桁の数になります。 このRSAのアルゴリズム中ではpとqを法としたフェルマーの小定理（正確にはその拡張であるオイラーの定理）を利用しています。つまり、pとqが合成数だとRSA暗号の大前提が狂ってしまいますので、pとqには確実に素数を選ぶ必要があります。 ところで、OpenSSLのRSA鍵生成の実装では、pとqの素数判定にMiller-Rabin素数判定法が用いられています。Miller-Rabin素数判定法は片側誤りの確率的アルゴリズムで、「たぶん素数」「確実に合成数」の判定ができるようなものです。pとqの素数性が重要なのに、その判定に確率的アルゴリズムを使っても問題
世界を支配する10のアルゴリズム | スラド IT
サイエンス系ブログ「io9」にて、「The 10 Algorithms That Dominate Our World」（世界を支配する10のアルゴリズム）なる記事が掲載されている。挙げられている10のアルゴリズムは以下の通り。 Google検索FacebookのニュースフィードオンラインデートサービスOKCupidのデートマッチング米国家安全保障局(NSA)によるデータ収集と解析、暗号化Amazonなどの「おすすめ」サービスGoogle AdWords高頻度取引(HFT)MP3圧縮犯罪発生予測システム「CRUSH(Criminal Reduction Utilizing Statistical History)」Auto-Tuneなどの音程補正ソフトウェア Google検索や高頻度取引、NSA関連などはまだ「世界を支配する」といっても良さそうな気はするが、OKCupidのデートマッチング
読んだ: 集合知プログラミング - ひだまりソケットは壊れない
ユーザーへの推薦やカテゴリ分類、いわゆるデータマイニングに興味があったので読みました。 集合知プログラミング 作者: Toby Segaran,當山仁健,鴨澤眞夫出版社/メーカー: オライリージャパン発売日: 2008/07/25メディア: 大型本購入: 91人 クリック: 2,220回この商品を含むブログ (275件) を見る 本書では集合知について次のように書かれています。 人々は集合知という言葉を長い間使い続けてきた。 それは新たなコミュニケーション技術の到来とともに、ますます人気と重要性を増して来ている。 集合知という表現は、集団の意識や超常現象を想起させるが、技術者がこの表現を使う場合は、今までにない知性を生み出すために、集団の振る舞い、嗜好、アイデアを結びつけることを指す。 『集合知プログラミング』 1.1 節 「集合知とは何か?」 本書は、何らかの集団 (例えば web ペー
基数ソート - Wikipedia
基数ソート（きすうソート、英: radix sort）は、「比較によらないソート」[1]のアルゴリズムの一つで、位取り記数法で表現可能な対象について、下の桁から順番にソートしてゆき、最後に最上位桁でソートすると、全体が順序通りに並ぶ、という手法である。 nをデータの数、kを桁数として、計算量のオーダーはO(nk)である。また、アルゴリズム自身の性質により、素直な実装が安定ソートになる。[2] このアルゴリズムは、データの種類が有限で、最大値・最小値がはっきりしているという仮定を置いており、全ての入力データが「3桁の整数」や「2文字のアルファベット」など決まった形式であることが分かっていなければならない。なおそれに加え、ある値のデータが必ず一つしか現れないとか、同じ値のデータは同一のものとしてしまって良い、といった場合には、もはやソートするのではなく、単純に、全体が入る大きさの配列を用意し、
高校生がスーパーコンピュータを使って5×5魔方陣の全解を求めることに成功 | 筑波大学 計算科学研究センター
概要 筑波大学計算科学研究センターは、全国共同利用施設として、一般公募による「学際共同利用プログラム」※1を実施しています。平成25年度に、茨城県立並木中等教育学校4年次（高校1年）の杉﨑行優（すぎざき・ゆきまさ）君の申請が採択されました。杉﨑君は筑波大学計算科学研究センターの朴泰祐教授と共同研究を進めた結果、スーパーコンピュータ「T2K-Tsukuba」※2を使った並列計算により、5×5の魔方陣の全ての解を求めることに成功しました。 魔方陣とは、正方形のマス目に、縦・横・斜めの合計が同じになるよう数字を置いたものです。5×5の魔方陣の全解は2億7530万5224通りあることがすでにわかっています。杉﨑君は「枝刈り法」を改良した求解アルゴリズムを考案し、スパコンに並列計算させるためのプログラムを開発しました。朴教授は、並列データの収集や並列化に関する詳細なアドバイスを行いました。並列計算
いまさらgrepが10倍高速化したのはなぜか – はむかず！
最近GNU grepコマンドの最新バージョンがリリースされ、速度が10倍になったとのアナウンスがあった。それを聞いて、なんであんな枯れた技術に10倍もの高速化の余地があったのだろうと不思議に思った人も多いだろう。 ニュース記事：grepコマンド最新版、”-i”で10倍の高速化 本家のリリースノート：grep – News: grep-2.17 released [stable] 今回のリリースでは正確には、マルチバイトロケールで、-iオプション（–ignore-case、つまり大文字小文字を区別しないオプション）をオンにした時の速度が10倍くらいになったそうだ。 なぜそんなに速くなったのか？逆を言えば今までなぜそんなに遅かったのか？ そもそも、多くの日本人にとって「大文字小文字の区別」というと英語のアルファベットか、せいぜいフランス語とかドイツ語とかのアクサン記号・ウムラウトがついたものく
「結城浩さんのCodeIQ問題は、なぜ面白いのか？」を7つのポイントで解説！｜CodeIQ MAGAZINE
CodeIQで結城浩さんが出題する問題はいつも大人気！なぜなら結城さんは解答者をどう楽しませるかを考えつくしているから。 今回は結城浩さんご自身に「なぜこんなに面白い問題を作れるのか」そのこだわりを７つのポイントに絞って書いていただきました。 by 馬場美由紀 （CodeIQ中の人） はじめに こんにちは、結城浩です。いつもCodeIQでの出題にご解答いただき、ありがとうございます。 今日は、CodeIQで出題しているときに私が心がけていることをお話しします。 なお、以下でお話しすることはあくまで私が出題する問題に対する心がけです。CodeIQにはたくさんの出題者さんがバリエーション豊かな出題をしています。他の問題に対して批判するという意図はまったくありませんので念のため。 最高の問題 出題するときに心がけていることの第一、それは最高の問題を作ろうということです。 せっかく時間を掛けて問題
某社の採用試験は迷路の最短経路探索プログラム | cyber205の日記 | スラド
人材獲得作戦・４ 試験問題ほか う～む。 AAで問題となる迷路を書いたテキストを読んでメモリに展開し、 最短経路を見つけて＄文字で埋めて帰すというモノ。 迷路の探索といえば、とにかく壁に当たるまで右か左に進んで、ダメだったら分岐を 一つ一つ引き返して別の道を行くというLISPで書いたら楽しそうなアルゴリズムが 思い付くけど、これだと問題によってはとてつもなく時間がかかって終わらないので、 見当はずれの間違いってことじゃないものの、正解ではないらしい。 自分は優秀じゃないので解けませんでした。 凄い人は３０分から１時間で解いてしまうのね。 というか、アルゴリズムの考え方がしっかりできる人でないと無理ぽ。 いまどきのプログラミングはどうにかして自前コードを書くよりも、既存のAPIと 便利なライブラリを組み合わせて、徹底的に手間をかけずにゴマかす方法を探す という部分が重視されてるからね。 #
計量学習を用いた画像検索エンジンとアニメ顔類似検索v3について - デー
まだgithubにはpushしていないのですが、さいきょうの組み込み型画像検索エンジンotamaに計量学習を用いて与えられたデータにあった画像間の距離関数を学習してそれを使って検索するというドライバを入れたので、先行的なデモとしてアニメ顔類似検索v3を作ってみました。 計量学習は、ベクトル間の距離の計り方を機械学習で決めるみたいな分野です。 アニメ顔類似検索v3 AnimeFace Search v3 - Otama LMCA_VLAD_HSV Driver randomボタンを押すと顔画像がランダムに出るのでどれかクリックするとそれをクエリに検索します。color weightは色の重みを調節するパラメーターで、1にすると色だけで検索します。0にすると形状やテクスチャだけで検索します。結果画像の上の数字は類似度的なもので、その横のgglは元画像をGoogle Search by Imag
「高速文字列解析の世界」を読む前に知っておくと良いこと - EchizenBlog-Zwei
「高速文字列解析の世界」という大変すばらしい本が発売された。わりと敷居が高い本ではあるので読む前に知っておくとよさそうなことを書いておく。 「高速文字列解析」とは 本書でいう高速文字列解析というのは主に2つのことを指している。ひとつはデータを圧縮して小さくしてディスクよりメモリ、メモリよりキャッシュというようにより高速な記憶装置で扱いましょう、という話。もうひとつはデータ構造を工夫することで複雑な操作もそこそこ高速に扱えますよ、という話。つまり「圧縮」の話と「効率的なデータ構造」の話があると考えておくと良い。 キーワードは3つ オビにも書いてあるけれど、本書が主に扱うのは「BWT」「簡潔データ構造」「ウェーブレット木」の3つ。具体的には「BWT」が「圧縮」に関わっていて「ウェーブレット木」が「効率的なデータ構造」に関わっている。「簡潔データ構造」は基本的な道具として本書の色々なところで出て
SHA-3 のアルゴリズムの選定が完了 - 強火で進め
keccak のものに決定したそうです。 NIST.gov - Computer Security Division - Computer Security Resource Center http://csrc.nist.gov/groups/ST/hash/sha-3/winner_sha-3.html NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition http://www.nist.gov/itl/csd/sha-100212.cfm 早速、 GitHub に各種言語向けにライブラリが上がっていたのでご紹介。 JavaScript https://github.com/drostie/sha3-js このライブラリは選定前の候補のもの全ての実装がされています。今回 keccak のものに決定したので ke
高層ビルのエレベーターホールには、なぜ階数表示がないのか - 本当は怖いHPC & AI
以前に高橋幸雄先生の授業で聞いて非常に面白いと思ったこと。 オフィスビルとかホテルとか、エレベーターが何基も設置されているビルの場合、エレベーターホールに階数表示が無いことが多い。エレベーターホールで画像検索してみればわかると思う。 これはなぜだろうか。 その理由は、「客がいても、その階を通過することができるようにするため」だ。 基本的に、多数のエレベーターを効率よく動かすのは難しい。工夫された高度なアルゴリズムが使われていることが多い。目標は「客の平均待ち時間を短くする」ことだ。ある階でボタンが押された場合、どのエレベーターがその客を迎えに行くか、という判断が平均待ち時間に大きな影響を与える。難しいアルゴリズムの中で、この点がもっとも重要なところだ。 高層ビルの場合、エレベーターはかなりの速度で走っている。既に客を乗せて走っているエレベーターが他の客を乗せるために停止すると、減速→停止→
牌山生成について | セガネットワーク対戦麻雀 MJ5
【１】「プレイヤー乱数シード」と「不確定要素」から、「乱数の種」を生成する。 ・「全員のプレイヤー乱数シード」を数値に変換し、小さい順に連結して640bitの値にする。 ※三人打ちでは480bitの値 ・640bitの値を不確定要素によって変化させ、乱数の種とする。（不確定要素は、毎局変化する値） 【２】「乱数の種」を使って、「牌山」を作る。 ・起家を起点に、「萬子」、「索子」、「筒子」、「字牌」の順に牌を並べ、仮の牌山を作る。 ・仮の牌山を、「乱数の種」によって生成した「乱数」を使ってシャッフルする。 【３】「乱数の種」を使って、「サイコロの目」を決める。 // 座席位置 var Direction = 2; // 牌山の計算 function calcYama(Pseed1,Pseed2,Pseed3,Pseed4,UEseed){ // 各プレイヤーシード(文字列)を16
制限付き∑100問題まとめ
がたろう TTLでCPUを作る爺（コンパイラやOSも手作りです） @duo6750 「1から100までの和を表示するプログラムを作れ」という問題を鼻で笑う諸君、「但し変数は宣言済の int x 以外は使わないこと」 という条件を付けても鼻で笑っていられるかな? 2012-03-25 18:00:43
変数を1個だけ使って1～100を合算するC言語プログラム - ひしだまの変更履歴
今日Twitterで、変数を1個だけ使って1から100までの和を作れというお題（Σ100）が流れていた。そのひとつであるtanakhさんのC言語のプログラムを見て、自分もC言語で作ってみた(笑) C言語ではmain関数からプログラムの実行が始まるのはみんな知ってるけど、（C言語ってのはひどい言語でｗ、）mainの引数は省略できるんだよね。 自分が知っている範囲では引数は3つあって、main(int argc, char* argv[], char *envp[])。（4つ目もあったような気がするけど、覚えてない…） argcは実行時引数の個数、argvはその値の配列、envpは環境変数（「変数名=値」という形式）の配列。引数の個数はargcで渡されるのに、envpの個数は渡されない。envp++でポインターを進めていって、*envpがNULLだったら終わり＾＾； ちなみにargvも「arg
グラフ問題とバルク同期並列の常識をGiraphで体得
グラフ問題とバルク同期並列の常識をGiraphで体得：ビッグデータ処理の常識をJavaで身につける（5）（1/3 ページ） Hadoopをはじめ、Java言語を使って構築されることが多い「ビッグデータ」処理のためのフレームワーク／ライブラリを紹介しながら、大量データを活用するための技術の常識を身に付けていく連載 ソーシャル時代の「グラフ問題」の重要性 「グラフ問題」とは、どのようなものか、ご存じでしょうか？ ご存じでない方でも実は、「グラフ」を活用したシステムを日常的に使っているのです。 その1つは「Google」「Yahoo!」といった、Webの検索システムです。Webの検索システムでは、検索結果の表示順の判断基準の1つとして、Webページの重要度を示す「PageRank（ページランク）」と呼ばれる指標を用います。このPageRankは「注目に値する重要なWebページは、たくさんのページ
エンジニアの面接でアルゴリズムを組ませる理由 | quipped
@shibataismさんが、日経Bizアカデミーに「日本のエンジニアはシリコンバレーで通用するのか？」という記事を書いている。 「僕は文系だけど、エンジニアとして一流だ」と自己主張する人がいますが、採用側から見て実際にそうであることは稀です。シリコンバレーの企業では、採用面接の際に「 ○○アルゴリズムを書いてみてください」といったように、具体的かつ実践的な課題が出されます。こうした面接で、文系の人は（そもそも大学できちんと勉強したことがないので）適切な回答をするのが難しい場合が多いのです。 とあるのだが、アメリカの大学で数学を勉強し、プログラミングは独習したソフトウェアエンジニアとして1、少し補足してみたいと思う。 「文系」だからといって諦める必要はない これはまあその人の経験によるのだろうけど、文系出身のエンジニアだからといって諦める必要はない。[平林さん](https://falla
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Java 暗号化アーキテクチャー標準アルゴリズム名のドキュメント
https://jp.techcrunch.com/2012/01/20/20120118improvement-on-age-old-mathematical-principle-could-yield-improved-images-video/
