Интеллектуализованный интерфейс пользователя информационно-поисковой системы в задаче поиска по ключевому слову ("образцу") с упреждающей подсказкой

УДК 681.3

Г.Е. КУЗЬМЕНКО, В.А. ЛИТВИНОВ, С.Я. МАЙСТРЕНКО, И.Н. ОКСАНИЧ

ИНТЕЛЛЕКТУАЛИЗОВАННЫЙ ИНТЕРФЕЙС ПОЛЬЗОВАТЕЛЯ ИНФОРМАЦИОННО-ПОИСКОВОЙ СИСТЕМЫ В ЗАДАЧЕ ПОИСКА ПО КЛЮЧЕВОМУ СЛОВУ ("ОБРАЗЦУ") С УПРЕЖДАЮЩЕЙ ПОДСКАЗКОЙ

Анотація. Розглядається типовий інтерфейс користувача у задачі пошуку за зразком (ключовим словом) з упереджувальною підказкою. Пропонуються математичні моделі оцінки трудомісткості варіантів інтерфейсу з покроковою та прицільною підказкою. Наводяться результати імітаційного моделювання процесів формування підказки.

Ключові слова: інтерфейс користувача, пошук за ключовим словом, GOMS, упереджувальна підказка.

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

Abstract. A typical user interface for the task of sample (keyword) search with the ahead prompt is discussed. Mathematical models for estimation of interface complexity with the step-by-step and aim prompt are proposed. The results of simulations of the prompt _ formation are given.

Типовая задача поиска по образцу, реализующая доступ к ресурсам информационнопоисковой (справочной) системы заключается в задании некоего образца (ключевого слова) и его нахождении в базовом словаре (БС) слов-эталонов. Целевые действия, выполняемые в случае нахождения (ненахождения) образца в БС, зависят от назначения системы поиска. Обычным действием общего характера является доступ к неким информационным ресурсам, связанным с соответствующим словом-эталоном.

Область приложения таких задач весьма широка - от простых систем учета товаров на складе до поисковых систем мультимедийных Web-ресурсов СППР.

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

Упреждающая подсказка, являющаяся признаком "интеллектуализованности" ИП в принятом нами смысле, заключается в том, что по мере ввода начальных символов образца, вплоть до ввода "детерминанта" [1], однозначно определяющего образец, прогнозируются возможные варианты искомого эталона и предоставляются пользователю.

В основу такой подсказки положены две особенности БС:

- лексикографическая упорядоченность слов-эталонов;

- информационная избыточность.

Примем следующие обозначения:

Aj = (a1...ai ...an) - j - е слово БС; i = 1,n; j = 1,N ;

© Кузьменко Г.Е., Литвинов В.А., Майстренко С.Я., Оксанич И.Н., 2011 ISSN 102S-9763. Математичні машини і системи, 2011, № 1

q - мощность множества символов (алфавита) составляющих слова - эталоны и образцы.

Лексикографическую упорядоченность слов БС определим следующим образом. Каждому значению символа а{ поставим в соответствие число

волу а1 припишем значение порядкового номера этого символа в алфавите q. БС лексикографически упорядочен, если выполняется

£ а гч ) >£ а (і)

]+і

Практически это означает, что слова-эталоны, интерпретируемые как числа в позиционной системе счисления с основанием q, упорядочены по убыванию значений.

Из [1] следует также, что —— = q, т.е. принято, что символы (а...а{ ...ап) перенумерованы в порядке убывания старшинства.

Строка образца

УУУ/УУШШ

ШІЇШЇШ

ШУ4ШШ

&ШІЇШШ

шушш

Т екущий справочник подсказки (т. слов)

Информационная избыточность слов БС означает, что из qn всевозможных значений комбинаций п символов для представления реально существующих слов БС используется только N комбинаций, составляющих незначительную часть qn ^п >> N). Это свойство позволяет идентифицировать искомое слово-эталон по части символов слова-образца (в частности, по

"старшей" начальной части) и реализовать упреждающую подсказку

Рис. 1. Общая схема интерфейса с упреждающей подсказкой п°льз°вателю.

Общая схема рассматриваемых интерфейсов приведена на рис. 1.

Общий алгоритм интерфейсов по схеме рис. 1 заключается в следующем. Пользователь последовательно вводит символы а1,а2,...,а{ образца (начиная с первого, старшего). На каждом шаге из БС в текущий справочник (возможно, виртуальный) помещаются слова с одинаковыми значениями символов а1, а1а2, ...,а1а2...аг..

Базовый

словарь

ШІШІШ

Назовем множество слов с одинаковыми значениями символов ala2...ai ai - множеством мощностью mt. На схеме рис. 1 показана ситуация, когда в текущем справочнике находится а2 - множество. Из свойства лексикографической упорядоченности слов - эталонов ясно, что m1 )m2)...) mt, т.е. область поиска образца сужается по мере ввода символов а1, а2,....

В идеальном случае, при строго регулярной равномерной структуре словаря mt / mi+1 » q. Практически распределение реально существующих значений слов-эталонов

среди qn всевозможных значений комбинаций символов a1...an носит случайный характер, и, соответственно, значения mi также носят случайный характер.

Относительно слов а.{ -множеств справедливы следующие очевидные положения.

Положение 1. a i+1 -множество является подмножеством а.{ - множества.

Положение 2. Слово - эталон, принадлежащее ai -множеству, принадлежит и ai+1 -множеству.

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

Одним из лучших подходов к количественному анализу интерфейса «пользователь-компьютер» считается применение семейства классических моделей GOMS [2, 3]. Применительно к рассматриваемому классу задач, связанных с клавиатурным вводом символов и анализом текстового сообщения, отображаемого пользователю на экране, в [4, 5] предлагается уточнение модели GOMS KLM (Keystroke-Level Model) [2], основанное на декомпозиции ментальных операторов, определяющих основную часть интеллектуальной нагрузки на пользователя. Подход, описанный в [4, 5], иллюстрирует рис. 2, на котором приняты следующие обозначения для микрооператоров, описывающих «атомарные» действия пользователя в рассматриваемом классе задач.

m - трудоемкость чтения текста с первичного носителя и его осмысление (запоминание) - с/симв;

m - трудоемкость поиска символов на клавиатуре и перемещение руки в позицию “над символом” - с/симв;

m - трудоемкость визуального анализа введенных символов на экране и принятие решения о дальнейших действиях (в частности, о наличии или отсутствии ошибки) - с/симв;

m4 - трудоемкость исправления ошибочного

m5 - трудоемкость визуального анализа и сравнения вводимого слова - образца с предлагаемым на экране словом - с/симв;

к - “чистая” трудоемкость нажатия клавиши рукой, расположенной над символом

- с/симв.

Рис. 2. Схема декомпозиции ментальных операторов

символа ой-line - с/симв;

По своей сути, операторы Ц\\ М3, М5 - это чисто ментальные операторы, к - оператор движения, м2 и М4 - композиция ментальных действий и движений.

Результаты экспериментального определения значений М\\ - М5, к, полученные в [5] для

Таблица 1. Измеренные и рассчитанные значения ц ,к

Язык ml m 2 m 3 m 4 к

КОД G,47 G,38 G,214 1,G6 G,G435 G,15

МНЕМОТЕКСТ G,16 G,25 G,G55 G,8G G,G45 G,15

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

Образец в словаре

Ошибка при вводе

Трудоемкость

интерфейса

Оценим трудоемкость Н различных вариантов ИП на основе подхода и результатов, представленных в п. 2.

Вне зависимости от варианта ИП при вводе образца и поиске соответствующего эталона возможны Есть Нет следующие ситуативные результаты (рис. 3):

- наличие или отсутствие ошибки пользователя при вводе образца;

- положительный (вероятность 5) или отри1 2 цательный (вероятность

Есть

H 21 v21_

Есть

Рис . 3 . С о ставляющие труд о емкости инте рф ейс а искомого слова в БС).

Поскольку вероятность искажения символа при вводе данных сравнительно невелика (порядка 6-8-\\0-3 [6]), ограничимся учетом относительно значимых составляющих Н\\~Н\\\\ и Н2~Н2\\, т.е. положим

И »д-Н\\ +(\\-д)Н2.

В этом варианте интерфейса на каждом шаге ввода образца (т.е. ввода символов a1v.., at)

из общего текущего справочника объемом mt слов пользователю предоставляется одна

страница из m слов, выбранная по некоторому критерию. Подобный интерфейс используется, например, в поисковых системах GOOGLE, YANDEX, RAMBLER и др.

Примем следующие обозначения:

v1(l), v2(l) - среднее количество символов образца, вводимых до завершения процесса поиска в случае положительного и отрицательного результатов поиска соответственно;

mi(l), m2(l) - среднее количество слов, участвующих в процессе визуального анализа предъявляемых страниц текущего справочника в случае положительного и отрицательного результатов поиска.

Определим ориентировочные значения Н ,(1) и Н21 на основе значений т2,М3,М5,к, приведенных в табл. 1.

н,(1) »(т2+к+т3К(1)+т,(1) -п-т5+(р+вв), (2)

Н 21) » (т2 + к +т3 )^2(1) + т21) П& т5 +(т2 + к) . (3)

Первое слагаемое в (2) и (3) определяет затраты времени на ввод и визуальную верификацию символов образца, второе - на визуальный анализ предъявляемых страниц текущего справочника, третье - на подтверждение того или иного результата поиска (Р, ВВ

- стандартные операторы ООМБ подвода курсора и клика мышью).

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

Предполагая случайным распределение N реально существующих слов БС среди qn всевозможных значений, рассмотрим следующую модель.

В некую урну "с узким отверстием" вбрасывается М шаров. Вероятность того, что

очередной шар попадает в отверстие урны, равна г = N/ п . Поскольку эта вероятность не

зависит от результатов предыдущих бросаний, общие вероятностные результаты вбрасываний могут быть описаны схемой и соотношениями процесса независимых испытаний

Бернулли, в соответствии с которыми вероятность р[(о, X) г,М] получить в точности х или менее удачных исходов равна

р[(°, х) г, М ]= ^СМ -г8-(1 - г )М-8 , (4)

а среднее количество удачных исходов Nм равно

^ 8-СМ,-г8-(1 - Г г-8 = гМ. (5)

В соответствии с такой интерпретацией для М = qn~& примем

Р (1) » т 1г п—г "

Безусловная вероятность р1(1)(г) того, что образец будет найден именно на шаге г ,

равна

г—1 / \\

р1,,(& )=р п (1 - р“’).

Если образец не был найден за (1т -1) шагов, то на шаге 1т, когда область поиска сузится до значений т 1т < т , образец определенно будет обнаружен, т.е. мы можем положить Р,^ = 1. Значение 1т определяется из условия —т > 1.

Таким образом,

*«) = £;-р1&){,)+!_-1-]П (1 - РЙ (6)

(i -1)- m +

m +1 2

P(i)(i)+

(!m - 1)-m +

m + 3

где Im - ближайшее целое, большее или равное log(

Если образец в БС отсутствует, то на шаге г это становится известным, если при вбрасывании qn~1 шаров в урну попадает 0,1,...,т шаров. Следовательно,

P21 = P[(0, m\\r,

Р<Ц(0 = Л?>- П(1 -С )

VF=Е^Чо.

Отсюда

(i -1)- m +—

p(1) (i) •

В выражениях (7), (9) принята равновероятность различных вариантов заполненности последней проверяемой страницы и результатов перебора представленных слов при поиске образца.

В табл. 2, 3 (МНЕМОТЕКСТ; т = 10, q = 32, п = 5 ) и 4 (КОД; т = 10, q = 10, п = 12) в качестве примера приведены результаты расчетов значений р(1\\р(1) (г) и Н(1),

у,(1), т,(1), у2(1), т2) для выбранных типовых значений параметров q и N, соответствующих словам русского языка и цифровым кодам. В частности, для русского языка принято: средняя длина слов БС п = 8 символов, количество слов в типовом словаре N = 105 [7]. Отсюда для q = 32,п = 8, N = 1,1 -105 величина г » 10-7. Для иллюстрации трендов взяты два значения N = 1,1 -106 (г = 10-6) и N = 1,1 -104 (г = 10-8). Аналогичные значения г выбраны и для гипотетических цифровых кодов.

Таблица 2. Значения р(((), р1(1) (г): МНЕМОТЕКСТ

r N P (!) i

P<" (i) 0,0003 0,0093 0,2866 0,7038

r N d vW m1(1) V(1) m2(1)

Таблица 4. Значения H(l), v(l), m/^, v2(l), m21: КОД

r N d vW ml(l) v(l) m2(l)

Как видно из данных табл. 3, 4, трудоемкость рассматриваемого интерфейса непропорционально велика. Например, в поисковых системах GOOGLE, YANDEX, RAMBLER и др. поиск и предоставление пользователю информационных ресурсов, связанных с образцом, требует менее секунды, а ввод и идентификация образца - до десяти и более секунд. Правда, на одном из шагов ввода до идентификации образца пользователь может обнаружить в словах-эталонах предъявляемой страницы что-то подходящее по смыслу и, таким образом, ввести в итоге меньше символов. Однако это требует дополнительных размышлений, более длительных, чем просто сравнение эталона с задуманным образцом (п • /и5). Кроме того, подобные размышления практически неприемлемы при вводе кодов.

Поэтому в целом трудоемкость ИП в рассматриваемом варианте представляется уместным оценить как относительно высокую. Тенденции, определяющие зависимости v1(l), H1 от значений r, N, d и алфавита образца, ясны из данных табл. 2-4.

Возможность снижения трудоемкости ИП с пошаговой подсказкой основана на следующих предпосылках.

Рассмотрим дискретную функцию P1 (i), представленную в табл. 2.

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

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

Эффективной программной реализацией этого приема (обозначим трудоемкость соответствующего ИП через H ^2)) должно быть предоставление пользователю для просмотра лишь последней страницы, объем которой < m, или, по крайней мере, информирование пользователя о появлении этой страницы (например, звуковым сигналом).

Еще более эффективным представляется решение, заключающееся в автоматическом сужении области поиска до одного искомого слова (обозначим трудоемкость ИП через H(3)).

Оценим значения H ^2) и H ^з) для отмеченных вариантов ИП на основе базового выражения (1).

Для оценки значений H ^2) справедливы выражения (2), (3) при условии подстановки соответствующих значений vl(2), v2(2), да/2), m2(2). Определим эти значения. Для этого вернемся к модели вбрасывания шаров в урну.

Поскольку пользователь обращается к экрану лишь при выполнении условия mi < т, условная вероятность завершения процесса на шаге 1 определяется через вероятность того, что на шаге г при вбрасывании дп-г шаров в урне окажется не более т шаров. При определении значений Р1г(2) и Р2^ учтем следующее.

В случае потенциально положительного результата поиска в БС есть искомый образец, и среди т{ слов одно имеет не случайное, а детерминированное происхождение. Это

означает, что один шар кладется в урну заранее, а 0, 1, ..., т -1 шаров попадают случайным образом, определяя удачные исходы испытаний Бернулли (т.е. в выражении (4) х := т -1).

В случае отрицательного результата поиска детерминированный шар в урне отсутствует, и следует х := т.

Таким образом,

р(2) 1 11

р[(о, т -1), г, д" 1 ],

:Р[(о, т) г, дп 1 ],

г-1 , ч

Р(2 &(О=Р&ЙГО - Р(2,’-).

Полагая ^(1 - Р^) » 0 (т.е. процесс определенно заканчивается при г < п ) и принимая прежнее упрощающее допущение о равновероятности вариантов заполненности проверяемой страницы и результатов перебора представленных слов, запишем следующие выражения для искомых значений:

V(2) 1,2

—(2) т + 3

В табл. 5 и 6 приведены результаты расчетов для образцов вида МНЕМОТЕКСТ и КОД и прежних наборов значений параметров т, д, п.

Таблица 5. Значения Н

(2) тг(2) ™(2) тг(2) ™(2) •

, т2 : МНЕМОТЕКСТ

г N 8 */2) т1(2) т22)

Таблица 6. Значения Н(2), V 1(2), т(2), у2(2), т2(2): КОД

г АТ 8 у<2) т1(2) т2(2)

N 1,0 0,75

Рассматриваемый вариант интерфейса является частным случаем предыдущего. Здесь х = 0 как для положительного, так и отрицательного результата поиска. При попадании в пресловутую урну 0 случайных шаров в случае положительного результата в урне оказывается только один детерминированный шар, а в случае отрицательного - 0 шаров.

Таким образом, P/3 = p[(o,o),r, qn - ],

p^o=Pm (1 - Кг*),

v£>= ^ i-Pj (i),

да/з) = 1, да2(з) » 0 .

В табл. 7 и 8 приведены результаты расчетов для прежних видов образцов и наборов значений параметров

Таблица 7. Значения Н(3), у/3), да/з), У2(3), да"2з): МНЕМОТЕКСТ

r N d v/ 3) m/3) v23) m2(3)

Таблица 8. Значения H(3), v1(3), m/3), v2(3), mf3: КОД

r N d v/3) m/3) v2(3) mi3)

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

Как видно из данных табл. 3-8, на фоне общей полезности упреждающей подсказки как способа снижения трудоемкость и повышение usability ИП в задачах поиска по образцу, прицельная подсказка обеспечивают существенно меньшую трудоемкость, чем пошаговая (в частности, с произвольным выбором предъявляемой пользователю страницы текущего справочника). Этот вывод иллюстрирует табл. 9, обобщающая результаты расчетов. В табл. 9 представлены относительные значения коэффициентов h21 =

= H (2\\

И31 = Н п/н (1) , мало зависящие от квалификации пользователя. Таблица 9. Обобщенные результаты расчетов

h r М Н Е М О Т Е К С Т к О Д

N d N d

h21 10-6 1,1106 0,30 0,30 1106 0,25 0,25

h31 10-6 1,1106 0,20 0,20 1106 0,21 0,20

Данные таблиц 3-8 также определяют общие тенденции зависимостей Н от г, N, ^.

оперируем не вероятностями случайных значений количества удачных исходов, т. е. попавших в урну шаров, а их средними значениями (расчеты по более точным формулам неприемлемо сложны из-за высокой размерности). Результаты имитационного моделирования ИП с пошаговой и целевой подсказками, проведенные для оценки погрешностей, связанных с отмеченными выше и другими принятыми допущениями, показали относительно небольшое расхождение между расчетными и экспериментальными данными. В табл. 10 для 8 = 1,0 сведены значения у1 , принятые в качестве основного критерия сравнительной оценки. Как видно, расхождение не превышает 3 4%. Примерно в таких же пределах находится и расхождение значений т1.

Таблица 10. Результаты имитационного моделирования интерфейсов

Образец r N Расчетные значения Экспериментальные значения

vW v/J) v/3) V1(1) V1(2) v/3)

МНЕМО- ТЕКСТ 10-6 1.1-106 3,69 4,00 4,67 3,70 4,02 4,74

КОД 10-6 1106 4,96 5,54 6,69 5,02 5,55 6,76

СПИСОК ЛИТЕРАТУРЫ

J. Kieras D. Using the Keystroke-Level Model to Estimate Execution Times [Електронний ресурс] / D. Kieras. - University of Michigan. - Режим доступу: ftp://www.eecs.umich/edu/people/rchong/kieras/GOMS/KLM.pdf.

Стаття надійшла до редакції 11.10.2010