完備辞書（簡潔ビットベクトル）の解説
以前、「簡潔データ構造 LOUDS の解説」というシリーズの記事を書いたことがあります。
LOUDS というのは木構造やtrieを簡潔に表すことができるデータ構造なのですが、この中で「簡潔ビットベクトル」というものについてはブラックボックスとして扱っていました。
また、中学生にもわかるウェーブレット行列を書いたときも、その中で出てきた「完備辞書」の実装には触れませんでした。
この「簡潔ビットベクトル」「完備辞書」は、同じものを指しています*1。
今回は、このデータ構造*2について書いてみます。
完備辞書でできること
ビット列に対する定数時間の rank と selectです*3。
rank()は、「ビット列の先頭から位置 k までに、1 のビットがいくつあるか」*4。
select()は、「ビット列の先頭から見て、n 個目の 1 のビットの次の位置はどこか」*5。
それぞれ例を挙げます。
"0100100111011110" というビット列（B とします）の中で、先頭から位置 12 までの間に、いくつ 1 があるか。
下の図で、先頭から矢印までの範囲の 1 を数えることになります。
数えてみると、6つあります。
つまり、rank(B, 12) = 6 ということになります*6。
また、このビット列の中で、4 個目のビット 1 の次の位置はどこか。
下の図は、先頭から 4 個の 1 に色をつけたものです。
4番目の 1 は位置 8 にあるので、その次である位置 9 が求めるものです。
つまり、select(B, 4) = 9 ということになります*7。
先頭から順に数えるというやり方では、サイズが大きくなるとこれらの操作には長さに比例した時間がかかりますが、完備辞書を使うと、これらの操作が定数時間で可能になります。
実装
ここでは、完備辞書の代表的な実装例を挙げます。
元のビット配列 B に加え、3 つの補助データを持つというものです。
それによって、定数時間での rank() が可能になります。
まず、一つ目の補助データです。
B の長さを n とすると、B を長さ lg(n) ^ 2 ごとの大ブロックに分割して、それぞれの大ブロックの先頭の rank() の結果を保存しておきます。
ここで、仮に B の長さ n が 2 ^ 16, つまり 65536 ビットだとします。
すると、lg(n) = 16 なので、lg(n) ^ 2 = 256 になります。
つまり、一つ目の補助データは 256 ビットごとに持っておくことになります。
記録するべきものは、0, 256, 512, ... の位置の rank() の結果です。
まず、位置 0 の rank()、つまり「位置 0 の左にいくつ 1 があるか」を考えます。
位置 0 は左端なので、答えは当然 0 になります。
これが、補助データの最初のものになります。
次に、位置 256 の rank() です。
位置 256 まで（下の図の A の範囲）に、いくつ 1 があるかということです。
この画像では途中が省略されているのですが、実際にはビット列があるので、数えればわかります。
たとえば 131個あったとすると、rank(B, 256) = 131 を補助データの次の要素として記録します。
その次は位置 512 の rank() です。
たとえば、256〜511 （図の A' の範囲）に 1 が 137 個あったとします。
この場合、記録する rank() は先頭からのものなので、B の範囲にある 1 のビットの数ということになります。
A の範囲には 131 個あったので、それに 137 を加えた 268 を書き込むことになります。
同じように、位置 768, 1024...についても先頭からの rank() を求めて、最後まで埋めます。
そして、次は二つ目の補助データです。
今度は、一つ目の補助データで分割した大ブロックを、さらに小ブロックに分割します。
小ブロックのサイズは、B の長さが n のとき、lg(n) / 2 のように決めます。
すると、n = 65536 のとき、小ブロックのサイズは lg(n) / 2 = 16 / 2 = 8 となります。
二つ目の補助データでは、この小ブロックごとに rank() を保存するのですが、保存するのは大ブロックの先頭との差分です。
たとえば、ビット列 B の 512 ビット目からの部分が次のようになっているとします。
すると、小ブロックは次のように、8 ビットごとの単位になります。
小ブロックについてもそれぞれ rank() を記録するのですが、小ブロックについては、それが属する大ブロックの先頭からの差分として記録します。
上の図で、512 からの小ブロックは大ブロックの先頭なので、記録する rank()（512からの差分）は 0 です。
次の 520 からの小ブロックは、512〜520 の間に 5 個の 1 があるので、5 を書き込みます。
528 からのものは、520〜528 の間に 3 個の 1 があるので、520 までのものと合わせて 520からの差分は 5 + 3 = 8 です。
同じように、位置 536 以降についても、位置 512 からの 1 のビットの数の累計を書いていきます。
すると、小ブロックについて書き込む数字は次のようになります。
さて、このように大ブロックと小ブロックについて、それぞれ rank()（またはその差分）を記録すると、何がうれしいか。
それは、小ブロックの先頭までの rank() を定数時間で求められる ということです。
たとえば、このデータを使って、位置 533 までの rank()、つまり rank(B, 533) を求めたいとします。
図の中では、次の場所です。
この位置の rank()、つまり先頭からの 1 のビットの数は、位置 533 が属する大ブロック・小ブロックを調べれば*8次のように分解できます。
- 位置 0 から 位置 512 までの 1 のビットの数
- 位置 512 から 位置 528 までの 1 のビットの数
- 位置 528 から 位置 533 までの 1 のビットの数
最初の 2 つについては、上で作った表を参照することで求めることができます。
まず、位置 0 から位置 512 までの 1 のビットの数です。
位置 512 から始まる大ブロックの rank() ということになるのですが、それは最初に作った表に書いてあります。
表によると、位置 512 までには 268 個の 1 のビットがあることがわかります。
次に、位置 512 から位置 528 までの 1 のビットの数です。
小ブロックについては、大ブロックの先頭（この場合、位置 512）からの差分の rank() が記録してあるので、それを見ます。
位置 512 から位置 528 までには、8 個の 1 のビットがあるということがわかります。
ここまでで、位置 528 までに 268 + 8 = 276 個の 1 のビットがあることがわかりました。
残りは、位置 528 から 位置 533 までのビット数ということになります。
位置 528 から 位置 533 の範囲は、次の灰色の部分です。
パッと見で、1 のビットは 2 個だということがわかります。
この例では、小ブロックのビット数は 8 なので、一瞬で数えることができます。
しかし、コンピュータは目で見て数えるということはできないので、3つ目の補助データを用意します。
ここで作るのは、ビット列にあたる数字の位置に、そのビット列が持つ 1 のビットの数を書いたテーブルです。
たとえば 8 ビットの場合、8 ビットで表せる数字は全部で 256 個なので、そのひとつひとつに対して 1 のビットの数を書いていきます*9。
次のような表です。
添字を 2 進数で表すと、数字が添字の 1 のビットの数に対応するというのがわかりやすいかと思います。
さて、今回の例で知りたいのは、位置 528 から位置 533 の間にいくつ 1 のビットがあるかです。
知りたい範囲を含む小ブロックのビットは次のようになっています。
この範囲から外れる部分を、ビットマスクで 0 にします。
そして、先ほどの表で、10010000（144）にあたる場所を見ます。
これで、10010000 の中の 1 のビットが 2 個であるということがわかります。
これで、位置 533 までに 268 + 8 + 2 = 278 個の 1 のビットがあることがわかりました。
作る補助データをまとめると、次のようになります。
- 大ブロック(長さ lg(n) ^ 2)ごとに、先頭からの rank() を記録したもの
- 小ブロック(長さ lg(n) / 2)ごとに、所属する大ブロックの先頭からの rank() を記録したもの
- 小ブロック(長さ lg(n) / 2)のすべてのビットパターンに対して、それの持つ 1 のビット数を記録したもの
ここまでの内容を知っていれば、完備辞書を作り、検索するプログラムを作ることはできます。
ですが、完備辞書にはある都合のよい性質があり、それがこのデータ構造の特徴となっています。
それは、元データの大きさが増えても、補助データの大きさはそんなに増えないということです。
どういうことか、具体的に見てみます。
まず、元データ B のビット数を、上での例のように n とおきます。
このとき、大ブロックの数は、n / (lg(n) ^ 2) となります。
ここで、それぞれの大ブロックに対して先頭からの rank() を記録するのですが、そのデータひとつあたり何ビット必要かわかるでしょうか。
それは lg(n) です。
元データ B の中での先頭からの rank() は、n 以上になることはありません。
0 以上 n 未満の数を表すのには、n が 2 ^ m で表せる形であれば*10、m ビットが必要です。
つまり、lg(n) ビットが必要ということになります。
今回の例で言うと、rank() は 0 以上 65536 未満で、65536 = 2 ^ 16 なので、rank() ひとつを表すのに 16 ビットが必要ということになります。
大ブロックの数は n / (lg(n) ^ 2) 個なので、それに lg(n) ビットをかけると、合計 n / lg(n) ビットになります。
これが、大ブロックのデータ格納に必要な容量ですが、 n / lg(n) なので、n が増えるに従って元データに対する割合は小さくなります。
次に、小ブロックについて考えます。
それぞれの小ブロックに対しては、大ブロック先頭からの rank() を記録するということになっています。
つまり、この差分の rank() は、大ブロックの大きさである lg(n) ^ 2 以上にはなりません。
数字ひとつを記録するのには、lg(lg(n) ^ 2)、つまり 2 * lg(lg(n)) だけのビットが必要ということになります。
小ブロックの個数は n / (lg(n) / 2) 個なので、小ブロック全体として必要なビット数は (n / (lg(n) / 2)) * (2 * lg(lg(n))) = n * 4 * lg(lg(n)) / lg(n) です。
lg(lg(n)) より lg(n) のほうがオーダーが大きいので、これもやはり n が増えるに従って元データに対する割合が小さくなります。
最後に、小ブロックのビットパターンそれぞれに対するビット数の表を考えます。
小ブロックの大きさは (lg(n) / 2) なので、要素ひとつあたりに必要なビット数は lg(lg(n) / 2)、つまり lg(lg(n)) - 1 です。
そして、表の要素数は (lg(n) / 2) 個のビットで表せる数だけ必要なので、2 ^ (lg(n) / 2) = n ^ (1 / 2)、つまり √n です。
また、ビットマスクをしない場合（上で脚注として書いた部分）を考えると、検索位置ごとに表を作ることになるので、小ブロックの大きさである lg(n) / 2 個となります。
表の要素数と、要素ひとつあたりに必要なビット数、それに表の個数をかけると、√n * (lg(lg(n)) - 1) * lg(n) / 2 なので、やはり n よりも小さいオーダーということになります。
そういうわけで、元データよりも小さなオーダーの補助データを使って、任意の位置の rank() が定数時間で求められるという話でした。
いい話ですね。
さて、記事の最初のほうで、rank() に対応する select() というものに触れたのを覚えているでしょうか。
select()は、「ビット列の先頭から見て、n 個目の 1 のビットの次の位置はどこか」。
この select() というのは、rank() に比べると、使いどころはだいぶ少ないのですが、たとえば LOUDS などでは使いまくるので、これも定数時間でできてほしいところです。
で、これも一応、元データよりも小さいオーダーの補助データを使って、定数時間で調べることができるようですが、こっちのほうは実装がかなり大変なうえ、補助データや検索時間の定数項も大きかったりするので、日和って rank() 用のブロックを二分探索したりしたり線形探索したりするのが普通です。
あんまりいい話じゃないですね。
rank() のほうも、n によって大きさを変えたりしないで、大ブロックと小ブロックの大きさを適当に決めて実装するのが普通です。
小ブロック中の 1 のビットを数えるのも、脚注で書いたように「検索位置ごとの表を作る」ということは普通やりません。
結局、定数時間とかはあんまり関係なくて、rank() と select() があんまり容量を取らないでけっこう速くできるというのが重要なポイントなので、実装をする際には時間を計ったりしながら適当に試行錯誤するのがいいのかもしれません。
ところで、実装時に注意することとして、小ブロックの rank() を記録するのに、サボって 32bit 型などを使わない ということがあります。
わざわざ大ブロックと小ブロックを分けた意味は、小ブロックに対して記録する rank() を小さくしてオーダーを抑えるということなので、小ブロックの rank() と大ブロックの rank() に同じサイズの型を使うなら、大ブロックを作る意味がありません。
もっとも、大ブロックを作らないで小ブロックだけで実装するというのもひとつのやり方だと思いますが、その場合「簡潔データ構造」ではなくなります（元データと同じオーダーの補助データが必要になるため）。
ここに書いたような内容は、「高速文字列解析の世界」や「日本語入力を支える技術」にも書いてあります。
この記事を書きながら、「ここまで詳しく書く必要があるのか」と思って「幼稚園児にもわかる完備辞書」というタイトルにしようかと思いましたが、さすがに思いとどまりました。
でも、まあ普通の大学生が真面目に読めばわかるんじゃないのかなぁぐらいには考えています。
*1:Wikipedia では、簡潔データ構造の項で簡潔辞書という名前で扱われているようです。
*2:今回の記事では「完備辞書」で統一します。
*3:実は、selectは後述するように定数時間でない実装が一般的です。
*4:rank1とすることが多いのですが、ここでは略しました。
*5:rank との対称性のために、直感的に少しわかりにくくなっています。
*6:引数は前からビット列、位置です。
*7:引数は前からビット列、1 の個数です。
*8:ビットシフトなどで求められます。
*9:これは実用寄りの話です。理論的にはビットマスクも lg(n) なので、それを避けるためか、小ブロック中の検索位置ごとに表を作るということをするようです。この例では、このような表を 8 個作ることになります。しかし、それを言うなら表のインデクシングとかも定数ではないような気がするのですが。
*10:そうでない場合は切り上げます。
「障害」書き換え説，あるいは戦前の雑さ
いつごろから広まったのか知りませんが、“「障害」は本来「障碍」と書くのに、戦後になって「障害」と書くようになった”という俗説があります。
結論から書きます。
「障害」は戦前からある書き方です。
今はGoogle ブックスという便利なものがあるので、画像を貼っておきます。
別表ニ掲グル身體障害二以上存スルトキハ重キ身體障害ノ該當スル等級ニ依リ障害扶助料ヲ支給スベシ
百聞は一見にしかず、ですよね。
この話はここでおしまいです。
…なのですが、どうしてこの手の俗説が絶えないのか、少し考えてみます。
この考え方の背景には、「社会は間違っている、自分は正しいことを知っている」という中二病的心理があるように思います。
典型的なのが、コラムニストの小田嶋隆さんに絡んでいる次のツイートのようなものです。
「真実を知っている自分」に酔っている様子がにじみ出ていますね。
そもそも、戦前の日本語を知っている人であれば、そのころは「障害」「障碍」「障礙」の三つが使われていたということは常識です。
たとえば、次の朝日新聞の記事があります。
「障害者」か「障碍者」か 「碍（がい）」を常用漢字に追加求め意見
戦前は障害や障碍、障礙（しょうがい）（礙は碍の本字）が妨げの意味で使われた。戦後、碍は当用漢字にも常用漢字にもならず、障害が定着した。
早とちりな人がこの文を読むと“そうか、「障害」は本来「障碍」「障礙」と書くのか”と思ってしまいそうなところですが、ちゃんと一語一語そのまま読むと、「障害や…」という部分があるんですよね。
きちんと読めば、「障害」が昔から使われていたと書かれていることがわかるようになっています。
じゃあ、戦前の「障害」「障碍」「障礙」には使い分けがあったのか。
そんなものはありません*1。
たとえば、「兒童心理學序説（大正十三年）」という本から引用します。
6個のうち3個が「障害」で、3個が「障碍」です。
この中で「障害」と「障碍」に使い分けがあるか。
考えるだけ無駄でしょう。
だいたい何でも、人間は昔に遡るほど雑に生きています。
昔の人間は考え方が雑なので、本の校正をする人でさえ、「障害」でも「障碍」でもどっちでもいいやみたいに考えていたりしたわけです。
今でも、ネット上の文章などでは表記が適当なものが多くあります。
たとえば、同じ文章の中で「目」と「眼」を何の基準もなく適当に交ぜていたり。
それと同じように、戦前にも「障害」「障碍」「障礙」を適当に使っている人が多くいたわけです。
「障害」の「害」の字はよくないから「障碍」と書こうとか、平仮名で「障がい」にしようとか言うのは、それは個人の意見なので好きにすればいいと思いますが、浜の真砂のように現れる「『障害』は本来『障碍』と書くのに、戦後になって「障害」と書くようになった」という間違った思い込みだけは何とかしてほしいなぁと思います。
戦前は旧字体・旧仮名遣いだったので、難しい書き方をみんな使いこなしていたかのようなイメージを持っている人もいるかもしれませんが、今より雑な人たちが書いていたので、当然使いこなせなくて間違いだらけでした。
戦後の当用漢字や現代かなづかいについて、日本語をダメにしたというように言いたてる人もいますが、それまでの日本語表記の適当さ・いい加減さが背景にあり、それを整理した結果として現在の日本語があるということは知っておいてほしいと思います。
ところで、この記事も相当雑なので、ツッコみどころはいろいろあると思います。
その中の一番は、「しょうがい」と「しょうがいしゃ」は別の話じゃないか、というものだと思います。
とりあえず適当に、「精神障害者」「視力障害者」「精神障碍者」「視覺障碍者」の例を挙げておきます。
（本当は用例数や年代ごとの移り変わりなども考えないといけないところだと思いますが、それは詳しい人に任せます）
この「しょうがい（しゃ）」問題は地雷のようで、過去にもtogetterまとめがあったりします。
誰か「碍」を常用漢字に追加することで生じる社会的不利益について説明してくれよ
私個人としては、この議論は不毛そうなのであまり立ち入りたくはないのですが、「書き換えだ」という誤解があまりにも多いので見ていられずに書くことにしました。
こういう「権威を叩く」的な考えは気持ちがいいから、どうしても広まってしまうんでしょうね。
正書法のない日本語 (そうだったんだ!日本語)
posted with amazlet at 14.01.13
話は変わるのですが、同じタイプの思い込みとして、古い話ですが“「NHKの紅白で山口百恵は『真っ赤なポルシェ』を『真っ赤なクルマ』と変えて歌わされた」”というものがあるようです。
実際は「普段の歌番組では『真っ赤なクルマ』にされていたが、紅白だけは『ポルシェ』だった」というもので、検証している記事があるのですが、そのコメント欄に
私が小学生か、中学生の頃のある年の紅白で、真っ赤なくるまと歌ってるのをこの目で見て、聴いて、子供ながらに非常に違和感を覚えた記憶があります。
私もこれ見ていましたが、「真っ赤な車」と言っていましたよ。
と書いている人がいたりして、気持ちのいい考えの影響力（記憶改竄力）というのは恐ろしいものだと思わされます。*2
「間髪をいれず」が殺された日
最近、マイナビウーマンが「日本語を貧しくしようキャンペーン」を展開しているようです。
間違っている読み方が定着していると知らずに使っていた日本語1位「輸入(ゆにゅう)【正】しゅにゅう」
「正しい日本語」ネタはPVが稼げるのでしかたないのでしょうが、日本語が金儲けのネタにされるのを見ると悲しくてなりません。
この中で、見逃せないのは次の部分です。
■番外編:これは明らかな間違いです
・間髪を容れず(かんぱつをいれず)【正】かん、はつをいれず「これだけは知っていた」(26歳男性/学校・教育関連/事務系専門職)
■間髪をいれず(×かんぱつをいれず→○かんはつをいれず)
こういうのは、いい大人が見たらあきれてしまうところです。
「何をバカなことを言っているんだ、『かん、はつをいれず』なんて聞いたことないよ」と。
もちろん、中国語や漢文をやっている人であれば、この言い方は中国語の「間不容髮」、すなわち「あいだに髪の毛を入れるすきまもない」というものから来ているので、日本語でも昔は「かん、はつをいれず」だったという知識はあるかもしれません。
でも、実際にそう発音する人はとっくの昔に死に絶えていて、今は誰でも「かんぱつをいれず」と言っているということも、いい大人ならみんな知っているところです。
記事を書いた人間のゴミどもも、そのことを知らないわけはないと思うんですけどね。
どのくらい昔から「かんぱつをいれず」が使われていたかというと、もう100年も前の本にも出てくるほどです。
非常に見にくいですが、拡大して、右上の「廢刀（はいたう）」や右下の「傍（かたは）ら」と比べると、違うのがわかると思います。
さらに、そのころにはこの「間髪」は一語として認識されていて、「此の間髪の機に乘じ」などのようなものも見られます。
Google Books「世界大戦史: 一九一四年. 後篇」
そういうわけで、100年前にはすでに一語となっていた「間髪」ですが、その後単独での用法はすたれたものの、「すかさず」という意味での「カンパツをいれず」は残りました。
国語辞典などは保守的なものが多いので、「『カン、ハツをいれず』が正しい」と書かれていたりしたのですが、もちろん人は国語辞典を読みながら話すわけではないので、国語辞典と話し言葉の間にずれがあるまま、共存状態が続いていたわけです。
しかしそれは、薄っぺらい知識で「正しい日本語オナニー」を始める輩が出てくるまでのことでした。
上に挙げたマイナビウーマンの二つの記事は、それだけでは影響力は限られていますが、すでに2chやまとめサイトに波及して、手がつけられないほど拡散しています。
こうやって「『カン、ハツをいれず』が正しい」というミームが広がってしまうと、もうどうしようもありません。
「『カン、ハツをいれず』が正しい」というミームが広がると、何が問題なのか。
それは、「間髪をいれず」という言い回し自体が死んでしまうからです。
人は、聞いたことのない言葉を書くことはできても、話すことはなかなかできません。
頭の弱い人が「そうか、『カン、ハツをいれず』が正しいんだ」と思ったとしても、明日から「そこで、カン、ハツをいれずこう言ってやったんだよ」のように言うということはなかなかできません。
そんな風にしゃべると、そもそも通じないですから。
聞く側に「昔は『カン、ハツをいれず』だった」という知識があれば、3 秒ぐらいたってから理解できるかもしれないですが、私なら「え、今の何？ カン、ハツをいれずって言った？ ごめん、面白いからもう一回言ってみて（笑）」と返してしまいそうです。
こうなると、「カンパツをいれず」が間違っていると言われる一方で「カン、ハツをいれず」と言うこともできないので、話し言葉からだんだんと消えていくことになります。
文章の上では、上の記事を書いたような輩が「間髪（かんはつ）をいれず」なんて書きながら「正しい日本語書くのギンモヂイイイイイィィィィィィ」とオナニーにふけるのがしばらく続くかもしれないですが、話し言葉から消えてしまえば、見せつける相手もいなくなるのでオナニーもおしまいです。
言語純粋主義者からしたら、「間違った日本語なんて消えてもかまわない」というところかもしれないですが、これまで実際に話されてきた生きた日本語を愛してきた自分としては、とてもそういうふうには思えません。
今後「『カンパツをいれず』は間違っている」ミームが増えるようなら別の言い方をせざるを得なくなりますが、「間髪をいれず」が殺されたという恨みはずっと持ち続けると思います。
しかし、こういうことはこれが初めてではありません。
ネット以前の時代ですが、「的を得る」が血祭りに上げられたときのことをよく覚えています。
そのころ、話し言葉ではみんな「マトオエタことを言う」というように言っていた*1のに、どこかのバカが「『的を得る』というのは理屈に合わない」とか「伝統的ではない」とか言い出して、実質的に「的を得る」が禁止されてしまいました*2。
まあ、今となっては「みんな『マトオエタ』と言っていた」という証拠なんてない*3ですが、少なくとも私の実感としては「マトオエタ」「マトオイタ」のどちらが正しいのか迷ったということはなく、「マトオエタ」が一方的に禁止されたというものです。
それ以来、私は「マトオエタ」とも「マトオイタ」とも言っていません。前者を言えば、知ったかぶりのバカにくだらないことを言われるのが目に見えてますし、かといって誰からも聞いたことのない後者を使う気にもなれません。
そういうときには適当に言い換えていますが、語彙からひとつの単語が「消された」恨みは今でも残っています。
こうした「言語純化」みたいなものは、多くの場合は失敗して単純に言語が貧しくなるだけで終わりますが、「重複」は最近純化が成功して、チョウフクが主流になりつつあるようです*4。
この場合は、ジュウフクが一般的だったものの、チョウフク派も少し生き残っていたからですね。
ちなみに、平成15年の文化庁の調査では「じゅうふく」が76％だったので、この10年で「じゅうふく」の言葉狩りが進んだということのようです。
しかし、成功したからといって、良くなったことは何一つありません。
中国語では「重い」という意味と「重なる」という意味で発音が違うのですが、日本語のジュウ・チョウはただの呉音と漢音の違いなので、「重箱」「五重塔」は重ねるのにジュウだったり、「貴重」「尊重」は「重要」という意味なのにチョウだったりと、法則がありません。
法則がない中で、「重複」という一語をジュウフクと読もうがチョウフクと読もうが、どうでもいい話です。
ちなみに今後は、「依存」「既存」「共存」などのイゾン・キゾン・キョウゾンという読みに対する言葉狩りが進むんじゃないかと思っています。
私は今はまだそれらを使っているのですが、これもいつ知ったかぶり野郎どもに「間違った読み」扱いされるかと不安です。
ところで、「間髪を『いれず』」の漢字ですが、「容れず」と書くこともできますし、「入れず」と書くこともできます。
前者は中国語的な書き方で、後者は日本語的な書き方というだけのことで、昔からどちらもあります。
日本語が中国語と肩を並べるれっきとしたひとつの言語だという考え方は、今でこそ当たり前ですが、120年ほど前に日本初の近代的国語辞典といわれる「言海」ができた時代にも、そうした考え方はまったく一般的ではありませんでした。
「言海」の序文は漢文で書かれていますが、これは「俗な言葉」である日本語の辞書を出版するにあたって、「正しい言葉」である漢文による権威付けが必要だったからですね。
その後、日本語がまともな言語であるという考え方はだんだんと受け入れられるようになったものの、漢文の呪縛から脱するようなはっきりしたイベントがあったわけではないので、「間髪をいれず」のように、「漢文の理屈では…」のようなことを言う輩が絶えないわけです。
そんなに中国様が好きなら、中国に帰化したらいいと思うんですけどね。中国語ではちゃんと「間不容髮」と言っていて、（彼らの目には）愚かな夷狄の国である日本みたいに、たとえば「不容間髮」とか「間不入髮」とか間違った言い方はしないので、オナニー野郎が身につけてひけらかすにはぴったりだと思います。
ところで、最近「アスペ日記」というタイトルに絡めたコメントをされることが時々あります。
そういうのを見ると、「アスペ*5」というものに変なイメージを持った人が多い気がします。
辞書を暗記したり、現実から離れた言語を使っていたりとかしているように思われていそうです。
でも、実際のところは、アスペというのは「権威に従う」「雰囲気を読む」といった人間的な能力が欠けているだけです。
「間髪をいれず」の例のように、国語辞典といった権威にへつらって、自分や父母や祖父母が使ってきた言葉を否定したり、「重複」の例のように、「みんなこっちが正しいって言ってる」という雰囲気を読んで、それまで多くの人が使ってきた読み方を間違っていると言ったり、そういう人間的な、あまりに人間的な営みを見るにつけ、とてもアスペにはついていけない*6と思わざるを得ません。
Googleのヒット件数について（続き）
Googleのヒット件数は当てにならないの続きです。
はてブで id:blueboy さんという方が
文中の「ページを進めると数が急減したのは、すべての結果を取得して件数が判明した」は誤りです。正しくは「途中で表示をやめるから」です。
と書いていたので、フォローアップ記事を書くことにしました。
フォローアップ記事なんてPV取れないし、そのコメントを見た人が読むことも少ないでしょうし、書いてもむなしい気もしますが。
むなしさを紛らすためにアフィリエイトを貼るので踏んでください。
Coders at Work プログラミングの技をめぐる探求
posted with amazlet at 13.11.07
さて、ブコメのリンク先の記事◆ Google の検索ヒット件数の謎について。
「安倍晋三 facebook 田中均」というキーワードで検索しているようです。
それで、結果が222件しか返ってこないと言っています。
（略）
最も的確な検索結果を表示するために、上の 222 件と似た
ページは除外されています。
検索結果をすべて表示するには、ここから再検索してください。つまり、たったの 222件しか表示されない。
これはどういうことか？ 実際にヒットした件数は 222件しかないということか？
いや、メッセージ読んでください…。
ここから再検索してください。って書いてあるのに。
再検索すると、だいぶ結果が増えます。
最後のほうのページはこんな感じになります。
だいたい 950件ぐらいまで結果が表示されたところで終わりになります。
これは Google の制限ですね。
試しに URL でパラメータをいじって 1000件目以降を表示させようとするとこういうメッセージが出ます。
1000件以降を表示しないのはわざとということです。
これは Google を少し使っている人間にとっては常識です（だと思います）。
じゃあ、最初の 222件というのは何かというと、重複したものをまとめた結果の件数です。
ちゃんと書いてあります。
最も的確な検索結果を表示するために、上の 222 件と似た
ページは除外されています。
つまり、Google のやり方としては、上位 1000件ほどの検索結果の中から、重複を除外しながら結果を表示しているということだと思われます。
その結果が 222件ということですね。
で、この場合は確かに途中で表示を（というか検索を）やめています。
しかし、それには条件があって、それは重複を除く前の検索結果が 1000件以上ある場合というものです。
"無い内定式" の場合は、重複を除いた検索結果が 49件で、除く前でも 500件ほどしかなかったので、これはそのパターンじゃないと思ったわけです。
（ただ、実際はフィルタのかかり具合によっては 1000件以上あるものが 500件しか残らないということもあるでしょうし、確かなところはわかりません）
私は検索に携わったことはないのですが（Google にいたことはありますが、検索にはまったく関わっていません。関わっていたら逆に何も書けないところです）、利用者としてはもう 10年以上 Google を使っているので、だいたいこんな感じでやってるんじゃないかというものはあります。
流れとしては、こんな具合じゃないでしょうか。
1. 結果を10件を表示するために、それより多めに上位の結果を取ってきて、不適切な結果をフィルタリングして重複を除いて10件残して、いい加減に推測した件数と一緒に表示する*1
2. さらに要求されたら、上位1000件ほどを取ってきて、不適切な結果をフィルタリングして重複を除いて、いい加減な件数と一緒に順次表示する
3. 最後のページ（数百件目）まで来ると、いい加減な件数の代わりにそこまでの件数を表示して、重複を除かない検索結果のリンクを出す
4. 重複を除かない検索結果を要求されたら、2で取ってきた1000件ほどをいい加減な件数と一緒に順次表示する
で、たとえば 2つの検索語の使われ方を比較したいという場合は、2 の段階で両方とも1000件を超えないようにすることがポイントになります。
そのために、平等に件数を減らすために適当な数字や固有名詞と一緒に検索するということをするわけです。
まあ、私が何を言っても推測にすぎないのですが、実際に検索エンジンに関わっている人が何かを書くわけもないので、推測以上のことはわかりません。
ここからは余談です。
検索エンジンの実力って、「エロじゃないけどエロと関連の強いキーワードで検索したときにどれだけエロくない結果を返せるか」に出ると思っています。
どういうことかというと、たとえば「清純」というキーワードで検索するような場合です。
Google（セーフサーチ：オン）では、次のような何の面白みもない結果が返ってきます。
これが bing（セーフサーチ：標準）だと、次のような感じです。
右の関連キーワードに「清純美少女エロ動画」があるわ、肌のあらわな動画のプレビューはあるわ、グラビアアイドルの公式サイトはあるわで、だいぶ派手な感じになっています。
逆に言うと、Google が上のようなつまらない結果を出せるというのは、裏にどれだけものすごい技術があるのか想像もつきません。
それで今回、「エロじゃないけどエロと関連の強いキーワード」ということで「女子高生」などで検索していたのですが、その途中で面白い現象がありました。
Google（セーフサーチ：オン）で 「bing 女子高生」で検索すると、結果が 1件も返ってこない*2のです。
これはどういうことなんでしょう。
再検索のリンクをクリックしても見つかりません。
推測ですが、10件より多少多めに取ってきた中から不適切な結果をフィルタリングするうちに表示できるものがなくなったんじゃないかと思っています。
そうだったら笑えるのですが、どうでしょうね。
ちなみに、「bing 女子大生」などは正常です。
以上、検索エンジンに関するどうでもいい話でした。
検索エンジンはなぜ見つけるのか ―知っておきたいウェブ情報検索の基礎知識
posted with amazlet at 13.11.07
また余談ですが、「検索エンジンはなぜ見つけるのか」の収まりが悪いのは、「見つける」が意志動詞と無意志動詞の間の中途半端なところにあるからだと考えています。
これがちゃんとした意志動詞の「探す」なら、「なぜ探すのか」は「何のために」という読み一択です。完璧な無意志動詞の「見つかる」なら、「なぜ見つかるのか」は「どのようにして」という読みになります。しかし、「なぜ見つけるのか」だと、「何のために」「どのようにして」のどちらかが定まらなくなってしまいます。ただ、個人的には「何のために」の読みが強いと思います。
Googleのヒット件数は当てにならない
（2013/11/08: 補足を書きました。Googleのヒット件数について（続き））
「Googleの検索件数は当てにならない」と言うと、多くの人は「何をいまさら」という反応かもしれません。
当てにならないことぐらいわかってるよ、と。
でも、「当てにならない」でイメージするものがどの程度かは人によって違うと思います。
結果が2倍ぐらい違ったりする、程度に思っている人もいるかもしれません。
しかし、実際はそんなレベルでの話ではありません。
「本当は50件なのに500,000件と返ってくる」ようなことも珍しくありません。
たとえば、ツイッターで見たネタなのですが、"無い内定式" というキーワードで検索してみます。
267,000件。
多いですね。
ここで、10ページ目をクリックすると、次のようになります。
「59 件中 6 ページ目」*1
一気に4桁も減ってしまいました。
どちらが本当の数字に近いのでしょうか。
今回この件について書こうと思ったのは、最近ツイッターで、言語系の大学院生の方が次のようなことをつぶやいていたことがあったからです。
“뺏아서”848,000件なのに対して“뺏어서”345,000件。
ハングルなので違いがわかりにくいですが、「後者が規範的な形で、前者は非規範的な形なのに、前者のほうが数が多い」という文脈でした。
これを見てちょっとおかしいなと思い、ツイッター検索をしてみました。
すると、85万件のはずの前者のほうが、35万件のはずの後者よりもまばらです。
なぜこういうことが起きるのでしょうか。
一番の理由は、検索エンジンは「最適な検索結果を返す」ためのものであって「正確なヒット件数を返す」ことは目的としていないというものです。*2
検索エンジンは「最適な検索結果を返す」ことを目的に最適化されているので、ヒット件数はどうしても二の次になります。
ユーザが正確な件数を求めているなら、それも頑張って計算をするところでしょうが、実際のところはあまり求められていないようです。
その証拠に、モバイル版の Google 検索では件数の表示をやめています。
それでユーザーの不満の声が世間に満ちているということもないようです。
そういうわけで、検索のヒット件数は非常に当てにならない（数万倍のオーダーで違う結果が返ってくる）ため、ある表現がどれだけ使われているか、また表現Aと表現Bのどちらがよく使われているかといった指標にはなりません。
じゃあ、どうすればいいか。
上で書いたようなツイッター検索は手軽でいいのですが、これはあまりにも層が偏っている（若い層が多いなど）のではないかという懸念があります。
そこで私は、件数の多い少ないを知りたいときは、無関係なキーワードと一緒に検索ということをよくしています。
検索件数が当てにならないというのは検索結果が多い場合の話で、すべての結果が返されているときの件数は比較的正確なものになります。
上の「無い内定式」の検索で、ページを進めると数が急減したのは、すべての結果を取得して件数が判明したことによるものです。
表現Aと表現Bのどちらがどれくらい使われているかを知りたいとき、両方について同じように検索結果が減らすことができれば、平等に比較ができます。
その方法として、無関係な単語（リンゴでもミカンでも何でもいいのですが）と一緒に検索するというものが考えられるのですが、まったく無関係なものを選ぶというのも意外と難しいので、私は適当な数字を使うということをよくしています。
上の "뺏아서", "뺏어서" の場合、たとえば "26023" という数字と一緒に検索するとそれぞれ 4件と 19件となり、ツイッター検索の結果に近いものとなります。
この方法は、もちろん日本語にも使えます。
たとえば、「見当がつかない」と「検討がつかない」で、どちらがどれだけ使われているかを知りたいとします。
普通に調べると、それぞれ現時点で5,710,000件と2,700,000件です。
けっこう後者も健闘しているように見えて、いよいよ日本語も終わりかという気分になりそうなところですが、上で書いたようにこの数字は当てになりません。
そこで、適当な数字 "21163" と一緒に検索してみます。
（検索結果は最後のページまで見ます）
すると、次のようになります。
29:4 と、まだまだ日本語も捨てたものじゃないという感じですね。
（ただ、ツイッター検索では拮抗しているので、ツイッターのユーザー層ではすでに同じぐらい使われているということかもしれません）
ところで、日本語特有の注意点としては、1000以下の数字を使うと2chやそのまとめサイトが大量にヒットするので、件数は減らないわ結果は偏るわであんまりうれしくないことになってしまったりします。
そういうときは、適当な地名などを使ったりすることもあります。
ここで書いたような方法はバッドノウハウのようなもので、あまりきちんとした場に出せるようなものではないのですが、日本語や外国語の使用状況について直感を裏付けたりする程度には使えると思います。
（ところで、すごくどうでもいい話なのですが、「検索エンジンはなぜ見つけるのか」というのは変なタイトルのように思えます。なくした財布を見つけた人がいたとして、その人に「あなたはなぜ財布を見つけるの？」とか聞いたら、かなり哲学的な感じがしますよね。「検索エンジンはどうやって見つけるのか」のほうがいいと思うのですが、「プログラムはなぜ動くのか」のようなものに無理やり合わせたのでしょう。）
ビット逆転ループ
注意: この記事は読んでも役に立ちません。頭を無駄に使いたい人向け。
普通のループは、たとえば 0 から 255 までなら、0 -> 1 -> 2 -> ... というようにループする。
そういう普通のループじゃなくて、ビットを逆転させた数字でループできたらいいのになぁということが最近あった。
0 -> 128 -> 64 -> ... のように。
探してみると、そういうページが見つかった。
さすがネットは広い。
コードは以下の通り。
int r = 0; // counter
int s = 0; // bit-reversal of r/2<
int N = 256; // N can be any power of 2
int N2 = N << 1; // N<<1 == N*2
do {
printf("%u ", s);
r += 2;
s ^= N - (N / (r&-r));
}
while (r < N2);
思わず「ファッ！？」と声が出てしまいそうな実装だ。
しかし、よくよく考えてみるとそんなに難しいこともない。
ビット演算に慣れている人向けの説明は次のようなものになる。
逆順インクリメントをしたい数字を p として、その全体のビット数を m とし、p の上から連続した 1 の数を n とする。
- p をビット逆順インクリメントした数は、上から n+1 個のビットが立っていて残りが 0 の数字(X とする)と p との XOR をとることで求められる。
- X は、上から n 個の 0 が並び、その下に 1 があり、残りはすべて 0 の数(Y) を 2 の m乗から引くことで求められる。
- Y は、下から n 個の 0 が並び、その上に 1 があり、残りはすべて 0 の数(Z) で 2 の m-1乗を割ることで求められる。
- Z は、p の逆順の数字をインクリメントした数字（qとする）と、そのマイナスの数字との AND をとることで求められる。
よって、ループ中には正順のループカウンタ+1（q にあたる）を持っておけばいい。上のコードでは、r が q * 2 にあたる。
まあ、これは簡潔すぎるので、より詳しく説明する（それでも紙に書かないとつらいと思う）。
まず、
r&-r
ここは何をしているのか。
これは、「ビット列の中で、一番下にある 1 のビット」だけを取り出すというコード。
まず、r という数字が、下から n 個の 0 が並んでいて、その上に 1 がある（目的のビット）とする。
n、つまり下から見て並んでいる 0 の数は、r が 1010 なら 1 個、r が 1011 なら 0 個、r が 1100 なら 2個といった具合だ。
ここで、「その数字のビットを反転させたもの」を考える。
1010 なら 0101、1011 なら 0100、1100 なら 0011。
「下から n 個の 0 が並んでいる数字」のビットを反転させたものは、下から n 個の 1 が並んでいる。
これは当たり前だ。
ここで、元の数字と、そのビットを反転させた数字で AND 演算をすることを考える。
この演算では、すべてのビットが反転しているので、共通部分がなくて 0 になる。
たとえば、元の数字が 1100（下から 2個の 0 が並んでいる）、つまり 10進数で 12 の場合。
ビットを反転させた 0011（下から 2個の 1 が並んでいる）との AND は次のように 0 になる。
1100 & 0011 ------ 0000
ここで、元の数字のビットを反転させた 0011、つまり「下から 2 個の 1 が並んでいる数字」をインクリメントするとどうなるかを考える。
0011 + 0001 ------ 0100
すると、「下から 2個の 0 が並び、その上に 1 がある数字」になる。
下から n 個の 1 があり、その上に 0 がある数字をインクリメントすると、下から n 個の 0 があり、その上に 1 があり、さらにその上はそのままという結果になる。
今度は、元の数字である 1100（下から 2個の 0 が並んでいる）と、この数字の AND をとる。
すると、「下から 2 個の 0 と、その上の 1」が共通ということになる。
それより上の桁は影響を受けないので反転したまま。
次のようになる。
1100 & 0100 ------ 0100
「下から 2 個の 0」は AND で 0 のまま、「その上の 1」は元々 1 だったところなので 1、それより上の数字は元の数字のビットを反転させたもののままなので、AND ですべて 0 になる。
結果として、「元の数字で下から見て最初の 1 だけ 1 として残り、ほかがすべて 0 になった数字」が得られたことになる。
ここで使った「ビットを反転させてインクリメント」という操作は、「マイナスをとる」というのと同じ操作になる。
この辺りについては、「1 の補数」「2 の補数」などをキーワードに調べることができる。
ここまでで、r & -r という操作で、「下から見て最初の 1 だけが立った数字」が得られることがわかった。
1100 なら 0100、1000 なら 1000、1010 なら 0010、1001 なら 0001 といったものになる。
ここで、数字逆順ループの話に戻る。
まず、2進数の普通のインクリメントでは、ビットはどういう変化をするかを考える。
たとえば、2進数の 1010、つまり 10進数の 10 に 1 を足す場合。
1010 + 0001 ------ 1011
一番下の桁だけ変化する。
つまり、0001 と XOR をとるのと同じことだ。
じゃあ、2進数の 1001、つまり 10進数の 9 に 1 を足す場合はどうだろう。
1001 + 0001 ------ 1010
一番下の桁が 1 から 0 になって、繰り上がって次の桁が 0 から 1 になる。
これは、0011 と XOR をとるのと同じことになる。
次に、2進数の 1011、つまり 10進数の 11 に 1を足す場合。
1011 + 0001 ------ 1100
2回繰り上がるので、下から 1番目と 2番目が 0 から 1 に、3番目が 0 から 1 になる。
0111 と XOR をとるのと同じということだ。
変化するのは、常に下から数えて連続したいくつかの桁ということになる。
その変化する桁の数は、繰り上がりの回数 + 1 になる（繰り上がりがなければ 1個、1回繰り上がるなら 2個)。
そして、繰り上がりの回数というのは、下から数えた連続した 1 の個数。
まとめると、変化する桁の数は
(下から見て連続した 1 の数) + 1
ということになる。
1001 なら、下から見て連続した 1 の数は 1個なので、変化する桁は 2個。
1010 なら、下から見て連続した 1 の数は 0個なので、変化する桁は 1個。
1011 なら、下から見て連続した 1 の数は 2個なので、変化する桁は 3個。
ここまでで一旦まとめる。
2進数のインクリメントには、次の性質がある。
- (下から見て連続した 1 の数) + 1 個だけ、下の桁で 0 と 1 が変化する。
つまり、次のことができたら、ビット逆順のインクリメントができることになる。
- (上から見て連続した 1 の数) + 1 個だけ、上の桁の 0 と 1 を変化させる。
つまり、「(上から見て連続した 1 の数) + 1 個のビットが上から立った数字(X とする)」が得られたら、それとの XOR をとることで、ビット逆順の数字のインクリメントができることになる。
1100 なら、上から 2 個の 1 が連続しているので、上から 3 つのビットが立った 1110 と XOR をとることで、次の数字が得られる。
1100 ^ 1110 ------ 0010
1100（0011の逆）-> 0010（0100の逆）と進んでいるので、ちゃんとビット逆順のインクリメントができている。
ここで、「（上から見て連続した 1 の数） + 1 個のビットが上から立った数字(X)」というのは、直接得ることはできない。
だが、上で見たように、「下から見て最初の 1 だけが立った数字」というものは r & -r という演算で簡単に得られる。
ここから、「下から見て最初の 1 だけが立った数字」を求める方法から、「（上から見て連続した 1 の数） + 1 個のビットが上から立った数字(X)」を得る方法を考える。
まず、「（上から見て連続した 1 の数） + 1 個のビットが上から立った数字(X)」を求める方法。
具体的には、そういう数字とは、
1001 なら、上から見て連続した 1 の数は 1個なので、求める数字は上から 2 個のビットが立った 1100。
0101 なら、上から見て連続した 1 の数は 0個なので、求める数字は上から 1 個のビットが立った 1000。
1101 なら、上から見て連続した 1 の数は 2個なので、求める数字は上から 3 個のビットが立った 1110。
これを求めるには、「上から見て連続した 1 の数だけ上から 0 が並び、その次に 1 があり、残りはすべて 0 の数(Y)」があればいい。
1001 なら、0100。
0101 なら、1000。
1101 なら、0010。
この「上から見て連続した 1 の数だけ上から 0 が並び、その次に 1 があり、残りはすべて 0 の数(Y)」があれば、2 の補数をとる（この例でいうと 10000 から引くというのと同じ）ことで、Xが得られる。
10000 - 0100 = 1100 10000 - 1000 = 1000 10000 - 0010 = 1110
次に、「上から見て連続した 1 の数だけ上から 0 が並び、その次に 1 があり、残りはすべて 0 の数(Y)」を求める方法。
これは、「逆順の数字で、下から見て連続した 1 の数だけ上から 0 が並び、その次に 1 があり、残りはすべて 0 の数(Z)」のビットを逆順にすることで求められる。
数字が 1101 なら、求めたい「上から見て連続した 1 の数だけ上から 0 が並び、その次に 1 があり、残りはすべて 0 の数(Y)」は、上で見たように 0010 となる。
この場合、逆順の数字は 1011 なので、これから「下から見て連続した 1 の数だけ下から 0 が並び、その次に 1 があり、残りはすべて 0 の数(Z)」を求められるとすると、Z は Y の逆の 0100 になる。
このように、「1 が一個だけ立っている数字」については、ビット逆順の数字を求めることは非常に簡単だ。
n桁の 2進数なら、n桁目（最上位ビット）だけが立っている数字をその数字で割ればいい。
4桁の場合、1000を割ることになる。
1000 / 0001 = 1000 1000 / 0010 = 0100 1000 / 0100 = 0010 1000 / 1000 = 0001
あとは、「下から見て連続した 1 の数だけ下から 0 が並び、その次に 1 があり、残りはすべて 0 の数(Z)」を求める方法。
まず、「下から見て 1 が n個連続した数字」について考える。
n個連続した 1 の、すぐ上の桁は必ず 0 になっている。
（上の桁が 1 なら、それも「連続した 1」としてカウントされるから）
たとえば 1011 で考えると、下から 1 が 2個並んでいて、その上に 0 がある。
ここで、「下から見て 1 が n個連続した数字」をインクリメントするとどうなるかを考える。
下から n個の 1 は、すべて繰り上がって 0 になる。
その上の 0 は、繰り上がりで 1 になる。
つまり、「下から n個の 0 が並んでいて、その上に 1 がある」という状態になる。
1011 で考えると、次のようになる。
1011 + 0001 ------ 1100
下から 2個の 1 が並んでいたのが、インクリメントすると下から 0 が 2個並んだ数字になる。
そして、「下から 0 が n個並んだ数字」から「下から見て連続した 1 の数だけ下から 0 が並び、その次に 1 があり、残りはすべて 0 の数」を求めるには、上で見た通りに、元の数字とそのマイナスの数字で AND 演算をすればいい。
ここまでで、必要な計算は一通り揃った。
流れを復習する。
数字の全体のビット数（仮に 4 とする）を m とする。
また、逆順インクリメントしたい数字の、上から連続した 1 の数を n とする。
- ある数字 p をビット逆順インクリメントするには、上から n+1 個のビットが立っていて残りが 0 の数字(X)と XOR をとることで求められる。
- X は、上から n 個の 0 が並び、その下に 1 があり、残りはすべて 0 の数(Y) を 2 の m乗（この場合は 10000）から引くことで求められる。
- Y は、下から n 個の 0 が並び、その上に 1 があり、残りはすべて 0 の数(Z) で 2 の m-1乗（この場合は 1000）を割ることで求められる。
- Z は、p の逆順の数字をインクリメントした数字（下から n 個の 0 が並んでいる。q とする）と、そのマイナスの数字との AND をとることで求められる。
ここで、p の逆順の数字をインクリメントした数字である q はループ時に持っておくことにする。
次のようにループすることになる。
p q 0000 0001 1000 0010 0100 0011 1100 0100 0010 0101 ...
p が逆順の 0, 1, 2, 3, 4 で、q が正順の 1, 2, 3, 4, 5 だということがわかるだろうか。
q を持っておけば、上の各数字は次のようになる。
（p の次の値を p' とする。また、べき乗は ** で表す。& = AND, ^ = XOR）
Z = q & -q Y = (2 ** (m - 1)) / Z X = (2 ** m) - Y p' = p ^ X
これらをまとめると、次のようになる。
p' = p ^ ((2 ** m) - ((2 ** (m - 1)) / (q & -q)))
ここで、N = 2 ** m とおき、また r = 2 * q とおくと、次のようになる。
p' = p ^ (N - (N / (r & -r)))
これで、元のコードとほぼ同じものになった。
元のコードに戻る。
int r = 0; // counter
int s = 0; // bit-reversal of r/2
int N = 256; // N can be any power of 2
int N2 = N << 1; // N<<1 == N*2
do {
printf("%u ", s);
r += 2;
s ^= N - (N / (r&-r));
}
while (r < N2);ここでは、正順のカウンターである r を 2 倍している。
これは、途中の計算を減らすためだ。
しかし、そこまで気にしないなら、N2 を減らして、また for 文を使って次のように書くこともできる。
int s = 0; // bit-reversal of r/2
int N = 256; // N can be any power of 2
for (int r = 0; r < N; ++r, s ^= N - (N / 2 / (r & -r) )) {
printf("%u ", s);
}だいぶすっきりした。
でも、これはコメントがないとつらそう。
で、ビット逆順のループなんかどこで使うのかという話だが、以前書いたウェーブレット行列の省メモリ構築方法で使っている。
ウェーブレット行列のライブラリはこちら。
ビット逆順のループについて知ったのはつい最近で、それまではビットを逆順にするテーブルを作っていた。
ビットを逆順にするテーブルの作り方についても前に書いたことがあるけど、あらためてコードを簡単にして書くと次のようになる。
int N = 8;
int t[256] = {0};
for (int i = 0; i < N; ++i) {
for (int j = 0; j < (1 << i); ++j) {
t[(1 << i) + j] = t[j] + (1 << (N - i - 1));
printf("%d\n", t[(1 << i) + j]);
}
}簡潔に書けるので気に入っている。
また、ある単独の数字のビットを逆転させたいというだけなら、有名な次のやり方がいい（32bit版）。
x = (x & 0x55555555) << 1 | (x & 0xaaaaaaaa) >> 1; x = (x & 0x33333333) << 2 | (x & 0xcccccccc) >> 2; x = (x & 0x0f0f0f0f) << 4 | (x & 0xf0f0f0f0) >> 4; x = (x & 0x00ff00ff) << 8 | (x & 0xff00ff00) >> 8; x = (x & 0x0000ffff) << 16 | (x & 0xffff0000) >> 16;
これは、4ビットや 8ビットの場合を紙に書いてやってみると、簡単なことをやっているのがわかる。
というわけで、ビット逆転についての話でした。
実用的には最後の有名なやり方だけでもいいと思うけど、簡潔に書けるとうれしい。
普通はなかなか使う機会がないと思う*1。
ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか
posted with amazlet at 13.10.18
正直に思ったことを書いて、いい結果になったという話
最近、ネットでものが言いにくい雰囲気があるとのこと。
「なんで辞めたの？」とか「次どこ行くの？」など、昨今のインターネットは若干書きにくい空気
個人的には、ぶっちゃけた退職エントリを書いたこともあるので、そういう風潮を憂慮している。
そういうわけで、「正直に思ったことを書いて、いい結果になった」という話を書いてみたい。
（といっても、上記エントリの話ではない）
前職を辞めて、半年ちょっとプラプラして、さて仕事を探すかーとなったとき。
まあプログラマというのは就活力の低い人間のクズが多いと思うけど、ぼくはその中でもかなり重症のほうなので、いろいろ苦戦していた。
まず、会社の数をこなせない。
それまでの就職でも、受けた会社の数はごくわずか。
就職経験は 2回なのに、就活したのは合計 4〜5社だけ。
今回の就職活動では、昔勤めていた大阪の K社というところが「よかったらうちに帰ってこないか」と声をかけてくれていた。
なんと、前職と同じぐらいの待遇をしてくれるという。
しかし、この K社というのは創立 30年ぐらいの小さな会社なのだが、創業社長が亡くなってからは社内の空気も沈滞気味で、技術レベルも低く、将来性があるようには思えなかったので、できれば帰ることは避けたかった。
それで、転職サイトと知り合いのすすめでそれぞれ 1社、合計 2社受けてみたのだが、両方ダメだった。
1社は態度が社会人としてアレだったということで、もう 1社は試験内容が Java のギョーム系のことばかりだったので（当時 Java経験なし）落ちてしまった。
凹んだ。
元々行きたかったのは IME の会社だが、諸事情によりそれもダメだった（受ける前の段階で）。
それで、気が進まないまま、K社に戻ることに決めた。
そのときに、上述のこと（社内の空気が沈滞気味・技術レベル低い・将来性がなさそう）のために帰りたくないが、帰る以上は頑張ろうというブログ記事を書いた*1。
最初の出勤日まであと数日というときになって、以前の上司から連絡があった。
ブログ記事の内容がよくないので、消してくれないかと。
ぼくとしては、納得できる理由があるなら消すなり編集するなりしてもよかったが、そういう理由も聞けなかったのでそのままにしていた。
そして、入社日の 2〜3日前。
K社から「内定取り消し」というメールが来た。
なにやら「情報セキュリティ委員会」とやら言うところが問題視したとか。
まあ 30人ぐらいの会社だし、なんとか委員会といっても数人の寄り合いみたいなものだけど、要は「気にくわなかった」のだろう。
それで就職活動を再開して、2社受けて（やはり数がこなせない）そのうちの 1社に受かって今に至る。
この一件で反省しているかというと、まったく反省していない。
それどころか、「正直に思ったことを書いたおかげでリスクが回避できてよかった」と思っている。
というのは、K社が「非合理なプレイヤー」であるということが明らかになったからだ。
もともと好待遇で帰ってきてほしいということなら、ぼくの語学力や技術力を使って金を稼げるという予想があったはず（当たり前だ、慈善事業じゃないんだからぼくに金をくれたくてそんなことを言ったというわけはない）。
それを、中の人の気を悪くするようなことを書いたからといって雇うのをやめるというのは、明らかに非合理的だ。
労働契約を「労働と金銭の交換契約」ではなく、「雇用主から被雇用者への施し」のように勘違いしているのだろう。
バカにはよくあることだ。
もちろん、そういう主体と関わるということは、いくら金をもらったとしても、いつ人事権を持つバカの機嫌を損ねて非合理的な報復行動に出られるかわからないということになる。
そういうのはぼくの人生にとって大きなリスクなので、避けられたというのは非常にいいことだ。
いま働いているところは、普通にコーディングや英語などのテストと面接を受けて通った、比較的新しい会社。
面接の過程でも対等な立場でぶっちゃけた話ができて、合理的な思考をしていることが伝わってきた。
おかげで、今では誰かの機嫌を損ねる心配などせずに思ったことを思った通りに書ける。
たまに転職活動をしたりして、それについて公開設定の日記に書いたりもしているけれど、その成否と関係なく真面目に仕事はしているし、会社としては問題視するところではないだろう。
ぼくにとって、働くにあたって重要なポイントというのは順番に次のようなものだ。
1. 人間としての尊厳
2. 働くうえでのプライド
3. 労働条件
4. 労働環境
1 の人間としての尊厳というのは、給料の支払いを「施し」のように思っている奴隷主のような雇用者の下で働かないということ。
2 の働くうえでのプライドというのは、自分の主義や信条に反しない仕事をするということ。たとえばぼくにとっては日本語というのは大切なものなので（つい最近も記事を書いた）、日本語破壊機を作る仕事（例です）のようなものは、どんな待遇だろうとできない。
3 の労働条件というのは、夜遅くまで働かされたり休日出勤させられたりしないということ。当たり前のようだけど。ちなみにぼくの今の職場では、6時になったその瞬間に帰ることができる（ぼくの場合。ほかの人は5〜10分後に帰ることが多いが、まあ誤差の範囲だ）。給料も高いに越したことはないが、生活できるという最低ラインをクリアしていればいい。
4 の労働環境というのは、開発環境や人間関係やその他もろもろ。まあ大事といえば大事だけど、上記 3条件に比べたら重要ではない。空気がピリピリしていて気が休まらないとか、リスクテイクができなくて古い環境を使い続けているとか、バージョン管理システムが活用できてなくてコードレビューのためにファイルを zip ファイルに固めて送らないといけないとか、そういうことはあったとしても些細なことだ。（2014/04/06追記: のちに、このようなことはより深い病理に根ざしているため軽視できないという洞察が得られた）
今のぼくの職場では、上の三条件が整っている。
まあ生活はしんどいし、いま住んでいるところの家賃が払っていけないから引っ越ししないといけないし、全体的につらくて死にたいし人生の敗残者という趣があるけど、まあそれが実力相応といったところなんだろう。
そういうわけで、「書きたいことを書いたらいいことがある」という話でした。
書きたいことを書いたおかげで、ろくでもない会社をそうであると判別できて、行くことを回避できたということ。
正直に思ったことを書くような人間を煙たがるようなところというのは、まあろくな場所じゃない。
仕事がしんどくて生活が厳しくて自殺したとしても、誰かの施しをもらったわけじゃないし、自分の主義に反する仕事に手を染めたわけでもないし、そういうのに比べたらマシだと思っている。
ここで宣伝。
無職でブラブラしている間に翻訳した、カフカの「変身」。
これまでほとんど売れず（人生は厳しい）、最低振り込み金額にも達しないので一文の得にもなっていない（達しても大赤字だ）けれど、費用対効果を度外視して好きな作品を訳したので、おすすめできる品質にはなっていると思う。
よかったら買ってください。
*1:最終的には消した。
