Browsing by Author "Darragh, John J."

Now showing 1 - 7 of 7
  • Thumbnail Image
    ItemOpen Access
    ADAPTIVE PREDICTIVE TEXT GENERATION AND THE REACTIVE KEYBOARD
    (1989-05-01) Darragh, John J.; Witten, Ian H.
    This paper explores the application of predictive text generation to the human-computer interface. Predictive techniques exploit the statistical redundancy of language to accelerate and amplify user inputs. Acceleration is achieved by making more likely language elements faster to select, while amplification is accomplished by selection of concatenated elements. The language models used are created adaptively, decoupling the prediction mechanism from the application domain and user's vocabulary, and conforming automatically to whatever kind of text is entered. A device called the Reactive Keyboard is described along with two user interface implementations, one for keyboard entry and the other for a mouse/window environment. A clear separation is made between the system's user interface and the underlying model it employs, and the two versions share the same prediction technique and adaptive modeling mechanism. The basic idea is to order context-conditioned candidate strings, which are predicted by the model, according to popularity and display them for selection.
  • No Thumbnail Available
    ItemMetadata only
    ADAPTIVE TEXT COMPRESSION TO ENHANCE A MODEM
    (1983-10-01) Darragh, John J.; Witten, Ian H.; Cleary, John G.
    The design of a coding system is described and evaluated in the context of a computer-to-terminal modem connection. Unlike other compression problems, it is hard to characterise the kinds of information that may require processing. For this reason the system uses an adaptive Markov model, in conjuction with arithmetic coding. The compression performance improves with available memory. Two techniques for storing the Markov model are described. Experimental results are reported for a variety of sample texts. It is shown that effective line speeds can be at least doubled, and in some cases tripled, using less than 64 Kbytes of memory.
  • Thumbnail Image
    ItemOpen Access
    BONSAI: A COMPACT REPRESENTATION OF TREES
    (1991-10-01) Witten, Ian H.; Cleary, John G.; Darragh, John J.
    This paper shows how trees can be stored in a very compact form, called "Bonsai", using hash tables. A method is described that is suitable for large trees that grow monotonically within a predefined maximum size limit. Using it, pointers in any tree can be represented within $6 + \s-3 left ceiling \s+3 log sub 2 n \s-3 right ceiling \s+3 $ bits per node where \fIn\fR is the maximum number of children a node can have. We first describe a general way of storing trees in hash tables, and then introduce the idea of compact hashing which underlies the Bonsai structure. These two techniques are combined to give a compact representation of trees, and a practical methodology is set out to permit the design of these structures. The new representation is compared with two conventional tree implementations in terms of the storage required per node. Examples of programs that must store large trees within a strict maximum size include those that operate on trie structures derived from natural language text. We describe how the Bonsai technique has been applied to the trees that arise in text compression and adaptive prediction, and include a discussion of the design parameters that work well in practice.
  • No Thumbnail Available
    ItemMetadata only
    A FAST COMPACT REPRESENTATION OF TREES USING HASH TABLES
    (1984-09-01) Cleary, John G.; Darragh, John J.
    A new representation of trees using hash tables is described. Like the usual pointer representation leaves can be reached or inserted in a time proportional to the depth of the tree. Each node uses only the space for its data plus an overhead of $10~+~left ceiling {log sub 2 n} right ceiling$ bits, where $n$ is the number of children allowed on each node. A parent node is accessible from its child, allowing an algorithm to be exhibited for traversing a tree using a small constant amount of storage and without modifying the tree itself. Expressions are given for the space and time required for traversal of trees, as well as, space and timing data from an actual implementation.
  • No Thumbnail Available
    ItemMetadata only
    THE REACTIVE KEYBOARD: A NEW TECHNOLOGY FOR TEXT ENTRY
    (1983-04-01) Witten, Ian H.; Cleary, John G.; Darragh, John J.
    This paper proposes a text entry device which does not use a fixed keyboard. Instead, it employs recently-developed adaptive techniques to display on a VDU predictions of the text the user is about to enter. One of these predictions is selected by the user using a suitable pointer technology. Design considerations for the system, and experience with one of its precursors, are discussed. Simulations are described which illustrate how the device will behave in practice. The use of an adaptive model of the text allows the system to predict on the basis of the language and vocabulary actually used in the text entered so far, and the model changes dynamically during the entry process. If desired, a sequence of typical text could be used to prime the device. Some possible applications and extensions include the graceful integration of spelling and syntax checkers into the predictive process, and hence into the reactive keyboard itself.
  • Thumbnail Image
    ItemOpen Access
    THE REACTIVE KEYBOARD: A PREDICTIVE TYPING AID
    (1989-11-01) Darragh, John J.; Witten, Ian H; James, Mark L.
    The Reactive Keyboard is a device that accelerates typewritten communication with a computer system by predicting what the user is going to type next. Text is entered by pointing into a menu of predictions. Predictions are based on a model of language that is created adaptively and updated continually as new text is entered. This new interface has great potential to enhance the ease and rate of communication, especially for physically limited people.
  • No Thumbnail Available
    ItemMetadata only
    REDUCING KEYSTROKE COUNTS WITH A PREDICTIVE COMPUTER INTERFACE
    (1982-09-01) Witten, Ian H.; Cleary, John G.; Darragh, John J.; Hill, David R.
    It has recently been demonstrated how techniques of non-deterministic structural modelling can be applied to reduce the number of keystrokes typed by a user in typical interactive computer sessions. The sequence of keystrokes is observed by the machine, modelled, and where possible used to form predictions of the characters about to be typed. This paper discusses the application of such an interface to the physically handicapped. Particular attention is paid to reducing the number of keystrokes needed to enter different kinds of text, such as source programs, interactive commands, and plain English. In some cases up to 50% of a users keystrokes are correctly predicted, resulting in significant keystroke count reductions.