Automatic word completion system for partially entered data

Details Automatic word completion system for partially entered data Automatic word completion system for partially entered data

1997-11-07

2002-04-23

Breene, John (Department: 2177)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

06377965

ABSTRACT:

TECHNICAL FIELD
This invention relates generally to the field of data entry systems and, more particularly, to automated word completion systems for operating with unstructured data files, such as word processing documents and e-mail messages.
BACKGROUND OF THE INVENTION
General purpose digital computers are widely used for a large variety of text-based applications, including word processing, e-mail, spreadsheets, personal calendars, etc. To use the computer for one of these purposes, a user typically types on a keyboard to enter text and commands into an active data file, which is open within an application program running on the computer. Other text input devices include a voice recognition interface, a touch-sensitive screen overlaid on top of a graphical image of a keyboard, or a system that detects the motion of a pen in combination with handwriting recognition software. The text and commands are then interpreted and manipulated by the application program in accordance with the syntax and functionality implemented by the application program.
For many users, the most time consuming computer activity is the entry of large amounts of text into various data files, such as word processing files and e-mail files. Regardless of the input method used, the speed at which the text can be entered into the computer is a major factor governing the user's efficiency. The designers of text-intensive application programs have therefore developed text-input aids to assist users in entering text into the computer.
A word prediction system is an example of such a text-input aid. Generally stated, a word prediction system predicts and suggests complete data entries based on partial data entries. This allows the user to type in a partial data entry and then accept a predicted word completion with a single keystroke, thus avoiding the keystrokes that would have been required to type the complete data entry. For example, a word prediction system may be configured to recognize a user's name so that the user's complete name, “Dean Hachamovitch” for instance, may be predicted after the user types the first few letters, “Dea” in this example.
Creating word prediction systems that exhibit acceptable memory-use and performance characteristics, and that are not overly disruptive or annoying to the user, is an on-going challenge for software developers. Three techniques have traditionally been used to meet this challenge: (1) organizing the user's document into structured fields; (2) restricting the data space used to predict word completions; and (3) requiring the user to request a word prediction when desired. As the drawbacks associated with each of these techniques are described below, it will become clear that there is a continuing need for word prediction systems that automatically predict unrestricted word completions for data entries in an unstructured portion of a data file, such as the body of a word processing document or e-mail message.
Because there are a limited number of words available in any given language, many of the words forming the vocabulary of the language are used frequently. This is particularly true for data files that include structured fields for certain data entries, such as the “from” and “to” fields of an e-mail message, or the “payee” and “amount” fields of a bank check. A structured field supplies a context for data to be entered into the field. This context can be used to limit the choice of word predictions for the field, and increase the likelihood that a suggested word completion is correct. Word prediction systems therefore work well for structured data fields because the choice of words used in a particular structured field can often be sufficiently limited so that the word prediction system can offer reasonably likely suggestions within acceptable memory-use and performance characteristics.
Most-recently-used (MRU) text completion has been deployed in connection with structured data fields to speed text entry and also serve as a memory aid for repetitive data entries. These word prediction methods use an MRU data entry list for each structured field to provide a list of word prediction choices for the field. That is, a list of the most recent items entered into the structured field is used to suggest word completions for partial data entries entered into the field. For example, a personal finance program may maintain a record of a person's previous bank checks. In order to speed entry of the check payee on a new check, the program keeps an MRU list of prior check payees. This list is used to automatically suggest a completion for the payee name after the first few letters of the payee have been typed by the user. For instance, if a user has previously written checks to “Georgia Power,” the complete data entry “Georgia Power” may be suggested after the letters “Ge” have been typed into the check payee field.
In MRU word prediction systems, an input character may be analyzed, with respect to the prior history of text entered, to predict the text likely to follow the input character or string of characters. Because MRU word prediction systems are based upon a prior history of text entered, the search time and amount of storage required for the systems are important parameters. Either a linear or a binary search is typically used to scan the text history in order to provide a text prediction. A linear search operates by sequentially examining each element in a list until the target element is found or the list has been completely processed. Because every entry must be analyzed, linear searches are primarily used with very short lists.
A binary search locates an item by repeatedly dividing an ordered list in half and searching the half that it is known to contain the item. This requires a value for the input that can be compared against values in a list of items arranged in a known sequence, such as ascending numerical order corresponding to alphabetical placement. The binary search begins by comparing the input value against the value in the middle of the list. If the input value is greater than the middle value, the lower half of the list is discarded and the search concentrates on the upper half. The input value is again compared with a value in the middle of the new list and again half of the list is discarded. The process continues, with the input value being compared against the middle of each succeeding smaller list, until the desired item is found.
Both linear and binary searches can require substantial time to complete, particularly for large search lists. MRU word prediction systems therefore tend to be costly in terms of computation resources and performance. Also, without a mechanism for increasing the likelihood of making a correct prediction, such as structured fields in the input data file, the word prediction system may make wrong predictions so often that the system may be perceived as more annoying than useful. For this reason, MRU word prediction systems have typically been deployed in connection with structured fields.
Restricting the search field using a limited word prediction data space, such as a known data range or naming syntax, is another approach to improving the performance of a word prediction system. For example, a spreadsheet program may use the data entries in adjacent rows and columns as a limited data space list for selecting word prediction choices when the user is entering a new heading into the spreadsheet. Similarly, an editing program for software development may use a predefined list of valid function and command names as a limited data space for selecting word prediction choices when the user is writing a software program. Or a filing system may use the list of previously-created file names as a limited data space for selecting word prediction choices when the user is selecting a file. Of course, these limited-data-space word prediction systems only work well when there is a limited and well-defined data space to use for selecting word predictions. They are not well suited to automatic application f

Affiliated with

Also associated with

Rating

Automatic word completion system for partially entered data does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Automatic word completion system for partially entered data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automatic word completion system for partially entered data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2919288