完備辞書（簡潔ビットベクトル）の解説 - アスペ日記
以前、「簡潔データ構造 LOUDS の解説」というシリーズの記事を書いたことがあります。 LOUDS というのは木構造やtrieを簡潔に表すことができるデータ構造なのですが、この中で「簡潔ビットベクトル」というものについてはブラックボックスとして扱っていました。 また、中学生にもわかるウェーブレット行列を書いたときも、その中で出てきた「完備辞書」の実装には触れませんでした。 この「簡潔ビットベクトル」「完備辞書」は、同じものを指しています*1。 今回は、このデータ構造*2について書いてみます。 完備辞書でできること ビット列に対する定数時間の rank と selectです*3。 rank()は、「ビット列の先頭から位置 k までに、1 のビットがいくつあるか」*4。 select()は、「ビット列の先頭から見て、n 個目の 1 のビットの次の位置はどこか」*5。 それぞれ例を挙げます。
腐った翻訳に対する態度について - アスペ日記
今回、SICPの翻訳改訂版を公開するにあたって、minghai氏の非公式日本語版（以下、minghai氏版）については「惨憺たる翻訳」「そびえ立つクソの山」などと書きました。これらの言葉は、もちろん本心からのものです。しかし、それを表に出すかどうかについては、冷静に考えた結果として意図的に選択したことも確かです。ここでは、その背景について書こうと思います。 約一年前、私が善意のひどい訳についてという記事を書いたとき、しぶかわよしき様から以下のコメントをいただきました。 趣味のお金にならない翻訳だとだいたい最初の下訳で出しちゃいますね。だからといってそれが悪いことだとは思いません。英語を読まない人は言うまでもなく、英語を読める人でも「下訳」があれば原文を読む時にの速度は上がりますからね。クオリティに対して個人でできることといえば、指摘などで黙々と時間コストを代わりに負担するか、takeda2
半年で（メジャーな）第二外国語を身につける方法 - アスペ日記
英語学習エントリに触発されて、第二外国語学習エントリを書いてみようと思います。 英語とその他の外国語で、学習方法が本質的に違うということはもちろんないのですが、中高 6年間にわたって学校で勉強する英語と、基礎がほとんどない状態から始める第二外国語では、細かいところでいろいろと違いがあります。 ちなみに私自身は、これまで英語以外には中韓西伊仏独露の 7言語を学んでいます（レベルはまちまち）。この中で中韓は留学して身につけた（中国に一年留学、ルームメイトが韓国人）もので、その他は日本国内で学んだものです。 今回は、日本国内で勉強するやり方について書こうと思います。 注意事項は次の 3点です。 私が学んだ言語は、すべて日本国内で教材が豊富に手に入る「メジャー外国語*1」ですので、マイナーな外国語には適用できない部分も多いかと思います。ご了承ください。 途中で高価な教材を紹介し、それの使用を前提と
「C言語でプログラミングする際の覚書」の誤訳箇所 - アスペ日記
ここでは、C言語でプログラミングする際の覚書の誤訳を列挙します。 参考として、私の翻訳はC言語プログラミングの覚え書き（改訳）にあります。 What follows is ... ×従うべきは ○これから述べるのは "What follows" で「続くもの」という意味です。ここでの「続く」というのは、現在の文章に続く、つまり「以下に述べること」です。 But they've been accumulating in my head, if not on paper until now, for a long time, ... ×しかし、私の意見は頭のなかにしばらくあったものをまとめたものであり、長らく文章として公開してきませんでした。 ○しかし、これらのことは、文書として書いたことはありませんでしたが、私の頭の中に長い時間をかけて蓄積してきたもので、… "if not on paper
いつからその方法で偏りのない乱数が得られると錯覚していた？ - アスペ日記
私はつい最近まで勘違いしていました。 ここのページに書いてあるような方法で、一様分布する整数が得られると。 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 がダウト。 思いっきりダウ
ウェーブレット行列の省メモリ構築方法 - アスペ日記
ウェーブレット行列の構築方法について。 前に書いた記事とは違って、「ウェーブレット行列大好き！」って人*1以外が読んでもあんまり益がない記事だということをあらかじめ書いておく。 内容としては、相変わらず中学生以上の知識が必要ということはないけれど。 上の記事で書いたように、ウェーブレット行列は 2進数の基数ソートと同じような感じで構築できる。 で、基数ソートをするには、元の配列と同じだけの領域が必要になる。 だが、ウェーブレット行列のように各段階でのビット列だけが必要であるなら、その領域は必要ない。 ウェーブレット行列でも、ウェーブレット木のノードのようなものを持っておくことで、配列長のオーダーでなく、文字の種類のオーダー（一般的に配列長よりずっと小さい）だけの記憶領域で構築できる。 ぼくのウェーブレット行列ライブラリである wavelet-matrix-cpp や、 id:echizen
中学生にもわかるウェーブレット行列 - アスペ日記
id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix"」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。 …嘘です。 日本以外ではあんまり来ていません。 理由としては、やはりアルファベット圏では単語境界が明確であるため、こちらの記事で書かれているような「キーワード分割の難易度」といったことがあまり問題にならないということがあるかもしれません。 まあ、そういうわけで局所的に来ているウェーブレット行列ですが、日本語をはじめとする単語境界のない言語圏にとっては重要なネタであると思うため、解説記事を書き直して*1みようと思います。 ウェーブレット行列でできること 主となる操作は、文字列に対する 定数時間の rank() と select()*2 です。 rank() は、「文
べき分布する整数データの圧縮方法 - アスペ日記
今更ながら、Faster and Smaller N-Gram Language Modelsを読んでみました。 この記事については、すでにACL2011論文「Faster and Smaller N-Gram Language Models」を読んだ - EchizenBlog-Zwei やN-gram 言語モデルを圧縮するには - やた＠はてな日記で紹介されているので、自分が興味を持ったところを少しだけ。 上の紹介記事でも言及されているように、この論文では N-gram を [token, context] の形で格納しています。token と context はどちらも ID。この形でソートすると、token も context も前のデータとの差が小さくなるので、差分を取ると小さい数が多い「べき分布」になるから圧縮しやすくていいよね、という話（だと思います）。 その圧縮方法というの
情報系修士にもわかるダブル配列 - アスペ日記
最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。 trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。 ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、この本の説明を読むことで理解ができた。 ありがたい。 感銘を受けたので、この本を教材に友達と2人勉強会をした。 この2人勉強会というのは、ぼくが復習を兼ねて友達に教えるというのがだいたいのスタイル。 しかし、いざやってみるといろいろと難しい。 次のようなところでひっかかるようだ。 例のサイズが小さく、イメージを喚起するのが難しい。 最初の図のノード番号と、最終的なダブル配列上の位置が異なるため、混乱する。 単語終端について言及がないので、どのノードが単語を表しているかがわから
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
