Задача об эргономичном размещении конечного числа символов по конечному числу ячеек. Основные варианты уменьшения числа нажатий клавишей при наборе фиксированного текста. Раскладка русского и английского алфавитов на клавиатуре мобильного телефона

Размещено на http://www.allbest.ru/

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

Москва, 2008 № 3, С.29 - 31.

Об одной задаче оптимального размещения и её приложении

З.Д. Усманов, И.Л. Васильева

Формулировка задачи

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

. (1)

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

, , и . (2)

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

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

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

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

. (3)

ЗАДАЧА 1

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

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

Приложение задачи 1

размещение символ мобильный телефон

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

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

ЗАДАЧА 2

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

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

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

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

Современная раскладка упомянутых алфавитов имеет следующий вид:

Размещено на http://www.allbest.ru/

(4)

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

Что касается , , то их значения принимаются равными частотам встречаемости букв в русском языке:

Таблица 1

а в случае английского языка - частотам встречаемости букв в английском языке:

Таблица 2

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

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

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

Размещено на http://www.allbest.ru/

Её недостаток в том, что в третьем ряду на первой клавише размещаются 6 символов (затруднительно реализовать на практике ввиду ограниченной площади клавиши). С практической точки зрения может быть предложена несколько худшая раскладка, см. далее, но содержащая не более пяти символов на каждой клавише. Трудоемкость такой клавиатуры - 2,0519, на 8,2% меньше, чем для (4).

Размещено на http://www.allbest.ru/

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

Размещено на http://www.allbest.ru/

Её недостаток в том, что в третьем ряду на последней клавише размещаются семь символов. С практической точки зрения может быть предложена несколько худшая раскладка, но содержащая не более пяти символов на каждой клавише. Трудоемкость представленной далее клавиатуры - 1,6317, что на 24,6% меньше, чем для (4).

Размещено на http://www.allbest.ru/

Раскладка букв русского алфавита на 9 клавишах. Среди = 7888725 возможных раскладок минимальная трудоемкость - 1,8574, на 16,8% меньше, чем для (4), достигается на следующей раскладке:

Размещено на http://www.allbest.ru/

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

Размещено на http://www.allbest.ru/

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

Раскладка букв английского алфавита на 9 клавишах. Среди = 1562275 возможных раскладок минимальная трудоемкость - 1,4947, на 30,9% меньше, чем для (4), достигается на следующей раскладке:

Размещено на http://www.allbest.ru/

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

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

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

2. http://tirantrain.livejournal.com

Размещено на Allbest.ru