キーボードの配列と最適化問題への入門
自作キーボード界隈を中心に（？）キーボードのより良い論理配列・物理配列を探求する動きがあるようです。
筆者は最近ZSA Voyagerを買い、論理配列の最適化について興味を持ったので、界隈でどういう動きがあるようなのか調べたり実装した結果をまとめていこうとしています。
アルゴリズムの実装には基本的にRustを用いました。Rustを使っているのは書いてみたかったからですが、Pythonだと探索問題の実行時間が遅く、試行錯誤にむしろ向いていないのも大きかったです。ただし、適宜その他のプログラミング言語も使います。
キーボード配列の問題
キーボードの物理的な配置自体も様々な工夫が試みられています。例えばZSA Voyagerであれば
- 分離型である: キーボードが左右に物理的に分かれている
- カラムスタッガードである: 同じ列のキーはズレずに配置されていて、同じ行のキーはズレて配置されている
- ロープロファイルである: 高さが低め
などの特徴を挙げることができます。
それはさておき、何らかの物理的なキー配置が与えられたときに、個々の物理キーにどのようなアルファベット等を割り当てるかが論理配列の問題となります。論理配列の中で最も普及しているのがQWERTY配列ですが、この配列が（何らかの意味で）最適かは明らかでな……いやむしろ、欠点が多いと指摘されることは多いです。
じゃあ具体的にどういう配列が最適なのか？という問題は多くの人が関心を持っていますが、今のところ諸説があり決定版はないようです。
いろいろな人が、いろいろなアプローチで、良い配列を探求していますね。
単純化して、組み合わせ最適化問題として扱う
筆者もこの問題に関心を持ったので、簡単に追試してみることにします。いくつか必要なものがあるので順番にそろえていきます。
- データセット: 典型的な入力を模倣するために必要になります
- キー入力のコストモデル: どのキーが押しやすい・押しづらいという情報をコスト関数にします
- 探索用のアルゴリズム: データセットの文字列を最も押しやすいアルファベット配置を探索します
キーのコスト
良い配置をどうモデリングするかですが、最初に行うのは、キーの位置にコストを割り当てることです。ホームポジションに近いキーは押しやすいのでコストは低く、遠いキーは押しづらいはずです。
具体的なコスト割り当ては容易ではない問題（個人差すらあり得る）ですが、例えばColemak Mod-DHではTyping Effort Modelなるものを提案していますし、Workmanでも類似のコスト表があります。
- https://colemakmods.github.io/mod-dh/model.html
- https://workmanlayout.org/#back-to-the-drawing-board
これらのコスト表があると、どのキーがどれぐらい押しづらいかがわかります。
データセット
アルファベットの出現頻度によって最適な配置は変わるはずです。例えば英語における最頻出のアルファベットはeなので、eキーは非常に押しやすい場所にあるのが良いはずです。そのような、一般的な入力の性質を捉えるデータセットを準備しておく必要があります。今回については
- とりあえず英語を前提にする（日本語はいろいろと準備が多いので）
- 平易で現代的な話し言葉を前提にする
- ほどほどのサイズで
というわけで、databricks-dolly-15kを使ってみることにしました。本来は対話タスクに関するデータセットのようですが、適当に結合して「自然な英語の並び」として利用します。
from datasets import load_dataset
dolly_dataset = load_dataset("databricks/databricks-dolly-15k", split="all")
with open("dolly-15k-flatten.txt", "w", encoding="utf-8") as f:
for data in dolly_dataset:
f.write(data["instruction"] + data["response"])
アルファベットの出現頻度を見てみます。とりあえず上位5件を見てみます。
# N-gram生成に使えそうなスクリプトだが今回はN=1として実行している
cat dolly-15k-flatten.txt | ruby -e'$stdin.read.gsub(/\s+/, "").chars.each_cons(1).map{|x| x.join("")}.each{|x
| puts (x)}' | sort | uniq -c | sort -nr | head -5
599930 e
436958 a
417638 t
380934 o
368156 i
Peter NorvigのGoogle Booksデータを使った調査だと、出現が多い順に1位からe t a o iなので、その意味では少しバイアスが乗っているのかもしれません。
いずれにしてもデータセットが手に入ったということで、続けていきます。
山登り法
キーの位置に対応するコスト表があるので、具体的なキー配列に対してデータセットを与えたときの総コストを計算することができます。今回は問題を単純化し
- キーボードの中心にある3x10部分だけを考慮する
- シフトキーのような修飾キーのことは一旦忘れる
- 未知の文字は無視する（適当な固定コストを入れているがあまり意味はない）
このような条件で実装してみます。
const LAYOUT_ROWS: usize = 3;
const LAYOUT_COLS: usize = 10;
#[derive(Clone)]
struct KeyboardLayout {
layout: [[char; LAYOUT_COLS]; LAYOUT_ROWS],
key_to_pos: [(usize, usize); 128],
cost_table: [[f32; LAYOUT_COLS]; LAYOUT_ROWS],
}
impl KeyboardLayout {
fn new(layout: [[char; LAYOUT_COLS]; LAYOUT_ROWS], cost_table: [[f32; LAYOUT_COLS]; LAYOUT_ROWS]) -> Self {
let mut key_to_pos = [(0, 0); 128];
for (r, row) in layout.iter().enumerate() {
for (c, &key) in row.iter().enumerate() {
key_to_pos[key as usize] = (r, c);
}
}
KeyboardLayout { layout, key_to_pos, cost_table }
}
fn swap_keys(&mut self, key1: char, key2: char) {
let pos1 = self.key_to_pos[key1 as usize];
let pos2 = self.key_to_pos[key2 as usize];
self.layout[pos1.0][pos1.1] = key2;
self.layout[pos2.0][pos2.1] = key1;
self.key_to_pos[key1 as usize] = pos2;
self.key_to_pos[key2 as usize] = pos1;
}
fn calculate_cost(&self, text: &str) -> f32 {
text.chars().map(|c| {
let c = c.to_ascii_lowercase() as usize;
if c < 128 {
let (row, col) = self.key_to_pos[c];
self.cost_table[row][col]
} else {
10.0 // 未知の文字
}
}).sum()
}
}
swap_keysはレイアウトを変更する関数です。後ほど山登り法で利用します。KeyboardLayoutを使うと、文字列に対するコストを計算できます。
fn main() -> Result<(), std::io::Error> {
let initial_layout = [
['q','w','e','r','t','y','u','i','o','p'],
['a','s','d','f','g','h','j','k','l',';'],
['z','x','c','v','b','n','m',',','.','/'],
];
let cost_table: [[f32; 10]; 3] = [
[3.0, 2.4, 2.0, 2.2, 3.2, 3.2, 2.2, 2.0, 2.4, 3.0], // 上段
[1.6, 1.3, 1.1, 1.0, 2.9, 2.9, 1.0, 1.1, 1.3, 1.6], // 中段（ホームポジション）
[3.2, 2.6, 2.3, 1.6, 3.0, 3.0, 1.6, 2.3, 2.6, 3.2], // 下段
];
let mut keyboard = KeyboardLayout::new(initial_layout, cost_table);
println!("{}", keyboard.calculate_cost("this is a pen")); // => 31.300001
}
キー配置の最適化とは、十分に大きなデータセットに対してコストが最小になるlayoutの発見です。
キー配置は膨大な組み合わせがあるので全探索は現実的ではないですが、コスト関数が改善するような配置を探索的に求めることはできます。今回は、最も基本的なアルゴリズムである山登り法を実装しました。このアルゴリズムについては資料が沢山あります。
山登り法は性能が良いとは限らない上に、局所解からの脱出が原理的にできない欠点があります。しかし、実装が容易かつ挙動が単純で、複雑なハイパーパラメータがいらないため、取り扱いがしやすい手法でもあります。
今回の問題では、近傍としてランダムに選んだ2つのキーを入れ替える操作を行い、コストが改善した場合にはそれを暫定の最適解として採用し、次の近傍を探索するという操作を一定回数繰り返します。
ちなみに乱数生成にはrandクレートを用い、配列の初期値としてQWERTY配列を与えました。
fn hill_climbing(initial_layout: &mut KeyboardLayout, iterations: usize, sample_text: &str) -> () {
use rand::prelude::*;
let mut rng = thread_rng();
let mut current_cost = initial_layout.calculate_cost(sample_text);
for _ in 0..iterations {
let key1 = initial_layout.layout[rng.gen_range(0..LAYOUT_ROWS)][rng.gen_range(0..LAYOUT_COLS)];
let key2 = initial_layout.layout[rng.gen_range(0..LAYOUT_ROWS)][rng.gen_range(0..LAYOUT_COLS)];
initial_layout.swap_keys(key1, key2);
let new_cost = initial_layout.calculate_cost(sample_text);
if new_cost < current_cost {
current_cost = new_cost;
} else {
initial_layout.swap_keys(key1, key2); // 元に戻す
}
}
}
fn main() -> Result<(), std::io::Error> {
let initial_layout = [
['q','w','e','r','t','y','u','i','o','p'],
['a','s','d','f','g','h','j','k','l',';'],
['z','x','c','v','b','n','m',',','.','/'],
];
let cost_table: [[f32; 10]; 3] = [
[3.0, 2.4, 2.0, 2.2, 3.2, 3.2, 2.2, 2.0, 2.4, 3.0], // 上段
[1.6, 1.3, 1.1, 1.0, 2.9, 2.9, 1.0, 1.1, 1.3, 1.6], // 中段（ホームポジション）
[3.2, 2.6, 2.3, 1.6, 3.0, 3.0, 1.6, 2.3, 2.6, 3.2], // 下段
];
let mut keyboard = KeyboardLayout::new(initial_layout, cost_table);
let text = fs::read_to_string("dolly-15k-flatten.txt")?;
let sample_text = &text;
println!("Initial layout:");
keyboard.print_layout();
println!("\nCost table:");
keyboard.print_cost_table();
println!("\nInitial cost: {}", keyboard.calculate_cost(sample_text));
hill_climbing(&mut keyboard, 10000, sample_text);
println!("\nOptimized layout:");
keyboard.print_layout();
println!("\nOptimized cost: {}", keyboard.calculate_cost(sample_text));
return Ok(());
}
実行例
実行例です。1万回程度の試行回数に対して、手元のPCだと1分ほどかかりました。
$ cargo run --release
Compiling keyopt v0.1.0 (/home/saka1/repos/keyopt)
Finished `release` profile [optimized] target(s) in 0.23s
Running `target/release/keyopt`
Initial layout:
q w e r t | y u i o p
a s d f g | h j k l ;
z x c v b | n m , . /
Cost table:
[3.0, 2.4, 2.0, 2.2, 3.2, 3.2, 2.2, 2.0, 2.4, 3.0]
[1.6, 1.3, 1.1, 1.0, 2.9, 2.9, 1.0, 1.1, 1.3, 1.6]
[3.2, 2.6, 2.3, 1.6, 3.0, 3.0, 1.6, 2.3, 2.6, 3.2]
Initial cost: 14993535
Optimized layout:
j g c m z | / u d y v
s n t a . | , e o i r
q b f l k | x h p w ;
Optimized cost: 11960405
結果はなんとなくそれらしいものです。出現上位のe a t o iが打ちやすい中段中央部に集まっています。母音のuが中央だが上段の微妙な位置にあるのも印象的（英語では出現頻度がまあまあなので理屈はわかります）で、ColemakやWorkmanと似た選択をしているようにも見えます。
改善はいくらでもできる
ここまでの実装はごく原始的な、入門レベルのものです。改善点は大量に挙げることができます。
- 同一の指や片手に負担が偏ることに対してコスト関数にペナルティを与える
- 例えばbigramでコストを計算するようにすると、局所的な履歴を活用した計算式が書ける
- コスト計算に無駄が多い
- 今回の範囲だとコストとして文字単位でしか見てないので、あらかじめテキストを文字単位でカウントしておき、文字のコストと出現数の積を取ればコストが出せる
- 近傍計算のとき、2つしかキーが更新されないので、ほとんどの文字に関してはコストが変わっていない。本来はここを差分計算したい
- 英語と一部の記号しか考慮していない
- データセットの多様性
- その他のキー・修飾キーなどの考慮
とはいえ、大枠としては、キーボードレイアウトの問題は組み合わせ最適化問題の一種として扱うことができそうだとわかりました。
ひとつ改良してみる
この記事では、とりあえずコスト関数を改良し、結果にどういった変化があるか観察する所までをやってみます。
- 同じ指の入力が続くのは大変なので、ペナルティを与える
- 片手での入力が続くのは大変なので、ペナルティを与える
これらの条件を扱うには、現在のキー入力だけでなく過去1文字分の入力履歴が必要です。この条件を素直に実装するのはそれほど難しくありません。
fn calculate_cost(&self, text: &str) -> f32 {
let chars = text.as_bytes();
let mut total_cost: f32 = 0.0;
for i in 1..text.len() {
let key1 = chars[i-1].to_ascii_lowercase() as usize;
let key2 = chars[i].to_ascii_lowercase() as usize;
if key1 >= 128 || key2 >= 128 {
total_cost += 10.0;
continue;
}
let pos1 = self.key_to_pos[key1];
let pos2 = self.key_to_pos[key2];
total_cost += self.cost_table[pos2.0][pos2.1]; // 指の基本コスト
// 連続運指
total_cost += match (pos1, pos2) {
((r1, c1), (r2, c2)) if c1 == c2 && r2.abs_diff(r1) <= 1 => 0.5,
((_, c1), (_, c2)) if c1 == c2 => 1.0,
(_, _) => 0.0,
};
// 左右交互打鍵ペナルティ
total_cost += match (pos1, pos2) {
((_, c1), (_, c2)) if c1/5 == c2/5 => 1.0,
(_, _) => 0.0
};
}
total_cost
}
ペナルティの値は適当に定めました。実行してみます。
Initial layout:
q w e r t | y u i o p
a s d f g | h j k l ;
z x c v b | n m , . /
Cost table:
[3.0, 2.4, 2.0, 2.2, 3.2, 3.2, 2.2, 2.0, 2.4, 3.0]
[1.6, 1.3, 1.1, 1.0, 2.9, 2.9, 1.0, 1.1, 1.3, 1.6]
[3.2, 2.6, 2.3, 1.6, 3.0, 3.0, 1.6, 2.3, 2.6, 3.2]
Initial cost: 19047266
Optimized layout:
; . g u q | k c l p w
h o a e j | , t n s r
/ x y i z | b d m f v
Optimized cost: 14638259
これもまた興味深い結果になりました。
- おそらく左右交互の打鍵を重視するようにコスト関数を書いたため、片手（左手）に母音が集中している
- 右手中段に
t n s rが出現したが、これはAstarte配列と同じ並びになっている
左手には母音u e iが縦に並んでいるのも気になるところです。母音が連続で出現することは稀なので、同一カラムに母音を配置することで同一カラム連続のペナルティを避けられ、しかもiの位置は中段小指とコストが変わらないため、この並びが発見されたように見えます。
まとめ
キーボード配列の発見を組み合わせ最適化問題として解くべく、必要な道具を順番に作っていくことをしてみました。
今回の実装は初歩の初歩というところで、発展の余地はいくらでもあります。しかしながら、ごく初歩的なコードであっても良いとされる並びを（部分的に）再発見できたのは興味深いことでした。
Discussion