文法圧縮入門：超高速テキスト処理のためのデータ圧縮（NLP2014チュートリアル）
言語処理学会第２０回年次大会（2014/3）のチュートリアル講義資料です。 - 要旨 - 文法圧縮とは，入力テキストをよりコンパクトな文脈自由文法（CFG）に変換する圧縮法の総称である． 文法圧縮の強みは圧縮テキストを展開すること無く，検索等のテキスト処理を効率よく行える点にある． 驚くべきことにその処理速度は，元テキスト上での同じ処理を理論的に，時には実際にも凌駕する． また近年，ウェブアーカイブやログ，ゲノム配列等の大規模実データを高効率に圧縮できることで注目を集めている． しかしながら，文法圧縮についての初学者向けの解説資料はまだまだ少ない． そこで本チュートリアルでは，文法圧縮の歴史的背景から最新動向までを幅広く紹介する． 具体的には文法変換アルゴリズム，圧縮テキスト上での文字列パターン検索，文法圧縮に基づく省メモリデータ構造等の解説を行う．
Clojureで学ぶデータ構造：ハッシュテーブル - HackerNews翻訳してみた
「HackerNews翻訳してみた」が POSTD (ポスト・ディー) としてリニューアルしました！この記事はここでも公開されています。 今回の記事は、Clojureでのハッシュテーブルの実装に関する記事です。長い記事で途中までの翻訳になりますがお楽しみください。 Original article: Data Structures in Clojure: Hash Tables by Max Countryman 前回のおさらい 前回の記事では連結リストについてお話ししました。具体的には、ミュータブルな片方向リストの実装方法を検証しましたね。片方向リストを選んだ理由についても、すでに説明済みです。ここで覚えておいてほしいのは、一般的にClojureではイミュータブルなデータ構造が用いられるということです。しかしミュータブルなデータ構造を利用した方が、アルゴリズムがよりシンプルで高速になるケ
WebSocketを再接続するアルゴリズムの工夫 - ワザノバ | wazanova
http://blog.johnryding.com/post/78544969349/how-to-reconnect-web-sockets-in-a-realtime-web-app 1 comment | 0 points | by WazanovaNews ■ comment by Jshiike | 約2時間前 John RydingのブログでWebSocketの再接続のアルゴリズムの工夫について紹介しています。 リアルタイムウェブアプリにおいて、何らかの理由でバックエンドとの接続が切れた場合、クライアントは一定間隔で再試行するというロジックを設定（参考コード）していたとします。その場合、大量のクライアントがいて、もし長い時間接続が不能であれば、再開時にバックエンドには大量のリクエストが集中することになります。 そこでJohnがお薦めするExponential Backoff
Spotify: 曲をシャッフルするのは単純にランダムではいけない - ワザノバ | wazanova
http://labs.spotify.com/2014/02/28/how-to-shuffle-songs/ 1 comment | 0 points | by WazanovaNews ■ comment by Jshiike | 約4時間前 SpotifyのLukáš Poláčekがプレイリストをシャッフルするロジックを改善した取り組みを紹介しています。 以前のロジック ランダムアルゴリズムには、Fisher-Yates shuffleを利用。 順次再生する曲を選ぶロジック同士には依存関係がなく、完全にランダムに選択される。よって、同じアーティストとの曲が連続して再生されることも可能性としてはある。 これはギャンブラーの誤謬と呼ばれる現象。例えば、コイントスで表が連続してでると、次は裏が出ると思いがちであるが、常に確率は1/2である。従前の結果が次の結果に影響を与えると考えてし
大量のテキストからランダムに少数の行を抽出したい - Reservoir Sampling - 唯物是真 @Scaled_Wurm
前に以下のような記事を書きましたが、大量のテキストではうまくいかなかったので新たに書きました ファイルからランダムにN行取り出す(shufコマンド) - 唯物是真 @Scaled_Wurm 上の記事ではテキストをランダムに\(k\)行取り出したい時"shuf -n k"コマンドでランダムにシャッフルした\(k\)行を取り出していました ところが非常に大きなテキストファイルに対して上のコマンドを実行すると、一度にデータを全部メモリに読み込み始めているのか、すごい勢いでメモリを消費していきました(sort -Rでも) そこでメモリをあまり使わずにランダムに\(k\)行取り出す方法について調べました まず基本的な非復元抽出のアルゴリズムは以下の記事の発展手法とか追記のあたりの話がわかりやすいと思います 非復元抽出の高速かつ実装が簡単な方法を考える - 睡眠不足？！ この記事の話も一度全部の要素を
jumbled pattern matchingというのを知った - EchizenBlog-Zwei
Binary Jumbled Pattern Matching via All-Pairs Shortest Paths(http://arxiv.org/pdf/1401.2065v1.pdf)という論文がLOUDS論文をreferしていて興味があったので読んでいた。jumbled pattern matchingという問題の時間計算量を改善したよ、という話だった。 不勉強ながらjumbled pattern matchingという言葉を知らなかった(もしくは忘れていた)。幸い、この論文にどういう問題であるか解説があったので容易に理解することが出来た。 なので忘れないうちにメモしておく。 jumbled pattern matchingというのはマッチさせる単語の文字の順番が入れ替わっていてもマッチさせるパターンマッチ。つまりabracadabraに対してabraだけでなくbaraもマッ
ぼくのかんがえたさいきょうのround関数 - hnwの日記
浮動小数点数の丸めにおいて丸め桁数を指定でき、それでいて精度を失わないようなround関数をCで実装してみました。 https://github.com/hnw/precise-round 実装としては、受け取った浮動小数点数から最短になる10進表記に変換し、浮動小数点をズラすことなく10進表記のまま四捨五入を行うものです。これを元に偶数丸めを実装するのも容易でしょう。 実際、前回記事「RubyとPythonとC#のround関数のバグっぽい挙動について」で指摘した5.015の例についても期待通りに丸めることができます。 #include <stdio.h> extern double precise_round(double x, int digits); int main() { printf("%f\n", precise_round(5.015, 2)); // 5.02 prin
Satoshi Whitepaper
1 ビットコイン：P2P 電子マネーシステム 中本 哲史 satoshi@gmx.com www.bitcoin.co.jp 概要：純粋なP2P電子マネーによって、金融機関を通さない甲乙間の直接的オンライン取引が可能になる。電子署名は問 題の一部を解決するが、依然信用できる第三者機関による二重使用予防が求めらため、その恩恵は失われる。当システ ムはP2P電子マネーにおける二重使用問題の解決を提案する。このネットワークは取引に、ハッシュベースの継続的なプ ルーフ・オブ・ワークチェーンにハッシュ値として更新日時を記録し、プルーフ・オブ・ワークをやり直さない限り変更できな い履歴を作成する。最長である一連のチェーンは、取引履歴を証明するだけでなく、それがCPUパワーの最大のプールか ら発せられたことを証明する。大多数のCPUパワーがネットワークを攻撃していないノード（ネットワーク接続ポイント）
easystar.js
What is EasyStar.js ? Easystar.js is an asynchronous A* pathfinding API written in Javascript for use in your HTML5 games and interactive projects. The goal of this project is to make it easy and fast to implement performance conscious pathfinding. Main Features Calculates asynchronously for better overall performance Simple API. Small. ~7kb. Framework independent. Use it with any existing Javascr
Visualizing min-heap algorithms with D3.js
I haven’t done any real work on learning Javascript and D3.js since my last attempt a couple months back. To keep at it, I thought I’d try using D3.js to visualize a simple algorithm: finding the largest couple of items in a list. This problem comes up all the time when doing search and recommendation type tasks. Every time you query a search engine, it has to find the couple best scored results i
DSIRNLP #3 LZ4 の速さの秘密に迫ってみる
現在のマルチスレッドプログラミングの抱える問題点と、代替案をわかりやすく解説いたします。最近登場したConcurrent Revisionsも解説します。
d.y.d. 2倍だけじゃない
10:01 10/07/20 それでも２倍だ 先日のvectorの伸長度合いの記事に関して 本当に1.5倍のほうがメモリ効率がよいのか という反応をいただきました。とても興味深い。みんな読みましょう。 自分の理解メモ： 「再利用ができるから嬉しい」等の議論をするなら、 今までに確保したメモリ (1 + r^1 + ... + r^k) のうち、 有効に使えてるメモリ r^{k-1} (バッファ拡大直後) や r^k (次のバッファ拡大直前) の割合で評価してみようじゃないかという。 まず簡単のために再利用をしない場合を考えると、この割合はそれぞれ (r-1)/r^2、 (r-1)/r になります（途中計算略）。 この利用率が最悪になる瞬間 (r-1)/r^2 を最善にしよう、 という一つの指標で考えてみると、式を微分なりなんなりしてみると r = 2 で最大(25%)となることがわかります
いつからその方法で偏りのない乱数が得られると錯覚していた？ - アスペ日記
私はつい最近まで勘違いしていました。 ここのページに書いてあるような方法で、一様分布する整数が得られると。 int random(int n) { return (int)(( rand() / (RAND_MAX + 1.0) ) * n); } この方法、一見すると実に一様分布が得られそうに見えるんですよね。 どういう思考回路を通っているかというのを自己分析すると、次のような感じです。 1. rand() では 0〜RAND_MAX のランダムな整数が得られる。 2. それを RAND_MAX + 1 で割ると、[0, 1) に一様分布する実数が得られる。 3. [0, 1) の一様な実数を n 倍して小数点以下を切り捨てたら、0 から n-1 に一様分布する整数が得られる。 これの罠なところは、1 と（特に）3 が正しいというところだと思います。 ただ、2 がダウト。 思いっきりダウ
Introducing Wire Protocol Buffers
EngineeringHijacking Amazon EventBridge for launching Cross-A...Securing the invisible paths: How cross-account event flows can become security ... Data ScienceRevamping Data Science InterviewsInterviews are not just about improving hiring outcomes - they are about strengt... EngineeringRoBERTa Model for Merchant Categorization at Squar...Harnessing Large Language Models to Deliver Accurate Busine
中学生にもわかるウェーブレット行列 - アスペ日記
id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix"」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。 …嘘です。 日本以外ではあんまり来ていません。 理由としては、やはりアルファベット圏では単語境界が明確であるため、こちらの記事で書かれているような「キーワード分割の難易度」といったことがあまり問題にならないということがあるかもしれません。 まあ、そういうわけで局所的に来ているウェーブレット行列ですが、日本語をはじめとする単語境界のない言語圏にとっては重要なネタであると思うため、解説記事を書き直して*1みようと思います。 ウェーブレット行列でできること 主となる操作は、文字列に対する 定数時間の rank() と select()*2 です。 rank() は、「文
Web上の膨大な画像に基づく自動画像補完技術の威力 - A Successful Failure
画像内に映り込んだ所望のオブジェクトを排除し、違和感の無い画像を生成するシーン補完技術に関しては近年複数の研究成果が発表されている。しかし中でも2007年のSIGGRAPHにて米カーネギメロン大のJames HaysとAlexei A. Efrosが発表した手法*1はブレークスルーとなりうる画期的なものだ。 論より証拠、早速適用例を見てみよう。本エントリで利用する画像はPresentationからの引用である。元画像の中から邪魔なオブジェクト等の隠蔽すべき領域を指定すると、その領域が補完された画像が自動的に生成される。 アルゴリズム 効果は抜群だがアイデア自体は単純なものだ。Web上には莫大な数量の画像がアップされており、今や対象となる画像の類似画像を一瞬にして大量に検索することができる。そこで、検索された類似画像で隠蔽領域を完全に置き換えてしまうことで違和感の無い補完画像を生成するのだ。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
いつからFIFOがスケールしないと錯覚していた
Wavelet Matrix | PDF
C#／Scala／Python／Ruby／F#でデータ処理はどう違うのか？
Block Nested Loop Join／Batched Key Access Join
