オープンソースとアルゴリズムの特許 - ny23の日記
GPL で公開していた構文解析ライブラリで実装していたアルゴリズム（の一つ）について，特許が出ているという指摘を受けたので，GPL で公開するのは不適切だと判断して，当該アルゴリズムの実装を取り除いた．このアルゴリズムは，同じくオープンソースな解析器 (LGPL/BSD) でも実装され公開されていたので，すっかり ok だと油断していた．確かに企業研究者の提案手法なので，特許が取られている可能性は頭の隅にはあったのだけど，それにつけても非常に残念だ．今回のアルゴリズムは，かんたん特許検索で提案者名を入れてもそれこそ「かんたんに」出てくるので，自分自身の過失だろう．が，それで済ませていいのだろうか．[最後にオチあり] 以前，Bayesian Setsの特許について - のんびり読書日記 を読んだ時も思ったけど，アルゴリズム（あるいはソフトウェア）の特許というのは，オープンソース開発者にとって
Bing検索の裏側―BitFunnelのアルゴリズム - Hatena Developer Blog
はてなアプリケーションエンジニアの id:takuya-a です。 この記事では、Microsoft の検索エンジン Bing で採用された BitFunnel アルゴリズムを紹介します。 昨年のエンジニアアドベントカレンダーでは、文字列検索のアルゴリズム全般について紹介しました（文字列アルゴリズムの学びかた - Hatena Developer Blog）。今年はそのなかでも、インデックス（索引）を使った全文検索アルゴリズムについてのお話になります。 この記事の前半は全文検索の入門にもなっていますので、検索技術になじみがない方にも楽しんでいただけるのではないでしょうか。 逆に、「そんなのもう知ってるよ！」という方は、本題である「BitFunnel アルゴリズムの詳細」から目を通していただければと思います。 この記事は、はてなエンジニア Advent Calendar 2017の21日目の
東京工業大学 情報理工学院 数理・計算科学系
大岡山地区の建物 大学正門より，桜並木のウッドデッキを通り，右手の芝生をつっきる小径が西8号館，西7号館に続くみちです． 大岡山西8号館（Ｅ棟，Ｗ棟）: キャンパスマップの18, 19番の建物にあたります．本館の西隣りに位置しています．正面玄関をはいったところは３階です． Ｅ棟においでの方は廊下をはいってすぐ左手のエレベータをご利用下さい． Ｗ棟にはじめておいでの方は十分に注意して下さい．Ｅ棟とＷ棟を繋いでいる通路は３階と１０階にしかありません．Ｅ棟のエレベータを利用すると迷子になります．正面玄関から廊下をまっすぐにおいでになり，奥の右手にあるエレベータをご利用下さい． 西7号館：キャンパスマップの17番の建物にあたります．西8号館から，建物を二つ挟んだ並びにあります．芝生から向う場合，左手に本館を見ながら進み，本館がとぎれたあたりの右手にある小さな建物が西7号館です．橋を渡ってはいったと
Suffix ArrayをRustで実装した - Islands in the byte stream
suffix arrayを一番簡単なアルゴリズムで実装する - アルゴリズム学習(その6) - $shibayu36->blog; を読んで、ちょうど自分も何らかの形で全文検索を一部実装してみようと思っていたのでRustで真似してみました。 Rustを選んだ理由は、以下の理由からです。 実際に全文検索を実装するのに耐えうるパフォーマンスであること パッケージマネージャなどのエコシステムが完備されていること Rustについてはそれほど詳しくはないのですが、GCや例外がないとのこと。であればパフォーマンスチューニングがC言語並にやりやすい可能性がありますし、一度真面目に勉強してみたいと思っていました。Goと異なり、ジェネリクスがあるのも魅力的です。 というわけでコードこんな感じになりました: pub fn make_suffix_array(s: &str) -> Vec<i64> { use
文字列アルゴリズムの学びかた - Hatena Developer Blog
こんにちは！はてなアプリケーションエンジニアの id:takuya-a です。 みなさんは、このような疑問をもったことはありませんか？ grep はどのように文字列を検索しているのか？ MeCab はどうやって辞書を高速にルックアップしているのか？ パーサやコンパイラを作りたいけど、何から始めればいいのか？ 本稿では、「文字列アルゴリズムとはどんなものなのか？」「なぜ重要なのか？」「何を知っておくべきか？」「どうやって勉強すればいいのか？」といった疑問にお答えしていこうと思います。 文字列アルゴリズムの意外な応用や、モチベーションを保ちやすい勉強のしかた、文字列アルゴリズムを勉強するために行った社内での取り組み、実装するときのコツといったトピックについても触れています。 このエントリは、はてなエンジニアアドベントカレンダー2016の22日目の記事です。昨日は id:syou6162 さんに
Alternating Least Square (ALS) でCP分解 - でかいチーズをベーグルする
テンソル分解の基本中の基本のCP分解を導出して実装した。最適化の方法は色々あるらしいけど多分いちばんよく使われる Alternating Least Square (ALS) を使った。ちなみにここでテンソルって呼んでるのはただの多次元配列のこと。 まとめ CP分解とは AlSによるCP分解の更新式を導出 ALSによるCP分解をpythonで実装 人工データを使って実験 CP分解とは CP分解が何かを知るためには、まず Matrix factorization (MF) について知ると良い。 MFでは、N x M 行列 X を以下のように分解する ここで、は N x R 行列で、は M x R 行列。この分解を要素ごとに書くとこうなる つまり要素 を なんかよくわからない次元のベクトル との内積で表現することにしましょうと言っているわけ。 じゃあこの と っていうベクトルたちをどうやって求
IPOL Journal · Image Processing On Line
IPOL is a research journal of image processing and image analysis which emphasizes the role of mathematics as a source for algorithm design and the reproducibility of the research. Each article contains a text on an algorithm and its source code, with an online demonstration facility and an archive of experiments. Text and source code are peer-reviewed and the demonstration is controlled. IPOL is
高速なハッシュテーブルを設計する | POSTD
(訳注：2016/9/28、頂きましたフィードバックを元に記事を修正いたしました。) はじめに 本稿では、高速で汎用的なハッシュテーブルを作るために行う、設計についての多くの意思決定事項を紹介します。最終的に、私の emilib::HashSet とC++11の std::unordered_set の間のベンチマークが出来上がりました。もし、ハッシュテーブルに興味があって、自分で設計したいなら（どのプログラミング言語かに関わらず）、本稿がヒントになるかもしれません。 ハッシュテーブル は、素晴らしい発明です。 ならし計算量O(1) ( O(√N)時間 )で、挿入、削除、検索を行うことができます。ならし計算量とは、ハッシュテーブルの計算に平均でO(1)の計算量がかかることを意味しますが、時々、これよりも多くの時間がかかる場合があります。具体的には、ハッシュテーブルに空きがない場合で、挿入の
ビットを数える・探すアルゴリズム
作成日：2004.05.04 修正日：2012.09.01 このページは 2003年の9/11、9/28 の日記をまとめて作成。 はじめに PowerPC 系や Alpha などには population count と呼ばれるレジスタ中の立っているビット数を数える命令が実装されている。 集合演算を行うライブラリを実装したい場合などに重宝しそうな命令である。 職場でこの population count 命令について話をしているうちにビットカウント操作をハードウェアで実装するのは得なのか？という点が議論になった。 CPU の設計をできるだけシンプルにするためには、複雑で使用頻度の低い命令は極力減らした方がよい。 例えば SPARC は命令セット中にビットカウント演算があるが、CPU 内には実装しないという方針をとっている(population 命令を実行すると不正命令例外が発生し、それを
確率的勾配降下法 — 数理最適化用語集
読み: かくりつてきこうばいこうかほう 英名: Stochastic Gradient Descent 確率的勾配降下法（Stochastic Gradient Descent，以下 SGD）は， 確率密度関数 \(p(z)\) に対して目的関数が期待値で表された以下のような最適化問題に対して有効なアルゴリズムである． 上式における \(l,w,z\) をそれぞれ損失関数，モデルパラメータ，データに対応する確率変数の実現値とすれば， 上記問題は機械学習における期待損失（汎化誤差）の最小化問題に他ならない． そこで，関数 \(L(w)\) は 期待損失 と呼ぶことにする． SGD# 期待損失の値やその勾配 \(\nabla L(w)\) はいくつかの理由により計算困難である場合が多い． 例えば分布 \(p(z)\) が未知，\(p(z)\) が既知であっても期待値計算が困難， あるいは母集団
Fast Non-Standard Data Structures for Python
Python provides great built-in types like dict, list, tuple and set; there are also array, collections, heapq modules in the standard library; this article is an overview of external lesser known packages with fast C/C++ based data structures usable from Python. Note Disclaimer: I created datrie, marisa-trie, hat-trie and DAWG Python wrappers. Bloom Filters Bloom Filter (wiki) is an extremely memo
Python Dask で Out-Of-Core / 並列 LU 分解 - StatsFragments
はじめに 正方行列 を となる下三角行列 と 上三角行列 に分解することを LU 分解という。LU 分解ができると連立方程式の解や逆行列が 前進/後退代入でかんたんに求められてうれしい。 Dask を使って LU 分解を Out-Of-Core / 並列でやりたい。 LU 分解の並列化にはいくつかやり方があるようで、東大講義 スパコンプログラミング(1)、スパコンプログラミング(Ｉ) の 第10回 LU分解法 にまとまっている。この講義、ガイダンス資料の単位取得状況を見るとかなり楽しそうな感じだ。 ここでは、Dask での実装がかんたんそうなブロック形式ガウス法 (資料 P33-) をやりたい。 ブロック形式ガウス法 ブロック形式ガウス法では入力となる行列をいくつかのブロックに区切り、ブロックごとに処理を行う。具体的には、左上の対角ブロックからはじめて、以下の順番で処理していく。 対角ブロ
Google Chromeが採用した、擬似乱数生成アルゴリズム「xorshift」の数理
2015年12月17日、Google Chrome の JavaScript エンジン（処理系）である V8 の公式ブログにて、 JavaScript の標準的な乱数生成APIである Math.random() の背後で使われているアルゴリズムの変更がアナウンスされました。 Math.random() 関数は JavaScript を利用する際には比較的よく使われる関数ですので、親しみのある方も多いのではないかと思います。 新たなバグの発見や、従来より優秀なアルゴリズムの発見によってアルゴリズムが変更されること自体はそれほど珍しくはないものの、 技術的には枯れていると思われる Math.random() のような基本的な処理の背後のアルゴリズムが変更されたことに驚きを感じる方も少なくないかと思いますが、 それ以上に注目すべきはその変更後のアルゴリズムです。 実際に採用されたアルゴリズムの原
絶対に見逃せない投稿が、そこにはある - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? Qiita の 「見逃せない投稿」 を独自に評価してランキングするサービス Qaleidospace を作りました。 本投稿では、そのようなサービスを作ろうと思った理由、投稿を評価するアルゴリズム、システム構成について書きます。 余談ですが、今なら Yearly Ranking がほぼ 2015 年の投稿ランキングとなっており、眺めていて楽しいです。 TL;DR Qiita の「見逃せない投稿」をランキングするサービス Qaleidospace を作った。 適切な評価システムがあれば、書き手も読み手もみんな幸せになれるはず。 ストック数
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.johngustafson.net/pdfs/BeatingFloatingPoint.pdf
Encyclopedia of Algorithms
The Eigenvalues of Mega-dimensional Matrices
Alpha Matting Evaluation Website
Asymmetric Numeral System
http://documents.tips/documents/lets-impl-sbv.html