Программные продукты и системы

В статье дается решение одной задачи комбинаторного анализа, имеющей прямое отношение к эргономичной раскладке букв на клавиатуре мобильного телефона.

Пусть  – упорядоченное n-множество символов и С={С1,С2,…,Сr} – упорядоченное r-множество ячеек, в которых размещаются наборы символов с сохранением порядка, то есть

 .                                             (1)

Предполагается, что ,

 , , и n.                          (2)

Отметим, что для использования однотипной записи в (1) введен индекс , значение которого равно нулю. Запись (1) при фиксированных значениях , s=1,…,r, будем называть вариантом размещения символов , , по ячейкам , s=1,…,r.

Условия (1) и (2) показывают, что мы рассматриваем только такие варианты размещения, в которых сохраняется общий порядок следования символов и ни одна из ячеек не пуста. В таком случае общее количество различных вариантов (1) будет зависеть только от числа символов, размещаемых в тех или иных ячейках, в то время как упорядоченность символов не будет иметь значения. Но тогда в соответствии с [1] количество различных вариантов определяется числом  сочетаний из  элементов по .

Введем два набора положительных чисел. Элементы одного из них (, , причем ) поставим в соответствие по индексу  символам  множества A. Другой набор положительных чисел – ,  – строго монотонно возрастающий, . В ячейке , , содержащей  символов, число  будем связывать с символом , .

Сопоставим каждому варианту размещения символов по ячейкам множества  количественный показатель

.                            (3)

Задача 1. Из множества вариантов размещений выявить тот, для которого показатель  принимает минимальное значение.

Для решения задачи предложен алгоритм переборного типа. Мы не приводим его описание, поскольку его основу составляет хорошо известное в комбинаторном анализе последовательное перечисление всех способов проведения  линий в  промежутках между неразличимыми элементами или же окрашивания  цветами n одинаковых объектов [1]. Опишем одну из практических интерпретаций рассмотренной задачи на примере мобильного телефона.

Приложение задачи 1. Возрастающая популярность сервиса коротких сообщений (SMS) заставляет задуматься о необходимости упрощения процедуры ввода текста. В настоящее время обсуждаются различные пути продвижения в данном направлении: это и создание виртуальных клавиатур (сенсорных дисплеев), и дальнейшее развитие QWERTY-клавиатур, например, с клавишами треугольной формы для ввода символов путем нажатия на соответствующий угол и т.д. Все предложения преследуют цели уменьшения трудоемкости или повышения скорости набора электронных сообщений.

У большинства мобильных телефонов клавиши содержат одну цифру и 3–5 букв, расположенных в алфавитном порядке. При формировании текста сообщений выбор необходимого символа осуществляется нажатием соответствующей клавиши, причем в количестве, равном его порядковому номеру среди символов данной клавиши. Вследствие этого при наборе текста количество нажатий клавишей оказывается больше числа символов текста, в связи с чем вполне естественной представляется следующая задача.

Задача 2. Возможно ли за счет иного размещения букв (с сохранением их алфавитного порядка) на клавиатуре мобильного телефона в сравнении с уже существующей раскладкой добиться уменьшения числа нажатий клавишей при наборе фиксированного текста?

Покажем, что поставленный вопрос может быть интерпретирован как трансформация задачи 1 в конкретную прикладную сферу. В качестве множества  будем рассматривать алфавит какого-либо естественного языка, элементами которого являются буквы , , а в качестве , , – относительные частоты встречаемости букв в фиксированном тексте естественного языка. Ячейки, о которых идет речь в задаче 1, отождествим с клавишами клавиатуры мобильного телефона. Остается пояснить значения . Полагая, что усилия, затрачиваемые на однократное нажатие клавишей, одинаковы, мы можем принять  ( ), то есть связать  с количеством нажатий на клавишу  для извлечения буквы , , .

В таком случае критерий качества W, введенный формулой (3), приобретает смысл относительной работы, затрачиваемой пользователем при наборе фиксированного текста, а минимальное значение  достигается на оптимальной раскладке букв на клавиатуре мобильного телефона.

Эргономичная раскладка русского и английского алфавитов на клавиатуре мобильного телефона

Современная раскладка упомянутых алфавитов имеет вид, представленный на рисунке 1.

Рис. 1

Покажем, какого рода раскладки букв получаются на основе предложенной математической модели. Для этих целей конкретизируем значения параметров  и . Отметим прежде всего, что мы будем рассматривать два варианта –  и , то есть размещать буквы на восьми клавишах, что ныне имеет место, а также и на девяти клавишах, поскольку нет особых причин отвергать такую возможность.

Что касается , , то их значения принимаются равными частотам встречаемости букв в русском языке (табл. 1).

Таблица 1

В случае английского языка значения принимаются равными частотам встречаемости букв в английском языке (табл. 2).

Таблица 2

В таблицах 1 и 2 частоты встречаемости букв, заимствованные из [2], показаны в процентах.

В связи с тем, что табличные значения  отличны от тех, которые имеют место для конкретных текстов, раскладки букв, полученные далее с помощью математической модели, названы нами эргономичными.

Раскладка букв русского алфавита по 8 клавишам. (Здесь и далее авторы будут сравнивать в процентах трудоемкость предложенной раскладки с с представленной на рисунке 1). Трудоемкость современной русской клавиатуры (рис. 1), рассчитанная по формуле (3), равна 2,2344. Среди  = 2629575 возможных раскладок минимальная трудоемкость – 2,0381, что на 8,8 % меньше, достигается на раскладке, изображенной на рисунке 2.

Рис. 2

Ее недостаток в том, что в третьем ряду на первой клавише размещаются 6 символов (затруднительно реализовать на практике ввиду ограниченной площади клавиши). С практической точки зрения может быть предложена несколько худшая раскладка, но содержащая не более пяти символов на каждой клавише (рис. 3).

Рис. 3

Трудоемкость такой клавиатуры – 2,0519, что на 8,2 % меньше.

Раскладка букв английского алфавита на 8 клавишах. Трудоемкость современной английской клавиатуры (рис. 1), рассчитанная по формуле (3), равна 2,1632. Среди  = 657800 возможных раскладок минимальная трудоемкость – 1,6009, что на 26 % меньше, достигается на раскладке, представленной на рисунке 4.

Рис. 4

Ее недостаток в том, что в третьем ряду на последней клавише размещаются семь символов. С практической точки зрения может быть предложена несколько худшая раскладка, но содержащая не более пяти символов на каждой клавише.

Рис. 5

Трудоемкость представленной на рисунке 5 клавиатуры – 1,6317, что на 24,6 % меньше.

Раскладка букв русского алфавита на 9 клавишах. Среди  = 7888725 возможных раскладок минимальная трудоемкость – 1,8574, что на 16,8 % меньше, достигается на раскладке, представленной на рисунке 6.

Рис. 6

Ее недостаток в том, что на первой клавише в третьем ряду располагаются 6 символов (затруднительно реализовать на практике ввиду ограниченной площади клавиши). С практической точки зрения может быть предложена несколько худшая раскладка, но содержащая не более пяти символов на каждой клавише (рис. 7).

Рис. 7

Трудоемкость такой клавиатуры равна 1,8712, что на 16,3 % меньше.

Раскладка букв английского алфавита на 9 клавишах. Среди  = 1562275 возможных раскладок минимальная трудоемкость – 1,4947, что на 30,9 % меньше, достигается на раскладке, представленной на рисунке 8.

Рис. 8

Указанные раскладки можно рекомендовать для практического использования.

Список литературы

1.   Рыбников К.А. Введение в комбинаторный анализ. – М.: Изд-во МГУ, 1985. – 308 с.

2.   http://tirantrain.livejournal.com