概要

この研究は、「シェルのコマンドライン補完をグーグルの検索ワードの補完みたいに賢くしたい」といふ筆者の願望を実現するための第一歩である。

この記事では、筆者が自作のコマンドラインシェルに実装した補完機能の仕組みとその精度について解説する。この補完機能では、過去に入力したコマンドとその状況を覚えておき、現在の状況に照らし合はせて最も次に実行される確率が高さうなコマンドを自動的に推定して補完するやうになってゐる。確率の計算にベイズ理論を応用したが、モデリングが単純であることもあって推定の精度はまづまづであった。

背景

皆さんのお気に入りのコマンドラインシェルが bash であるか zsh であるかあるいはその他のどマイナーなシェルであるかは知らないが、Unix 系環境で作業をする上でコマンドラインシェルは重要な要素であり、一日に百回以上シェルにコマンドを打ちこむことも珍しくない。筆者は yash といふ自分で作ったシェルを常用してゐるが、そのシェルが現在有してゐるコマンドライン補完機能には以下の様な不便さがあった。

• Tab キーによってコマンド名や引数を補完することはできるが、候補がたくさんあるときはその中から「正解」を選ばなければならないので結局補完するより直接打った方が速い。
• よく使ふコマンドラインは限られてゐるにもかかはらず Tab キーでの補完はあらゆる候補を律儀に提示し「正解」を素早く選ぶことを妨げる。

この不便さを補ふ為に zsh の history-beginning-search-backward に相当する履歴検索機能を使ふこともできるが、それでも「正解」にありつくためにはあらかじめコマンドの先頭部分を十分な長さまで入力しておかなければならない。

より早く「正解」のコマンドを補完するためには、コマンドの入力が始まってからその入力済みの部分に基づいて候補を提示するのではなく、より早い段階で候補を出す必要がありさうだ。そのためには、コマンドが入力されるよりも前にコマンドの内容を推定しなくてはならない。

推定の方法はたくさんあるだらうが、今回は簡単なベイズ推定を応用してみることにした。なぜベイズ推定なのかといふのは微妙な問題だが、あまりにも単純な手法では精度が低くなりさうだといふ疑念があった一方で複雑な手法では実装に時間がかかって面倒だといふ思ひがあった。簡単なベイズ推定はその中間に位置し、最初に試してみる手法としては手頃に思はれた。

手法

実装した手法の概略は以下の様になってゐる:

1. 毎回シェルでコマンドを実行する (ために Enter キーを押す) たびに、実行しようとしてゐるそのコマンドとその時の状況 (後述) を記録する。
2. シェルがコマンドの実行を終へて次のコマンドの入力を受け付けようとするとき、その時の状況に最もよく合致する過去のコマンドを記録から探し出し、それを補完の候補として提示する。

コマンドを決める「状況」

ユーザーがどんなコマンドを入力しようとしてゐるのかは何らかの要因によって決まるはずである。その様な要因のうちシェルにとって観測可能でありコマンドの推定に役立てることができるものをまとめて状況と呼ぶことにする。そしてとある状況を構成してゐる一つ一つの要因を属性と呼ぶことにする。

実際の推定に使用する属性として、今回は以下の三つを使用することにした:

• 直前に実行したコマンドライン
• 直前に実行したコマンドの終了ステータス
• カレントディレクトリーのパス

これらの属性は、それぞれ prev_exit_status=0 の様な文字列表現に変換され、さらに 64 ビット整数にハッシュ化される¹。そして、ユーザーがコマンドを実行するたびにそのコマンドの文字列とその時の状況 (三つの属性) を組にして記録に追加する。

ベイズ推定

ユーザーが入力しようとしてゐるコマンドを推定するアルゴリズムは、ベイズ推定の単純な応用である。以下の様に変数を定義すると:

• $P(T)$ = コマンド文字列 $T$ が入力される確率
• $P(C)$ = 状況 $C$ が発生してゐる確率
• $P(C|T)$ = コマンド文字列 $T$ が入力されるときに状況 $C$ が発生してゐる確率
• $P(T|C)$ = 状況 $C$ が発生してゐるときにコマンド文字列 $T$ が入力される確率

ベイズの定理により以下の式が成り立つ:

P(T|C) = P(T) P(C|T) / P(C)

すると求めたいもの (つまり補完の候補) は、現在の状況 $C$ の下でコマンド文字列 $T$ が入力される確率 $P(T|C)$ を最大化する $T$ である:

{\rm argmax}_{T} P(T|C) = {\rm argmax}_{T} P(T) P(C|T) / P(C)

ここで $P(C)$ の値は $T$ に依存しないので無視することができる:

{\rm argmax}_{T} P(T|C) = {\rm argmax}_{T} P(T) P(C|T)

あとは、記録に残ってゐる各コマンドに対して $P(T) P(C|T)$ を計算して、それが最大となるコマンドを求めればよい。$P(T)$ の計算はとても簡単で、$T$ がこれまでに実行された回数を数へればよい。一方 $P(C|T)$ の計算はもう少し頭をひねる必要がある。上述の通り状況は三つの属性で構成されると定義したが、単純に $P(C|T)$ を計算すると三つの属性が完全に合致する状況しか考慮されない。三つのうち一つあるいは二つの属性のみ合致する場合でも確率の値に貢献する様にした方がより正確な確率が得られさうである。そこで三つの属性が互ひに独立であると仮定して² $P(C|T)$ を分解する:

P(C|T) = P(a_1|T) P(a_2|T) P(a_3|T)

それぞれの $P(a_i|T)$ を計算するのは簡単である。過去にコマンド文字列 $T$ が実行された回数のうち属性 $a_i$ が満たされてゐた回数の割合を求めればよい。

擬似カウント

状況やコマンドの実際の出現 (記録) 回数のみに基づいて確率を計算すると、未知の状況 (これまでに一度も記録されてゐない状況) に対する確率が 0 になり、結果としてその状況でのあらゆるコマンド文字列の確率がすべて 0 になってしまふ。これでは確率を最大化するコマンド文字列を選ぶことができないので、確率が 0 にならない様に偽の出現回数を加へる。それぞれの属性及びコマンド文字列の出現回数は、実際に記録された出現回数に 1 を加へた値で確率を計算する³。

結果と考察⁴

冒頭にもリンクを貼ったデモは bash と zsh をそれぞれダウンロード・ビルド・インストールする流れのビデオである。ビデオ内では、入力済みのコマンド文字列は赤い文字で、推定によって提示されたコマンド文字列は白い文字で表示されてゐる。シェルがコマンド入力待ちになった瞬間に推定されたコマンドが白い文字で表示されてゐる。またユーザーがコマンドを一文字打つたびに、先頭部分が一致しないコマンドを除外して推定し直されてゐる。

このビデオでは、最初に bash のダウンロード・ビルド・インストールを行ってゐる間はシェルはほとんど役に立たない推定結果を提示してゐる⁵。その後 zsh のビルドとインストールをしてゐる際は、configure した後に make と make install が正しく提示されてをり、それぞれ確定キーを押すだけでコマンドが実行されてゐる。

もっともこのデモは人工的に作った短いものであり、実際の使用感はもっと長いスパンで測られるべきだらう。筆者が職場で一週間程度使ひ込んでみた所感としては、推定が当たることもあれども外れることもまだまだ多いといったところである。今回の手法が上手く効果を発揮できないパターンを以下にいくつか挙げる。

未知の状況での特殊例へのこだはり

以下の表の様に、コマンド T がこれまでに 6 回、コマンド U がこれまでに 1 回実行されてゐるとする。属性 $a_1$ は D と E の二つがこれまでに出現してゐるが、属性 $a_2, a_3$ はそれぞれ P, S しか出現してゐない。

ここで、現在の状況において属性 $a_2$ に未知の値 Q が現れたとする。補完候補として提示すべきコマンドは T か U か。過去の記録を見ると T の出現回数が U より何倍も多いので、T を提示するのが自然であると思はれる。ところが実際に確率を計算すると、U の確率の方が高くなる。

「属性値 P のもとで T を何度も実行した」といふ事実は、「T が実行される確率を U よりも高める」よりも強く「T が P 以外の属性値のもとで実行される確率を低める」方向に作用する。結果として、Q 以外の属性値のもとで実行された実績の少ない U の方が選ばれてしまふ。

これは体感的にはかなりイライラする誤判定で、「T を入力したいのに U が提示される」「提示された U を T に修正して実行する」といふ面倒なやり取りが何度も繰り返されることになる。

忘れ去りたい過去

以下のコマンド履歴を見てみよう。vim と make と ./a.out の単調な繰り返しに見えるが、途中から vim で編集するファイルが foo.c から bar.c に変はってゐる。どうやら最初は foo.c のデバッグを行ってゐた様だが、今は bar.c のデバッグを行ってゐる様だ。

$ vim foo.c
$ make
$ ./a.out
$ vim foo.c
$ make
$ ./a.out
$ vim foo.c
$ make
$ ./a.out
$ vim foo.c
$ make
$ ./a.out
$ vim bar.c
$ make
$ ./a.out
$ vim bar.c
$ make
$ ./a.out
$ 

ここで ./a.out の次に提示すべき候補は何だらうか。vim bar.c が正しさうに思はれるが、出現回数に基づいて確率が高い方が選ばれるので vim foo.c が提示される。vim bar.c が提示される様になるには、出現回数が vim foo.c を上回るまで vim bar.c を実行しなければならない。それまでは vim bar.c を実行したくてもずっと vim foo.c が提示される。

この問題の対策としては古い記録を無視する様にするとか新しい記録がより大きく確率に寄与する様に重みを与へるとかが考へられる。

錯誤の再現

コマンド名を打ち間違へてゐることに気付かず実行してしまったり、コマンドを実行した後に必要なオプションが足りてゐなかったことに気付いたりすることはよくある。この様な間違ったコマンドも均しく記録に残されるので、将来同じ状況が発生した時にその間違ったコマンドが再び候補として提示されてしまふ。

対策としては、間違って記録されたコマンドをユーザーが指定して記録から抹消できる様にするとか、間違ったコマンドを何らかの方法で自動判別して候補から除外する様にするとかが考へられる。当然後者の方が難しい。

今後の展望

……とまあこの様にコマンドの推定は結構な頻度で外れるし、コマンドの入力効率を高めるための改善の余地は多さうである。

今後進むべき方向は、予測が外れた時にいかにすばやく (少ない打鍵数で) リカバリーするかを先づ模索することだらう。例へば、今回実装した手法では過去の記録の中で最も確率の高いコマンド一つしか候補として提示しないが、提示する候補数を数個に増やすとかすれば第一の候補が外れたとしても他の候補が当たるかもしれない。

正解が出る確率を上げるためにベイズ推定のモデルを改良するといふ道も考へられるが、膨大な数のパラメーターの調整を地道に行ってゆくことになるだらうから、容易な道ではない。また、パラメーターの調整を機械学習の様な自動化された手法で行ふのはおそらく現実的ではない。なぜなら、学習のために大きなサイズのサンプルが必要となるからである。上述の例で見た様に、シェルが正しい候補を出す様になるまで何十回もシェルに正解を教へ続けなければならないとしたら、そもそも補完の目的は達成されてゐない。

さらに別な道としては、ベイズ推定以外の方法によって候補を算出することを模索するとか、コマンド文字列を行単位ではなく単語単位で区切って細かく補完してみるとか、アイディアはいろいろ出て来る。

とはいへ、今回実装した様なものをずっと C 言語で実装し続けてゆくのは骨が折れるので、筆者がこのまま (今回実装したものをさらに拡張する形で) 実験を進めてゆくかどうかは未定である。

ソースコード

今回実装したシェルのソースコードは筆者の GitHub レポジトリーに置いてある。本記事の補完機能を使ふ為にはいろいろと設定が要る (がそれらは文書化されてゐない)。今回の実装は実験用と位置付けてゐるので、これをシェルの正式なリリースに組み込むかどうかも未定である。

参考文献

• Allen B. Downey 著、黒川利明訳『Think Bayes: プログラマのためのベイズ統計入門』オライリー・ジャパン、オーム社、2014 年。ISBN978-4-87311-694-5。
• Wikipedia のベイズ統計学関連記事