NIK/kana

遺伝的アルゴリズムで求めた

口語に適した中指シフトかな配列

○配列

名無しさん

2006/07/30

結果、以下の配列が得られた (★は前置シフト)。

アンシフト
け	に	と	こ	さ	れ	っ	い	の	る	ま
し	た	★	か	て	く	ん	★	゛	な	ー
ら	す	よ	は	ょ	き	う	、	。	゜	・
シフト(★の後)
ぁ	ゃ	ろ	ほ	ゆ	わ	む	や	え	ぇ	「
ぃ	お	も	あ	ゅ	め	り	つ	ち	せ	」
ぅ	ね	そ	へ	ふ	ぬ	み	ひ	を	ぉ

目的
設計方法の概要
- 配列の条件
  - 固定文字
打鍵時間の測定
指の使用率を決定
資料収集
- 資料の修正
N-gram 作成
遺伝的アルゴリズムによる配列生成
結果
- 配列の評価
- 総評
付録
- 参考文献

この文章でのキー位置の表記について注意

普通、キーの位置をあらわすためには QWERTY 配列でその位置にある英字を使う (例: 下段左端のキーを Z と書く)。しかし、この文書では Dvorak 配列で位置を表している。これは以下の理由による。

打鍵時間の測定や GAプログラム内部では Dvorak 配列を用いているので、それらと統一するほうが混乱が少ない。
測定の被験者が普段 Dvorak 配列を使っていることにより、指の訓練度が QWERTY 配列使用者とは異なっているかもしれない。例えば上段左中指は、QWERTY 配列では E というよく使われる文字だが、Dvorak 配列では . (ピリオド) という記号である。被験者はC++プログラマで、浮動小数点数をあまり使わないので、上段左中指の訓練度が低いかもしれない。これに留意するため。

一般的な QWERTY キーボード使用者には読みづらい文書になるが、ご容赦いただきたい。

目的 †

以下のような特徴をもつ、新しい中指シフト配列を作成する。

日常的な文章 (メール・チャット・ブログなど) を楽に打てる
手首接地、肘を軽く開いた姿勢で楽な運指になるようにする
特殊なキーボードは使わない

現在、中指シフト配列の主流は「月配列2-263」であろう。月配列は十分に優れた配列だが、ですます調の文・くだけた文を入力するとき、難しい運指が出現しやすい。これは月配列の元になった新JIS配列が、高校教科書・科学/情報論文・朝日新聞の天声人語などを基礎資料としたからだろう。

新JIS設計当時に比べ、多くの人がPCを使うようになった。教科書・論文・新聞記事を書く人の割合が相対的に減り、メール・チャット・ブログなど、くだけた文を書く人の割合が増えていると考えられる。以下に例を挙げる。

教科書・論文・新聞記事など	メール・チャット・ブログなど
なのではありませんか	なんじゃないですか
私だけではないが	俺だけじゃないけど
仕方あるまい	しょうがない
慎重な議論が求められる	ヤダヤダ！そんなのヤダ！(ｼﾞﾀﾊﾞﾀ)

ここで作る配列は、口語的な、くだけた文の入力に最適化する。肘を軽く開き、脱力して前腕・手首を接地した姿勢を想定する。エルゴノミックではない普通の安価なキーボードを使う。つまり端的に言えば、以下のようになる。

正しくない日本語を
正しくない姿勢で
正しくないキーボードを使って
最高に楽に入力できる配列

↑

設計方法の概要 †

以下の手順で配列を設計した。

配列の条件を設定する。
打鍵時間の測定。範囲内のキー 2つのすべての組について、打鍵時間を測定し、打ちやすい運指・打ちにくい運指を数値化する。
指の使用率を決定。各指の筋力を測定する。筋力に比例した指の使用率を理想使用率と定める。
資料収集。新配列で入力することを想定する文章サンプルを大量に集める。
N-gram 作成。文章サンプルを1文字～6文字単位で区切り、出現頻度の高い順にソートする。
遺伝的アルゴリズムによる配列生成。打鍵時間・指使用率・N-gramを使って評価関数を定義し、評価関数の値が最少になるような配列を、遺伝的アルゴリズムで求める。

↑

配列の条件 †

中指シフト配列である。中段中指を前置シフトキーとする。
使用するキーは、上中下段の3段、左手5列 (小指・薬指・中指が1列、人差し指が2列)、右手6列 (薬指・中指が1列、人差し指・小指が2列)、合計33キー。Dvorak配列では以下の英字の位置に相当する。

' , . P Y F G C R L /

A O E U I D H T N S -

; Q J K X B M W V Z \
配置する文字は以下の 63 文字。
```
  ｡｢｣､･ｦｧｨｩｪｫｬｭｮｯｰｱｲｳｴｵｶｷｸｹｺｻｼｽｾｿﾀﾁﾂﾃﾄﾅﾆﾇﾈﾉﾊﾋﾌﾍﾎﾏﾐﾑﾒﾓﾔﾕﾖﾗﾘﾙﾚﾛﾜﾝﾞﾟ
```
- キーが33個あり、うち2キーはシフトに使用するから、アンシフト面に31文字・シフト面に33文字で合計64文字を配置できることになるが、配置する文字はこれより1文字少ない。よってキー位置はひとつ余る。

↑

固定文字 †

ある程度覚えやすい配列にするために、いくつかの文字は下記の位置に配置すると決める。

アンシフト

★

゛

ー

★(シフト) ゛(濁点) ー(長音記号)

、

。

゜

・

、(読点) 。(句点) ゜(半濁点) ・(中黒)

シフト

ぁ

ぇ

「

ぁぇ(小) 「(左カギ括弧)

ぃ

」

ぃ(小) 」(右カギ括弧)

ぅ

ぉ

○

ぅぉ(小) ○(文字なし)

月配列2-263を参考にした。
現代日本語では外来語が多いだろうから、長音記号をアンシフト中段右小指外側に配置し、同下段に中黒を配置する。これらの記号は口語的な日本語でも頻繁に使われる (感動詞など)。

↑

打鍵時間の測定 †

範囲内のキー 2つのすべての組について、打鍵時間を測定した。

測定結果は KeyTime.txt のとおり。書式は、

    ab 15 1555
    ~~ ~~ ~~~~
    打 測 合
    鍵 定 計
       回 時
       数 間[msec]

↑

機材・測定対象 †

使用キーボード

PFU製 Happy Hacking Keyboard Lite 2 (日本語配列), PD-KB210W/P, S/N B02030008763
- 『窓使いの憂鬱』で Dvorak配列 にしてある。

被験者

成人男性、右利き
プログラマー、主にC++言語を使用
肘を軽く開き、手首を接地した姿勢

↑

キーの範囲 †

以下の 33 キー(Dvorak配列)について、任意の 2つの組み合わせを打鍵する時間を測定した。33*33=1089組ある。

'	,	.	P	Y	F	G	C	R	L	/
A	O	E	U	I	D	H	T	N	S	-
;	Q	J	K	X	B	M	W	V	Z	\

↑

測定方法 †

使用したファイルは KeyTimeKana ディレクトリにある
測定プログラム KeyTime.exe
測定結果は save.log に記録 (以降このファイルを ..\KeyTime.txt に改名して使用する)
結果を表示するツールは ktDisp.exe

KeyTime.exe を使って、以下のように測定した。

測定回数の最も少ないキー組からランダムで1組を選ぶ (たとえば A B )
被験者はそのキー組を3回連打する。(ABABAB)
キー組が正しく入力されるたびに、かかった時間を記録する。
- 間違ったキーを打ったときは記録しない
- ABABAB のキーを測定するとき、AB の時間だけを記録し、BA の時間は加算しない。
1089組すべてについて十分な個数のデータが集まるまで、以上を繰り返した。

なお、被験者は以下の点に気をつけて打鍵した。

普段通りの運指にする。(AEAEAEを打つとき、Aを左手・Eを右手で打つ、などは反則)
疲れない程度に、できるだけ速く入力する。

↑

結果 †

KeyTime.txt から (平均打鍵時間) = (合計時間) / (測定回数) を求めると、以下のようになった。

第2キー
		'	,	-	.	/	;	\	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
第1キー	'	153	134	82	103	74	297	99	221	101	86	98	173	87	114	94	135	213	178	76	108	88	220	119	253	83	85	98	133	97	106	160	158	101
	,	126	161	77	104	91	235	90	138	117	91	95	172	124	115	109	147	237	170	96	114	99	210	135	293	86	91	97	135	108	120	193	136	110
	-	143	141	161	117	189	135	245	142	139	118	148	135	216	153	128	123	117	160	204	135	130	127	138	137	137	208	121	108	177	142	119	130	250
	.	123	113	83	166	70	216	98	160	109	106	114	211	117	111	112	156	232	195	73	98	98	184	138	271	125	91	105	123	114	114	195	165	113
	/	134	136	245	123	169	171	284	151	144	124	138	127	150	132	137	122	146	144	208	168	204	140	125	127	117	231	163	125	240	231	117	111	260
	;	304	259	77	232	58	174	78	251	107	83	98	139	94	102	106	150	128	158	83	92	85	188	205	172	83	75	84	139	112	111	147	191	83
	\	126	127	259	125	276	141	186	134	166	227	196	134	287	247	181	133	134	127	315	161	186	149	130	134	227	219	163	116	197	175	148	136	233
	A	245	196	69	114	53	206	94	158	104	92	104	107	93	90	83	102	171	128	72	95	73	119	133	216	66	80	96	102	75	84	145	121	86
	B	112	108	129	108	134	134	142	107	177	126	203	105	266	243	194	96	116	95	100	218	121	111	125	132	119	85	107	83	153	176	122	110	121
	C	105	106	147	116	120	120	245	130	145	158	105	109	131	110	85	96	112	117	109	138	117	107	103	138	101	127	197	95	217	244	110	116	195
	D	105	116	104	101	116	115	204	96	196	93	172	105	202	206	191	113	107	108	95	222	114	110	103	115	111	96	131	80	175	225	88	105	160
	E	155	197	77	187	80	171	94	107	112	107	104	168	95	110	97	126	233	128	77	105	91	110	171	167	84	68	98	97	94	84	175	180	103
	F	106	97	205	134	116	111	261	129	238	138	208	112	181	206	228	113	128	132	112	266	172	124	108	115	139	154	230	99	289	291	107	158	243
	G	101	103	145	94	109	120	266	101	231	103	182	98	205	171	192	87	128	96	97	234	115	105	108	141	95	115	194	89	247	255	118	119	222
	H	115	124	111	94	74	121	157	89	192	84	193	100	217	195	183	96	115	103	86	202	96	105	91	113	94	93	90	90	160	198	108	102	128
	I	151	182	86	189	78	162	101	135	112	116	98	148	99	129	111	169	216	226	82	100	85	171	227	214	99	93	109	213	101	120	222	222	97
	J	220	221	82	262	79	155	99	145	113	95	124	219	129	136	93	169	170	107	74	113	96	202	202	143	97	92	86	166	101	131	175	215	109
	K	202	229	85	218	86	156	106	135	128	110	121	169	128	117	114	224	114	167	90	101	93	186	241	150	87	88	98	236	94	113	207	273	85
	L	127	128	236	110	201	131	300	125	147	87	113	112	124	104	117	101	125	122	158	142	190	121	128	139	128	213	131	100	269	230	128	103	252
	M	129	99	98	97	127	108	135	100	185	109	209	96	255	217	195	95	118	92	113	181	100	108	109	110	113	90	82	92	100	152	100	101	118
	N	114	123	202	117	190	133	190	94	123	75	114	102	184	141	91	102	101	108	160	106	200	103	100	123	208	110	90	103	204	138	91	101	172
	O	152	206	77	164	82	186	94	113	100	110	93	102	84	97	89	141	191	140	84	97	70	167	110	196	81	65	87	76	105	104	173	150	100
	P	130	154	83	115	75	195	99	127	116	109	117	191	111	117	100	242	254	253	71	116	95	156	168	242	82	90	100	213	114	109	240	176	95
	Q	237	263	76	235	82	137	71	157	113	97	98	188	108	113	100	143	141	120	74	91	67	242	230	161	88	75	94	149	87	88	176	243	98
	R	113	118	189	86	160	136	246	117	150	88	119	107	132	105	94	108	123	116	91	143	202	110	122	121	164	128	104	92	249	192	106	113	230
	S	140	124	208	113	212	137	232	132	142	91	111	96	154	114	89	108	128	130	220	122	102	127	132	146	112	176	95	113	167	147	137	121	208
	T	115	122	142	116	133	114	174	108	130	174	138	85	217	164	92	94	110	111	94	115	92	107	98	126	95	90	178	92	149	200	95	109	124
	U	149	141	78	123	98	151	117	118	117	109	123	115	123	123	104	197	204	239	84	104	95	121	230	196	97	75	98	162	119	111	215	209	125
	V	131	134	142	122	227	112	182	113	161	167	189	106	218	224	153	98	116	111	245	112	205	116	128	145	253	190	100	114	189	126	102	112	164
	W	163	120	145	112	217	104	157	110	178	253	216	95	278	259	181	126	123	124	219	124	97	105	117	132	211	136	201	109	125	175	115	126	138
	X	245	224	78	222	78	207	92	155	133	99	114	202	154	118	144	217	211	240	71	100	83	196	290	201	104	78	108	219	94	128	163	276	97
	Y	167	217	105	171	98	188	100	149	131	108	125	189	115	129	125	241	253	252	90	121	112	180	209	258	114	80	112	224	103	127	240	175	113
	Z	151	113	272	147	272	147	237	135	172	186	204	126	257	224	126	114	139	127	297	107	162	138	130	141	287	210	132	108	136	145	127	124	174

↑

打鍵時間の計算方法 †

この実験データから、さまざまな運指の時間を計算することができる。

ホームポジションからあるキーまで指を移動させるために必要な時間は、ホームポジションとそのキーの打鍵時間を平均して求まる。

連続した複数の打鍵にかかる時間も求めることができる。例えば以下のよう結果があるとき、

  al 3 195
  sa 3 390
  sl 3 803

それぞれ測定回数が3回だから、平均は al 65msec, sa 130msec, sl 268msec である。 s a l という運指は、s→a が130msec、a→lが65msec だから、s a l は 130+65 = 195msec で打てる…わけではない。実際には s → l という難しい運指がボトルネックとなり、268msecかかってしまう。

↑

ボトルネックを考慮した計算方法 †

まず測定結果はこのようになっているとする。

S H A L の打鍵時間を求めたいとする。ボトルネックを考慮に入れて、正確な計算をするには、以下のよう考える。(以下は熟練者の指の動きであり、初心者の場合はまた違う計算が必要になるだろう)

'	,	.	P	Y	F	G	C	R	L	/
A	O	E	U	I	D	H	T	N	S	-
;	Q	J	K	X	B	M	W	V	Z	\

最初のキー S を打つための時間は、同手ホームポジションにある他のキーからの時間を平均して求める。つまりDvorak配列の右手ホームには H T N S があるから、測定結果のうち hs, ts, ns の平均 60msec を最初のキー S を打つ時間とする。
指が S H と打つ。S を打った右小指は、右人差し指が H を打鍵しようとする間に、最上段の L キーへ向かって移動を開始する。S→L の距離は 300msec かかるが、SH を打つまでにそのうちの 70msec ぶんを右小指は進んでいる。
右人差し指の H に続いて、左小指が A を打つ。これには 90msecかかる。この間も右小指の L キーまでの旅は続いている。右小指は sh 70msec, ha 90msec で 160msecぶんの距離を移動した。
最後に、右小指は L キーを押そうとする。 A L を連打するだけなら A→L は 100msec で済むはずだが、まだ右小指は L キーにたどり着いていない。 sh 70msec + ha 90msec + al 100msec = 260msec だから移動はあと 40msec残っている。これがボトルネックとなる。
合計は 60+70+90+100 + ボトルネックの 40 = 360 msec

このように計算するプログラムを key2time.exe (コンソールアプリ) として作成した。また同等な計算をするクラスを定義し、遺伝的アルゴリズムの評価関数に用いた。

↑

ホームポジションからキーへの時間 †

ボトルネックを考慮した計算方法で記述したように、各キーのホームポジションからの時間を求めた。

ホームポジションから手を移動して、あるキー X を押すまでにかかる時間は、同手ホームポジションにある他のキーからの時間を平均して求める。
ただしキー X がホームポジションにあるキーの場合は、平均を求めるときに X から X への時間 (連打) は加えない。
例えば E の時間は、AE OE UE の平均で求める。

この計算方法だと、ホームポジションにあるキーを打つまでの時間が 0 にはならないが、これは「あるキーを押そうと脳が判断してから指がキーを打つまでのタイムラグ」を表すと考えた。 (最初はホームポジションにあるキーを打つ時間を 0 と扱ったが、そうすると「遠いキー1回よりホームのキー2回のほうが速い」ことになり、打鍵数の多い配列が生成されたので)

このように各キー単独での時間を求めると以下のようになった。

' 175	, 184	. 146	P 160	Y 164	F 192	G 152	C 105	R 126	L 139	/ 151
A 112	O 115	E 107	U 91	I 141	D 138	H 90	T 91	N 96	S 97	- 165
; 178	Q 193	J 199	K 158	X 176	B 146	M 135	W 170	V 169	Z 157	\ 187

また、(反対側の手の) 中指シフトキーを押してからあるキーを押すまでの時間をボトルネックを考慮した計算方法の方法で求めると、以下のようになった。

' 205	, 213	. 206	P 189	Y 199	F 202	G 216	C 213	R 191	L 183	/ 187
A 199	O 197	E 175	U 183	I 185	D 211	H 204	T 204	N 198	S 174	- 184
; 205	Q 216	J 200	K 202	X 185	B 219	M 211	W 190	V 201	Z 210	\ 201

↑

指の使用率を決定 †

各指の筋力を測定し、これに比例して指の理想使用率を定めた。

まず、料理はかりで各指の押下力を測定した。ただし、使用したのが最大計量2kgのはかりで、指の圧力を一定に保つこともできなかったので、数値の精度はよくない。

測定結果は以下のようになった。

左				右
小	薬	中	人	人	中	薬	小
800	1500	2300	1800	1900	2400	1600	900	単位:g

これに比例するように、指の理想使用率を以下のように決定した。(わかりやすいのは百分率(%)だが、配列生成プログラムでは1024分率を用いたので併記してある)

左				右
小	薬	中	人	人	中	薬	小
6	11	17	14	14	18	12	7	単位:%
62	116	178	140	147	186	124	70	単位:1024分率

遺伝的アルゴリズムによる配列生成では、生成したキー配列の指使用率と、この理想的な指の使用率の差を取り、その差が大きいほど評価関数が悪くなるように設定した。評価関数の定義は後述する。

↑

資料収集 †

新配列で入力することを想定するサンプル文を大量に集めた。

文章サンプルとして「2ちゃんねる」を選んだ。これは以下のような理由による。

今夜のおかずからハッキングまで、幅広い話題がある。
この配列で入力することを想定する、くだけた文体が多い。
十分な量のサンプルが簡単に得られる。
一定のフォーマットに従っているため自動処理しやすい。

2ちゃんねるから、以下のようにサンプルを取得した。

2ちゃんねるの板を上から順に片っ端から見ていき、投稿数が上位6番までのスレをランダムに選び、ひとつの板から一つのスレを取得した (ギコナビのdatファイル)。そのスレの内容をサンプルに追加していった。約70MBのdatファイルを得た時点で、この作業を停止した。この70MBを「生サンプル」とする。

↑

資料の修正 †

生サンプルに対して以下の処理を行った。

名前・投稿日・AA・コピペ荒らしなどを除去する処理 sample\_clean.pl, sample\clean2ch.pl を行った。
Kanj2nas (eightban氏のフリーソフト) を用いて、漢字をひらがなに変換した。
不自然な読みになった部分を、sample\_replace.pl で自然な読みに近づけた。
HanKana\HanKana.exe ですべて半角カナに変換した。
半角カナの中に不自然な読みが残っていれば手作業で置換し、自然な読みに近づけた。この作業はテキストエディタの置換で行った。置換内容は HanKana\makefile.mak にメモしてある。
以上によって作った半角カナのテキストファイルを文章サンプルとした。

文章サンプルは約40MBのファイルになった (sample\all2ch_hk.txt)。このファイルは著作権の問題とサイズのため添付していない。

↑

N-gram 作成 †

以下の作業を Ngram ディレクトリで行った。

↑

1. 生N-gram作成 †

文章サンプルを1文字、2文字、3文字、4文字、5文字、6文字で区切り、文字列の並びの出現頻度の高い順にソートしたデータファイルを作成した。このために ngram.exe を使用した。文章サンプルは半角カナなので、(半)濁点を1文字と数えている。

結果は freq01.txt～freq06.txt。書式は「文字列出現回数」で、出現回数が多い順に並んでいる。

留意点

ngram.exe は、4096行を処理するたびに、その時点で1回しか出現していない文字列を消去するようにしてある (N が大きくなったときに大量のメモリを消費するのを防ぐため)。
N-gram を抽出して、その中に通常はさほど使わない文字列が異様に多く出現している場合、コピペ荒らしによるノイズの可能性が高い。これを利用して、 N-gramの抽出・荒らしを目視発見・資料の修正> の手順を数回繰り返した。

↑

2. 固定文字・濁点の修正 †

固定文字のみの N-gram 要素 (ﾞ｡･･｡｣など) は、処理時間の無駄なので削除した。
(半)濁点つきの文字 (ﾀﾞﾃﾞｶﾞﾊﾟなど) を 2-gram から 1-gram 扱いに移動した。(freq02.txtから濁点付き文字を freq01_dk.txt に移動し、残りの2-gramを freq02_dk.txt として保存した)

↑

3. 重複の修正 †

このままでは (N+1)-gram に含まれる N-gram が重複して数えられている。このため、これ使って配列を生成すると、長い N-gram に偏重した、短い N-gram の打ちにくい配列ができやすい。そこで以下のようにして、不完全ではあるが、重複して数えられた N-gram の出現回数を減算した。

N-gram のうち遺伝的アルゴリズムによる配列生成・文字列サンプルの作成で読み込む順位までを抽出した一時ファイルを作る。3-gram の1024位までを freq03_fxrk.txt、4-gram の512位までを freq04_fxrk.txt、5-gram の256位までを freq05_fxrk.txt として取り出した。

上のように取り出した (N+1)-gram と、 N-gram 全体を見比べる。(N+1)-gram の要素である文字列 S の出現回数が A であるとき、N-gram の要素で文字列が S の部分文字列であるものの出現回数から A/2 を減算した。以下に計算例を示す。

もとの4-gram		5-gramの256位まで		結果の4-gram
文字列	出現回数	文字列	出現回数	文字列	出現回数
ｼﾞﾌﾞ	300	ｼﾞﾌﾞﾝ	100	ｼﾞﾌﾞ	250
ﾞﾌﾞﾝ	200			ﾞﾌﾞﾝ	150

「A/2 を減算する」とした理由は、以下のように、N-gram に含まれる文字列は (N+1)-gram では2回数えられるからである。

    分解する文章サンプル
      ｹﾞﾝｼｮｳ
    2-gram      3-gram
      ｹﾞ          ｹﾞﾝ
      ﾞﾝ          ﾞﾝｼ
      ﾝｼ          ﾝｼｮ
      ｼｮ          ｼｮｳ
      ｮｳ
    ﾝｼ に注目すると、3-gram で ﾝｼ を含む要素は ﾞﾝｼ ﾝｼｮ の2つある。

行頭・空白直後から取り出した N-gram については、A/2 を減算するのではなく A を減算すべきだが、今回はすべて A/2 を減算した。これが「不完全ではあるが」と書いた理由である。

今後は、以上のように固定文字・濁点・重複の修正した N-gram を用いることにする。

↑

遺伝的アルゴリズムによる配列生成 †

打鍵時間・指使用率・N-gramを使って定義した評価関数が最少になるような配列を、遺伝的アルゴリズムで求める。

↑

文字列サンプルの作成 †

文字列サンプル は「文字列」と「その文字列の重み」の集合である。文字列サンプルは重複の修正を行った N-gram から作る ( mGeneKana.cpp, CMain::InitData() )。その手順は以下のとおり。

1-gram はすべて読み込む。
N=2～6 の N-gram については、出現回数の多い 2048/( pow(2, N-2) ) 位までを読み込む。
文字列の重みは、出現回数とする。

具体的には以下のようになる。

1-gram はすべて読む。2. 固定文字・濁点の修正のステップで(半)濁点つき文字は 1-gram 扱いにしている。
2-gram は2048位まで読む。2. 固定文字・濁点の修正のステップで(半)濁点つき文字は 1-gram 扱いにしているので、2-gram からは除かれている。
3-gram は1024位まで読む。
4-gram は512位まで読む。
5-gram は256位まで読む。
6-gram は128位まで読む。

以上のように 1-gram ～ 6-gram を読み込むと、4057 個の文字列サンプル要素ができた。

2-gramは2048、3-gramは1024、4-gramは512…という読み込み個数を決めたのは、処理速度の問題である。今回用いたプログラムとPCの性能では、我慢できる時間内に解が求まるには、約4000要素が限度だった。今後PCの処理速度が上がるかプログラムを改良して高速化できれば、今回切り捨ててしまったN-gramも含めた、より多くの文字列サンプルを使ってよりよい配列を作れるだろう。

↑

評価関数の定義 †

遺伝的アルゴリズムの評価関数は、以下のように定義した。結果が小さいほど「よい配列」ということになる。 ( gene.cpp, TGene::GetScore() )

↑

打鍵時間を求める †

まず文字列サンプルの打鍵時間を求める。

値 ret = 0 に初期化する。
文字列サンプルのすべての要素について以下の処理を行う。
- カナを運指英字に変換。文字列サンプルの要素の文字列 (半角カナ) を、評価している配列で打つときの運指 (キー位置を表す英字列) に変換する。
- 運指時間を算出。運指がどれだけ時間がかかるか、打鍵時間の測定・打鍵時間の計算方法を使って算出する。
- (かかる時間) * (文字列の重み) を ret に加える。

↑

ペナルティを求める †

以下のように、指の使用率によるペナルティを求める。 ( gene.cpp, TGene::GetFingeredScore() )

文字列サンプルのうち長さ = 1 の要素について、運指を求め、使用される指ごとの変数に重みの数値を加える。重みは文字の出現頻度になっているので、すべての 1文字について指ごとに重みを合計すれば、指の使用回数が得られる。
指の使用回数を 1024分率で表す。各指について指の理想使用率との差の2乗を合計して変数 delta に格納する。ただし、小指の使用率が理想使用率より高い場合は、差の2乗の 16 倍を加える。
ペナルティ値は、delta * ( (現在のret)/1048576 ) とする。

上記の手順で、16倍・ret/1048576 といった定数は恣意的なパラメータである。試行錯誤して、ペナルティがもとの ret の 3.0% ～ 0.1% 程度の値になるように調整した。これらのパラメータを調整すると、もっと指の使用率を厳密に制限する配列や、逆に指の使用率は偏っているが速度は速い配列を作ることもできる。

↑

打鍵時間とペナルティを合計する †

評価関数は、打鍵時間とペナルティの合計を返す。

つまり、よく出現する文字列が素早く打てない配列や、指の使用率バランスが悪い配列に対して、評価関数は高い値を返す。

↑

1. 発生フェーズ †

乱数による配列の生成。以下のようにして、配列の条件の固定文字を満たすランダムな配列を、256 種類生成した。

まず SWAP関数 (2つの文字の交換) を定義する。

  SWAP(位置 a, 位置 b) 
  {
    a または b にある文字が固定文字であれば、何もしない。
    そうでなければ、a, b の位置にある文字を入れ替える。
  }

SWAP 関数を使って、以下のようにしてランダムな配列を生成した。o

固定文字を配置する。
残りの文字を空いている位置に配置する。
すべての位置 i について (33キー * 2シフト = 66位置) 、ランダムに選んだ別の位置 r と SWAP(i, r) する。

↑

2. 改良フェーズ †

256 種類の配列すべてについて、以下の手順で SWAP を繰り返すことで改良する。

位置の個数だけ要素をもつフラグ配列 growFail[] を用意する。growFail[] は配列を乱数で生成したとき 0 に初期化する。
(このフラグは、この位置といかなる位置をSWAPしても評価関数値が改善しないと判明したとき 1 にする)
この配列の gromFlag[] がすべて 1 なら、この配列はこれ以上改良できない。
1. この配列が 256 番目の配列ならフェーズ 3. 淘汰フェーズへ進み、
2. そうでなければ次の配列について 2. 改良フェーズを行う。
SWAPの位置の片方 a を乱数で決める。
bestSwapPos を無効値で初期化する。
位置 b は、a の次の位置から始める。
1. 試しに a と b の文字を入れ替えてみて SWAP( a, b ) 、評価関数値が改善するかどうかを見る。評価関数値が最も改善する位置を bestSwapPos として記録する。
2. b を次の位置に進める (一番右下のキーに到達したら一番右上のキーに戻る)。
3. b が a まで到達したら、b が一周したので b のループを抜ける。そうでなければ i. に戻ってループする。
もし bestSwapPos が無効値でなければ、SWAPで評価関数値できる位置を見つけたということだから、
1. 本当に SWAP( a, bestSwapPos ) する。
2. このSWAPの結果、さらに評価関数値が改善できる可能性が生じたかもしれないので、growFail[] をゼロクリアする。
3. 次に試す位置 a は今回の bestSwapPos にする。
4. ステップ 4. まで行き、繰り返す。
もし bestSwapPos が無効値であれば、a といかなる位置をSWAPしても評価関数値を改善できないということだから、
1. growFail[a] = 1 にする。
2. ステップ 2. まで行き、繰り返す。

↑

3. 淘汰フェーズ †

評価の悪いキー配列を死滅させる。

256 種類の配列に対して、以下の処理を行う。

全く同じ配列が複数個体いる場合は、メモリと処理速度の無駄なので、ひとつを残して他は突然変異させる。
評価関数値順にソートして、評価関数値の高い (悪い) 128 個体は死滅する。

死滅した個体のメモリをクリアして、次の 4. 交配フェーズへ進む。

↑

4. 交配フェーズ †

3. 淘汰フェーズで空いたメモリを使って、新しい配列を作る。新しい配列は、既存の配列のうち評価関数値の低いものの特徴を継承するように、以下の手順で作る。

↑

親を選択 †

親を乱数で2つ選ぶ。以下の関数を使って、順位が上 (評価関数値が低い) の配列は選ばれやすく、順位が下 (評価関数値が高い) 配列は選ばれにくくする。

  /// 0 ～ n-1 の乱数を発生。
  /// 確率は 0 が最高、n-1 が最低で、その間では確率は線形に減少する。
  TriangleRand( n )
  {
    int a = random(n) + random(n);
    if (a>=n-1) a-=n-1;
    else a=n-2-a;
    return a;
  }

この関数の戻り値とその確率は以下のようになる。1位は1.556%、2位は1.544%の確率で親として選ばれることになる。

戻り値	確率	TriangleRand(128)での確率 [%]
0	(2*n - 1) / (n^2)	1.556
1	(2*n - 3) / (n^2)	1.544
2	(2*n - 5) / (n^2)	1.532
:	:	:
n-2	3 / (n^2)	0.018
n-1	1 / (n^2)	0.006

↑

子を作成 †

2つの親 (G1, G2) をもとに、新しい配列を作る。これは以下のようにする。

まずすべての固定部品を置く。
位置 pos を乱数で決める。
すでに位置 pos に文字が割り当てられていれば、pos を+1進める (一番右下の位置に達したら一番左上の位置に戻る)。
親 G1, G2 の片方を乱数で選び、その親の位置 pos に割り当てられている文字 part を得る。
1. もし文字 part が子のどこかの位置に割当済みなら、G1, G2 の一番左上の位置から右下の位置へ向かって順に、まだ子に割り当てていない文字を探し、見つけたものを part とする。
すべての文字を置くまで、ステップ 3～を繰り返す。
子の配列が親 G1, G2 のいずれかと全く同じであれば、そうでなくなるまで突然変異する。

↑

突然変異 †

今回用いたプログラムでは、全く同じ配列が作られたときのみ突然変異させた。

SWAPによる改良が完全に終わっているとき、1回のSWAPでは評価関数値が上がる (悪くなる) 方向にしか進まないので無駄である。そこで突然変異は以下の手順で行う。

SWAPする回数を決める。2回の確率が 1/2, 3回が1/4, 4回が1/8, 5回が1/16 ... となるように決める。
「連鎖的に」SWAPする。位置 k0 と k1 を入れ替え、k1 と k2 を入れ替え、k2 と k3 を入れ替え…のようにする。位置 k0, k1, k2 ... は乱数で決める。

↑

5. 繰り返す †

十分によい配列が得られるまで、 2. 改良フェーズへ戻って繰り返す。

終了条件は、「10 世代の間、最良の配列がよりよい配列に取って代わられていないとき」とした。終了条件が満たされると、プログラムは現在の状態をファイルに保存し、乱数を初期化しなおして、また 1. 発生フェーズから繰り返す。

↑

結果 †

結果、以下の配列が得られた (★は前置シフト)。

アンシフト
け	に	と	こ	さ	れ	っ	い	の	る	ま
し	た	★	か	て	く	ん	★	゛	な	ー
ら	す	よ	は	ょ	き	う	、	。	゜	・
シフト(★の後)
ぁ	ゃ	ろ	ほ	ゆ	わ	む	や	え	ぇ	「
ぃ	お	も	あ	ゅ	め	り	つ	ち	せ	」
ぅ	ね	そ	へ	ふ	ぬ	み	ひ	を	ぉ

評価関数の値は 18595837407 だった。2位の配列の評価値は 18596165298 だから、0.002% のオーダーまで最適化されている (少なくともこのアルゴリズムでは)。

↑

配列の評価 †

GeneKana.exe で Import (Ctrl+I) を押し、配列ファイルと文章ファイルを選び、配列を評価した。また比較対象として月配列2-263についても同様の評価をした。

月配列2-263

アンシフト
そ	こ	し	て	ょ	つ	ん	い	の	り	ち
は	か	★	と	た	く	う	★	゛	き	れ
す	け	に	な	さ	っ	る	、	。	゜	・
シフト(★の後)
ぁ	ひ	ほ	ふ	め	ぬ	え	み	や	ぇ	「
ぃ	を	ら	あ	よ	ま	お	も	わ	ゆ	」
ぅ	へ	せ	ゅ	ゃ	む	ろ	ね	ー	ぉ

Import 機能は、指定された配列ファイルを使って、文章ファイル (半角カナのみ) を打鍵 (英字文字列) に変換し、打鍵の情報を得るものである。

打鍵数	打鍵 (英字文字列) の数。中指シフトも1打鍵と数える。
time	ボトルネックを考慮した計算方法で算出した総打鍵時間 [msec]
左, 人, 中, 薬, 小	それぞれ左手全体、左人差し指、左中指、左薬指、左小指の使用率 [%]
右, 人, 中, 薬, 小	それぞれ右手全体、右人差し指、右中指、右薬指、右小指の使用率 [%]
上段, 中段, 下段	それぞれ「',.PYFGCRL/」「AOEUIDHTNS-」「;QJKXBMWVZ\」の使用率 [%] 下段の括弧内の数字は良下段の割合。
交互	交互打鍵の割合 (TA PB など) [%]
同指	同指異鍵の割合 (TC KU など) [%]
跳躍	同手2段跳躍の割合 (QP GV など)。括弧内の数字は良跳躍の割合。[%]
和音	アルペジオ打鍵の割合 (TD JK など) [%]

良下段・良跳躍
下段・2段跳躍は一般に打ちにくいと言われているが、条件によっては打ちやすいこともある。打ちやすい下段を「良下段」、打ちやすい2段跳躍を「良跳躍」と定義する。ホームポジションからキーへの時間で、下段だが速いキーを良下段に、また ktDisp.exe で、2段跳躍だが速いキー組を良跳躍と考える。良跳躍は、長い中指・薬指で上段キーを打ち、肘を軽く開くと人差し指が自然に届く位置の下段キーを打つパターンとする。一般的なキーボードでは、上段は左に、下段は右にずれているため、X は打ちやすいとは言えない。

良下段	K B M
良跳躍	,K K, .K K. CB BC RB BR CM MC RM MR

Dvorak配列での良下段・良跳躍を以下に図示する。

'	,	.	P	Y	F	G	C	R	L	/
A	O	E	U	I	D	H	T	N	S	-
;	Q	J	K	X	B	M	W	V	Z	\

↑

2ちゃんねる(40MB) †

資料収集で得た約40MBの2ちゃんねるログを評価した。

-	打鍵数	time	左	人	中	薬	小	右	人	中	薬	小	上段	中段	下段	交互	同指	跳躍	和音
○配列	46289784	5318916816	45.8	16.7	14.4	8.4	6.3	54.2	16.2	15.9	14.2	7.9	24.3	56.6	19.1 (7.9)	68.1	4.3	3.0 (0.8)	12.7
月配列2-263	46497748	5527440890	47.0	17.9	16.3	8.4	4.5	53.0	16.6	16.3	14.0	6.1	28.5	53.6	17.9 (6.7)	68.4	4.7	3.0 (0.8)	12.0

打鍵数は 0.5% 減っている。左人差し指の負担が減っている。下段は増えているが良下段が増えただけである。同指異鍵は減っている。和音は増えている。○配列は月配列2-263に比べてわずかによいといえるだろう。

↑

宮沢賢治『めくらぶどうと虹』 †

ですます調の文章の例として選んだ。

-	打鍵数	time	左	人	中	薬	小	右	人	中	薬	小	上段	中段	下段	交互	同指	跳躍	和音
○配列	3705	428720	47.2	15.8	16.7	8.8	5.9	52.8	13.0	17.0	14.5	8.2	24.5	54.3	21.2 (7.2)	68.2	3.7	3.4 (0.9)	13.2
月配列2-263	3754	451161	49.4	16.6	18.8	8.1	5.8	50.6	13.1	17.8	13.7	6.0	25.7	56.9	17.5 (5.6)	68.3	6.1	3.1 (0.4)	11.1

打鍵数は 1.3% 減っている。指の使用率は似ているが、○配列のほうが小指使用率が高い。下段は、良下段を除いても、やや多い。同指異鍵はかなり減っている。跳躍は、良跳躍を除いた数で見れば、少し減っている。和音は増えている。この例文では、下段が多いこと以外は、月配列よりも良いだろう。

↑

Wikipedia秀逸な記事 †

やや硬い文章の例として選んだ。記事のページ全体をコピペした後、[編集] [バグの報告] などの機能部分を除去したものを使った。

-	打鍵数	time	左	人	中	薬	小	右	人	中	薬	小	上段	中段	下段	交互	同指	跳躍	和音
○配列	1261305	145455793	45.1	17.1	14.5	7.1	6.3	54.9	17.6	16.5	13.9	6.9	23.9	55.3	20.8 (9.2)	68.9	4.6	3.5 (0.9)	11.0
月配列2-263	1249115	148305733	44.8	16.5	15.7	8.5	4.2	55.2	18.0	17.6	13.1	6.5	30.7	51.8	17.5 (5.7)	67.9	4.3	3.0 (0.7)	12.2

人差し指の使用率は、○配列も月配列2-263も多いが、月配列2-263は右人差し指の使用率が際だって高く、○配列は両方の人差し指が多い。段ごとでは、○配列は上段が減り、中段が多く、下段は増えたが良下段が多い。交互打鍵は増えたが、同指異鍵や跳躍は増え、和音が減っている。この例では、使用者の嗜好にもよるが、月配列のほうがやや良いだろう。

↑

日本国憲法序文 †

かなり硬い文章の例として選んだ。

-	打鍵数	time	左	人	中	薬	小	右	人	中	薬	小	上段	中段	下段	交互	同指	跳躍	和音
○配列	1122	129794	46.6	16.9	15.2	6.9	7.7	53.4	20.4	16.1	11.6	5.3	28.0	49.4	22.6 (8.5)	71.9	4.5	3.2 (0.4)	10.7
月配列2-263	1111	131548	45.9	12.8	16.2	12.2	4.7	54.1	18.0	21.3	10.3	4.5	33.0	48.1	18.9 (4.7)	70.9	3.2	2.2 (0.2)	13.5

○配列では、右人差し指の負荷が異様に高く左薬指より左小指が多いなど、指使用率が悪い。月配列2-263ではかなり指使用率が理想に近い形である。段・運指については、Wikipedia秀逸な記事と同様、○配列のほうが悪い。硬い文章ではやはり、新JISをもとにした月配列2-263が有利だろう。

↑

総評 †

2ちゃんねる・めくらぶどうと虹といった、口語調・ですます調の文では○配列のほうがよい。Wikipediaや憲法といった、硬い文章では月配列2-263のほうがよい。

メール・チャット・ブログなど口語調のくだけた文に適した配列を作る、という設計目標は達成できたといえる。

しかし○配列は、硬い文章で極端に打ちにくくなる。口語調・ですます調は打ちやすく、かつ硬い「だ・である」調もさほど打ちにくくならない配列を作るために、文章サンプルに硬い文章を加えるべきかもしれない。

↑

付録 †

↑

参考文献 †

新JIS http://www.ykanda.jp/input/jis/jis.htm
花配列 http://homepage3.nifty.com/togasi/hana_no_kuni/index.html
2ちゃんねる新JIS・月キーボード配列 4打鍵目 http://pc7.2ch.net/test/read.cgi/pc/1139243753
(N-gramの重複修正について482の指摘が役立った)
キー文字配列の最適化 (ニケルズの最適化主法) http://www.ccad.sccs.chukyo-u.ac.jp/~mito/yamada/chap7/1/index.htm
GAで配列を作る(英語) http://www.visi.com/~pmk/evolved.html