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

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

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

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

Общим для всех рассмотренных выше задач является то, что в основе их решения лежат процедуры выделения характеристик для описания объектов, представление этих описаний в удобном для анализа

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

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

1. Решетников В.Н. Алгебраическая теория информационного поиска. // Программирование. - 1979. - № 3. - C. 78-83.

2. Решетников В.Н. Информационный поиск и Z-струк-тура. // Математические вопросы задач оптимизации и управления. - Изд-во МГУ, 1981.

3. Решетников В.Н., Сотников А.Н. Алгоритмы отсечения для построения псевдорелевантных множеств. // Программное обеспечение вычислительных комплексов. - Изд-во МГУ. -1985. - С. 60-64.

4. Прохоров А.Ю., Сотников А.Н. Поиск во временном ряде фрагментов, «похожих» на заданный шаблон. // Программные продукты и системы. - № 3. - 2003.

5. Bereznev V., Sotnikov A., Cherednitchenko I. The system for hand-written and textual symbols identification. // Pattern recognition and Image analysis, № 4, 1995.

6. Сотников А.Н., Чередниченко И.Н. Построение автоадаптивного фонта в документах электронных библиотек. // Программные продукты и системы. - 2008. - № 2. - С. 16-19.

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

З.Д. Усманов, академик АН РТ

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

Пусть А={а(1),а(2),...,а(п)} - упорядоченное п-

множество символов и С={С15С2,^,СГ} - упорядоченное г-множество ячеек, в которых размещаются наборы символов с сохранением порядка, то есть

С={С1[а(/0 +1),...,а(/1)],...,С8[а(/8_1+1),...,а(/,)]

Сг[а

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

/8-1 +1< ^, 8=1,...,г , и 1г = п.

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

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

ветствии с [1] количество различных вариантов определяется числом Сгп__11 сочетаний из п_1 элементов по г_1 .

Введем два набора положительных чисел. Элементы одного из них (А,(к) , к=1г..,п , причем

п

^Х(к)=1) поставим в соответствие по индексу к к=1

символам а(к) множества А. Другой набор положительных чисел - N , р = 1,2„..,п_г+1 - строго монотонно возрастающий, N<N<...<^_г+1 . В ячейке С8, 8=1г..,п_г+1, содержащей /8_/8-1 символов, число N будем связывать с символом

а(/8.1+р), 1< р < /8 _ .

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

г р=/

W = X X *•

8=1 р=1

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

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

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

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

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

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

Покажем, что поставленный вопрос может быть интерпретирован как трансформация задачи 1 в конкретную прикладную сферу. В качестве множества A={a(1),a(2),.. ,,a(n)} будем рассматривать алфавит

какого-либо естественного языка, элементами которого являются буквы a(k) , k=1r..,n , а в качестве A,(k) , k=1r..,n , - относительные частоты встречаемости букв в фиксированном тексте естественного языка. Ячейки, о которых идет речь в задаче 1, отождествим с клавишами клавиатуры мобильного телефона. Остается пояснить значения Np . Полагая, что усилия, затрачиваемые на однократное нажатие клавишей, одинаковы, мы можем принять Np = p

(p = 1,2,.,.,n —г+1 ), то есть связать Np с количеством нажатий на клавишу s для извлечения буквы

a(ls—1 + Р) , p^ h — ls—1 , s = 1,-",Т .

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

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

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

А Б В Г A B C

Д Е Ж З D E F

иикл

GHI

Т У Ф Х P Q R S

М Н О J K L

Ц Ч Ш Щ Ъ T U V

П Р С M N O

Ы Ь Э Ю Я W X Y Z

Рис. 1

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

Что касается А,(к) , к=1г..,п , то их значения

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

Таблица 1

А Б В Г Д Е Ж З И й К

7,51 1,75 4,53 1,8 3,02 8,73 0,97 1,75 7,44 1,18 3,37

Л М Н О П Р С Т У Ф Х

4,2 3,12 6,45 11,01 2,8 4,77 5,5 6,49 2,48 0,19 1,07

Ц Ч Ш Щ Ъ Ы Ь Э Ю Я

0,45 1,49 0,68 0,45 1,01 1,97 0,79 0,32 0,73 2,12

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

A B C D E F G H I J K L M

7,96 1,6 2,84 4,01 12,86 2,62 1,99 5,39 7,77 3,16 0,41 3,5 2,43

N O P Q R S T U V W X Y Z

7,51 6,62 ,81 0,1' 6,83 6,62 9,72 2,48 1,15 1,8 0,17 1,52 0,05

В таблицах 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. Среди С26 = 657800 возможных раскладок минимальная трудоемкость - 1,6009, что на 26 % меньше, достигается на раскладке, представленной на рисунке 4.

Е Б О

N о р (2

А в

н I ] к

Я 8

С Б

ь м

ТиУ№ХУ2

Рис. 4

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

А В С Б

Е Б О

Н I Б

Я 8

ь м

Т и V

N О Р О

X У Ъ

Рис. 5

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

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

А Б

В Г Д

Е Ж З

И ИК

СТУФХЦ

Л М Н

Ч Ш Щ Ъ

О П Р

Ы Ь Э Ю Я

Рис. 6

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

А Б

В Г Д

Е Ж З

И ИК

С ТУ Ф Х

Л М Н

Ц Ч Ш Щ Ъ

О П Р

Ы Ь Э Ю Я

Рис. 7

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

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

А В

Н I 1К

С Б

Е Б О

Я 8

ь м

Т И V

N О Р О

W X У Ъ

Рис. 8

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

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

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

2. http://tirantrain.livejournal.com