NAME

carpalx - given text input, determine optimal keyboard mapping to minimize typing effort based on a typing effort model

SYNOPSIS

  # all configuration read from etc/carpalx.conf
  carpalx -keyboard_input keyboard.conf -keyboard_output keyboard-optimized.conf
          -corpus corpus/words.txt
          -action loadkeyboard,loadtriads,optimize
          -conf etc/carpalx.conf
          [-debug]

DESCRIPTION

carpalx is a keyboard layout optimizer. Given a training corpus (e.g. English text) and parameters that describe typing effort, carpalx uses simulated annealing to find a keyboard layout to minimize typing effort.

Typing effort is modeled using three contributions. First, base effort is derived from finger travel distance. Second, row, hand and finger penalties are added to limit use of weaker fingers/hands and distinguish harder-to-reach keys. Third, stroke path effort is used to rate the effort based on finger, row and hand alternation (e.g. asd is much easier to type than sad).

CONFIGURATION

Configuration file name and path

carpalx will look in the following locations for a configuration file

  .
  SCRIPT_BIN/../etc
  SCRIPT_BIN/etc
  SCRIPT_BIN/
  ~/.carpalx/etc
  ~/.carpalx

where SCRIPT_BIN is the location of the carpalx script. If the name of the configuration file is not passed via -conf, then SCRIPT_NAME.conf is tried where SCRIPT_NAME is the name of the script. For example,

  > cd carpalx-0.11
  > bin/carpalx

will attempt to find carpalx.conf in the above paths.

Using -debug -debug will dump the configuration parameters.

  > bin/carpalx -debug -debug

Configuration structure

The configuration file comprises variable-value pairs, which may be placed in blocks.

  a = 1
  <someblock>
    b = 2
    <anotherblock>
    c = 3
    </anotherblock>
  </someblock>

Combinations of related parameters (e.g. base effort, keyboard configuration) are stored in individual files (e.g. etc/mask/letters.conf) which are subsequently imported into the main configuration file using <<include>>

  ...
  <<include etc/mask/letters.conf>>
  ...

HISTORY

• 0.10

  Packaged and versioned code.

• 0.11

  Adjusted typing model to include weights for base, effort and stroke components.

  Improved clarity of effort reports.

  Improved consistency in configuration file.

  Added fonts/

• 0.12

  Can now load a cache file basedon parsed corpus instead of original corpus.

BUGS

Report!

AUTHOR

Martin Krzywinski <martink@bcgsc.ca> http://mkweb.bcgsc.ca

CONTACT

  Martin Krzywinski
  Genome Sciences Centre
  100-570 W 7th Ave 
  Vancouver BC V5Z 4S6

INTERNAL FUNCTIONS

The content below may be out of date

optimize_keyboard()

  $newkeyboard = optimize_keyboard($keytriads,$keyboard);

Simulated annealing is used to search for a better keyboard layout. The function uses the list of triads, generated from the input text document, and an initial keyboard layout.

_swap_keys()

  $newkeyboard = _swap_keys($keyboard,$reloc_list,$n);

Swap one or more pairs ($n randomly sampled pairs) of keys on the keyboard. Lower and upper case characters remain on the same key (e.g. no matter where 'a' is, A is always shift+a). This applies to both letter and non-letter characters (e.g. 1 and ! are always on the same key).

This function returns a new keyboard object with the keys swapped.

_swap_key_pair()

  $key1 = [$row1,$col1];
  $key2 = [$row2,$col2];
  _swap_key_pair($keyboard,@$key1,@$key2);

This function modifies $keyboard in place.

calculate_effort()

  my $effort = calculate_effort($triads,$keyboard);

Given a list of triads and the effort matrix, calculate the total carpal effort required to type the document from which the triads were generated. The effort is a non-negative number. The effort is a sum of the efforts for each triad. The total effort is normalized by the number of triads to remove dependency on document size.

  abcdefg
  abc     -> effort1
   bcd    -> effort2
    cde   -> effort3
      efg -> effort4
  -------    -------
  abcdefg -> total_effort = ( effort1 + effort2 + effort3 + effort4 ) /4

Given a triad xyz, the effort is calculated by the following empirical expression

  effort = e = k1*effort(x) + k2*effort(x)*effort(y) + k3*effort(x)*effort(y)*effort(z) + k4*patheffort(x,y,z)
             = k1*effort(x)*[1 + effort(y)*(k2 + k3*effort(z))] + k4*patheffort(x,y,z)

The form of this expression is motivated by the fact that the effort of three keystrokes is dependent on not only the individual identity of the keys but also alternation of hand, finger, row and column within the triad as well as presence of hard-to-type key combinations (e.g. zxc zqz awz ). For example, it is much easier to type "ttt" than "tbt", since the left forefinger must travel quite a distance in the latter example. Thus the insertion of the "b" character should impact the effort.

In the first-order approximation k2=k3=k4=0 and the effort is simply the effort of typing the first key, effort(x). The individual effort of a key is defined in the <effort_row> blocks and is optionally modified by (a) shift penalty - CAPS are penalized and (b) hand penalty (e.g. you favour typing with your left hand). Since triads overlap, the first-order approximation for the entire document is the sum of the individual key efforts, without any long-range correlations.

The addition of parameters k2 and k3 is designed to raise the effort of repeated difficult-to-type characters. This is where the notion of a triad comes into play. Notice that if effort(x) is zero, then the whole triad effort is zero.

The patheffort(x,y,z) is a penalty which makes less desirable triads in which the keys do not follow a monotonic progression of columns, or triads which do not alternate hands. Once you try to type 'edc' on a qwerty keyboard, or 'erd' you will understand what I mean. The patheffort is a combination of two factors: hand alternation and column alternation. First, define a hand and column flag for a triad

The definition of path effort here is arbitrary. I find that if the hands alternate between each keystroke, typing is easy (e.g. hf=0x). If both hands are used, but don't alternate then it's not as easy, particuarly when some of the columns in the triad are the same (e.g. same finger has to hit two keys like in "jeu"). If the same hand has to be used for three strokes then you're in trouble, particularly when some of the columns repeat. You can redefine the value of the path effort in <path_efforts> block.

read_document()

 $triads = read_document(); # create hashref to triad frequencies

 $triads->{aab} = frequency of aab;
 $triads->{abc} = frequency of abc;

Read a document from file and create a list of of character triads. Triads are overlapping (more on overlapping below) 3-character combinations. Each triad is stored along with the number of times it appears in the document. All triads are stored, including overlapping triads.

For example, if the document line is

  I am a very lazy dog with big ears.

Then the triads will be

  i am              iam
    am a            ama
     m a v          mav
       a ve         ave
         ver        ver
          ery       ery
           ry l     ryl
            y la    yla
  ...

and so on. Notice that spaces in the document are disregarded during construction of the triads.

Depending on the parse mode, the input document undergoes some transformation before triads are constructed. Each mode must be defined using a <mode_def> block. Three modes are defined and you can add more.

You can control how the triads are read by the <triad> block

  <triad>
  maxnum = 1000 # limit number of triads
  overlap = yes # if set to yes, a triad potentially begins at each character (triads overlap by maximum of 2 characters)
                # if set to no, triads abut 
  </triad>
 
=over

mode = perl

If the mode is set to "perl", then all comment lines are disregarded. Comments are identified by lines that begin with #.

mode = english

English mode removes all non-alphanumeric characters before constructing triads.

mode = letter

All non-letter characters are removed and remaining letters are switched to lower case.

_parse_keyboard_layout

Parse the <keyboard><row> blocks to determine the location of keys on the keyboard.

Keyboard structure is stored as a hashref. Each key is stored by row/col position

  $keyboard->{key}[ROW][COL]{lc}     = lower case at ROW,COL
  $keyboard->{key}[ROW][COL]{uc}     = upper case at ROW,COL
  $keyboard->{key}[ROW][COL]{finger} = finger for hitting key at ROW,COL

  $keyboard->{map}{CHAR}{row}    = ROW for key CHAR
  $keyboard->{map}{CHAR}{col}    = COL for key CHAR
  $keyboard->{map}{CHAR}{case}   = CASE of key CHAR
  $keyboard->{map}{CHAR}{finger} = FINGER for hitting key CHAR

make_relocatable_list()

  my $list = make_relocatable_list($mask)

Based on the key mask generated by _parse_mask(), this function returns a list of all keys that can be relocated. The list is a set of row,col pairs.

  $list = [ ... [row,col], [row,col], ... ]

create_keyboard()

  my $keyboard = create_keyboard();

Parses the keyboard layout and creates an array that keeps track of the keys, their positions, character assignments and typing effort. The keyboard array is indexed by row and column of the key and contains a hash

  $keyboard->{key}[row][col]
                           {lc}
                           {uc}
                           {row}
                           {col}
                           {effort}

The keyboard layout is read from the <keyboard><row> blocks. The effort in the {key} part of the keyboard object is the canonical effort for the row,col combination as defined in <effort_row> plus any baseline and hand penalties.

The keymap hash is a direct mapping between a character and its position and hand assignment on the keyboard

  $keyboard->{map}{CHAR}
                       {row}
                       {col}
                       {hand}
                       {effort}

The effort in the {map} part of the keyboard object is the effort for the character, based on its row,col combination and includes the shift penalty.

For the standard qwerty layout, look at the keyboard you're using right now (true for >99% of typists). For Dvorak layout, see http://www.mwbrooks.com/dvorak.