# 			Automatic keyboard layout
#		http://www.freaknet.org/alpt/src/misc/akl/akl.awk
#
# --
#
# A program which, given a text as input, computes the most efficient keyboard
# layout for the given text.
#
# "Most efficient keyboard layout" means a layout which permits to write the
# given text in the fastest and easiest way. 
#
# *** Usage
#
# 	./akl.awk < input | less -R
# 
# Note: the non printable ASCII character are printed in their hexadecimal
# form.
#
# *** Example
#
#$ echo idiki the wiki | ./akl.awk 
#,___________________.
#|___|___|___|___|___|
#|___|_t_|_d_|___|___|
#|___|_h_|_i_|_w_|___|
#|___|_e_|_k_|_ _|___|
#|___|___|___|___|___|
#
#,_______________________.
#|___|___|___|___|___|___|
#|___|___|_t_|_h_|_e_|___|
#|___|___|_d_|_i_|_k_|___|
#|___|___|___|_w_|_ _|___|
#|___|___|___|___|___|___|
#
# *** Algorithm
#	
#	- build the frequency list for each pair of keys
#	
#	- sort the list and traverse it, starting from the most frequent
#	  pair
#
#		- Let (a,b) be the current pair
#
#		- If  a  has been previously added in the layout matrix, set
#		  p=coordinates_of_a
#
#		- If  a  doesn't exists in the layout matrix, try the swapped
#		  pair: t=b, b=a, a=t
#
#		- If  a  still doesn't exist, find the a key  p  in the
#		  layout matrix such that (p,a) is an existing pair and the
#		  frequency of (p,a) is higher than (x,a), for any valid
#		  x.
#
#		- Find, in the layout matrix, the nearest empty points to  p.
#
#		- Choose the nearest empty point  e  to  p  in term of
#		  frequency, i.e. (e,p) must be higher than any other (e',p).
#
#		- Add  b  in  e.
#

http://www.freaknet.org/alpt/src/misc/akl/akl.awk