ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Публикационная активность

(сведения по итогам 2016 г.)
2-летний импакт-фактор РИНЦ: 0,493
2-летний импакт-фактор РИНЦ без самоцитирования: 0,389
Двухлетний импакт-фактор РИНЦ с учетом цитирования из всех
источников: 0,732
5-летний импакт-фактор РИНЦ: 0,364
5-летний импакт-фактор РИНЦ без самоцитирования: 0,303
Суммарное число цитирований журнала в РИНЦ: 5022
Пятилетний индекс Херфиндаля по цитирующим журналам: 355
Индекс Херфиндаля по организациям авторов: 499
Десятилетний индекс Хирша: 11
Место в общем рейтинге SCIENCE INDEX за 2016 год: 304
Место в рейтинге SCIENCE INDEX за 2016 год по тематике "Автоматика. Вычислительная техника": 11

Больше данных по публикационной активности нашего журнале за 2008-2016 гг. на сайте РИНЦ

Вход


Забыли пароль? / Регистрация

Добавить в закладки

Следующий номер на сайте

4
Ожидается:
16 Декабря 2017

Задача о клавиатуре

Статья опубликована в выпуске журнала № 3 за 2003 год.[ 24.09.2003 ]
Аннотация:
Abstract:
Авторы: Усманов З.Д. () - , ,
Ключевое слово:
Ключевое слово:
Количество просмотров: 5414
Версия для печати
Выпуск в формате PDF (13.63Мб)

Размер шрифта:       Шрифт:

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

При проектировании компьютерной клавиатуры под какой-либо новый естественный язык L проектировщик размещает буквы алфавита L на множестве клавишей , оставляя по возможности неизменными назначения клавишей множества . Последнее удается сделать при условии, что число m клавишей множества  не меньше числа n букв алфавита L, то есть m. Если же , то весь алфавит L не может быть размещен на множестве .

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

Теперь предположим, что множество  тем или иным образом уже приспособлено для раскладки на нем алфавита языка L, то есть выполнение неравенства  обеспечено. Именно в таком предположении перейдем к рассмотрению следующей задачи.

Задача К. Разместить по клавишам множества  все буквы алфавита языка L так, чтобы каждому клавишу соответствовало не более одной буквы.

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

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

Алфавит, сформированный таким образом, подсказывает, в свою очередь, естественный ПРИНЦИП раскладки букв на клавиатуре: более приоритетные буквы следует размещать в центре, а менее приоритетные – на  периферии множества .

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

Формализация задачи. В плоскости клавиатуры K выберем прямоугольную систему координат  и отметим на этой плоскости точки, соответствующие центрам буквенных клавишей множества . Полученный таким образом дискретный набор точек обозначим через B. Этот набор, состоящий из m точек – образов буквенных клавишей, является образом буквенной части компьютерной клавиатуры K. В связи с этим интересующая нас раскладка букв языка L по клавишам множества  может быть получена путем установления отображения алфавита A на множество B. При m=n, когда A и B имеют одинаковые мощности, речь идет о взаимно-однозначном отображении их элементов, а в случае m>n, об отображении A лишь на часть множества B.

При построении конкретного отображения  мы воспользуемся тем фактом, что в алфавите  его буквы  уже расположены в порядке убывания соответствующих им частот встречаемости в текстах языка L. Если теперь осуществить упорядочение точек b множества B, то есть , то конкретизировать отображение P можно будет, например, следующим образом:        то есть соответствующими объявляются та буква  и та точка (клавиш) , которые получают одинаковый порядковый номер i (). В этой связи вопрос о построении отображения P, а потому и о надлежащем способе размещения букв по клавишам множества , сводится к выбору некоторого критерия для упорядочения точек множества B.

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

Критерий 1. Из двух точек множества B меньший порядковый номер следует присвоить той, которая имеет меньшее значение .

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

Обсудим еще один критерий упорядочения точек множества B, достаточно близкий к уже рассмотренному. Предположим, что каким-то k точкам  уже присвоены порядковые номера от 1 до k. Обозначим через   подмножество множества B, состоящее из оставшихся, непронумерованных точек.

Критерий 2. Порядковый номер k+1 следует присвоить той точке подмножества  , которая в  сравнении с другими точками имеет наименьшее значение показателя , вычисляемое на точках, принадлежащих .

При сопоставлении правил принятия решений по критериям 1 и 2 нетрудно обнаружить, что они определяют одну и туже точку множества B в качестве самой приоритетной, получающей номер 1, а все другие точки, вообще говоря, ранжируют по-разному. В самом деле, только на первом шаге оба критерия оперируют с одним и тем же множеством значений показателя . В дальнейшем критерий 1 использует прежнее множество , что касается критерия 2, то его решения принимаются на подмножестве , включающем в себя только те точки, которые еще остаются непронумерованными.

Определение приоритетной точки. Для выявления закономерностей в расположении приоритетной точки обратимся к рассмотрению более общей задачи, полагая, что множество B есть замкнутая многосвязная область на плоскости C, снабженной прямоугольной системой координат . Обозначим через  и ,  комплексные координаты соответственно точки области B и произвольной точки плоско- сти C. Среднеквадратическое отклонение точки  от всех точек  вычисляется по формуле:

.                                         (1)

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

                  (2)

Из этой формулы следует, что именно центр тяжести  области B является той точкой, для которой показатель  принимает минимальное значение.

Полученный результат нуждается в комментарии. Причина в том, что если область B выпуклая, то  является ее внутренней точкой, а потому и приоритетной. Однако если же B невыпуклая область, то  может и не принадлежать области B. Тем не менее, с помощью  легко определяется приоритетная точка области B с минимальным значением .

Введем обозначение: .

Из формулы (2) следует, что линиями уровня , на которых показатель  принимает постоянные значения , являются концентрические окружности радиуса R с центром в точке . Очевидно, что  при .

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

Упорядочение точек. Опираясь на результаты предыдущего пункта, перейдем к упорядочению точек дискретного множества B. Координаты его средней точки (центра тяжести)  вычисляются по формуле: , в которой комплексные числа ,  задают координаты центров m буквенных клавишей. Первой приоритетной точкой множества B, которая одинаковым образом выявляется критериями 1 и 2 и которой присваивается но- мер 1, объявляется точка, оказавшаяся на минимальном расстоянии от . Если же таковых окажется несколько, например p штук , то они получают порядковые номера от 1 до p либо произвольно, либо с учетом каких-то дополнительных ограничений.

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

Нумерация точек в соответствии с критери- ем 2, по существу, сводится к выполнению однотипных процедур. После выявления первой приоритетной точки (или же нескольких таковых точек) она (они) удаляется (удаляются) из множества B и затем на вновь полученном множестве опять-таки отыскивается средняя точка (центр тяжести), а с ее помощью и первая приоритетная точка и т.д. Процедура повторяется до тех пор, пока не останутся лишь две непронумерованные точки, которым приписываются последние порядковые номера, то есть  и m.

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

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


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=629
Версия для печати
Выпуск в формате PDF (13.63Мб)
Статья опубликована в выпуске журнала № 3 за 2003 год.

Возможно, Вас заинтересуют следующие статьи схожих тематик: