私がこのブログ記事を書いたきっかけは、Russell Brandにバナナを投げる女性を見たことでした。しばしお付き合いいただければ幸いです。

そう、果物を使ったこの攻撃的行為を目撃した私はすぐ、友人にメッセージを打って知らせました。その際、携帯電話で「banana」と「Brand」という単語を最新のSwype式キーボードで打つのが信じられないほどイライラする作業だったのです。可哀想な親指は、画面上の「A」と「N」の間を何時間も行ったり来たりしているかのようでした。もっといい方法があるはずだ、と思いました。親指を動かす距離を最小限に抑えて、左手に起きてしまうであろう反復性ストレス障害（RSI）の発症を遅らせてくれるような方法が。

本記事では、英語のQWERTYキーボードのレイアウトを最適化することについてお話ししていきます。目標は、単語を打つために指が移動する平均距離を最小化することです。それでは、見ていきましょう。

QWERTYキーボード

まずは、標準的な英語キーボードのレイアウトであるQWERTYについて検討してみます。

距離の単位としては、上の画像で文字間の縦と横のオフセットを1単位とします。例えば、単語「QWERTY」をタイプするのに必要な距離は5単位、「TREE」なら2単位となります。

全ての文字ペア間の距離を図にすると、以下のようになります。

上図において、濃い色は距離が大きいことを示す。

これを見ると、特に距離が大きいのはQとPの間などであることがすぐに分かります。しかし、英語ではその2文字が単語の中で隣接することはあまりないので、それほど問題はありません。基本的な確認で、各文字から他の全文字までの平均距離を図にしてみました。

各キーの各文字までの合計距離

これを見ると、Qはたまにしか使わないのでキーボードの一番端にあっても問題ないと思うでしょうが、もっと頻繁に使うAはもう少し中央寄りの方が良いかもしれません。

この考えを量的に表すため、 NLTKライブラリ にあるReutersのコーパスを使って、英語の様々な文字間の遷移の頻度を集計してみました。

文字の組み合わせで特に多いのは「TH」、「HE」、「IN」、「AN」のようです。もしキーボードをスワイプする平均距離を私が最小化するとしたら、これらの文字ペアができるだけくっつくように配置したいかもしれません。

上の遷移頻度にQWERTYキーボードでの距離を掛け合わせることで、単語の距離を増やす最大の原因となっているのはどのキーであるかを可視化できます。

この図ですぐ目につくのは、英語のスワイプにおいて「AN」の遷移の距離が突出して大きいことです。AとNの間の距離はキーボード上で一番離れているわけではありませんが、ペアとして頻繁に出現するので合計距離が非常に大きくなっているのです。また、キーAから、およびキーAへの合計距離が最大となっているのは、よく使われる文字でありながらキーボードの端に配置されているからであることも分かります。

このため、そして他にも距離の大きなペアがあるため、英語で1文字当たりに必要となる平均距離はおよそ3.2となっています。つまり平均すると、QWERTYのレイアウトにおいて、親指は文字と文字の間でキー3個以上を移動しているということです。

この残念な状況を最適化する作業に入る前に、上記の数値を私がどうやって算出したか簡単にご説明しましょう。

単語の平均距離の計算

ここでは、重要な量が2つあります。

• 文字間の遷移確率を計算する文字遷移行列、 （ここで意図しているのはIとJではない。 を使っているのは、文字をアルファベット順に索引付けするためである。つまり、 の文字はA、 の文字はBといった具合になる）。これは単に言語、ここでは英語の関数とみなせる。
• 文字間の物理的距離を格納する文字距離行列、 。これはキーボードレイアウトの関数で、前掲の図はQWERTYの場合の例となる。

文字 からの合計移動距離は以下のようになります。

なお、 は対称なので、簡潔に と書けることに注意してください。

次に、英語の各文字の出現確率 を出す必要があります。これは、前と同様にReutersのコーパスから計算することができます。また、 はマルコフ連鎖を表すので、固有値1に対応する の左固有ベクトルは単純に文字頻度 となることに注意してください。

そして最終的に、このキーボードの平均距離 は、以下のように単純に表されます。

この量が、前の図の一番上に記されているものです。

最適化の手順

キーボードレイアウト案を考える際には、以下の制約があります。

• ちょうど26個のキーがある
• キーの位置は変わらない
• 各文字のキーは1個ずつしかない

そして、順列空間を探索することになります。仕様に沿ったキーボードレイアウト案はそれぞれ、 の行と列に等しく適用される順列に相当します。この順列を適用して、上記の計算を行うと、平均距離の値を求めることができます。

あいにく、考慮すべき順列は 個もありますので、力ずくで全部をチェックすることはできません。

そこで、2種類の近似探索アルゴリズムを試しました。

• 焼きなまし法：2個のキーを繰り返しランダムに交換し、平均距離の変化 を計算する。この変化を確率 で受け入れるが、ここで はある「温度」を表す。新しい順列の方が距離が小さければ、 となり、変化は常に受け入れられる。局所最小値で行き詰まるのを避けるため、 が より大きすぎない場合は、平均距離を増やす変化を受け入れることもできる。解に収束させるために、繰り返しの際には を徐々に小さくする。
• ナイーブな山登り法：ランダムな初期設定から始めて、可能な全ての26×26文字の交換をチェックする。成績が最も改善される交換を選び、それを繰り返す。改善される交換がない場合は終了する。

最適化されたキーボードレイアウト

ちょっと驚いたことに、どちらの手法も似たような成績となり、キーボードレイアウトの改良案がいくつも見つかりました。どちらも厳密なアプローチではありませんので、より優れたレイアウトが存在するかもしれませんが、最も成績が良かったのは私がNALMY/ZVDNALMY/GIEROと呼ぶ以下のレイアウトです。

平均距離が2を切りました！　正確には1.99324です。これは標準のQWERTYに比べて成績が39％改善されており、平均で親指が文字と文字の間をキー3個ではなく2個だけ移動すればよいことになります。

他にも、平均距離が2未満となる良いレイアウトが、以下のようにいくつか見つかりました。

訳注:こちらは元々Javascriptのアニメーションとなっています。この記事ではキャプチャを載せていますが、より正確なものは 元記事 を参照してください。

これらのレイアウトを見ると、いくつかの共通点があることが分かります。

• アクセスしやすいよう、キーEは一貫してキーボードの中央に配置されている
• AとNは常に隣接している
• IとNは常に隣接している
• R、S、Tは常にかたまっている
• Z、Q、K、J、Xは常にキーボードの外側に追いやられている

以上の明らかな特徴の他に、H、C、L、Dといった “二流” の文字の一部をちょうどいい場所に配置することも重要です。これらの文字は通常、特定の文字の近くにあるべきなので、その配置は、頻繁に使われる文字から成る中核部の細かな配置によってかなりの部分が決まるのです。

成績の比較

NALMYとQWERTYの有効性は、直接比較することができます。例えば、この2つのアプローチについて、英語の全単語の距離を計算するのです。以下の図は、全単語の1文字当たりの距離を示したものです。

これは英単語についての分布ですが、NALMYでは多くの単語を1文字当たり（キー）2単位未満の距離でタイプでき、QWERTYの平均約3単位よりはるかに成績が良いということが一目瞭然です。

QWERTYでタイプする1文字当たりの距離が最も大きい単語は、 palapalai、papal、jalapa でした。

NALMYでタイプする1文字当たりの距離が最も大きい単語は、 syzygy、Uzbek、cozy でした。

これらの単語距離を同時分布で表すこともできます。

黒色の線はレイアウト間が等しくなる点を示す。

線より上にある点は、NALMYの方が距離の大きくなる単語を表し、線より下にある点はNALMYの方が距離の小さくなる単語を表します。明らかに大多数は距離が小さくなっているものの、いくつかの単語ではNALMYの方が成績が悪くなっています。最も顕著な単語は「look」です。この単語は、QWERTYではユニークに最適化されているのです（面白いことに、単語「pookoo」も同様です）。

「Alan」、「land」、「dial」といったNALMYで最も改善されている単語はどれも、QWERTYではキーボード上をぎこちなく動き回る必要がありました。

バナナの結果は？

この問題の核心に入りましょう。私が単語「banana」で感じたイライラは、本当にもっともなものだったのでしょうか。英語全体でベンチマークテストを行った結果、以下のことを確認できました。

• QWERTYで「banana」をタイプするには1文字当たり4.6単位移動する必要があり、全英単語中99パーセンタイル順位に該当する。
• NALMYで「banana」をタイプするには1文字当たり1.3単位しか移動する必要がなく、全英単語中6パーセンタイル順位にまで下がる。

成功です！

私のレイアウト案が適正であることを最終確認するため、以下のように仮定してみます。

• 世界で英語を話す約5億人が、Swype式キーボードの配置をNALMYに切り替える。
• 1人が1日当たり約1,000文字を携帯電話でタイプする。
• キー1個当たりの距離は約8ミリメートルである。

すると、NALMYなら親指の動きを1日当たり500万キロメートルも節約できるのです。親指を8ミリ動かすと 約1ジュールのエネルギー を消費するとすれば、1日当たり625ギガジュールのエネルギーの節約となります。つまり、世界の平均消費人力を10メガワット低減できるのです。

コード

この記事のために使ったコードは粗末なものですが、Jupyterノートブックとして本ブログのリポジトリで公開しています。謎めいた索引付けと１文字変数が混在しています。

https://github.com/jasmcole/Blog/tree/master/Swype%20Right

この問題についてより効率の良いアプローチがありましたら、ぜひコメントをお寄せください！