差分検出アルゴリズム三種盛り - Object.create(null)
こんばんは. 気がつけばもうずいぶんと涼しくなってきました. 勢い余って凍ってしまったりせぬよう, くれぐれも普段の言動にはお気をつけください. はじめに さて, 我々人類にはどうしても二つの文字列 (あるいは行ごとに区切られたテキスト) 間の差分を求めなければいけない瞬間が発生します. 先人たちはそういった時のために diff のようなツールを開発し, それを利用することで文明はめざましい発展を遂げてきました. しかしながら, 使用するアルゴリズムを比較検討したい場合, 「差分」の定義を変えるなどして既存のアルゴリズムに変更を加えたい場合, diff のない異世界に飛ばされて自分で実装しなければいけない時などにおいては, 差分検出アルゴリズムについての理解が必要不可欠です. というわけで, この記事では文字列間の差分検出とは何かということと, 差分を求める三種類のアルゴリズムの紹介・解説
Amazonの推薦システムの20年
IEEE Internet Computingの2017年5・6月号に "Two Decades of Recommender Systems at Amazon.com" という記事が掲載された。 2003年に同誌に掲載されたレポート "Amazon.com Recommendations: Item-to-Item Collaborative Filtering" が Test of Time、つまり『時代が証明したで賞』を受賞したことをうけての特別記事らしい 1。 「この商品を買った人はこんな商品も買っています」という推薦で有名なAmazonが1998年にその土台となるアルゴリズムの特許を出願してから20年、彼らが 推薦アルゴリズムをどのような視点で改良してきたのか 今、どのような未来を想像するのか その一端を知ることができる記事だった。 アイテムベース協調フィルタリング 20年前も
どうぶつしょうぎ名人 - まめめも
どうぶつしょうぎ AI を作りました。絶対に勝てません。無力感を味わってください。 ref: http://mame.github.io/dobutsu-shogi-master どうぶつしょうぎとは 3 マス x 4 マスの単純化された将棋です。ライオン（王相当）、ぞう（1 マスしか進めない角行）、キリン（1 マスしか進めない飛車）、ひよこ（歩相当、にわとりに成ったら金相当）の 4 種類の駒を動かして、相手のライオンを取るか、トライ（ライオンを一番奥の行まで運ぶ、ただし直後に取られる場合はだめ）に成功すれば勝ちです。詳しくは Wikipedia の記事を見てください。 どうぶつしょうぎは後手必勝であることが知られています（研究報告）。つまり、後手が正しくプレイする限り、先手は絶対に勝てません。どうぶつしょうぎ名人は常に正しくプレイするので、先手のあなたは絶対に勝てません。 なんで作ったの
電王・Ponanza開発者が語る、理由がわからないけどスゴイ“怠惰な並列化”
皆さんこんにちは。 私は将棋プログラム「Ponanza」の作者、山本一成と申します。Ponanzaは初めてプロ棋士を破った将棋プログラムで、近年最も強い将棋プログラムと言えると思われます。また、2017年もトッププロ棋士の方と対局することが予定されています。Ponazaの改良のための機械学習に現在ジサトライッペイさんのPC「大紅蓮丸」の計算リソースを借りているのですが、その関係で原稿を書いてとお願いされたので、3回に渡って将棋プログラムの今について、書いていきたいと思います。 フリーランチの終焉、並列化の効率問題 アスキー読者の方々には言うまでもないのですが、まずは近年のCPU事情について解説していきたいと思います。ちょっと昔まではCPUはシングルコアが当たり前で18ヶ月経過すればCPUのトランジスター数は倍になり、性能が向上するという流れが続いていました。ソフトウェアはその性能向上に伴い
Lepton image compression: saving 22% losslessly from images at 15MB/s | Dropbox Tech Blog
Lepton image compression: saving 22% losslessly from images at 15MB/s This open-source project is no longer maintained or supported by Dropbox. Please refer to Lepton’s GitHub page for more information. ~ ~ ~ We are pleased to announce the open source release of Lepton, our new streaming image compression format, under the Apache license. Lepton achieves a 22% savings reduction for existing JPEG i
Linuxカーネルのコードを読んで勉強になったこと - φ(・・*)ゞ ｳｰﾝ カーネルとか弄ったりのメモ
Linuxカーネルのコードを読んでて、なるほど〜と思うことはよくあるけど、その中でも特に今までの考え方をぶち壊してくれたのはなんだっけと思ったところ、やっぱりリスト構造かなと言うところ。 c言語でリスト構造を作る場合、一般的な教科書方式だと↓のようにデータとnextポインタは密結合になってると思います。これの場合、struct foobarのポインタをnext要素に使っているので、他の構造体（例えば、struct hogehoge）で同じことをしようとすると、その構造体ではstruct hogehoge *nextというメンバ変数を持つ必要があります。 ヘッド要素はstruct foobarです。 struct foobar { int n; char s[64]; struct foobar *next; }; struct foobar head; Linuxカーネルの場合、データとリ
Brotli - Wikipedia
Brotli is a lossless data compression algorithm developed by Google. It uses a combination of the general-purpose LZ77 lossless compression algorithm, Huffman coding and 2nd-order context modelling. Brotli is primarily used by web servers and content delivery networks to compress HTTP content, making internet websites load faster. A successor to gzip, it is supported by all major web browsers and
レベルデザインに遺伝的アルゴリズムを活用する
2015年Apr6日レベルデザインに遺伝的アルゴリズムを活用する こんにちは。オインクゲームズの新藤です。 先日、弊社のデジタルゲーム第二弾となる「OLYM」がリリースされました。OLYM はターン制限のあるパズルゲームで、各ステージごとに決められたターン数が設けられてています。このターン数以内に目標を達成できないと、クリア失敗になってしまいます。そのため、このターン数をどう決めるかが、難易度に大きく影響する一因となっています。OLYM では、ステージごとのターン数を決定するのに遺伝的アルゴリズムを活用したので、今日はそれをご紹介します。 最終的にやったことは非常にシンプルです。端的に言えば、AI に実際にパズル解かせて、何手で解けたかをレベルデザインの参考にするということです。この AI を作る際に、遺伝的アルゴリズムを活用しました。そもそもは「自動でパズル解いてくれる AI がいたら面
合議システムと文殊
合議アルゴリズムと文殊のページ 電気通信大学 情報工学科 伊藤研究室 伊藤毅志、小幡卓弥、塙雅織 取り急ぎ、２００９年５月３日公開開始！ （全般にまだまだ工事中、、、） １．合議とは 「三人寄れば文殊の知恵」という諺がありますが、さまざまに違う意見を持った人が集まって、意思を決定 しなくてはならないことは、人間社会ではよくあります。一人で結論を出すよりも、みんなで意見を出し合っ てその意見を集約することでより良い結論を導くことがければ、まさに「文殊の知恵」となります。しかし、逆に 「船頭多くして船山に登る」という諺のように、意見がまとまらずにうまくいかなくなってしまうこともありえます。 どちらになるかは、この多数の意見の中から、どうやって意見を決めていくのかにかかっていると言えます。 ここでは、複数の意見をもとに一つの意見を集約することを「合議」と呼ぶことにします。 ２．
［CEDEC 2014］「ゲーム世界を動かすサイコロの正体 〜 往年のナムコタイトルから学ぶ乱数の進化と応用」 - 4Gamer.net
［CEDEC 2014］ナムコ作品で見る乱数の歴史。「ゲーム世界を動かすサイコロの正体 〜 往年のナムコタイトルから学ぶ乱数の進化と応用」レポート ライター：箭本進一 神奈川のパシフィコ横浜で行われた，ゲーム開発者向けイベントCEDEC 2014の最終日である2014年9月4日，「ゲーム世界を動かすサイコロの正体 〜 往年のナムコタイトルから学ぶ乱数の進化と応用」という講演が行われた。 登壇したバンダイナムコスタジオ HE技術部 加来量一氏 この講演のユニークな点は，旧ナムコの作品を「乱数」という視点から振り返るということだ。バンダイナムコスタジオ HE技術部のプログラマーである加来量一氏は，旧ナムコの初期作品50本を解析し，それぞれの時代でどのような乱数が使われていたかを特定した。そこから見えてくる乱数技術改良の歴史を見ていくというのが，講義の主旨なのである。 1980年代のナムコアーケ
平方数かどうかを高速に判定する方法 - hnwの日記
平方数とは、ある整数の平方（＝二乗）であるような整数のことを言います。つまり、0,1,4,9,16,...が平方数ということになります。 ところで、与えられた整数が平方数かどうかを判定するにはどうすれば良いでしょうか。与えられた整数の平方根の小数点以下を切り捨て、それを二乗して元の数になるかどうか、というのがすぐ思いつく実装です。 <?php function is_square($n) { $sqrt = floor(sqrt($n)); return ($sqrt*$sqrt == $n); } しかし、平方根の計算は比較的重い処理です。もっと高速化する方法は無いのでしょうか。 多倍長整数演算ライブラリGNU MPには平方数かどうかを判定するmpz_perfect_square_p関数が存在します（PHPでもgmp_perfect_square関数として利用できます）。本稿ではこの実装
b-Bit MinHashによる高速かつ省スペースな類似度判定 | SmartNews開発者ブログ
ゴクロの浜本です。ネットカフェでコードを書くのが好きです。 前回のエントリーでも触れられていますが、SmartNewsはホットな話題をユーザにお届けするために、常時、膨大な数のツイートおよびURLをクロールしています。こうして収集した記事に対し、様々な分析が施されますが、その中でも重要な処理の1つに、記事の類似度判定があります。内容の似通った記事をインデックスから発見し、グループ化する処理です。 毎秒、大量の新着記事が到着することから、この類似度判定は高速に実行する必要があります。また、インデックスを全てメモリに載せているので、類似度判定を実現する際の空間効率も要求されます。 今回は、SmartNewsが高速かつ省スペースな類似度判定のために使用しているb-Bit MinHashと呼ばれる手法を紹介します。2年前に、PFIの岡野原さんが非常に分かりやすい解説記事を書かれており、本エントリー
Cookpadのレシピを機械翻訳する · Naoki Orii's blog
前回のつくれぽ数の予測に引き続き、今回もCookpadネタです。 皆さんご存知の通り、英語版Cookpad（https://en.cookpad.com）が8月5日にリリースされました。 今のところ、英語圏のユーザがレシピを投稿するのではなく、どうやら日本語版サイトのレシピを翻訳しているみたいです： 日本食の家庭料理のレシピ数では世界一を誇るクックパッドのレシピのなかから、海外の家庭でも手軽に作りやすい人気レシピを英語に翻訳していきます。（中略）オープン当初は約1,500品の掲載レシピ数からスタートし、早期に数万品まで増やしていく予定です (クックパッド英語版『COOKPAD』をリリース) そのため、Cookpadの日本語のレシピと英語のレシピは1対1の関係にあります。例えば「たまにはね♪塩鯖のトマト煮(^m^*)」を英語に翻訳したものは「Salted Mackerel, Simmered
Cのrand()よりmt19937の方が速いことがあるという話 - Educational NLP blog
おはようございます。2年ぶりの記事ですね。 もう1月程前になってしまいましたが、id:sleepy_yoshi:20130720 で id:sleepy_yoshi さんが高速な非復元抽出をやっておられ、その中で、Cのrand関数を使っておられました。僕は、普段、std::mt19937を使っていたので、ちょっと比較してみた、という記事です。 C++11では、大別して、2つの擬似乱数生成の方法があります。１つはC（cstdlib）のrand関数で、高速ですが乱数の質が低く、もう１つはrandomヘッダのmt19937（メルセンヌ・ツイスタ）で、低速ですが乱数の質が高い（科学実験に適する）と、一般には思われていると思います。この高速・低速ですが、mt19937を使うことがボトルネックになるほど遅いことは殆どない、というのが今までの実感でした。なので、僕は、非復元抽出のような処理では、特にボト
Closest pair of points problem - Wikipedia
Closest pair of points shown in red The closest pair of points problem or closest pair problem is a problem of computational geometry: given points in metric space, find a pair of points with the smallest distance between them. The closest pair problem for points in the Euclidean plane[1] was among the first geometric problems that were treated at the origins of the systematic study of the computa
PHYSICAL AUDIO SIGNAL PROCESSING FOR VIRTUAL MUSICAL INSTRUMENTS AND AUDIO EFFECTS
Next | Index | JOS Index | JOS Pubs | JOS Home | Search PHYSICAL AUDIO SIGNAL PROCESSING FOR VIRTUAL MUSICAL INSTRUMENTS AND AUDIO EFFECTS JULIUS O. SMITH III Center for Computer Research in Music and Acoustics (CCRMA) Preface Organization Book Series Overview Acknowledgments Errata Physical Signal Modeling Intro But How Does It Sound? What is a Model? The Basic Science Loop Models for Music
様々な全域木問題
最小カットを使って「燃やす埋める問題」を解く方法について、問題とソースコードつきで、まとめました。ニコニコ生放送「TopCoderでプログラムしてみた」2000回記念放送の資料です。
へ、変態っ！！読めないからやめてっ！bit使ったデータ構造・アルゴリズム実装集 - Negative/Positive Thinking
この記事はCompetitive Programming Advent Calendar Div2012の2日目の記事です。 12月20日追記： Darseinさんが20日目の記事で、ビット演算についての詳しい説明を紹介してくださっています！必読ですね！！！！：） はじめに Y＾´ ∨／／ ／,∠ ,. ' ／l／／／ ／, ' , '／ ! ｜ ｌ }´ 〈 〉 変 〈/ , ' ／／￣｀>< ／／／ ／／／ _,.=‐|'"´l ｌ〈 変 / 〈 態. ∨, '／l| ,.'-‐､｀/／｀7/ ／''"´__ ｜ ﾊ l丿 態 { 人） ! ! （／! |ヽ〈_ ・.ﾉ〃 〃 ／ '／⌒ヾ.! ,' !く ! ! （_ ト､__／ ヽ､_,.イ ／ｌ ｌ ｜:::::::｀｀`/:::::／...´..
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - google/brotli: Brotli compression format
Noise shaping - Wikipedia