"Watch What I Do" Chapter 8


Figure 1. Reformatting an address list

Chapter
8

TELS:
Learning Text Editing Tasks
from Examples

Ian H. Witten
and
Dan Mo



Introduction

People who employ interactive text editors are frequently confronted with simple repetitive editing tasks which are trivial and tedious to perform manually, yet hard to automate. When the text lacks formal structure, neither structured editors nor simple keyboard macros will do. Custom-built programs are rarely worth considering: the tasks are riddled with special cases that drive up the cost of a program that may be used only once.

Three such tasks are illustrated in Figures 1-3. They all involve reformatting textual databases: an address list, a set of match scores, and a bibliography. Each can be accomplished using an editor with a macro definition capability, but this requires careful advance planning and is difficult to get right the first time. Moreover, any programming solution suffers from excessive rigidity--in reality, the tasks are defined incrementally and may be extended as more examples are encountered. In practice, people are likely to accomplish such tasks by manually editing each entry, perhaps using global search-and-replace to perform sub-tasks where feasible.

Programming by demonstration seems a natural way to approach these problems. Rather than programming a task, users need only demonstrate examples of how to perform it, from which a program is synthesized that performs the task itself. [Nix 84] has investigated the application of "by example" techniques to text editing by looking only at inputs and outputs, and seeking a transformation that maps blocks of input text into corresponding output blocks. While this works well for rigidly-structured tasks like that of Figure 2 (which was taken from Nix's thesis), it breaks down when faced with less artificial transformations that involve rules and exceptions, like those of Figures 1 and 3. In contrast, the scheme developed in the present paper adopts a procedural stance: editing actions are recorded and generalized into a program that transforms input into output. This seems to offer better potential for complex, ill-structured, editing problems where many different cases may arise.


Figure 2. Reformatting a simple database

Figure 3. Reformatting a bibliography


TELS

Uses and Users

Application domain: Text Editing

Tasks within the domain: Reformatting textual data

Intended users: non-programmers

User Interaction

How does the user create, execute and modify programs?
The user records one complete example of the task -- that is, edits one block of text. When the user signals the end of the block, TELS enters performance mode. The system will predict actions on the remaining blocks of text. It confirms each action step by step. Predicting actions can involve behind-the-scenes generalization of the program. If TELS makes a mistake, the user is invited to enter a debugging phase which in effect reverts to learning mode.
There is no view of the program. The user modifies programs by debugging.

Inference

Inferencing: TELS merges steps that have the same "action" (insert, locate, select, or delete) if their parameters are similar, such as constant numbers or strings with the same format (e.g. "3023 Blakiston Dr.," and "1124 Brentwood Dr.," have the format "[digit]* [space] [letter]* [space] Dr.,").

Types of examples: TELS learns from a single block of text which may include several examples of some steps. Then, it incrementally generalizes or modifies the constructed program as the user confirms or corrects subsequent predictions. It generalizes character string patterns and procedures from multiple examples.
If the user rejects a prediction, TELS treats the predicted text selection as a negative example: when searching, TELS skips over any selections that match a negative example.

Program constructs: Variables, loops, nested loops and conditionals.

Knowledge

Types and sources of information:
User actions are mapped into four high-level editing commands -- insert, locate, select and delete. For each action, TELS knows the words preceding and following the selection, the location of the selection in the document, and the relative distance of the selection from its previous location.
TELS has a generalization hierarchy for characters (e.g. digits, letters, characters) and positions within lines and paragraphs.

Implementation

Machine, language, size, date: Macintosh; Pascal (using the MiniEdit routines). 1988-89.

back to ... Table of Contents Watch What I Do