Google のクソデカ ngram を解析する その1
モチベーション
過去に
を作りました。これを作り直します(`・ω・´)
nextword とはなにか?
look コマンドの ngram 版です。 look コマンドは内部で二分探索を用いており、これはもしかして ngram にも応用できるのでは? と思い作ったソフトウェアです。 当初はエディタの英語補完に使えるかな? と思って作りましたが、いろいろな使い方があって面白いなと思いました。
CLIで英単語を引くのがちょっと話題になってたからnextword + fzf + weblioで単語引くワンライナー雑に書いた pic.twitter.com/Ag7VHNE9un
— Yano (@yuki_ycino) 2020年11月10日
nextword にはひとつ問題があり、データがでかすぎます。 でかいデータをローカルに保存するのはとてもストレスなので、次は小さなデータに加工できないかなという気持ちがありました(`・ω・´)
なんかめっちゃ容量消費しているものがいるなぁと思ったら nextword 用のデータだったw pic.twitter.com/xKEbP7hJ9c
— Ress (@ress997) 2020年7月21日
Google ngram クソデカデータ
Google は ngram のデータを公開しています。
こいつを入手して加工することで ngram の解析ができますね。
ところで、このデータセットは英語版だけでファイルが 33600 個程度あり、gzip の圧縮ファイルで1個 600MB あります。 展開するとだいたい 1.7GB あります。 つまり、全部解析すると 60 TB くらいにはなりそうです。これを全部ダウンロードして加工します。 将来的には多言語で使いたいので、扱うデータは 100TB オーダーと見積もってよさそうです。
サイトには、
If you're interested in performing a large scale analysis on the underlying data, you might prefer to download a portion of the corpora yourself. Or all of it, if you have the bandwidth and space. We're happy to oblige.
と書いてあります。やはりデータを全部使ってくれたら嬉しそうです。使います。勝負だ(`・ω・´)
クソデカデータを加工するサーバの用意
やはり OSS として公開する都合上、可能な限りお金をかけずに全データをさばいてみたいと思います。 Bigquery なんてもってのほか、そんなことをしていては Google に最初から負けているようなものです。
可能な限り安上がりにするために、ハードウェアは極力シンプルに、ソフトウェアは全部無料で調達することにしました。 今回は以下のハードを使います。
- Raspberry Pi 4 Model B (8GB)
- 120GB SSD
- 6TB HDD
これで戦っていきたいと思います。CPU の遅さが気になりますが、実際4コアあり、メモリも 8GB と十分です。 どうせ CPU ではなく IO がボトルネックになると思うので、Raspberry Pi でも十分勝負になる気がしてきました。
次回へ続く。
Mac を macOS + Windows + Linux (Gentoo) のトリプルブートにする(`・ω・´)
Mac をトリプルブートしたい方は「なんでトリプルブートするんだろう?」ということに疑問を持つことはないと思いますので、前置きはこの辺にしておきます(`・ω・´)
Linux のディストリビューションの選び方
結論: Gentoo がよいのではないでしょうか(`・ω・´)?
Mac に 3 つの異なる OS を動かそうとすると一番問題なのはブートローダをどうするかということです。 ESP に各 OS のブートローダを相乗りさせたいところですが、ESP は正直手動でいじりたいパーティションではないです。 OS のインストーラは勝手にパーティションをいじったり ESP にファイルを配置したりして管理上良くないので、 Live CD から手動でインストールするタイプの Arch Linux や Gentoo Linux がよいかと思われます(`・ω・´)
ところで最近 M1 Mac というものが登場しました。 これは amd64 ではないので本家の Arch Linux をインストールすることはできません。 いま自分の手元にある Mac はすべて Intel Mac ですが、将来のことを考えたときに、 Gentoo Linux が最も未来があるのではないでしょうか(`・ω・´)
環境
- iMac 2019 (19,2)
- Big Sur 11.2.3
今回の目標
手順
- macOS をディスク全体にインストールする
- Boot Camp を用いて Windows 10 をインストールする
- Windows 10 から Windows のパーティションを縮小して Gentoo のための空き領域を確保する
- Mac から rEFInd をインストールする
- Gentoo をインストールする
- Gentoo は grub を使わずに rEFInd から直接起動する
macOS のインストール
macOS は最初からインストールされていると思います。 ここでのポイントはディスクユーティリティなどを使ってパーティションを切ったりしておかないことです。
macOS を暗号化するには FileVault を使えばよいのでらくちんです(`・ω・´)
Windows 10 のインストール
Boot Camp を用いて Windows 10 をインストールしましょう。 ここでのポイントは Windows の領域を大きめにとっておくことです。 Windows + Linux の大きさの領域を準備しておきましょう(`・ω・´)
Windows を暗号化するには BitLocker を使います。 Mac で BitLocker を使うときに TPM が使えないので代わりに USB メモリを使うことになります。 このとき USB メモリは FAT でフォーマットしておきましょう。 私は exFAT にしてしまったのですが、これは Linux で暗号化するときに面倒なことになります(なりました)
Gentoo のための空き領域を確保する
Windows を起動して Windows から Windows のパーティションを縮小します。 これは Windows の標準機能で操作が可能です(`・ω・´)
Mac から rEFInd をインストールする
rEFInd をブートに使うのが安定です。 rEFInd のインストールには SIP を無効にする必要があるので気をつけましょう。 Mac からインストールするのがよいと思います。 Gentoo の /boot に Btrfs を使いたい場合は Btrfs のドライバもインストールするようにしましょう(`・ω・´) (これはめんどくさいので /boot は ext4 にするのがよいと思われます)
Gentoo をインストールする
Gentoo Wiki を見ながらインストールします。 今回は、
- Dm-crypt を使ってルートを暗号化する
- key file を使う
- Btrfs の透過圧縮を使う
- Btrfs の subvolume を使ってスナップショットを簡単に取れるようにする
- Genkernel を使ってカーネルをビルドする
- Grub は使わない
という路線でいきます。
そうだ、Gentoo をインストールするときは tmux を使っておくと色々はかどります。 Live CD にインストールされているので使わない手はない(`・ω・´)!
Gentoo の暗号化には dm-crypt を使うのがよいと思います。 パーティション構成は
/dev/nvme0n1p1 (EFI) (Linux からいじらない) /dev/nvme0n1p2 (macOS) /dev/nvme0n1p3 (Windows) /dev/nvme0n1p4 /boot ext4 /dev/nvme0n1p5 / btrfs
にするのがよいでしょう。
ここでのポイントは /boot を ext4 でフォーマットすることです。 rEFInd は普通のインストールで ext4 のドライバのみがインストールされます。 Btrfs もブート可能ですが操作がちょっと面倒になるので ext4 が簡単でよいです(`・ω・´)
/dev/nvme0n1p5
を dm-crypt で暗号化することになります。
ここでのポイントは cryptsetup open
をするときに root
という名前で open することです。
# cryptsetup open /dev/nvme0n1p5 root
Arch Wiki を見ると cryptroot
という名前になっていますが、root
にしないと
Genkernel がルートを開けない(もしくは追加のカーネルパラメータが必要になる?)
みたいです。
ちゃんと調べてないですが cryptroot
だとハマったので root
がよいみたいです(`・ω・´)
ここで Gentoo の起動時に毎回パスワードを打ち込みたくないという気持ちになります。 このとき key file を使うとよい気分になれます。 ちょうど Windows の BitLocker のために準備した USB メモリがあるのでこれを使いましょう。 USB メモリは FAT でフォーマットされていることだと思うので、ここに key file を設置しておきます。 Genkernel でビルドした initramfs からは exFAT を見に行くことができないので、 FAT でフォーマットすることはとても大事です(`・ω・´)
Btrfs の便利機能に透過圧縮があるので今回は使うことにします。 透過圧縮のアルゴリズムは lzo がよさそうです。 zstd も試してみましたが、カーネルのビルド時間が倍になりました。 透過圧縮を使うときはマウントしたあとに remount することでできます。
# mount /dev/mapper/root /dev/mnt # mount -o remount,compress=lzo
Btrfs の便利機能に subvolume を用いたスナップショット作成があります。 Subvolume の配置は Arch Wiki を参考にしました。 ルートディレクトリに / が配置されないのはなんか面白いですね。 Btrfs Wiki も参考にしました。 fstab は
UUID=**** /var/lib/docker btrfs noatime,subvol=/var/lib/@docker 0 0
みたいな雰囲気になります。 ところで fstab で思い出しましたが、NVMe の SSD では discard にしないほうがよいらしいです(Should TRIM be avoided for NVMe drives?) あと fsck も 0 がよいらしいです(`・ω・´)
Genkernel を使ってカーネルと initramfs をビルドします。 Genkernel を使えば楽ができてよいですね〜〜とおもっていたのですが案外ハマりポイントが多いです。 Genkernel は次のオプションを付けて実行します
# genkernel all --keymap --luks --btrfs --microcode
Genkernel のハマりポイントを上げていきます。
- cryptsetup がインストールされていなくてもルートをマウントできてしまう
これまじでなんで?? ってなります。お前 cryptsetup インストールしてないやん。 cryptsetup のインストールを忘れずに行いましょう。
まじかーって感じです。FAT にしましょう。
そしてこれは Mac 特有の問題ですがカーネルのソースコードをいじらないと Bluetooth が使えるようにならないらしいです(State of Linux on the MacBook Pro 2016 & 2017) カーネルのソースコードに書き加えるコードは数行なので、 Genkernel する前に書き換えておくとよいですね(?)
最後にブートローダですが Grub のかわりに rEFInd を使います。
/boot/refind_linux.conf を設置してカーネルパラメータを書いていきましょう。
今回は Genkernel を使ったので man genkernel
しながらパラメータを書いていきます。
ポイントを上げていきます。
- cryptroot=UUID=**** する
- root_key=path/to/key する
- root_keydev はなくても keyfile を探してくれる(あったほうがよい)
終了
OS をインストールすることと OS を便利に使うことは違うと思いますが、 すべての OS がひとつの PC で動くようになって満足です(`・ω・´)
GentooInstallBattle した(`・ω・´)
Gentoo Linux を VirtualBox 上にインストールした
来年から研究室でなんのOSを使おうかな〜〜と考えたときに,Linux にしようかと思いました。せっかくならキワモノを使いたいということで,練習のために VM に Gentoo をインストールしました(`・ω・´)
じゃじゃーん(`・ω・´)
構成
- Grub
- Dm-crypt を用いて root を暗号化
- Genkernel
- Systemd
- i3wm
覚えたこと・詰まったこと
Arch Linux のインストールとそんなに変わらなかった
Arch Linux をインストールすることには慣れていましたが,手順はだいたいいっしょだなあということを確認できました。違いは GCC のパラメータを設定することくらいです。とくに今回は OpenRC ではなく Systemd を使ったため,本当に違いを感じませんでした。OpenRC と Systemd のどちらを使うかまだ決めていませんが,おそらく Systemd を使うことになるでしょう。時代の流れだもんね……(`・ω・´)
Grub にカーネルパラメータを渡せない
Dm-crypt で root を暗号化する際には,カーネルパラメータで root が暗号化されていることを教えなければなりません。具体的には,
cryptdevice=/dev/sdaX:cryptroot root=/dev/mapper/cryptroot
を渡します。
しかしこれが何故かうまくいきません。
原因はおそらく grub のインストール方法にあると思います。今回のインストールでは --removable
フラグを与えて,
# grub-install --target=x86_64-efi --efi-directory=/boot --removable
としてインストールしました。うろ覚えですが VirtualBox を EFI boot するとき,ブートローダーのパスは/EFI/BOOT/bootx64.efi
しか受け付けてくれなかったはずです。Grub の設定は従来どおりに
# grub-mkconfig -o /boot/grub/grub.cfg
としてしまったため,どうやら grub.cfg
を読みに行かなかったようです。いま書いていて気づいた……。
いままで systemd-boot ばかりつかっていたので grub よくわからん…….。あとで man 読みます……。
とはいえブートに失敗しても grub の rescue shell が起動します。Shell に入って
# cryptsetup open /dev/sdaX cryptroot
とすることでブートできるので,多少めんどいだけでどうにかなります(`・ω・´)
<追記>
今回カーネルにパラメータを渡せなかったのは genkernel を使っていたからでした。
Genkernel の man ページを見ると initramfs を使った場合のブートの仕方が書いてありました。
なるほど感(`・ω・´)
カーネルのビルド
今回はカーネルの設定までやっていたら日が暮れてしまうので,genkernel でカーネルビルドすることにしました。Dm-crypt で root を暗号化している都合上 initramfs も作成しなければならなく,genkernel にまかせてしまえば一石二鳥です。やったね!
Genkernel を実行する際には --luks
オプションを渡し忘れないようにしましょう。
本番では自力でカーネルビルドしてみようかな〜〜と思っています。でもアップデートがめんどくさそうですね。みなさんどうしてるんだろ(`・ω・´)
Systemd
Gentoo の wiki は OpenRC をデフォルトとして扱っているので,systemd を使う際は気をつけないといけないなと思いました。一方 Arch Linux は systemd を使っているため,情報が豊富です。インストールの際は Gentoo の wiki と Arch の wiki を交互に見るようになりますね(`・ω・´)
i3wm
流石に CUI で研究生活を送るわけには行かないので i3wm を導入することにしました。Gnome いれるの Gentoo ではきつそう……。Gentoo では Arch と違って dmenu や i3bar がついて来ません。せっかくなので polybar をインストールしてみました(`・ω・´)
dmenu がセグフォで落ちる
dmenu に文字を打ち込もうと思うと突然 dmenu が消えます。なんで?? と思ってログを見ていると,どうやらセグフォで落ちてしまうようです。困った。 ということでググったら情報が出てきました。
どうやら locale が変わったところだと落ちるようです。なんで??
仕方がないので dmenu が実行されるときだけ locale を変更します。今回は i3wm を使っているので,~/.config/i3/config
の dmenu のところを
exec LC_ALL=en_US.UTF-8 dmenu_run
にします。これで動いて一安心です(`・ω・´)
USE フラグの立て忘れに注意
ターミナルエミュレータをなんか入れないといけないので,とりあえず urxvt をインストールしました。いざ開いてみると文字化けします。困った。
原因がわからずに 1 時間くらい溶かしました。
そこで,$ equery u rxvt-unicode
で USE フラグを確認すると,xft
のフラグを立て忘れていました。どうりでフォントがおかしくなるわけだ……。フラグを立て直してビルドし直したら無事にフォントがきれいに表示されました。めでたしめでたし(`・ω・´)
emerge --oneshot
が便利
Gentoo をインストールした記念に neofetch のスクショを撮るのが恒例だそうです。でも neofetch のスクショとったらもう neofetch 使わなくないですか……?
そんなときは --oneshot
をつけるのが便利です! --oneshot
をつけると neofetch がインストールされたことが world に記録されないため,次回の emerge --depclean
できれいに消えます。Gentoo を使う人はきっと潔癖なので,こういうオプションが生まれたのでしょう(`・ω・´)
Arch よりは安定してそう
Arch よりも Gentoo のほうがカーネルのバージョンが古いです。なんとなくカーネルパニックになりにくそうな気がしています。気のせいかな? まあ lts を使えという話ではあると思います(`・ω・´)
感想
一通りやってみて,意外とやっていけるのではないかという気がしてきました(`・ω・´)
AtCoder が水色になった(`・ω・´)
AtCoder が水色になりました。やった〜〜(`・ω・´)!!! うれしいなあ(`・ω・´)
経緯
2019年の4月に AtCoder を始めました。1〜2週間に1回強制的にプログラムを書かなければいけない日を作って,プログラムの書き方を忘れないようにする目的で始めました。 レートに猛烈にこだわることはなく,寝不足の日もお酒を飲んだ日も構わずやりました(`・ω・´)
しばらく緑で停滞していたので,2020 年に入った頃に,そろそろちゃんとやろうかな? という気になりました。LeetCode の問題を解いて競プロに出るアルゴリズムの勉強を始めました。すぐにレートが上がって水色に届いたので,勉強の成果が少しは出ているのではないかなあと思います(`・ω・´)
茶→水になるまでやったこと
- Python の書き方を覚える
- 入出力に困らないようにする
- 何も考えずに
map()
を使って数列をint
に変換する
- 何も考えずに
- 標準ライブラリを把握する
- 入出力に困らないようにする
- 入力の条件をよく確認する
- 計算量を気にする
- 変なバグを埋め込まない
- 1始まりのインデックスをあらかじめ0始まりに変換しておく
- Python 独特のインデントのミスなど
- DFS を何も見ずに書けるようにする
- 再帰でもスタックでも
- BFS を何も見ずに書けるようにする
- 二分探索を書けるようにする
- 簡単な DP を完全に理解する
- Deque を使えるようにする
- Priority queue を使えるようにする
- Bit を使って全探索できるようにする
- 累積和を使えるようにする
- しゃくとり法を使えるようにする
- Union-Find の存在を知る
- ローマ字の変数を躊躇なく使う(!)
- 変なコーナーケースに引っかからない
- 蟻本を手元に置く
- LeetCode の Easy から Medium を 100 問くらい解く
- Golang を習得する
- Gentoo Linux をインストールできるようにする
こうやって書いてみるとやることたくさんありますね(`・ω・´)
思えば AtCoder を始めた4月は DFS も BFS もおぼつかないレベルだったので,進歩したなあと思います。
ローマ字変数を使うことについて
例えば
wa = sum([1, 2, 3])
とします。
これはいかがなものかとお考えになるでしょう。 しかし,ローマ字変数をを使うことにはメリットがあります。
- 英語に訳さなくて良い
- Python の組み込み関数を上書きしなくて済む
とくに 2. は大きいと思います。
sum
という変数名が使えないから total
にしようとか変なことを考えずにコーディングに集中できて良いです。
競プロ以外では使わないようにしましょう(`・ω・´)
就活
水色は就活に役に立つのか??? 立ってほしいなあ……(`・ω・´)
勉強法
LeetCode の Easy から Medium を100問くらい解きました。LeetCode の問題は木の探索や DP など教育によさそうな問題が多くありました。AtCoder のように考察が必要な問題は多くはありませんが,アルゴリズムの習得という点では良いのではないのでしょうか(`・ω・´)
感想
水色はうれしいなあ〜〜(`・ω・´)
ここから先の色になるのは趣味の領域だなあと感じているので青を目指すかどうかはわかりませんが,ゆるゆるやっていきたいと思います(`・ω・´)
英語の入力補完をする VSCode 拡張を公開した(`・ω・´)
英語の入力補完をする VSCode 拡張を書きました!
これを使うことで英文の入力が楽々になります(`・ω・´)!
できること
すでに入力された英文から次に来やすい単語を推測して表示します。
また,英単語の綴りの入力補完もできます。
インストール
このプラグインを VSCode にインストールする前に, nextwordと nextword-data をインストールする必要があります。
これに関しては前に書いた記事
をご覧ください。
コマンドラインツールのインストールを終えたら,VSCode 上で "Nextword" を検索します。 すると以下のスクショのように見つかるはずです。
満を持してインストールボタンを押して完了です(`・ω・´)
ブラウザ上でも "Nextword" を探すことができます。 以下のリンクから見つけることができます。
VSCode を使って英語を書く方におすすめなので是非使ってみてください(`・ω・´)!
英語の入力補完に使えそうなコマンドラインツールを作った(`・ω・´)
与えられた英文に続く単語を予測するプログラムを書きました。
ごらんください(`・ω・´)
Nextword
標準入力に入力された英文から,次に最も現れやすい単語を標準出力に返すコマンドラインツールを作りました。
このツールは2通りの使い方ができます。
単語の入力補完
単語の続きまでを入力すると,そのスペルで始まる単語をぶわーっと返します。 難しい単語もスペル丸わかりですね(`・ω・´)!
英文の入力補完
英文の続きまで入力すると,その英文の次に来る単語の候補を 出やすい 順で返します。 これはめっちゃ便利(`・ω・´)!
このとき,英文の最後に スペース を入れてください。これは「単語の入力補完」モードと区別するために必要です。
インストール
このプログラムは本体とデータセットに分かれているため,両方をインストールする必要があります。
本体のインストールには,まず Go 言語のコンパイラを入手します。 それが終わったら以下のコマンドをターミナルで入力します。
$ go get -u github.com/high-moctane/nextword
これで本体のインストールは終わりです。
次にデータセットのインストールをします。 データセットは以下のリンクから入手できます。
small と large がありますが,これはデータの大きさです。 大きいほうが賢いですが,容量を食います。 好きな方をダウンロードして適当なところに展開します。
保存したら環境変数を登録します。変数名は NEXTWORD_DATA_PATH
で,値は展開先のパスです。
お使いの OS によって登録方法が違うのでご確認ください。
ターミナルで
$ nextword
としてエラーメッセージが出なければインストール終了です。
オプション
実行時に渡すオプションで振る舞いが変化します。
-c
オプション
-c n
オプションは表示する候補の最大数を n
にします。
$ nextword -c 100
とすると,候補が大量に表示されます。
-g
オプション
-g
オプションを与えると,できる限り多くの候補を表示します。
例えば,"Alice was beginning to " という入力に対し,デフォルトでは
get
のみが表示されますが,-g
を与えると,
get feel be think take look wonder show make see
になります。
原理の説明はちょっとむずかしいのでまた今度にします(`・ω・´)
応用
このプログラムをテキストエディタに使うことによって入力補完ができるようになります(`・ω・´)! これは VSCode 上で入力補完できているスクリーンショットです。
こちらはまだ公開していませんが,そのうちできたらいいなあと思っています(`・ω・´)
ラップ bot を書き直した(`・ω・´)
ラップ bot とはなにか?
ラップをひたすらつぶやく Twitter の bot です。
佐賀県転生
— ラップbot (@rhymer_bot) November 11, 2019
世の中には芸術的感性
海外限定
意思と無関係
ありがとうたんてい
韻を踏んでいるのが特徴です(`・ω・´)
作った背景
マルコフ連鎖を使って人工無能が作れるという話を聞きました。 それを応用して面白おかしい Tweet をする bot が存在していることを知りました。 じゃあ自分もやってみようかな,と思いましたが全く同じものを作ってもしょうがない。 ならば韻を踏ませてはどうか,ということでラップ bot のアイデアが誕生しました。
それと同時期に新しい言語を習得してみたいというモチベーションを持っていました。 当時の私は C と Ruby をかじったことがある程度でした。 C 言語で Twitter の bot を作るのは大変厳しい。 Ruby は bot を作るのが大変簡単だが,ラップ生成アルゴリズムと相性が悪いのではないか。 ということで Go 言語に行き着きました(`・ω・´)
アルゴリズム
マルコフ連鎖を使って大量に短文を生成しておきます。
短文を生成したときに,同時にその短文の発音方法を解析しておきます。
短文を2つ用意します。
2つの短文の発音方法が似ていたらラップ成立,似ていなかったら短文を捨てて 3 に戻ります。
最悪計算量は O(∞)です。 でもやってみるとすごい勢いでラップが生成されます。 なんでも試してみることですね(`・ω・´)