Alphabetical List Item Selection

User interfaces often require users to select an item from a list of alphabetical items. The value to be selected might be known in advance, or browsing might be necessary to pick out the correct item. This article describes a method of selecting alphabetical list items that reduces the number of keystrokes and hand movements from keyboard to mouse.

1. Introduction

User interfaces often require users to select an item from a list of alphabetical items. The value to be selected might be known in advance, or browsing might be necessary to pick out the correct item. Operators of telephone information services often have to look up street or business names to find post codes or telephone numbers, for example. If the customer knows the name of the street or business, the operator can enter the name and quickly retrieve the required information. If the customer is unsure of the name the operator may need to browse the list of names using the limited information supplied by the customer. This article describes a list filtering algorithm for implementing user interfaces for selecting an item from an alphabetical list. The algorithm reduces the number of keystrokes and hand movements from keyboard to mouse and back.

2. User Interface

The list filtering algorithm is designed for a user interface composed of a standard scrolling alphabetical list of items and a text input box. The scrolling list and text input box provide the standard behavior expected of such a combination: the name of the item can be typed into the input box and the item can be selected from the list. The complete list is displayed to enable recognition over recall by browsing.

The text input box is connected to the scrolling list by the list filtering algorithm: typing characters into the input box reduces the number of items displayed in the list by filtering out the items that do not begin with the characters in the input box. The input box restricts the characters that can be entered to ensure that when the list is filtered, it will always contain at least one item.

When a sufficient number of characters have been entered to uniquely identify an item, the remaining characters of the item’s name are added to the characters in the input box to complete the name. The number of keystrokes required to select an item is reduced to the number required to uniquely identify it.

For large lists, the list filtering algorithm is used to reduce the number of items in the list to enable the user to select an item more easily. A study of the street names in four U.K. cities, for example, shows that the average length of a street name is between 10 and 12 letters, and that, on average, 3 letters need to be entered to reduce the number of street names in a list to a manageable 20 names.

3. The Algorithm

The following list of street names will be used to explain the algorithm:

Aberporth Road
Adelaide Street
Albany Road
Allensbank Road
Atlantic Wharf
Atlas Road

When selecting the street name Aberporth Road, entering the character a in the text input box reduces the list to the street names beginning with A (the first character is always transformed into upper case) The next valid characters that the input box will accept—called the next discriminating characters—are the characters that differentiate the items in the list given that each item begins with the same sequence of letters, in this case the letter A. The set of next discriminating characters for the items beginning with a contains the characters that follow the character a in each item. The set of next discriminating characters for the items

Aberporth Road
Adelaide Street
Albany Road
Allensbank Road
Atlantic Wharf
Atlas Road

is

b d l t

Tapping backspace to erase the character A displays the full alphabetical list of items.

Typing b into the text input box reduces the list still further to the street names starting with Ab, in this case the only matching name is Aberporth Road. Because no more characters are required to differentiate Aberporth Road from the other street names, the text Ab in the input box is automatically expanded to the full name Aberporth Road which can then be selected by pressing return:

Ab ⇒ Aberporth Road

Only two characters (plus return) are required to select this 14 character street name. The list of items is reduced from

Aberporth Road
Adelaide Street
Albany Road
Allensbank Road
Atlantic Wharf
Atlas Road

to

Aberporth Road

This name could also have been selected with the mouse from the list but pressing return after entering the character b reduces the number of hand movements.

Tapping backspace when the input box contains the name Aberporth Road automatically reduces the text to the character that occurs before the character in the set of next discriminating characters, i.e. those following the character A:

Aberporth Road ⇒ A

No other items begin with the characters Aberporth Roa, Aberporth Ro, Aberporth R, etc., so repeatedly tapping backspace to delete the characters berporth Road (or selecting and deleting them with the mouse) is a waste of keystrokes.

If the characters Al are entered into the text box, the list is reduced to

Albany Road
Allensbank Road

The next valid characters are the discriminating characters b and l. Entering b completes the name Albany Road; entering l completes the name Allensbank Road.

If the characters At are entered, the list is reduced to

Atlantic Wharf
Atlas Road

Because both of these names begin with the characters Atla, the text in the input box is automatically expanded up to the next discriminating characters n and s:

At ⇒ Atla

Two keystrokes (l and a) are saved in this example. Entering n completes the name Altantic Wharf; entering s completes the name Altas Road.

When the input box contains the characters Atla, tapping backspace to delete the character a automatically deletes the character l too:

Atla ⇒ At

Because none of the items begin with the characters Atl followed by a letter other than a, tapping backspace to delete the character l is a waste of a keystroke.

4. Implementation

The implementation of the list filtering algorithm appends characters to the text in the input box and deletes characters from it. When a character is appended to the text in the input box, the text is checked to see if it can be expanded. The expansion algorithm begins by reducing the list to the items that begin with the character sequence in the input box, s, and proceeds as follows:

1. find the item, i, with the greatest length;
2. iterate through the characters in item i from the first character to the last: while the character in item i at position p is the same as the character at position p in each of the other items in the list, append the character at position p to s and increment p.

The set of next discriminating characters contains the character at position p in each item. In the following example, the value of p starts at 2 and ends at 5 where the next discriminating characters are n and s:

1 | 2 3 4 | 5 6 7 8 9 10 11 12 13 14
A | t l a | n t i c _ W  h  a  r  f
A | t l a | s _ R o a d

A stack is used to store the extended input characters so the correct character sequence is available when a character in the input box is deleted. The following sequence is followed when the backspace key is tapped:

1. pop the previous input character sequence, s, off the top of the stack;
2. find the items in the list that start with s;
3. update the list of matching items on the screen;
4. update the text input box to show the input character sequence s.

As shown in the table below, when the input characters are Atlantic Wharf and backspace is tapped, the character sequence Atla is popped off the stack and replaces the characters in the input box. The list is filtered to include all the items that start with the character sequence Atla. If backspace is tapped again, the character A is popped of the stack and the list is filtered to include all the items that start with the character A.

Input Characters	Text in Input Box	Stack
A	A	A
t	At ⇒ Atla	Atla
n	Atlan ⇒ Altantic Wharf