Locality Sensitive Hashing に挑んでみた - download_takeshi’s diary
久々のエントリです。 Locality Sensitive Hashing を perl で使うためのモジュールを書いてみました。Algorithm::LSHと名付けました。 先ほどDeveloper ReleaseとしてCPANにあげましたが、反映されるまで時間かかるので、興味ある方はcodereposからみてください。 Algorithm::LSH CPAN: http://search.cpan.org/~miki/Algorithm-LSH/ coderepos: http://coderepos.org/share/browser/lang/perl/Algorithm-LSH 超アルファバージョンな状態ですが、そのうちgithubにもupする予定。 そうそう、そう言えば WEB+DB PRESS Vol.49 にレコメンドエンジンの特集があって、その中に偶然にもLocality
比較的強固なライセンスキーの生成 - kaisehのブログ
プログラムのバイナリ自体が改ざんされる可能性を無視して、解析・偽装が困難なライセンスキーを生成/検証する手法というと、やっぱり以下のような公開鍵暗号方式になるんだろうか。 RSAのキーペアを作成しておく。 管理者側は「プログラム固有の情報＋ユーザ固有の情報」を秘密鍵で暗号化してライセンスキーとする。 1024ビットの鍵の場合、パディングの88ビットを引いて936ビット=117バイトを固有情報の記述に使用可能。ユーザ名とメールアドレス程度の情報は格納することができる。 この場合、ライセンスキーの長さも1024ビットになる。これをBase64でエンコードすれば172文字のキーになる。Base16なら256文字。 プログラム側には公開鍵を埋め込んでおく。 ユーザが入力したライセンスキーを公開鍵で復号化して検証する。 以下はライセンスキー生成部のサンプル。 import java.math.Big
並行分散ソフトウェア／並列分散ソフトウェア 2005年
このページは、筑波大学／ システム情報工学研究科／ コンピュータサイエンス専攻 および、 理工学研究科／ 理工学専攻 を対象とした講義、並行分散ソフトウェア／並列分散ソフトウェアのためのページです。 担当教官：新城 靖(しんじょう やすし)、追川 修一(おいかわ しゅういち) 科目番号：システム情報工学研究科 並行分散ソフトウェア 02CC020, 01CC305 科目番号：理工学研究科 並列分散ソフトウェア 01D1562 学期：３学期 曜時限：金曜日３、４ 教室：３Ａ４１０ ■シラバス（システム情報工学研究科／並行分散ソフトウェア） ■レポート ■パスワード生成 ■授業内容メモ 2005年12月02日 並行・並列・分散プログラミングとは 2005年12月09日 マルチスレッド・プログラミング(1) 2005年12月16日 マルチスレッド・プログラミング(2) 2005年12月22日 マ
ブルームフィルタ - Wikipedia
この項目では、確率的データ構造について説明しています。画像にぼかし効果を付加する画像フィルタについては「川瀬のブルームフィルター」をご覧ください。 ブルームフィルタ（英語: Bloom filter）は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、あるデータが集合の要素である（集合に含まれている）かどうかの判定に使われる。ただし判定は正確ではなくて、含まれていないのに含まれていると誤って判定すること偽陽性（false positive）の可能性がある。しかし含まれているものを含まれていないと誤判定すること偽陰性（false negative）はない。なお集合に要素を追加することはできるが、集合から要素を削除することはできない（ただし、拡張をした counting filter であれば削除もできる）。集合に要素を追加していくにつれて偽陽性の
Parsing Expression Grammar - Wikipedia
Parsing Expression Grammar（PEG）は、分析的形式文法の一種であり、形式言語をその言語に含まれる文字列を認識するための一連の規則を使って表したものである。PEGは再帰下降構文解析を文法を示すためだけに純粋に図式的に表現したものと見ることもでき、具体的な構文解析器の実装やその用途とは独立している。 PEGにおける構文（文法）の定義は文脈自由文法のバッカス・ナウア記法によるそれに似ているが、文脈自由文法では一般に「｜」（縦棒、バーティカルバー）で表される「これらのうちどれか」ではなく、「最初の解析がうまくいったらそれを、失敗なら次を順に試してゆき、成功したものを採用」（「/」であらわす）という意味を使う。 このため、文脈自由文法とは異なり、PEGには曖昧さは存在しない。文字列を構文解析する場合、正しい構文木は常に1つしかない。このためPEGはコンピュータ言語の構文解析
Prediction by Partial Matching - Wikipedia
Prediction by Partial Matching(PPM)は1984年にJ.G.ClearyとI.H.Wittenによって考案されたデータ圧縮アルゴリズムの1つ。 この改良版が7-zip等に用いられている。非常に高い圧縮率の反面、圧縮速度はかなり遅くメモリも多く消費するアルゴリズムである。 この亜種としてPPMC、PPMd、PPMZ等がある。 aabacaabbaとデータを符号化したとして、次にどの記号が出現するかを統計的に予測する。 この場合、統計的にaの次にはaが出現する可能性が高い。逆にcが出現する可能性は低いであろう。このように出現確率に偏りがあるとハフマン符号や算術符号で圧縮することが出来る。 しかし、上記の場合に次に出現する符号をaを50%、bを40%、cを10%と予測したとすると、他の記号は絶対に現れないということになり、新たな記号(dとする)が出現したときに対応
スキップリスト - Wikipedia
スキップリスト（英: skip list）は、平衡二分探索木と似た用途に使う乱択アルゴリズムのデータ構造。連結リストを並列に連結させて作る。比較により順序づけ可能な要素を挿入し、スキップリスト内ではソートされた状態で保持される。ソートされた連想配列や集合の実装などに使える。挿入と探索と削除は平均O(log n)である。1989年にウィリアム・ピューが発表した[1][2][3][4]。 スキップリストは順序つきの連結リストの前向きの飛び越しのリンクを追加したものである。ノードは幾何分布や負の二項分布にてランダムに高さを設定して追加され（高さ1が確率50%、高さ2が25%、高さ3が12.5%など）、リスト上の探索において連結リストの一部を高速に飛ばすことができる。 スキップリストの例。1〜10を追加し、ソートされた状態で保持されている。 スキップリストはリストの階層になっている。最下層は通常の
Rabin-Karp string search algorithm - Wikipedia, the free encyclopedia
In computer science, the Rabin–Karp algorithm or Karp–Rabin algorithm is a string-searching algorithm created by Richard M. Karp and Michael O. Rabin (1987) that uses hashing to find an exact match of a pattern string in a text. It uses a rolling hash to quickly filter out positions of the text that cannot match the pattern, and then checks for a match at the remaining positions. Generalizations o
E.W.Dijkstra Archive: Transcriptions
A group of volunteers is undertaking to transcribe the EWDs and other documents to simple HTML files, in order to make them both searchable and accessible to the visually impaired. If you might be interested in lending a hand in this effort, please read this. The transcriptions completed so far, and those in progress, are indexed here:
Perl で配列をシャッフル
Landscape トップページ | < 前の日 2004-11-12 2004-11-13 次の日 2004-11-14 > Landscape - エンジニアのメモ 2004-11-13 Perl で配列をシャッフル 当サイト内を Google 検索できます * Perl で配列をシャッフルこの記事の直リンクURL: Permlink | この記事が属するカテゴリ: [Perl] Perl で配列をシャッフルする方法。Perl クックブックに「配列のランダマイズ」として載ってたけどメモ。自分のライブラリにもあるけど、ブラウザからさくっとコピー & ペーストできと便利だしね。 mixi perlならではの便利な短いコードを書き留めたい http://mixi.jp/view_bbs.pl?id=2041 2004年11月12日 15:03 32: あとむ #===============
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
JavaScriptで配列をシャッフル
配列をシャッフル、つまりランダムに要素の位置を入れ替えるというのを、sortメソッドを使ってやってみたのだけど、明らかにダメダメなものになってしまった。その後、あーでもないこーでもないと考えたのだけど、算数が得意すぎて頭が痛くなった。ということを某所でぼやいたらはてのくんがコードを見つけてくれた。どうやらFisher-Yatesという有名なアルゴリズムでやると良いらしい。 最初に書いたコードは、 var a = new Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9); a.sort( function (a, b) { return Math.ceil(Math.random() * 3) - 2; } ); というもの。sortメソッドは、パラメータに与えられた関数が負の値・0・正の値を返すことによって要素の順序を決定するので、その関数がランダムに値を返せばランダ
最速インターフェース研究会 :: 実践JavaScriptで配列をシャッフルする方法リファクタリング
JavaScriptで配列をシャッフルする話を見て、そういえばArray#shuffleは以前書いた記憶があるなーと思って調べてみたらコピペだった。 http://www.fumiononaka.com/TechNotes/Flash/FN0212002.html Fisher-Yatesというアルゴリズムだそうです。 Array.prototype.shuffle = function() { var i = this.length; while(i){ var j = Math.floor(Math.random()*i); var t = this[--i]; this[i] = this[j]; this[j] = t; } return this; } a = [1,2,3,4,5]; a.shuffle() // 3,1,5,2,4 a // 3,1,5,2,4 ごく普通に実装
javascript - シャッフルシャッフル : 404 Blog Not Found
2006年08月30日18:30 カテゴリLightweight Languages javascript - シャッフルシャッフル なるほど。Schwartzian Transformの意外な利用法だなあ。 snippets from shinichitomita’s journal - JavaScriptの配列をsort関数でシャッフルする Array.prototype.shuffle = function() { return this.map(function(a){ return { weight: Math.random(), value: a } }) .sort(function(a, b){ return a.weight - b.weight }) .map(function(a){ return a.value }); } でも、実践ではどうだろう。調べてみた。
JavaScriptの配列をsort関数でシャッフルする - snippets from shinichitomita’s journal
あえてsort関数を使う方法でシャッフルしてみる。比較関数自体がランダムな値を返す場合と違って、これなら偏らない。 Array.prototype.shuffle = function() { return this.map(function(a){ return { weight: Math.random(), value: a } }) .sort(function(a, b){ return a.weight - b.weight }) .map(function(a){ return a.value }); }とりあえずFirefox1.5でOK。IEでもmap関数を自分で定義してやれば大丈夫のはず。 置換によるシャッフルと違って、weight値のところを適当に変化させれば、要素ごとに重みづけてのシャッフルもできると思う。たとえばよく聞く曲は優先的に前の方に持ってくるとか、その逆と
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
binomial tree
Algorithm-RabinKarp-0.41
www.hizum.net is Expired or Suspended.
Sedition·com is under the knife
配列をシャッフルする