「シェルのコマンドライン補完をグーグルの検索ワードの補完みたいに賢くしたい」といふことで、以前ベイズ推定を用ゐた補完機能を自作のコマンドラインシェルに実装してみたのであるが、まづまづの結果に終はった。今回は、補完のアルゴリズムを一新して出直した。結果としては自分の実用に堪へるレベルの使ひやすさを達成できた。

この記事では、シェルに実装した補完機能のアルゴリズムについて解説する。この補完機能では、過去に入力したコマンド文字列とその順序を覚えておき、現在の入力状況に照らし合はせて最も次に入力される確率が高さうなコマンド文字列を自動的に推定して入力候補として提示する様になってゐる。候補が合っていればそれを確定させることで素早くコマンド文字列が入力できるといふ寸法である。

背景

まづ、この機能の有用性をまだ理解してゐない方のために、前回の記事の一部をここにコピペしておく。

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

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

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

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

ベイズ推定を用ゐる補完候補の提示手法では誤った候補が提示されることが多いといふのが前回の結果であった。前回の手法では、候補とするコマンドラインの確率を行単位で計算してゐたため、一部が共通する複数のコマンドラインの確率を十分に考慮できてゐなかった。例へば cd で始まるコマンドの履歴として以下がほぼ同確率で記録されてゐるとする。

cd Documents/2016/11/23
cd Documents/2016/12/25
cd Documents/2017/1/1
cd Documents/2017/1/9
cd Documents/2017/2/11

次に cd と入力した時、どの様な候補が提示されるべきか。前回の手法では上記四行のうち最大の確率を持つもの一つが選ばれるので、cd Documents/2017/3/20 と入力したかったのに cd Documents/2016/12/25 が提示されるといふ様なことが起こりがちであった。その様な誤った候補が提示された場合、結局補完に頼らずにコマンドを打ち込むかあるいは補完をしたのち誤った部分を削除しなければならず、コマンドの入力に必要なキーストロークはあまり減ってゐない。これを改善するために、今回の手法では文字単位で確率を求めることによってコマンドラインの一部を候補として提示できる様にする。

手法

今回の手法の概略は以下の様になってゐる:

1. 新しいコマンドラインの入力を始める時、シェルはこれまでのコマンド履歴に基づいて “prediction tree” を生成する。
2. Prediction tree と入力途中のコマンドライン文字列に基づいて、補完候補を生成する。

Prediction tree の生成

Prediction tree とは、文字列に確率を対応させる写像である。効率化のためにプログラム内でトライ木構造を取ることから、prediction tree と呼んでゐる。しかし木構造のことはさて置いて、文字列に対する確率がどの様に決まるかに着目しよう。

そのためにまづ、コマンド履歴の各行に対して確率を割り当てる表を作成する。以下に例示する表では、「コマンド」の列に書いてある文字列が過去に入力され履歴に保存されてゐるコマンド文字列を表してゐる。表の上の方にある行がより古い履歴を表してをり、一番下の行が最新の履歴 (つまり直前に入力されたコマンド) である。

履歴にある各コマンドに対して、$P_0$ から $P_3$ まで四種類の確率¹を割り当てる。$P_0$ は、新しいコマンドから順に 1/2, 1/3, 1/4, ... と値が小さくなるやうに自然数の逆数を割り当ててゆく。これは、「最近入力されたコマンドは昔入力されたコマンドよりも再び入力される確率が高い」といふヒューリスティックをモデル化したものである。1/1 ではなく 1/2 から始めるのは、最新のコマンドが他のコマンドに比べて相対的に高すぎる確率を持たない様にするためである。

$P_1$ も同様に 1/2, 1/3, ... と自然数の逆数を割り当ててゆくが、それぞれの直前のコマンドが今入力しようとしてゐるコマンドの直前のコマンドと一致しないものは飛ばす。この例では今入力しようとしてゐるコマンドの直前のコマンドは baz であるから、直前のコマンド (つまり一つ上の行) が baz となってゐるコマンドに対してのみ確率を割り当てる。これは、「このコマンドを実行した後にはあのコマンドを実行する確率が高い」といふ様なコマンドの連続性をモデル化するものだ。

$P_2$ も同様だが、今度は直前のコマンドとその一つ前のコマンドの二つが一致するもののみに確率を割り当てる。この例では、直前が baz でその前が bar となってゐるコマンドに対してのみ割り当てることになる。二つのコマンドの一致をみることで、$P_1$ よりもより強固なコマンドの連続性を確率化する。

$P_3$ も同様に三つのコマンドが一致するもののみに確率を割り当てるが、この例では該当するものは無い。同様に $P_4, P_5, ...$ とどんどん求めてゆくことができるが、それほど多くのコマンドの連続性を考慮しても補完候補の精度は上がりさうにないので $P_3$ で止めておく。

$P_0$ から $P_3$ までを求めたら、それぞれのコマンドについて $P_0$ から $P_3$ までの最大値を $P$ とする。これが、「そのコマンドが今再入力されようとしてゐる確率」であり「そのコマンドを補完候補として提示すべき度合ひ」である。ただしこれはあくまでも履歴にある各コマンドの確率を独立して求めたに過ぎない。ここから文字単位の確率に分解し、同一の文字(列)に対する確率を合成してゆく。

例へばこれから foo といふコマンド文字列が入力されようとしてゐるとする。しかし foo を入力するためにはまづ fo を入力する必要があり、そのためには初めに f を入力する必要がある。となると、もし foo が入力される確率が 1/2 だとしたら fo および f の確率もまた 1/2 であると言へよう。この考へに従って、上の表に示した $P$ の値をそれぞれのコマンド文字列の先頭部分文字列に対しても割り当てると、以下の様になる。

• b, ba, bar → 1/9
• b, ba, baz → 1/8
• f, fo, foo → 1/2
• b, ba, baz → 1/6
• b, ba, baz → 1/3
• f, fo, foo → 1/2
• b, ba, bar → 1/3
• b, ba, baz → 1/2

ここで同一の文字列同士をまとめて確率の和を取ると、文字列から確率への写像すなはち prediction tree が得られる。

前述の通り、prediction tree はプログラム内ではトライ木構造によって表現される。このトライ木構造は、上記の例の様な表を介して生成する必要はない。コマンド履歴内にあるコマンド文字列を一つづつ辿りながら直接確率を計算しトライ木に追加 (加算) してゆけばよい。履歴を辿る途中で覚えておく必要があるのは次に来る $P_0, ..., P_3$ の値のみである。²

補完候補の生成

補完候補の文字列は prediction tree に基づいて生成する。

まづ、現在入力中のコマンドラインに既に何文字か文字が打ち込まれてゐる場合は、その文字で prediction tree を辿る。これにより、これから入力されようとしてゐる部分のみを対象とする prediction tree の部分木構造が得られる。以降はこの部分木を単に prediction tree と呼ぶ。

次に、prediction tree の中から長さ 1 の文字列で確率が最も大きいものを選ぶ。上の例では、 b (≒1.57) と f (=1.00) の二つのうちより大きい確率を持つ b が選ばれる。これが、次に入力される可能性が最も高いと思はれる文字である。

続いて、その文字で始まる文字列の中で確率がその文字の確率の半分以上のものに候補を絞り込む。残った候補のうち最も文字数の多いものが最終的な補完候補となる。上の例では b の確率は 1.57 であったから、b で始まる文字列のうち 1.57/2 = 0.78 以上の確率を持つものが残る。

• b (1.57)
• ba (1.57)
• baz (1.13)

これらの中で最も文字数が多い baz が補完候補となる。

最終的に選ばれる候補が何を意味してゐるかといふと、ユーザーが次に入力しようとしてゐる一文字の推測 (b) が当たってゐるといふ前提の下で、ユーザーがこの候補 (baz) を入力する条件付き確率が 1/2 以上だといふことである。つまりこの候補は 1/2 以上の確率で「当たってゐる」はずだといふことになる。³

考察

今回のアルゴリズムは、確率の高い文字列を候補とすることと確率の低い文字列を候補から除外することとを両立させることができてゐると感じてゐる。背景の節に上げた cd コマンドの例を振り返ると、prediction tree における c の確率と cd Documents/201 の確率は同等となるから候補として少なくとも cd Documents/201 までは提示される。しかし cd Documents/2016/12/25 の様な個別のコマンド文字列全体は c よりも低い確率を持つことになるから、そこまでが候補として提示されることは少なくなる。

今回のアルゴリズムも、過去の入力されたコマンドの履歴のみに基づいて補完を行ふといふ点では前回と同様である。したがって、まだ一度も入力されたことのないコマンド文字列を候補として提示することはできない。一方で、今回実装したシェルには Tab キーを押すと入力中のコマンド文字列に応じてコマンド名や引数を補完する機能があり、こちらを使へばまだ入力されたことのないコマンド文字列も補完候補として提示することができる。これら二種類の補完方式を統合して候補の精度を高めることにはまだ着手できてゐない。

プログラム

ここで説明した補完アルゴリズムは筆者が自作したコマンドラインシェル yash のバージョン 2.44 に実装してある。ソースコードは GitHub でも見られる。