Masterobjects, Inc. v. Microsoft Corp

Filing 15

MICROSOFT CORPORATIONS' CORRECTED ANSWER to Complaint with Jury Demand, COUNTERCLAIM against Masterobjects, Inc. byMicrosoft Corp. (Attachments: # 1 Exhibit A)(Kalay, Leeron) (Filed on 8/1/2011)

111111

United States Patent

[19]

Miller
WORD PREDICTION SYSTEM

[75]

Inventor:

[73]

Assignee: Microsoft Corporation, Redmond,
Wash.

[21]

Appl. No.: 382,074

[22]

Filed:

[56]

US005805911A

[11]

[45]

[54]

[51]
[52]
[58]

1111111111111111111111111111111111111111111111111111111111111

John W. Miller, Kirkland, Wash.

Patent Number:
Date of Patent:

5,805,911
Sep. 8, 1998

A Space-Economical Suffix Tree Construction Algorithm by
Edward M. McCreight, Xerox Palo Alto Research Center,
Palo Alto, California the Journal of the Association for
Computing Machinery, vol. 23, No.2, Apr. 1976, pp.
262-272.

Primary Examiner-Phu K. Nguyen
Attorney, Agent, or Firm-Jones & Askew, LLP

Feb. 1, 1995
6

Int. CI. ...................................................... G06F 15/00
U.S. CI. .............................................................. 395/796
Field of Search ......................... 364/419.15,419.09;
395/161, 155, 796; 3451792, 795, 797
References Cited
U.S. PATENT DOCUMENTS
4,558,302 12/1985 Welch ..................................... 340/347
4,814,746 3/1989 Miller et al. .............................. 341/95
4,955,066 9/1990 Notenboom ............................... 382/56
4,969,097 11/1990 Levin ...................................... 364/419
5,109,433 4/1992 Notenboom ............................... 382/40
5,261,091 11/1993 Yuyama .................................. 395/600
5,367,453 11/1994 Capps et al. ....................... 364/419.13

OlliER PUBLICATIONS

The Reactive Keyboard, (Table of Contents, Chapters 2, 3, 5,
and 6 submitted), by John J. Darragh, Dept. of Computer
Science, University of Calgary, Alberta, Canada and Ian H.
Witten, Department of Computer Science, University of
Waikato,Hamilton, New Zealand, Cambridge University
Press 1992.
Implementation of the Substring Test by Hashing, by Malcolm C. Harrison, New York University the Communications of the ACM, Dec. 1971, vol. 14, No. 12.

~

I

CONTROL

[57]

ABSTRACT

A computer-implemented method of providing and selecting
multiple text prediction from text entered from multiple
windows of a computer system using an applicationindependent text prediction system. Applicationindependence is the ability to work with many different
applications without being customized for each applications.
Because different prediction methods are appropriate for
different applications, multiple prediction components
called "prediction modules" provide text predictions based
on each prediction module's prediction method from which
the best prediction may be displayed. The best prediction
from the results of the multiple methods may be displayed.
In accordance with providing multiple predictions from
various modules, a method is provided for choosing which
modules' predictions should be used from the set of possibly
contradictory predictions. Each prediction module produces
a weighted list of predictions. The prediction module
weights are based on the prediction modules' estimation of
the probability that the completion text will be entered by the
user. The resulting best prediction or predictions with the
greatest weights may then be presented to the user.
22 Claims, 15 Drawing Sheets

SHIFT

19

17

u.s.

Patent

Sep. 8, 1998

5,805,911

Sheet 1 of 15

1\10
14
~

.. I

/

I

I

.

/

II

Pred~l

15~

(

1
34

18

35

16

1111111111111111111111
SIDFT

I

I

CONTROL

19

17

u.s.

Patent

Sep. 8, 1998

5,805,911

Sheet 2 of 15

12)

,-- - -- ---___ L_ -- ----

--l

22

CENTRAL PROCESSING
UNIT

24

BUS

MEMORY UNIT

20

26

INPUT/OUTPUT
PORTS

I
I

I
I
- I

I

I

I

I

I

L ________________________ ..J

2
I

u.s.

Patent

Sep. 8, 1998

°7

r-..

APPLICATION

APPLICA TION

3

36)

t

5,805,911

Sheet 3 of 15

32

31

APPLICA TION

~
~

h

GRAPHICAL WINDOWING
SYSTEM

FORMS PACKAGE

------ \--------------

\------

34

-

PREDICTOR
SYSTEM

40~

WINDOWS-TOFORMS PACKAGE

\46

~

42

PREDICTION MODULE MANAGER

t
MOST
FREQUENTLY
USED
PREDICTION
MODULE

43)

-

r
IN FORMA TION
RETRIEVAL
MODULE

44

,......

ATTRIBUTE
CORRELATOR
PREDICTION
MODULE

47~
BEST MATCH
PREDICTION
MODULE

440-~

MOST RECENTLY
USED PREDICTION
MODULE

DICTIONARY
PREDICTION
MODULE

4sJ
44b

u.s.

Patent

Sep. 8, 1998

5,805,911

Sheet 4 of 15

c
)

35

FIELD 1

TO:

I

FIELD 2

FROM:

I JOHNDOE

~

RE:

I

JMILLER

I

I

JMILLER

FIELD 3

FIELD 10

-""

--'" CC:

JANEDOE

35J

J

35

~5

u.s.

Patent

Sep. 8, 1998

5,805,911

Sheet 5 of 15
PREDICTION LIST

NUMBER OF
CORRECT
PREDICTIONS

67

J

NUMBER OF
PREDICTION ATTEMPTS

FIELD 1

4

8

FIELD 2

3

7

1

1

•

•
•
•
FIELD 10

6

~

RECENTLY USED
FIELD ID #'S
7

5

3
6

~.

I

4

}5

9

LIj-

8
10

BEST PREDICTION FIELD PAIRS_

6 :3

V

SELECTED
FIELD ID #

BEST PREDICTION
FIELD ID # FOR
SELECTED FIELD

1

1

2

2

3

3

4

1

5

5

6

6

7

7

8

8

9

9

10

3

u.s. Patent

Sep. 8, 1998

5,805,911

Sheet 6 of 15

52

50

(
0

RECORD

RECORD

RECORD

RECORD

1

RECORD

RECORD

RECORD

RECORD

2

RECORD

RECORD

RECORD

RECORD

RECORD

RECORD

RECORD

RECORD

RECORD

RECORD (3)

HASHED
INPUT

CHARACTER
SEQUENCE

3

56

•
•
•
N

RECORD

RECORD

52

{54

I# IsIu Ii Ie I Is Ie I. I. Is I Is IeIaIs Ih IeI. I. Is I
fz
1

2

3

4

5

6

7

8

9

10

11

12

13

---.D. ·

I

14

Uj1

15

7

16

17

18

19

20

21

22

u.s.

Patent

Sep. 8, 1998

UPDATE AUXILIARY
DATABASE FOR
INFORMA TION
RETRIEVAL MODULE

822

824;

841

DISPLAY PREDICTION
IN LIGHTER SHADE
THAN INPUT TEXT

GET TEXT
PREDICTIONS FROM
INFORMATION
RETRIEV AL MODULE

SHIFT
KEY OR
MORE

GET TEXT PREDICTION
FROM DICTIONARY
MODULE

826

5,805,911

Sheet 7 of 15

828

85'2J

GET PREDICTION
FROM MOST
FREQUENTLY USED
MODULE

DISPLAY
CHARACTERS
IN BLACK
TEXT

830
GET TEXT PREDICTION
FROM ATTRIBUTE
CORRELATOR MODULE

MOVE CURSOR TO END
OF SELECTION

DETERMINE BEST
PREDICTIONS
FROM MODULES
USING WEIGHTED
BELIEF FACTORS

854

I
~

832

H*/
_

B

u.s.

Patent

Sep. 8, 1998

5,805,911

Sheet 8 of 15

1--------------------------1

\902

r

912

LOOK IN LIST OF FIELD
ID PAIRS AND FIND THE
MOST RECENT PAIR
WHICH BEGINS WITH THE
CURRENT FIELD ID

IF THE FIELD OF
ENTRY CHANGES,
RECORD THE NEW FIELD
ID # IN A LIST OF
RECENTLY USED FIELDS

914)

904)

I
I
I

I

I
t

I

I
I
I
I

ACCESS LIST TO FIND
THE MOST RECENTLY
USED FIELDS

QUERY THE BEST MATCH
MODULE WITH
THE SECOND ID IN THE
PAIR

(,916

t

I

QUERY THE BEST MATCH
MODULE FOR EACH FIELD
LISTED

IF NO MATCH FOUND
QUERY OTHER PAIRS IN
LIST UNTIL PREDICTION
FOUND

t

I
I
I
I
I
I

I
t

I
t

I
t

I

918l

DETERMINE THE FIELD
WITH THE HIGHEST
BELIEF FACTOR
RETURNED BY THE BESTMATCH MODULE

9 08~

I
I

I
I

('906

I
I

I

RETURN BEST MATCH
FOR SECOND ID AS
PREDICTION

-

,

I

I
I
t

I
I
I
I
I
I
I
t

I
I
t

STORE IN A FIELD PAIR
LIST THE CURRENT FIELD
ID # WITH THE FIELD
CONTAINING THE
HIGHEST BELIEF FACTOR

CONTINUE

,------------------------5---t

910

I
I

I

J

~L·

I

1rLL/
~

I

9A

830

u.s.

Patent

Sep. 8, 1998

5,805,911

Sheet 9 of 15

~---------------------------l

I

\

I
I
I
I
I
I
I

I
I
I

I

902

(

04~

I

LOOK IN LIST OF FIELD ID
P AIRS AND FIND PAIR
WHICH OCCURS MOST
WHICH BEGINS WITH THE
CURRENT FIELD ID

IF THE FIELD OF ENTRY
CHANGES, RECORD THE
NEW FIELD ID # IN LIST
OF RECENTLY USED
FIELDS
9

912b

914)

I
I

I
I

ACCESS LIST TO FIND THE
MOST RECENTLY USED
FIELDS

I
I
I
I

I
I
I
I
I

QUERY THE BEST MATCH
MODULE WITH THE
SECOND ID IN THE PAIR

(906
[916
QUERY THE BEST MATCH
MODULE FOR EACH FIELD
LISTED

IF NO MATCH FOUND
QUERY OTHER PAIRS IN
LIST UNTIL PREDICTION
FOUND

I

I
I
I

I
I
I
I
I

I
I
I
I
I

I
I
I
I

DETERMINE THE FIELD
WITH THE HIGHEST
BELIEF FACTOR
RETURNED BY THE BESTMATCH MODULE

908

0

9 18 )
RETURN BEST MATCH
FOR SECOND ID AS
PREDICTION

1

STORE IN A FIELD PAIR
LIST THE CURRENT FIELD
ID # WITH THE FIELD
CONT AINING THE
HIGHEST BELIEF FACTOR

CONTINUE

910

L - - __ : ]_______________________ J
830

u.s.

Patent

Sep. 8, 1998

Sheet 10 of 15

5,805,911

r------------I

I
I

RECEIVE PREDICTION
BELIEF FACTOR FROM
EACH PREDICTION
MODULE FOR CURRENT
PREDICTION

I

1002

l-----J

ACCESS LIST OF
SUCCESSFUL
PREDICTIONS AND
NUMBER OF PREDICTION
ATTEMPTS FOR THE
CURRENT FIELD OF
ENTRY

REWEIGH THE BELIEF
FACTOR BASED ON THE
RATIO OF SUCCESSFUL
PREDICTIONS TO NUMBER
OF PREDICTION
ATTEMPTS

~

1004

1006

~

1008)
PROVIDE BEST
PREDICTIONS FOR
DISPLAY

DETERMINE WHICH
PREDICTIONS HAVE THE
HIGHEST BELIEF
FACTORS

Ir

RETURN REWEIGHED
BELIEF FACTORS FOR
PREDICTION IN ORDER OF
DECREASING BELIEF

I

CONTINUE

f----

1
'------_ _---Ir / \}

I
L ____ )

(

_______ _

__ _

1010

__ _

I
I

-I;--~"---Uz-· 10
---)

9 32

I

--=r

I

_ _ _ _ _ _ _ _ _ _ _ _ ...1

u.s.

,-

Patent
- -

- -

-

Sep. 8, 1998

-

--

-

-

-

-

-

5,805,911

Sheet 11 of 15

- - - -

-

-

-

-

-

-

-

-

-

-

-

-

-

- --..,

MATCH LENGTH <
mSTORY LENGTH?

NO

1110

1124

1112

CALCULATE HASH VALUE
FOR MOST RECENT
OCCURRENCE OF
CHARACTER SEQUENCE

INCREMENT MATCH
LENGTH

1114

1130

CALCULATE HASH VALUE
FOR CURRENT CHARACTER
SEQUENCE

LONGER
MATCH AT MOST
RECENT OCCURRENCE
POSITION?

1116
DETERMINE WHETHER
POSITION STORED IN
DATABASE REPRESENTS
FIRST OCCURRENCE OF
CURRENT CHARACTER
SEQUENCE

STORE POSITION OF THE
MATCH FOR THE MOST
RECENT OCCURRENCE HASH
VALUE

UPDATE CURRENT
CHARACTER HASH VALUE
FOR THE LONGER MATCH

NO

I

I

I
I
I

I
I

1132

I

1118

FIRST

1

1120
FIRST OCCURRENCE
POSITION OR POSITION
FOR A NEW lWDATED
SEQUENCE?

1- _______________________

-----------------~

I
I

I
I

I
I

~.

I

:~822

....J

ill

Uj-

u.s.

Patent

Sep. 8, 1998

5,805,911

Sheet 12 of 15

r - - - - - - - -- - - - - - - - - - - - - - - - - - - - - -

- - - - -

I

INPUT CHARACTER SEQUENCE

1

"I

1

I

I
I
MATCH LENGTH = 1

1
1

I
I

1224

1210

1

1
1

I

MATCH LENGTH < INPUT
TEXT LENGTH?

NO

1
1

INCREMENT MATCH
LENGTH

1

I

1214

I
1

12:30

1
1

CALCULATE HASH VALUE
FOR CURRENT CHARACTER
SEQUENCE

I

LONGER MATCH
AT MOST RECENT
OCCURRENCE
POSITION?

1

I
1

I

I
DETERMINE WHETHER
POSITION STORED IN
DATABASE REPRESENTS
FIRST OCCURRENCE OF
CURRENT CHARACTER
SEQUENCE

YES

1232

1
1

I
UPDATE CURRENT
CHARACTER HASH
VALUE FOR THE
LONGER MATCH

1
1
1
1

1

1216

1
1

I FIRST

I
1
1

I
FIRST OCCURRENCE
POSITION OR POSITION
FOR A NEW UPDATED
SEQUENCE?

1

UPDATE

1222

1223

I
1

1220

1

I
I
1

1

RETURN STORED POSITION
FOR PREVIOUS UPDATE OF
CURRENT SEARCH INPUT

PROVIDE CHARACTERS
FOLLOWING STORED
POSITION OF STEP 822
AS PREDICTION

I

1
I

I
I
I
I
I
I
I

L------------------------C;-----~
824

----ffiUj '_ 1 2
I
_

u.s.

Patent

Sep. 8, 1998

5,805,911

Sheet 13 of 15

DATABASE
ADDRESS

C
, ,
, ,

-

, ,
,,
'S'
'A'
'A'
'E'
'E'
'E'
'E'
'E'
'E'
'E'
'H'
'H'
'H'
'H'
'I'

'I'
'L'
'L'
'L'
'L'
'L'
'0'
'S'
'S'

's'
's'
'S'
'S'
'S'
'S'
'U'
'2'

SEED

HASH (C, SEED)

0
5895
13685
15420
0
0
5895
0
5885
5965
11285
12175
17895
20195
0
1385
1785
18455
0
18455
0
2185
5895
12175
16625
10860
0
1385
1785
5885
11285
12765
18455
20195
0
0

HSTRING
"- "
" S"
" - SE"
" SELLS S"
"S"
"A"
"AS"
"E"
"E "
"ELLS S"
"E SE"
"EL"
"ELL"
"E S"
"H"
"HELL"
"HEL"
"HE"
"I"
"IE"
"L"
"LS S"
"LS"
"LL"
"LLS S"
"0- SELLS- S"
"S"
"SELL"
"SEL"
"S"
"s SE"
"SELLS S"
"SE"
"s S"
"U"
"2"

5885
20195
11285
10860
1690
10075
15230
18455
13210
12765
14590
1785
1385
4300
3795
1555
530
18030
5890
17635
12175
16625
19340
17895
5965
19525
5895
18890
1320
20205
13405
15420
13685
2185
10085
20560

I

Ek;'
_

13

u.s. Patent

Sep. 8, 1998

5,805,911

Sheet 14 of 15

DATABASE AT
STEP 1116 OF F1G. 11

DATABASE AT
STEP 1118 OF F1G. 11

DATABASE
ADDRESS

DATABASE
CONTENTS

DATABASE
ADDRESS

1

[1690 ]

INVALID

[1690 ]

2

2

[10085]

INVALID

[10085]

3

3

[20560]

INVALID

[20560]

4

4

[5890 ]

INVALID

[5890 ]

5

5

[18455]

INVALID

[18455]

6

6

[5885 ]

INVALID

[5885 ]

7

7

[5895 ]

INVALID

[5895 ]

8

ITERATIONS
OF STEPS
1116 AND 1118

DATABASE
CONTENTS

8

[18455]

6

[18455]

9

9-

[13685]

INVALID

[17635]

6

10

[12175]

INVALID

[12175]

10

11

[12175]

10

[12175]

11

12

[17895]

8

[1785 ]

10

13

[5895 ]

8

[ 5895 ]

12

14

[19340]

INVALID

[20195]

8

15

[5885 ]

7

[5885 ]

13

16

[20205]

INVALID

[13210]

7

17

[5895 ]

12

[5895 ]

14

18

[20195]

8

[19340]

12

19

[2185 ]

INVALID

[4300 ]

8

20

[18455]

9

[18455 ]

15

21

[13405]

INVALID

[14590 ]

9
-

22

[10075]

INVALID

[10075 ]

23

[5895 ]

14

[5895

]

17

24

[15230]

INVALID

[20195 ]

14

25

[3795 ]

INVALID

[3795

]

18

[18455 ]

19

16

26

[18455]

15

27

[18030]

INVALID

[13685 ]

15

28

[12175]

11

[12175 ]

20

29

[1785 ]

10

[17895 ]

11

30

[530

INVALID

[1320

]

10

31

[12175 ]

20

[12175]

21

32

[17895 ]

11

[1785

]

20

33

[1555

]

INVALID

[18890 ]

11

34

[5895

]

11

[5895 ]

22

]

JliUj'_14
I

u.s.

Patent

Sep. 8, 1998

Sheet 15 of 15

5,805,911

1510

WINDOW 2

WINDOW 1 OR
WINDOW 2

WINDOW 1

1514

1512

CALCULATE DATABASE
ADDRESSES SPECIFIC TO
WINDOW 1 FOR
CHARACTER SEQUENCE
POSITIONS IN HISTORY
ARRAY

CALCULA TE DATABASE
ADPRESSES SPECIFIC TO
WINDOW 2 FOR
CHARACTER SEQUENCE
POSITIONS IN HISTORY
ARRAY

1515
1513

PROVIDE WINDOW
SPECIFIC PREDICTION
BASED ON WINDOW 1
DATABASE ADDRESSES

PROVIDE WINDOW
SPECIFIC PREDICTION
BASED ON WINDOW 2
DAT ABASE ADDRESSES

CONTINUE

1516

5,805,911
1

2

systems either a linear or a binary search is used to scan the
text history in order to provide a text prediction. A linear
TECHNI CAL FIELD
search operates by sequentially examining each element in
a list until the target element is found or the list has been
The present invention relates generally to the field of 5 completely processed. Linear searches are primarily used
communication aids and more particularly to the field of
with very short lists. A binary search locates an item by
computer implemented word prediction systems.
repeatedly dividing an ordered list in half and searching the
half that it is known to contain the item. A binary search
BACKGROUND OF THE INVENTION
requires a value for the input that can be compared against
General purpose digital computers are widely used for 10 values in a list of items arranged in a known sequence, such
as ascending order. The binary search begins by comparing
text based communications including word processing and
the input value against the value in the middle of the list. If
electronic mail. Text is generally entered into the computer
the input value is greater than the middle value, the lower
by means of a keyboard. Other text input devices include a
half of the list is discarded and the search concentrates on the
touch-sensitive screen overlaid on top of a graphical image
of a keyboard, or a system which detects the motion of a pen 15 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
in combination with handwriting recognition software. The
discarded. The process continues, with the input value being
text is then sent to a particular software application running
compared against the middle of each succeeding smaller list,
on the computer.
until the desired item is found.
Typically, a computer system effectively allows for mulIn using either of these search methods, the time required
tiple applications to be running simultaneously. These appli _ 20
for a prediction can become substantial. Also, without
cations appear in different portions of the screen (called
special provisions for storage of various strings of the text,
windows), with usually only one window or field of entry at
the search time required can also become substantial as
a time receiving text input. Regardless of the input method
searches of repeated substrings may be duplicated.
used, the speed at which text can be entered into a computer
25
is a factor in effective and efficient use of the computer.
The computer programs discussed above are generally
application-dependent programs, in that, the programs have
Because there are a limited number of words available in
been customized to work only with a particular application.
any given language, many of the words forming the vocabuApplication-dependent prediction can cause wasteful dupli1ary of the given language are used frequently. Recognizing
cations. Duplication of software occurs when similar prethat various patterns of language or words are repeated,
computer systems have been devised which complete text, 30 diction programs are implemented by several different applications. Duplication of memory can also be a problem. For
based on the prior history of text entered.
example, it can be wasteful to have several different appliDefault text completion is a feature of a user interface
cations keep separate histories of commonly used words.
which offers simple shortcuts for entering very common
Another problem with application independent modeling is
input. These shortcuts speed text entry and also serve as a
memory aid. For example, most recently used (MRU) lists 35 that since the prediction processes do not take advantage of
text input into other applications, there are common repetiare utilized in text completion applications. The MRU list
tive patterns of text input which are not used to improve
gives a menu of recently used names or files so that they can
prediction.
be quickly opened without retyping the name. The list of
Thus, there is a need in the art for a text prediction system
possible completions can be viewed as predictions of likely 40
that may operate with multiple applications with little or no
text input. Additionally, some computer programs complete
application specific programming and that provides a fast
input text based on a record of prior words entered. For
search method for text in a text history array.
example, some personal finance programs maintain a record
of a person's bank deposits and checks written. In order to
SUMMARY OF THE INVENTION
speed entry of the information on a bank check, the program 45
keeps a list of check payees. This list is used to complete the
Generally, the present invention is an applicationpayee name automatically after the first few letters of the
independent text prediction system. Generally, applicationpayee have been typed by the user. Such word prediction
independence is the ability to work with many different
systems have been particularly used in computer systems in
applications without being customized for each application.
which there are a limited number of selected terms that may 50 Because different prediction methods are appropriate for
be predicted.
different applications (such as MRU lists, English
In addition to MRU prediction mechanisms, other text
Dictionaries, etc.), the present invention allows for multiple
completion mechanisms may include: English dictionaries
prediction components called "prediction modules" to provide text predictions based on each prediction module's
and custom dictionaries such as a list of city names. With a
dictionary prediction mechanism, the information contained 55 prediction method from which the best prediction may be
displayed. For example, a "dictionary prediction module"
within the dictionary does not generally change based on
may provide a prediction method which finds the most
text that has been entered within the computer system. The
common word or words which complete the currently
dictionary prediction mechanism provides predictions based
entered prefix, whereas a MRU list may provide a prediction
on the originally supplied information or on information that
may be provided during periodic updates of the dictionary. 60 list based on the most recently entered text that matches the
input sequence. Thus, the best prediction from the results of
In word prediction systems, an input character may be
the two methods may be displayed. Thus, the present invenanalyzed, with respect to the prior history of text entered, to
tion allows multiple prediction modules to work together to
predict the text likely to follow the input character or
efficiently produce predictions for presentation to the comsubstring of characters entered. Because word prediction
systems are based upon a prior history of text entered, the 65 puter user.
One of the multiple prediction modules provided by the
search time and amount of storage required for the systems
are important parameters. For some of these word prediction
present invention enables text provided with a field of entry

WORD PREDICTION SYSTEM

5,805,911

3

4

of one application to be utilized for text prediction in a
prediction, a user may not be overly distracted by the text
different field of entry of another application. For example,
predictions during typing.
an electronic mail (email) application might maintain a list
Another aspect of the present invention provides for
of commonly used email names. This list can be installed
efficient use of memory among the various prediction modinto the system as a prediction module so that whenever the 5 ules. The different prediction modules are able to efficiently
prefix to an email name is entered, the prediction module is
access a common history of user input so that there is not
able to predict the full name. Although this email prediction
wasteful duplication of history information between differmodule would be primarily of use within the mail
ent prediction modules. A prediction module termed, "the
application, if another application has a text window where
information retrieval prediction module", is used to help
email names are commonly entered (such as an application 10
efficiently store text in and retrieve text from a common
for scheduling meetings), the prediction module manager
input text history array. Rather than have each prediction
will find that the email name prediction module has been
module keep a separate history, each prediction module can
successful at predicting text for these window scheduling
make queries to the information retrieval prediction module
programs. Thus, the prediction module manager will begin
to find and read locations in the history array. The informato use text predictions from the email name prediction 15
tion retrieval prediction module implements a "best match
module within that particular window of the scheduling
prediction" module that locates the longest sequence of
program window. Therefore, a prediction module designed
characters duplicated in the history array that matches the
for primary use for one application is made available to other
input sequence. The information retrieval prediction module
applications and may provide useful predictions.
also implements a "most recently used" prediction module
In accordance with providing multiple predictions from 20 that finds the most recently entered match for the input text.
various modules, the present invention provides a method
Generally described as part of the best match prediction
for choosing which modules' predictions should be used
module of the information retrieval module, the present
from the set of possibly contradictory predictions. In the
invention also provides a method of locating text within a
present invention, a "prediction module manager" keeps a
record of the prediction success of each prediction module 25 history array that has a search time that is independent of the
length of the text history array. The present invention
within each different application window where text is
provides a text storing method that enables the present
entered. Each prediction module produces a weighted list of
invention to quickly locate a match for the input character
predictions. The prediction module weights are based on the
sequence, in the history array, for which a prediction is
prediction modules' estimation of the probability that the
completion text will be entered by the user. The prediction 30 desired and displays, as the prediction, the characters following the most recent occurrence of the longest matched
module manager then adjusts these weights based on the
input character sequence up to the end of word following the
prior success of each prediction module in the current text
matched sequence.
input window of the particular application. The resulting
More particularly, the "best match prediction" module
best prediction or predictions with the greatest weights may
35 aids in storing text in a text history array in the order in
then be presented to the user as default inputs.
which the characters are input by a computer user and stores,
A general problem in implementing an applicationin a database, values that indicate the positions of various
independent prediction system with a standard keyboard
character sequences in the history array. As characters are
occurs because different applications use the keyboard and
being input and added to the history array, an address is
screen in different ways. For example, using the tab key to
indicate that a prediction should be accepted may not work 40 calculated, preferably by a hash coding technique, that is
representative of the current input character sequence and
for all applications because existing applications may
the position of the character sequence in the history array is
already use the tab key for another operation. However, in
stored at the database address calculated for the input
the preferred embodiment, the shift key is utilized as a text
character sequence.
selection mechanism. The shift key is depressed to indicate
Each time a new input character is entered, the database
that the proposed text should be entered as if it were typed 45
is queried, using the calculated address, to determine if a
in by the user. Utilizing the standard shift key alone as a text
valid position for the history array has been stored at the
selection method provides a key that typically is not used
calculated address. If a valid position for the text history
alone by an application to produce a visible result on the
array has been stored at the calculated database address, this
display monitor. The shift key selection method is differentiated from normal use of the shift key for capitalization 50 indicates that the character sequence has previously
occurred in the history array. If the character sequence has
because no other key is depressed simultaneously with the
not previously occurred in the history array, then the position
shift key. Because applications, in general, do not use the
of the character sequence is stored in the database as
shift key alone as a control signal, the shift key selection
discussed above. If the character sequence has previously
mechanism may be used for multiple applications without
control signal conflicts with the multiple applications. Also, 55 occurred, the position of the current character sequence is
stored in the database at the calculated address to replace the
because of the conventional location of the shift key, the
position that was previously stored in the database for the
shift key may be typed easily without interfering with
previous occurrence of the input sequence in the text history
normal touch typing. Depressing the conventional "control"
array.
key without pressing another key simultaneously may also
be used to select a new prediction in the same manner as the 60
Additionally, after the present invention locates the posishift key.
tion in the text history array for which the current character
Displaying predicted text on a monitor with input text can
sequence has most recently occurred, the adjacent preceding
be a distraction to a computer user. In the preferred
characters from the most recent occurrence position in the
text history array are compared against the adjacent precedembodiment, the method for displaying predicted text is to
show the prediction in light gray text following the charac- 65 ing characters of the current input characters to locate the
ters already entered by the user. By using gray or a lighter
character and the position at which the sequence does not
match. A hash database address location is calculated for the
shade of color of the input text for displaying the text

5,805,911

5

6

non-matching sequence, and the position in the text history
FIG. 4 illustrates multiple fields of entry for a computer
array of the non-matching sequence, which begins with the
application.
originally located sequence, is stored to the database at the
FIG. 5 illustrates tables used in providing text predictions.
address calculated for that sequence. By additionally updatFIG. 6 illustrates a table used in providing a text predicing the database to point to the longer character sequence 5 tion.
which did not match all of the characters of the input
FIG. 7 illustrates a database and text history array utilized
sequence at the most recent occurrence position for the input
in the preferred embodiment of the present invention.
sequence, the database is continually updated to point to
FIG. 8 illustrates a general flow diagram of the preferred
multiple character sequences that begin with the same
character or characters which enables direct addressing to 10 steps implemented in the preferred embodiment of the
present invention.
quickly locate the different character sequences. By providFIG. 9a illustrates a flow diagram of the steps impleing direct addressing to locate matching character
sequences, the search time for providing a prediction based
mented in a prediction module of the present invention.
on matching characters in a history array is fast.
FIG. 9b illustrates an alternate embodiment of the flow
In order to provide a prediction for input characters based 15 diagram of FIG. 9a.
upon the history of text entered, the present invention
FIG. 10 illustrates a flow diagram of the steps utilized in
calculates an address that is representative of the character
selecting a text prediction.
sequence, preferably by a hash coding technique as disFIG. 11 illustrates a flow diagram of the hashing functions
cussed above. The database is queried using the calculated
used in the preferred embodiment of the present invention to
hash database address, and if the character sequence has 20
update a database of character positions.
previously occurred, the most recent position in the text
FIG. 12 illustrates a flow diagram of the hashing functions
history array of the character sequence will be returned. The
used in the preferred embodiment of the present invention to
word prediction system may then display the longest match
locate a sequence of characters in a text history array.
of characters for the most recent occurrence up to the next
25
FIG. 13 illustrates a table of hash values calculated for
word.
selected character sequences.
Thus, it is an object of the present invention to provide an
FIG. 14 illustrates a table of values of changes to the
efficient word prediction system.
database as the database is being updated.
It is also an object of the present invention to use a
FIG. 15 illustrates a flow diagram illustrating the predatabase to aid in searches through a text history array.
30
ferred process of calculating addresses for multi-window
It is also an object of the present invention to quickly
applications is shown.
locate an address in the database that corresponds to the
input character sequence.
DETAILED DESCRIPTION
It is also an object of the present invention to determine
Referring to the figures, in which like numerals refer to
the longest match of input characters using a hash address- 35
like parts throughout the several views, a word prediction
ing scheme.
system made according to the preferred embodiment of the
It is also an object of the present invention to provide a
present invention is shown. Referring to FIG. 1, a word
text prediction system that operates across multiple windows
prediction system 10 is implemented with a computer 12
or field of entries of an operating system.
It is also an object of the present invention to provide 40 connected to a display monitor 14. The computer 12 receives
input data 15 from a conventional keypad 16 via an input
multiple prediction methods or modules from which a
line 17. It should be appreciated by those skilled in the art
displayed prediction may be selected.
that text entry also may be accomplished by using a touchIt is also an object of the present invention to provide a
pad or input selection device in conjunction with software
method to weight the multiple predictions from the various
45 for recognizing input signals as a character selection. Shown
prediction modules in order to aid in prediction selection.
in gray or a lighter shade of color than the input data 15 is
It is also an object of the present invention to enable text
the predicted text 18.
to be predicted for a field of entry based on text entered in
In the preferred embodiment, the predicted text 18 may be
another field of entry.
accepted when a user presses and releases the shift key 19
It is also an object of the present invention to provide a 50 of the keypad. Because the pressing and releasing of a shift
method of displaying a text prediction.
key without simultaneously pressing another key normally
It is also an object of the present invention to provide an
has no effect on an application, the shift key text selection
easily operated text selection mechanism.
method does not interfere with normal keypad input by the
These and other objects, features, and advantages of the
user.
present invention will become apparent from reading the 55
With respect to first the nomenclature of the specification,
following description in conjunction with the accompanying
the detailed description that follows is represented largely in
drawings.
terms of processes and symbolic representations of operations by conventional computer components, including a
BRIEF DESCRIPTION OF THE DRAWINGS
central processing unit (CPU) associated with a general
FIG. 1 illustrates the preferred embodiment of the word 60 purpose computer system, memory storage devices for the
prediction system of the present invention.
CPU, and connected pixel-oriented display devices. These
FIG. 2 illustrates some of the components associated with
operations include the manipulation of data bits by the CPU
the computer utilized in the preferred embodiment of the
and the maintenance of these bits within data structures
present invention.
supplied by one or more the memory storage devices. Such
FIG. 3 illustrates the subsystems of a computer system 65 data structures impose a physical organization upon the
that implements multiple windows and illustrates subcollection of data bits stored within computer memory and
systems that may be implemented in the present invention.
represent specific electrical or magnetic elements. These

5,805,911
7

8

process descriptions and symbolic representations are the
processing unit 22 may be communicated along the computer system bus 24 to input/output ports 26, for transfer to
means used by those skilled in the art of computer programdisplay monitor 14 (FIG. 1). The display monitor 14 proming and computer construction to most effectively convey
vides a visual display of input data 15 and the predicted text
teachings and discoveries to others skilled in the art.
For the purposes of this discussion, a module or process 5 18 generated from the processes implemented at the central
processing unit 22.
is generally conceived to be a sequence of computerThe following discussion of text entry in a windowing
executed steps leading to a desired result. These steps
environment is given with reference to FIG. 1, FIG. 3, and
generally require physical manipulations of physical quanFIG. 4 which shows a block diagram of the operative
tities. Usually, though not necessarily, these quantities take
10 subsystems of a text entry system in a windowing environthe form of electrical, magnetic, or optical signals capable of
ment. At any given time in the computer system, multiple
being stored, transferred, combined, compared, or otherwise
applications 30, 31, and 32 may be running simultaneously.
manipulated. It is conventional for those skilled in the art to
Generally, applications send data to a graphical windowing
refer to these signals as bits, values, elements, symbols,
system 34 to display text and graphics on the monitor 14.
characters, terms, numbers, records, files or the like. It is 15 When the user produces mouse or keyboard input, the
also conventional for such signals to be manipulated through
graphical windowing system 34 sends this information to
the use of conventional computer programs as designed
one of the applications. This application is said to have
through conventional programming techniques. It should be
focus.
kept in mind, however, that these and similar terms should
Rather than directly communicating with the windowing
be associated with appropriate physical quantities for com20 system 34, an application can instead communicate with a
puter operations, and that these terms are merely convensubsystem 36 generally known as a forms package or a
tionallabels applied to physical quantities that exist within
dialog package. The forms package 36 is a set of procedures
and during operation of the computer.
which handle the most common input-output interaction
It should also be understood that manipulations within the
with the windowing system 34. For example, the application
computer are often referred to in terms such as adding, 25 can call a procedure in the forms package that causes a
comparing, moving, etc. which are often associated with
window or field of entry 35 to be created which prompts the
manual operations performed by a human operator. The
user for text input as shown in Fig. new 4. Because the forms
operations described herein are machine operations perpackage 36 is customized for the most common types of
formed in conjunction with a human operator or user that
input tasks, the application can use a less complicated,
interacts with the computer. The machines used for perform- 30 higher level interface when communicating with the appliing the operation of the present invention, as will be
cation 30 than is available to an application 32 calling the
understood, include general purpose digital computers or
windowing system directly. The forms package 36 handles
other similar computing devices.
the low level details. For example, when a user types a"}"
Furthermore, it should be kept in mind that there is a
into a field of entry 35 within an application using the forms
distinction between the methods, steps, or operations com- 35 package 36, the forms package 36 receives notification of
pleted by a computer, and the method of computation itself.
the keypad input from the windowing system 34 and signals
The present invention relates to methods, processes, steps,
to the windowing system to display the letter "}" in a specific
or operations for a computer and the processing of electrical
location.
or other physical signals to generate desired physical signals
In addition to the subsystems of a general windowing
and to display results and interactions.
40 system, multiple predictor subsystems 40 may be utilized by
word prediction system 10 to produce the predicted text. The
In addition, it should be understood that the programs,
predictor subsystems 40 may be available to a forms packprocesses, methods, etc. described herein are not related or
age 36 to help provide text completion. Each of the sublimited to any particular computer or apparatus. Rather,
system modules 43, 44, 44a, 44b, 45 and 47 may provide
various types of general purpose machines may be used with
programs constructed in accordance with the teachings 45 text completion based on a different set of prediction rules.
Within the limits of the memory resources on the computer
described herein. Similarly, it may prove advantageous to
system, a plurality of prediction modules can be installed
construct specialized apparatus to perform the method steps
into the prediction system. When a new prediction module
described herein by way of dedicated computer systems with
hard-wired logic or programs stored in nonvolatile memory,
is installed, a prediction module manager 46 is given an
50 identifier by conventional programming techniques, as
such as read only memory.
known by those skilled in the art, which specifies how a new
Referring to FIG. 2, the hardware components of the
prediction module is to be called. When a user inputs data,
computer 12 that are utilized by the word prediction system
a forms package 36 may create a query to the prediction
10 in accordance with the present invention are illustrated.
module manager 46 to present the current state of the user
For simplicity of the drawings, many components of a
standard computer system have not been illustrated such as 55 input.
Upon receiving the user input text, each prediction modaddress buffers, memory buffers and other standard control
ule provides a prediction based on its prediction technique.
circuits because these elements are well known and illusAlong with each prediction by each prediction module, each
trated in the prior art and are not necessary for the underprediction module may provide a "belief factor" that is an
standing of the present invention. Computer programs used
to implement the various steps of the present invention are 60 estimate of the likelihood that its prediction is correct. The
belief factor is a number that increases with the increasing
generally located in the memory unit 20, and the processes
probability that a predicted word or the predicted text is
of the present invention are carried out through the use of a
correct. The manner in which the belief factor may be
central processing unit 22. The memory unit 20 and the
calculated for the various modules is discussed in more
central processing unit 22 are interconnected by a computer
system bus 24 on which digital information is exchanged 65 detail below.
The prediction module manager 46 provides the best
between computer system components. The data signals
prediction or predictions from the modules 43, 44, 44a, 44b,
resulting from the processes implemented at the central

5,805,911

9

10

45, and 47 to the windowing system for display. The form
The information retrieval module 44 maintains a text
package 36 sends instructions to the windowing system 34
history array and accesses the best match prediction module
to display the predicted text in light gray type 18 in the
44a to provide predicted text based on the longest match for
location that the text would be written if entered by the
the current input text in the text history array. Additionally,
computer user. If the computer user indicates that the 5 the information retrieval module 44 accesses the most
recently used prediction module 44b to provide the most
prediction is correct, the forms package 36 darkens the
predicted text and updates the state of the forms package 36
recently used word that matches the input sequence. For
as if the user had typed in the full predicted text.
example, if a field of entry prompts the user for a filename
and the user has entered "re" and the most recent files names
For applications which do not use forms package 36, text
completion is accomplished using the lower level informa- 10 were (in order) "rope report2 real rhymes" then the prediction is "report2" for the best match prediction module 44a
tion available from the graphical windowing system 34. A
and the prediction is "real" for the most recently used
windows-to-forms package 42, as referred to herein, is
prediction module 44b. Similarly, if the previous entry was
utilized for low level communications with the graphical
"this is a test" and the current input is "another te", then the
windowing system 34 to provide text completion for applibest match prediction module 44a of the information
cations that do not interact with a forms package 36. To the
predictor subsystems 40, programming calls from the 15 retrieval module 44 will predict "test" as the word being
entered. Preferably, successive predictions will give the best
windows-to-forms package 42 are handled in the same
prediction available excluding any predictions previously
manner as programming calls from the forms package 36.
generated by the same query to the information retrieval
The windows-to-forms package 42 takes predictions and
module 44.
instructs the windowing system to display the prediction in
the gray text 18. The windows-to-forms package 42 then 20
Because the information retrieval module 44 keeps a
history of the user text input, the other prediction modules
monitors the keypad signals to determine if the user has
indicated that the prediction is correct. When a user indicates
do not need to keep duplicate copies of the history of user
that a prediction is correct, the windows-to-forms package
input. Instead, the other prediction modules can query the
42 instructs the windowing system 34 to indicate to the
information retrieval module 44 directly to determine what
application that the predicted text has been entered.
25 has been typed in the past. To make the information retrieval
module 44 more useful for other modules, the information
When a user inputs text data, the forms package seeks a
retrieval module 44 can be queried for matches within any
prediction from the multiple prediction modules through the
field of entry from any form, not just the field of entry which
prediction module manager 46. The prediction module manis the subject of the current query. By providing a commonly
ager 46 receives the results of the predictions from each
prediction module and returns the best predictions to the 30 accessible the common text history array, each module does
not have to store a separate text history array and therefore
forms package 36. As discussed in more detail below, the
memory can be saved.
forms package 36 maintains a list that indicates the number
As noted above, each prediction module provides a belief
of correct predictions received from each prediction module
factor with each prediction. For the best match prediction
within the current field of entry, such as fields 1-10 illustrated in FIG. 4. The correct prediction list information is 35 module 44a, the belief factor returned with the prediction is
the number of characters matched, as long as a full word is
used with the "belief factor" returned by the prediction
matched. For the most recently used prediction module 44b,
modules to create an "adjusted belief factor." The adjusted
the belief factor returned with the prediction equals 1+ l/(the
belief factor provides an adjusted calculation of the probdistance back in the text history array the match occurred).
ability that a prediction from a particular prediction module
is correct for the current field of entry. The predictions are 40 The distance back in the text history array that the match
occurs can be determined by counting the number of charthen returned to the forms package 36 in order of decreasing
acters (or bytes) or words back from the last character input
adjusted belief factor. A list of the predictions may be
in the text history array.
displayed to the user or only the best prediction may be
displayed.
Unlike the information retrieval module 44, the dictionary
As noted above, multiple prediction modules may be 45 prediction module 45 does not change over time with user
input. The dictionary prediction module 45 simply looks up
provided. For example, prediction modules that may be
the current input text in a dictionary and finds all the words
provided include: a most frequently used prediction module
for which the current input is a prefix. The dictionary
43 which may provide a list of the most frequently used
prediction module 45 then orders these words by a frewords beginning with the input text; an information retrieval
prediction module 44 that includes an array of input text that 50 quency (or probability) stored with each word. The resulting
word list is returned to the prediction module manager 46 in
has been entered, a best match prediction module 44a that
sorted order with belief factors for the set of words returned.
locates the longest match in the text history array, and a most
The dictionary and the belief factors for the dictionary
recently used prediction module 44b that locates the most
module 45 can be created by taking a large corpus of
recently used word that matches the input text; a dictionary
prediction module 45 that contains an ordered and generally 55 documents of text related to the type of dictionary being
unchanging set of words; and an attribute correlator module
provided and counting the number of times each word
47 that searches other fields of entry with the current input
appeared in the text then storing the frequency count as the
text and determines which of the other fields contain words
belief factor with each corresponding word. It should be
that can provide the best predictions for the current field. It
appreciated that words not in the corpus of documents can
should be appreciated by those skilled in the art that other 60 be additionally included and certain words that appeared in
types of prediction modules may be provided and that the
the corpus of documents may be removed. Preferably, the
prediction modules discussed herein are illustrative of the
dictionary is compressed along with the log-base two of the
types that may be provided. The belief factors for each of the
number of times that each word appeared in the corpus. For
prediction modules may be calculated in different ways
example, if a word occurred 700 times, the number nine is
depending on the nature and basis of the prediction method 65 stored as the frequency count for that word since 700 occurs
utilized by the module. The operation of the various predicbetween 2 9 =512 and 210=1024. Thus, the result is a set of
tion modules are discussed below.
words with a general estimate of their frequency.

5,805,911
11

12

As noted above, the "most frequently used" prediction
computer system even if the filenames had never been typed
module 45 tracks the number of times the most common text
into a field of entry of form.
values have been typed into the current field of entry or
Because multiple predictions are returned for a given set
window. The probabilities or belief factors for these words
of text or characters, the word prediction system uses a
may be calculated by dividing the number of times that the 5 reweighting process to determine which prediction from the
predicted word appeared in a given context by the total
multiple prediction modules provides the best prediction for
number of words that occurred in the given context.
the current field of entry. The reweighting process of
Also, as noted above, the present invention also contains
returned predictions from the prediction modules are based
an attribute correlator prediction module 47. The purpose of
on prior learning or a prior record of which prediction
the attribute correlator prediction module 47 is to find other 10 modules returned predictions that were accepted by a user in
fields of entry 35 where the current input text might have
the current field of entry. The acceptance of a prediction by
been recently entered. The attribute correlator prediction
user is considered as a successful prediction.
module 47 accesses or calls the best match prediction
The preferred reweighting process, which determines
module 44a to search other fields of entry 35 with the current
which prediction to use from the multiple predictions,
input text. Within the attribute correlator prediction module
15 implements the following steps:
47, the best match prediction module 44a is used to return
W~(N/(N+1))*(S/N)+(1/(N+1))*BF
a prediction as if the current text had been typed in a field
of entry other than the current field of entry. The attribute
where W is the corrected or reweighted belief factor; BF is
correlator prediction module 47 is useful because often it is
the belief factor returned by the expert; S is the number of
the case that the current input text or word has never been 20 successful predictions that have occur ed within a predetertyped in the current field, although it has been typed in
mined range that the returned belief factor for the current
another field. For example, referring to FIG. 4, if
field of entry falls within; and N is the total number of times
"JMILLER" is entered in the "RE:" field of a mailing
that returned belief factors for the current field of entry have
program, and subsequently "JM" is entered in the "CC:"
fallen within the same range. Preferably, the predetermined
field of the same program, the attribute correlator will be 25 range of values used in determining the number of successable to predict "JMILLER" in the "CC:" field even though
ful predictions, S, and the total number of attempts, N,
"JMILLER" has not previously been entered in the "CC:"
within the predetermined range values are values separated
field.
by the powers of two from -R to +R. For example, the range
Referring to FIG. 5, the attribute correlator prediction
of values using R=5 would be: 1132, 1;16, 1fs, Y4, Y2, 1, 2, 4, 8,
module 47 uses two list of information in association with its 30 16,32. An example calculation of the corrected weight is as
method of prediction. A "recent field use" list 61 of a
follows. If the BF returned by the prediction module is 5
preselected number of the most recently used field identifi(BF=5) and there were S=2 prior successful attempts and 6
cation numbers (i.d.'s) is accessed and maintained by the
failures, out of N=8 tries with belief factors between 4 and
attribute correlator 47. When the field of entry 35 (FIG. 4)
8 (the range that BF=5 falls in) then the adjusted weight or
is changed by a user, the new field of entry 35 moved into 35 belief factor is W=(%) * (%)+(119) * 5=0.777. Note that as
is recorded in the recent field use list 61. Every time a word
N increases, W approaches SIN. FIG. 6 illustrates a table or
is entered in a field of entry 35, the most recently used field
list of prediction successes of prediction attempts within a
i.d. numbers are accessed from the recent field use list 61.
given range.
For each field i.d. in the recent field use list 61, the best
As noted above, the information retrieval module 44
match prediction module 44a provides a prediction. The 40 maintains a history array of characters that have been
field returning the highest belief factor is stored and assopreviously entered. Because many characters and combinaciated with the current field i.d. as the second field i.d in a
tions of characters may be repeated in a text history array,
"best prediction field pair" list 63. These second field i.d. of
searches through a history array using conventional search
field i.d. pairs of the pair represents the i.d. of the field that
methods, as discussed above, may be unacceptable for
generally provides the best prediction for the current field. 45 certain applications. To help reduce the time required for
When the attribute correlator prediction module 47 is
searching through a text history array, the present invention
queried for a prediction, the "best prediction field pair" list
provides an indexing or addressing scheme to provide for
63 is accessed to find the most recent pair that has the current
fast searches.
field i.d. as the first field i.d. of pair. The best match
Depending on the application for which the prediction
prediction module 44a is then queried with the second i.d. of 50 system is used, the method of displaying a text prediction
the located pair. The prediction returned using the second
may vary. As noted above, a text prediction may be disi.d. of pair is returned as the prediction for the attribute
played as the predicted completion immediately following
correlator prediction module 44a. In an alternative
the input text 15. When the predicted text immediately
embodiment, rather than using the most recent pair, the
follows the input text, the forms package 36 displays, as the
attribute correlator prediction module 47 may locate from 55 prediction, the text that has the highest prediction weight
the best prediction field pairs in the list 63 with the selected
among the prediction weights returned with each text prefield i.d. and may query the best match prediction module
diction from the prediction modules.
44a with the second i.d. in the pair which occurred most
Alternatively or in addition to displaying text at the end of
frequently in the list. Additionally, if there is no prediction
the input text, the predictions may be stored to a prediction
returned by the best match prediction module 44a, the 60 list. The prediction list may be displayed to the user in the
second most recent pair or second most frequent pair could
form of a graphical pull-down menu. The predictions are
be searched with the current first i.d. depending of the
preferably arranged in order with the most likely text
embodiment implemented.
prediction appearing first in the displayed list followed by
In addition to the modules discussed above, additional
the second most likely prediction and so on to the least likely
modules may evaluate information available on the com- 65 text prediction. The ordering of the prediction list is preferably based on the calculated weights for each text predicputer system. For example, a filename module may evaluate
tion.
the names of the files and directories available on the

5,805,911

13

14

Referring to FIG. 7, a general block diagram of a database
characters of the string equals the value that the hash
indexing or addressing process is shown which is used to
function returned from the hash operation on the subsequent
implement fast searching of a text history array 54 in
character of the string. Modulo is a function that performs a
information retrieval module 44. As part of the process when
division operation and returns the remainder of the division
text is input, the text history array 54 is updated in sequential 5 operation. For example, the value for the hash string "sel"
order to indicate the appropriate text history as shown. A
equals hash (,s', hash (,e', hash' 1',0)). The hash process is
database 50 contains address locations 52, for example, 0
repeated for each subsequent character of the sequence until
all the characters of the character sequence have been
through n, that have values that point to the positions of
operated upon to provide an appropriate pseudo random
various character sequences found in the text history array
54. It should be appreciated that the term character 10 number for the entire character sequence. Generally, different character sequences will produce different pseudo ransequence, as used herein, may refer to a single character or
dom numbers for different character sequences.
multiple characters. When the text history array 54 becomes
The resulting hash number is not truly a random number
full (i.e. the last byte of the text history array is filled), new
because the process will produce the same pseudo random
input characters are stored starting at the beginning of the
text array history 54 and thus overwrite any previous input 15 number given the same input character sequence 56.
characters in the order that the characters where input. This
Therefore, the same input character sequence 56 will be able
type of array may be termed circular.
to access the same address. The deterministic random nature
As noted above, a hashing technique is used to aid in
of the hashing function helps to save storage space because
searching for an appropriate match. In database
the input character sequence 56 does not have to be stored
management, hashing may be described as an indexing 20 with an associated value. By utilizing a hashing function
with respect to various input character sequences 56, longer
technique in which the value of a key (a character sequence
input character sequences in the text history array 54 beginas used herein) operates as a record identifier, and the key is
numerically manipulated to directly calculate either the
ning with the input character sequences can be found in an
location of its associated record in a file or the location of the
efficient manner.
In the preferred embodiment of the present invention, a
starting point for a search for the associated record. If the 25
hash function is performed on the input character sequence
key value is a character string, each possible character is
56 to obtain an address location 52 of the database 50. The
assigned a numeric code to permit the numerical manipulation. The manipulation performed on the key is known as
address location 52 contains a record that is a pointer to a
the hashing function, for example, assume two keys, CAT
position in the text history array 54 of the most recent
and MOUSE. If the characters in these words are assigned 30 occurrence of the current input character sequence. If the
numeric values by totaling the ASCII values of the letters, a
character or character sequence has not occurred in the text
formula, or hashing function, could be created that might
history array 54, the position of that input character or input
character sequence 46 is stored as the record or pointer to the
calculate a value of 1000 for CAT and a value of 1800 for
MOUSE. Based on these values, record 1000 would contain
character sequence of the history array 54. If a character
the key value CAT and record 1800 would contain the key 35 sequence has been found within the text history array 54,
value MOUSE.
additional hash operations are performed to locate the longBy utilizing hashing, the input character sequence 56 does
est match of characters corresponding to the characters
not have to be stored along with the record. Instead, when
preceding the input character sequence 56. The position of
the hash is performed on the character sequence, the numeric
the longest match of characters that correspond to the input
value determined is used as the address into the database 50. 40 character sequence 56 is returned.
Because the address space available for the database to
The address value provided from the hashing function on the
occupy is finite and the number of potential character
character sequence is preferably a pseudo random number.
Generally, the pseudo random number may be generated by
sequences or keys is infinite, a problem may arise where
multiplying the ASCII value of the first letter of the key by
multiple keys of the hashed character sequence map to the
a large number to obtain a product that is divided by another 45 same address. The mapping of input character sequences 56
large number to obtain a remainder. The remainder is the
to the same address is termed a collision problem. In order
pseudo random number of the hashing function.
to accommodate or lessen the problem of collisions of a
particular address location, a bin, as known to those skilled
If the character sequence contains more than one
in the art, is utilized at the address locations 52. A bin stores
character, the value of the pseudo random number may be
determined as follows. The pseudo random number from the 50 multiple records at that one address.
Because it is possible that different text values yield the
first hash operation is multiplied by the ASCII value of the
second character to obtain a product that is divided by the
same calculated database address, the input characters are
same large divisor from the previous hash operation to
compared to the text pointed to by the first record in the bin.
obtain a remainder. The remainder from the second hash
If the input characters do not match characters associated
operation is the pseudo random number for the two character 55 with the first record then the text value pointed to by the next
sequence. The process may be repeated for each subsequent
record in the bin is compared to determine if the characters
character of the character sequence.
match or until all records within the bin have been checked.
The preferable hash function of the preferred embodiment
Another way to distinguish text sequences which generate
the same address is to calculate "signatures" with this
of the present invention accepts two variables: a character c
and a "seed" value. The hash function utilized to obtain an 60 method, in addition to the pseudo random number generated
address location in the database 50 in the preferred embodito identify the address, another pseudo random number
called a "signature" can also be calculated for each key. As
ment of the present invention is:
known to those skilled in the art, a signature is usually
hash( c,seed)~( (c+constant X)x(seed+constant Ylmodulo constant
selected or calculated to contain fewer bytes than the actual
Z)
65 bit representation of the pseudo random number generated
as the key or address for the character sequence. Although
where the seed value equals zero for the last character of a
the addresses may be the same for a particular key, the
character sequence and where the seed of each of the other

5,805,911
15

16

signature for those keys that provide the same address may
of the input character sequence. At step 850, the user of the
system has an option of pressing and releasing the shift key
be calculated to be different. By providing signatures for
19, without pressing another input key simultaneously, to
input character sequences, four different input character
accept the word prediction or inputting another character. If
sequences may map to the same address location 52 and still
be distinguished. Thus, when a hash function is performed 5 the user presses and releases the shift key 19 at step 850, the
process proceeds to step 852 where the characters that were
on an input character sequence, the address corresponding to
previously displayed in gray text are now displayed in black
the input character sequence is located, then the bin is
as though the characters were input directly by the user. At
searched for the corresponding calculated signature. As
step 854, the cursor is moved to the end of the characters
noted above, the record points to a position in the text history
accepted by the user. The process may then proceed to step
array 54 that corresponds to the input character or input 10
802 where the prediction process of the preferred embodicharacter sequence being evaluated.
ment of the present invention is repeated as described above.
In summary, to determine whether or not a character
Referring to FIG. 9a, the processes and steps implesequence has occurred within the text history array 54, a
mented in the present invention for providing a text predichash operation is performed on an input character sequence
tion from the attribute correlator are illustrated. FIG. 9a is
which yields an address. At the address location, a determi- 15 discussed in conjunction with FIGS. 3 and 5. At step 902,
nation is made whether characters have a match in the bin.
when the field of entry is changed by a user, the field of entry
If there is a match, the record points to the location in the text
moved into is recorded in the most recently used fields list
history array 54 of the corresponding input character
61. At step 904, the most recently used field i.d. numbers are
sequence. If no match is found in the bin, then there is no
accessed from the "recent field use" list 61. At step 906, for
match for this input character sequence, and the record is set 20 each field i.d. in the "recent field use" list 61, the best match
to point to the new input characters in the array. If a bin is
prediction module 44a provides a prediction. At step 908,
full and the current record pointed to the character sequence
the field returning the highest belief factor is returned. The
is to be written in the bin, the oldest record is replaced by the
process then proceeds to step 910. At step 910, the field
current record.
returning the highest belief factor is stored and associated
In connection with the text prediction, the present inven- 25 with the current field i.d. as the second field i.d in a "best
tion utilizes a selection device that is not likely to be used by
prediction field pair" list 63 of field i.d. pairs. These second
field i.d. of the pair represents the i.d. of the field that
the various windows in which the word predictor system
operates. Referring to FIG. 1, the shift key 19 is illustrated
generally provides the best prediction for the current field.
The process then proceeds to step 912.
and operates according to the present invention to designate
selection of a word prediction. The shift key is unlike many 30
At step 912, when the attribute correlator prediction
other keys because the shift key 19 must normally be pressed
module 47 is queried for a prediction, the "best prediction
simultaneously with another keypad input to produce a
field pair" list 63 is accessed to find the most recent pair that
visible effect on the display monitor 14. Also the "control"
has the current field i.d. as the first field i.d. of pair. At step
key of a conventional keyboard may be used as the text
914, the best match prediction module 44a is then queried
selection method. Therefore, by utilizing the shift key 19 or 35 with the second i.d. of the located pair. At step 916, if no
control key as the text selector for predictions, it is less likely
match is found with the initial query, another pair that has
that a window or application would have an operation that
begins with the current i.d. is queried for prediction until the
responds only to the pressing and releasing of the shift key
list is exhausted. At step 918, the prediction returned using
19. In this manner, the text selection mechanism of the word
the second i.d. of pair is returned as the prediction for the
predictor is easy to access and is not likely to interfere with 40 attribute correlator prediction module 44a.
designated input operations allocated to specific keys on the
Referring to FIG. 9b, an alternate process for the attribute
keypad.
correlator 47 of the present invention is shown. The steps
implemented in FIG. 9b correspond to the steps impleReferring now to FIG. 8, a flow diagram illustrating the
preferred steps of the method of the present invention is
mented in FIG. 9a except that instead of searching the i.d.
illustrated. FIG. 8 will be discussed in connection with 45 pair that most recently occurs with the current i.d., the i.d.
FIGS. 1 and 3. At step 802, input data is received from
pair that occurs most which begins with the current field i.d.
keypad input from a computer user. At step 822, the inforis searched. In the process illustrated in FIG. 9b, step 912b
mation retrieval module 44 is called by the prediction
of replaces step 912 of FIG. 9a.
module manager 45 and the input data is added to the history
As noted above, the present invention provides a
array 54. The information retrieval module 44 updates, as 50 reweighting process for the belief factors returned by the
discussed in connection with FIG. 7 and 11, the database 50
prediction modules. The reweighting process is an adjusted
to point to the most recent occurrence of the input character
calculation of the probability that a prediction from a
sequence. The process then proceeds to step 824 where the
particular prediction module is correct for the current field of
information retrieval module 44 provides its text prediction
entry. Referring to FIG. 10, the reweighting process of the
based on the best match for the input character sequence or 55 present invention is illustrated. At step 1002, the predictions
the most recently used match. The process then proceeds to
are received from each prediction module. At step 1004, the
step 826 where the dictionary prediction module 46 provides
list 67 (FIG. 6) of the number of successful predictions and
its text prediction, as discussed above, for the input data. At
the number of prediction attempts for the current field of
step 828, the prediction module manager 46 calls the most
entry is accessed. The process then proceeds to step 1006
frequently used prediction module 43 to provide its text 60 where the process reweights the belief factors based on the
prediction for the current input data. At step 830, the
ratio of successful predictions to the number of predictions
attribute correlator is accessed for its text prediction. At step
attempts for the current field of entry. At step 1008, the
832, after each module has provided its prediction, the
predictions having the highest belief factors are determined
prediction module manager 46 determines the best predicand, at step 1010, the prediction having the highest
tion as discussed above.
65 reweighted belief factors are returned in order of decreasing
The process then proceeds to step 841 where the character
belief. At step 1012, the best prediction or predictions are
prediction is displayed in gray text following the black text
provided for display.

5,805,911
17

18

Referring to FIG. 11, the processes implemented in the
preferred embodiment of the present invention for updating
the database 50 to point to character sequences in the text
history array 54 is shown. Before any text processing has
occurred, the database is initialized to values (invalid
positions) that are not contained in the history array 54, such
a negative position value. At step 1102, a variable match
length, length, is set to 1. The match length variable provides
a count for the number of characters that match the current
character sequence as compared to the most recent occurrence of the character sequence in the history array 54. At
step 1104, the input character sequence is provided by a
computer user. At step 1110, a determination is made as to
whether the match length is less than the history length. If
the match length is not less than the history length, then at
step 1110 the process returns to step 1102. If, however, at
step 1110, the match length is not less the length of the
history array then the process proceeds to step 1112 where
the hash value is calculated for the most recent occurrence
of the character sequence. As noted above, the hash value is
determined according to the hash equation (1). The character
c of the hash function (1) may be represented by h[ x], where
h is the history array 54 and x represents a position variable
for a character in the history array 54, so that h[ x] represents
the character in the history array 54 at position x. The hash
function implemented to calculate the most recent occurrence hash value (MRORV) is:

If, at step 1120, the position is not valid and thus is the first
occurrence of character sequence then the process returns to
step 1102 where processing may begin for an additional
input character as discussed above. If, however, the position
stored for the current character sequence has occurred in the
history array then the process proceeds to step 1124 where
further processing of the current sequence will yield an
updated database value to point to a longer non-matching
sequence that occurred prior to the current sequence but
which begins with currently processed character sequence.
At step 1124, the match length, mlength, is incremented
by 1. At step 1130, the next character looking back mlength
characters from the current character sequence in the history
array is compared to the character at the most recent
occurrence position looking back in the history array
mlength characters. If the character at the most recent
occurrence position matches looking back in the history
array mlength characters, then the current character hash
value eeRV is updated according to the hash function (3)
above. The process then proceeds to step 1124. If, at step
1130, the character at the most recent occurrence position
did not match looking back in the history array mlength
characters, the process proceeds to step 1110.
Referring to FIG. 12, the processes implemented in the
preferred embodiment of the present invention for finding a
character sequence in the history array is shown. The
processes implemented for finding are similar to the processes implemented in the database updating process discussed in connection with FIG. 11, however, steps 1104,
1112 and 1118 are omitted and the text history length is
replaced with a short string input from a particular window.
At step 1201, a character string is received from a window
or field of entry. At step 1202, a variable match length,
mlength, is set to 1. The match length variable provides a
count for the number of characters that match the character
sequence as compared to the most recent occurrence of the
character sequence in the text history array 54. At step 1210,
a determination is made as to whether the match length is
less than the history length. If the match length is not less
than the history length, then at step 1210 the process returns
to step 1202.
If, however, at step 1210, the match length is less than the
history length the hash value for the current character
sequence is calculated at step 1214. The hash function
implemented to calculate the hash value for the current
character sequence is:

MROHV~Hash(h[posMRO-mlength],

CCHV)

CCHV)

10

15

20

25

(2)

where posMRO is the position number of the most recent
occurrence of the character sequence and the seed, eeRV,
is the current character sequence hash value. When the input
character is first received at step 1104 the eeRV value is set
to zero and posMRO is set to equal the length of the history
array. Also, if the character sequence has not previously
occurred, the MRORV value is also the hash value for the
current sequence. After the hash value is calculated for the
most recent occurrence of the character sequence, the hash
value for the current character sequence is calculated at step
1114. The hash function implemented to calculate the hash
value for the current character sequence is:
CCHV~Hash(h[hlength-mlength],

5

30

35

40

(3)

where hlength is the length of the history array (i.e. the
number of characters in the history array). The process then
proceeds to step 1116.
At step 1116, the database is accessed to get the history
array position value for the current character sequence hash
value eeRy. An invalid position will be returned at step
1116 if the character sequence has not occurred (i.e., the first
occurrence of the character sequence in the history array) or
valid position, if the sequence is located in the history array,
will be returned at step 1116. The process then proceeds to
step 1118 where the position of the match for the most recent
occurrence of the character sequence is stored in the database at the MRORV location of the database. By storing this
occurrence of the character sequence, subsequent accesses
of the database using the hash value for the sequence will
point to the most recent occurrence position in the history
array. At step 1120, a determination is made as to whether
the stored database position obtained from step 1116 is the
first occurrence of the character sequence (i.e., an invalid
position). If the position is valid then the character sequence
has been previously input in the history array and thus a
valid position pointer for history array is stored at the eeRV
location in the database.

45

CCHV~Hash(h[ alength-mlength],

50

55

60

65

CCHV)

(4)

where alength is the length of the character string. The
process then proceeds to step 1216. At step 1216, the
database is accessed to get the history array position value
for the current character sequence hash value eeRy. An
invalid position will be returned at step 1216 if the character
sequence has not occurred or a valid position, where the
sequence is located in the history array, will be returned at
step 1216. The process then proceeds to step 1220. At step
1220, a determination is made as to whether the stored
database position obtained from step 1216 is the first occurrence of the character sequence (i.e. an invalid position).
That is, has the character sequence been previously input in
the history array and thus a valid position pointer for history
array is stored at the eeRV location in the database. If, at
step 1220, the position is not valid and thus is the first
occurrence of character sequence then the process returns to
step 1222 where the stored position for the previous update
for the current search process is returned. If there has been
a previous update step then the position for that update step

5,805,911

19

20

represents the last matching position and thus will be
be made to ensure that the match of characters is not longer
returned as the prediction. If, however, the position stored
than the maximum match length. Because the history array
for the current character sequence has occurred in the history
is a circular buffer, when the end of the history is reached,
the maximum match length number of characters should be
array then the process proceeds to step 1224 where further
processing of the current sequence will yield an updated 5 copied to the beginning of the history array. As known to
database value to point to a longer sequence beginning with
those skilled in the art, by using this technique no special
currently processed character sequence.
case is required during matching for patterns which start
near the end of the history array and continue at the start of
At step 1224, the match length, mlength, is incremented
by 1. At step 1230, the next character, looking back mlength
the history array.
characters from the current character sequence in the history 10
Referring to FIG. 11, at step 1102, mlength (the match
length) is initialized to 1. At step 1104, the input character
array 54, is compared to the character at the most recent
occurrence position looking back in the history array
'#' is added to the text history array 54 at position 1. At this
mlength characters. If the character at the most recent
point in the process, the current length of the text history
occurrence position matches looking back in the history
array 54 is 1 and the mlength is also 1, so at step 1110, the
array mlength characters, then the current character hash 15 process returns to step 1102. As before, at step 1102, the
mlength is initialized to 1. The new input character'S' is
value CCHV is updated according to the hash function (3)
above. The process then proceeds to step 1224. If, at step
added to the text history array 54 at position 2 and hlength
1230, the character at the most recent occurrence position
is incremented to 2. At this point in process mlength=1 is
did not match looking back in the history array mlength
less than the history array length hlength=2. The process
characters, the process proceeds to step 1210.
20 then proceeds to step 1112.
The processes of the present invention are discussed
At step 1112, the hash value for the most recent occurbelow in connection with specific examples. As noted above
rence (MROHV) of the current character sequence is genthe information retrieval module 44 updates a database 50
erated which is a signature of the character sequence of
and locates character sequences in a historic array 54. The
length 1 starting at position 2 in the text history array 54:
information retrieval module 44 finds the position of the 25 "S". Because the position of the most recent occurrence
longest ending match of a short string A from a long history
(posMRO) is initially set to equal the hlength, at step 1114,
H. An ending match is a sequence of adjacent characters
the characters hashed in step 1112 are the same as the
which occurs in both H and A (ignoring differences in case)
characters hashed in step 1114 and thus, the hash value for
and which includes the last character in A. For example
the current character sequence (CCHV) has the same sigH="Suzie sells seashells by the seashore" and A="what does 30 nature as generated in step 1112. In this example, the
Suzie s." In this example, H and A have a match sequence
signatures are calculated according to the hash function (1)
of: "s" at positions 1,7,11,13,16,21,30, and 33; " s" at
above with specific values substituted for the constants as
positions 7, 13, and 30; "e s" at positions 7 and 30; and "ie
follows:
s" at position 7 only. The longest match is thus at position
hash(c, seed)~((c+3297)x(seed+43985)modulo 20945)
35
7.
An example implementing the method of the present
where the character c is the ASCII representation of the
invention for processing a text history array so that longest
character c as an integer.
matches can be determined is discussed below. As noted
Referring to FIG. 13, a table of hash values generated by
above, the processes of the present invention maintain a
the processes of the present invention for the character
database of values which are used to aid in searches though 40 sequences processed in this example is shown. Because all
a history array of text. The time required to find the longest
non-zero seeds are generated by the result of another calculation of "hash(c, previously calculated_seed)", a relamatch is proportional to the length of the match. In contrast
to other methods for find the longest match which have been
tionship exist between the different seeds which is shown by
used for prediction, the time required to the update database
the hash string (hstring). For example, the third row of the
when H is appended to is very fast. If a character is added 45 table in FIG. 13 shows hash(, _', 13685)=11285. The charto the end of H to create a string H', the time required to
acter "_" is used here instead of the space character for
update the database for efficient lookup of H' is proportional
illustration purposes. The hstring of "_se" indicates 11285=
to the match length, mlength, of the longest ending match of
hash(, _' ,hash(,s' ,hash(,e' ,0))).
H with H'. A method of processing a history array so that
Referring again to step 1112, the signature for "s" is given
longest matches can be determined is discussed below in 50 to be 1690. MROHV and CCHV are now both 1690. The
CCHV signature is used to query the database 50 to find the
connection with FIGS. 3, 6, and 8.
Referring to FIGS. 3, 7 and 11, as noted above, the
position where the character sequence "s" has previously
database is initialized to all invalid values. The below
occurred in the history array. In this case, this character
discussion uses shows how the input string "#Suzie sells
sequence "s" has not occurred previously so the position
seashells" is processed. The '#' character is added to the 55 returned at step 1116 is an invalid position. At step 1118, the
current position 2 of this sequence "s" is stored using the
history array to serve as a history array bounds check. In this
example, the first character processed is a unique character
MROHV value of 1690. At step 1120, since the position that
"#" which is not repeated in order to insure that no match
was originally stored in the database 50 was an invalid
sequences overlap the beginning of the history array. It
position at step 1116, the processing of this character "s" is
should be appreciated by those skilled in the art that other 60 complete. The process then returns to step 1102. Referring
history array bound checking techniques could be used.
additionally to FIG. 14, a table shows the changes to the
The preferred method of bounds checking is to allocate
database 50 as the characters of this example are processed.
memory "before" the start of the history buffer to ensure that
The next character of the example, 'u,' is processed.
Again mlength is initialized to 1 at step 1112. The process
there is no access error if the data before the beginning of the
text history is overrun. It is preferable to allocate as much 65 completes as previously discussed with the processing of
memory as the maximum allowed match length. When
"s" except this time the position is 3 for sequence "u" which
examining the characters in the history array, a check should
has signature 10085. The signature 10085 corresponding to

5,805,911

21

22

"u" is used to store position 3 for later querying of the
be readily understood by one skilled in the art in light of the
database 50. As with the processing of "S", "u" has not
above figures and related discussion.
previously occurred. so the value returned at step 1116 from
After setting up the database 50, the process searches for
the database is an invalid position. The current position 3 of
text to be predicted from the history array 54. The process
this sequence "u" is stored using the MROHV value of 5 for searching the processed text for the longest matching
10085. Because step 1116 yielded an invalid position value,
character sequence is similar to the text updating processed
the processing of "u" is complete and the process returns to
described above, the primary difference is that the database
step 1102.
50 is not modified. In the text updating process, the two
So far 3 characters '#' "s", and 'u' have been processed
signatures, MROHV and CCHV refer to two character
from the full example "#Suzie sells seashells." The follow- 10 sequences in the history array. The MROHV represents the
ing characters 'z', 'i', 'e', and's' all follow a similar pattern
sequence with the last character at the position of the longest
of processing as the processing of'S' and 'u.'
match, the CCHV represents the sequence ending at the end
Now, when the process encounters 'e' in "sells" the
of the history array 54.
process takes additional steps to process this second occurIn the find match position process, the sequence ending at
rence of 'e' in the history array. As discussed above, mlength 15 the end of the history array is replaced with a new character
is initialized to 1 at step 602. The character 'e' is added to
string which is passed into the process for the new search.
The find match position process shown in FIG. 13 carries out
the history array 54 which now begins "#Suzie se".
MROHV is calculated at step 1112 for the sequence 'e' to be
the same steps as the update text process shown in FIG. 12
18445. Again at step 1114, CCHV is the same as MROHV
except that steps 1204, 1212, and 1218 are omitted and the
at this point in the at step 1114. At step 1116, the database 20 history length is replaced with the length of searched for
string.
50 is queried with signature 18445 to determine the last
position that the sequence "e" has occurred. For the first time
The following example for finding a match uses the input
in this example an invalid position is not returned by the
search string "Who sells s". The process produces the output
"Who sells seashells." The database 50 has been set to find
database 50. The position 11 is returned at step 1116
indicating that 'e' has previously occurred. Now, at step 1118 25 sequences from the string "#Suzie sells seashells" as disthe current position 9, representing the 'e' in "sells", is
cussed above. Referring to FIG. 12, at step 1202, mlength is
stored using the new signature MROHV (which is also
initialized to 1. Because mlength is less than the input search
18455). At this point, the process has determined that the
string length, the process proceeds to step 1214. At step
1214, the signature CCHV, for "S" generated from the last
character at position 9 in the history array matches the
character at position 11 in the history array. Because 'e' has 30 character of "Who sells s" and is calculated to be 5895. The
signature 5895 is used to query the database 50 at step 1216
previously occurred and a pointer has been set to point to the
for the most recent occurrence of a "s" which is found to be
current character 'e', the process proceeds to steps 1124,
position 22. Position 22 is the final's' in "seashells." Since
1130, and 1132. At steps 1124, 1130, and 1132, the process
position 22 is a valid position, the process proceeds to step
is enabled to update the database to point to a longer
non-matching sequence that occurred prior to the current 35 1224, where mlength is incremented.
sequence but which begins with currently processed charAt step 1230, the characters of the input search string
acter sequence. At steps 1124, 1130, and 1132, the process
counting back from the end of the input search string are
determines how many more characters match starting with
compared with the characters of the text history array
preceding the located position 22. At step 1230, the last
positions 8 and 5, and counting backwards in the history
array. At step 1130, since position 8 is a's' and position 5 40 space ' , in "Who sells s" is compared with the last '1' in
is an 'i', there are no further matches and the process
"seashells." These two characters do not match so the
proceeds to step 1110 with mlength=2.
process proceeds to step 1210 with mlength=2. The process
Now, at step 1110, the processing of 'e' continues with
proceeds to step 1214 where CCHV is calculated by hashing
the' , character with the 5895 to get 20195. The signature
mlength=2 because mlength is less than the history length
hlength=9. At step 1112, the letter at position 5 (' i') is hashed 45 5895 is used to query the database 50 to get 14. Since 14 is
with 18445 to get MROHV=17635. MROHV is the signaa valid position, the match length is incremented to 3 at step
ture which represents the sequence "ie" since HASH
1224 and the characters in the input string ending with the
final's' in "Who sells" are compared at step 1230 with the
(i,HASH(e,0))=17635. Similarly CCHV is calculated by
characters from the history ending with "#Suzie sells." At
hashing the letter at position 8 (,s') with 18445 to get
CCHV=13685. CCHV is a signature representation of the 50 step 1230, because the ending "s" of "sells" in "Who sells"
matches the ending "s" of "# Suzie sells", the current input
sequence "se" since HASH(s,HASH(e,0))=13685. At step
1116, the database 50 is queried to determine if "se" has ever
hash value is updated for the longer match by the hash
function (4). These comparisons continue at each iteration
occurred in the history array 54. The position returned at step
1116 is an invalid position indicating that "se" has not
through the steps 1224, 1230, and 1232 until mlength is 8
previously occurred. The position 11 is stored at step 1118 55 (i.e. when the 'e' in "#Suzie" is found to be different than the
'0' in "Who"). The process then continues to step 1210 with
in the database using MROHV=17635. Because the database position returned is an invalid position, we are through
mlength equal to 8. The process proceeds to step 1214 where
processing the 'e' in "sells".
the character '0' is hashed with the current signature to get
19525 which represents the sequence "0 sell s". The signaReferring to FIG. 14, examination of the changes to the
database 50 shows that position 6 had been stored earlier at 60 ture 19525 is used to query the database 50 and an invalid
position is returned indicating that this sequence has not
signature 18455 for sequence "e." Position 6 was replaced
previously occurred. So the process ends with the position
with position '9,' while position 6 was stored at signature
17635 for sequence "ie". Thus, the changes to the database
14 returned. The word prediction system takes the match
position and writes out the characters from this position to
occurred so that the signature of each sequence stored in the
database can be used to look up the most recent occurrence 65 the end of the word as the predicted text. This causes the text
"seashells" to be written out as the completion for the partial
of the character sequence. The effect of processing the
remainder of the characters in "#Suzie sells seashells" can
text "Who sells s."

5,805,911

23

24

As noted above, prior art word prediction systems are
Each time a new input character is entered, the database
based upon text entered from within only a single window
is queried, using the calculated address, to determine if a
or single application. Referring to FIGS. 1, 3, and 15, the
valid position for the text history array has been stored at the
word prediction system 10 may be utilized across multiple
calculated address, which indicates that the character
windows to provide an individual and collective method to 5 sequence has previously occurred in the history array. If the
character sequence has not previously occurred in the histrack the input text history across the multiple windows. A
tory array, then the position of the character sequence is
window or field of entry is a portion of a screen that contains
stored in the database as discussed above. If the character
its own document or message. In window-based programs,
sequence has previously occurred, the position of the current
the screen can be divided into several windows, each of
which has its own boundaries. Each window may contains 10 character sequence is stored in the database at the calculated
address to replace the position for previous occurrence of the
its own menu or other controls.
The preferred embodiment of the present invention may
input sequence.
Additionally, after the present invention locates the posiprovide a dynamically linked library, as known to those
tion in the history array for which the current character
skilled in the art, to make the text history available across the
system of windows. In a multi-window environment, the 15 sequence has most recently occurred, the adjacent preceding
word prediction system 10 attempts to find the best match
characters from the most recent occurrence position in the
within the current window 62 in which the user is operating.
history array are compared against the adjacent preceding
The prediction system then may look for a better match
characters of input characters of the history array to locate
the position at which the sequence does not match. An
available from the entire system of windows. In order to
differentiate text input in a specific window, each window 20 appropriate hash address location is calculated for the character that was determined not to match, and the position of
has a number constant associated with the window. Thus,
different addresses are calculated for the database 50 for the
the non-matching sequence, which begins with the origisame character sequences in the different windows.
nally located sequence, is stored to the database. By addiBy using window specific constants for calculating datationally updating the database to point to the longer charbase addresses and an overall word prediction system con- 25 acter string at the most recent occurrence position, the
stants for database address calculation, two different
database is updated continually updated to point to multiple
matches are returned: one is a best match in any context and
character sequences that may begin with the same characters
the other is the best match within the current window. The
with permits direct addressing to locate different character
system of priority of prediction between two matches
sequences.
In order to provide a prediction for input characters based
returned is a matter of user design. For example, the longest 30
match of the current window may constitute the prediction
upon the history of text entered, the present invention
for the prediction system 10. If there is a tie between the
calculates an address for the input character sequence,
lengths of the matches between system text history and the
preferably by a hash coding technique as discussed above.
current window text history, the word prediction may be
The database is queried using the calculated hash address,
taken from the current window. Another design choice may 35 and if the character sequence has previously occurred, the
require that the length of the match from any context be a
most recent position of the character sequence will be
certain length greater than the length of the match found
returned. The word prediction system may then display the
from the current window.
longest match of characters for the most recent occurrence
up to the next word.
Referring to FIG. 15, a flow diagram illustrating the
preferred process of calculating addresses for multi-window 40
The foregoing relates to the preferred embodiment of the
present invention, and many changes may be made therein
applications is shown. The process of FIG. 15 continues
without departing from the scope of the invention as defined
from C of FIG. 5 as indicated. At step 1510, the computer
by the following claims.
determines which of the multiple windows or field of entry
is currently operating. At step 1512, if window 1 is the
I claim:
current window, step 1122 is repeated using different num- 45
1. In a computer system, a computer-implemented method
ber constants in the hash operations to provide database
for predicting text for presentation on a display monitor,
address locations specific to window 1 for the character
comprising the steps of:
sequence positions in the text history array 54. At step 1513,
receiving input text from a text input device;
step 1124 is repeated with the window 1 database address
providing said input text to a text prediction system within
values to provide a word prediction specific to window 1. At 50
said computer system,
step 1514, if window 2 is the current window, steps 1122 and
said text prediction system comprising:
1124 are repeated using different number constants in the
a first text prediction module for predicting text based
hash operations to provide database address locations speon a first text prediction method, and
cific to window 2 for the character sequence positions in the
a second text prediction module for predicting text
text history array 54. At step 1515, step 1124 is repeated with 55
based on a second text prediction method;
the window 2 database address values to provide a word
analyzing said input text by said first text prediction
prediction specific to window 2.
method of said first text prediction module and providIn summary, in order to aid in making text predictions, the
ing a first output text prediction from said first text
present invention builds a text history array of text as
prediction module to said text prediction system;
characters are input by a computer user and builds a database 60
of values that are the positions of various character
analyzing said input text by said second text prediction
sequences in the history array. As characters are being input
method of said second text prediction module and
and added to the history array, an address is calculated,
providing a second output text prediction from said
preferably by a hash coding technique, for the current input
second text prediction module to said text prediction
system, said second output text prediction capable of
character sequence and the position of the character 65
sequence in the history array is stored at the database address
being contradictory when compared to said first output
calculated for the input character sequence.
text prediction;

5,805,911

25

26

in response to receiving said first and second output text
12. In a computer system, a computer-implemented
predictions, determining which of said output text
method for predicting text for presentation on a display
predictions to display; and
monitor, said text being entered within a plurality of fields
displaying said output text prediction, from said step of
of entry, comprising the steps of:
determining, to said display monitor.
5
receiving input text within a first field of entry; and
2. The method of claim 1 further comprising the step of
providing a first output text prediction in said first field of
providing a first belief factor from said first text prediction
entry based on text that was entered in one of a plurality
module and providing a second belief factor from said
of second fields of entry.
second prediction module, said first belief factor indicative
13. The method of claim 12 wherein said step of providing
of the likelihood that said first output text prediction is 10
said first output text prediction based on text that was
correct and said second belief factor indicative of the likeentered in one of a plurality of second fields of entry
lihood that said second output text prediction is correct.
comprises utilizing a second field of entry that is most likely
3. The method of claim 2 further comprising the step of
to provide a correct prediction.
determining whether said first output text prediction should
14. The method of claim 12 wherein said step of providing
be displayed or whether said second output text prediction
should be displayed based on said first and second belief 15 a first output text prediction in said first field of entry based
factors.
on text that was entered in one of a plurality of second fields
4. The method of claim 3 further comprising the step of
of entry, comprises:
providing a first reweighted belief factor to more accurately
accessing a list of pairs of identification numbers, each of
reflect the likelihood that said first output text prediction is
said identification numbers representing an input text
correct and providing a second reweigh ted belief factor to 20
field of entry, the first of said identification numbers of
more accurately reflect the likelihood that said second output
one of said pairs representing the field of entry from
text prediction is correct.
which the input text was entered and the second of said
5. The method of claim 4 wherein said step of providing
identification numbers of said one of said pairs reprea first reweighted belief factor comprises determining said
senting said one of said plurality of second fields of
first reweighted belief factor based on the number of suc- 25
entry; and
cessful predictions provided by said first text prediction
providing said first output text prediction utilizing the text
module within the text field of entry from which said first
previously entered into said one of said second fields of
output text prediction is provided.
entry represented by said second identification number.
6. The method of claim 5 wherein said step of providing
15. The method of claim 14 wherein said step of providing
a second reweighted belief factor comprises determining 30
said first output text prediction utilizing the text previously
said second reweighted belief factor based on the number of
entered into said second field of entry represented by said
successful predictions provided by said second text predicsecond identification number comprises utilizing said section module within the text field of entry from which said
ond field of entry that is most likely to provide a correct
second output text prediction is provided.
7. The method of claim 6 further comprising the step of 35 prediction for the field of entry from which the input text
was entered.
determining whether said first output text prediction should
16. The method of claim 14 wherein said step of providing
be displayed or whether said second output text prediction
said first output text prediction utilizing the text previously
should be displayed based on said first and second
entered into said one of said second fields of entry reprereweighted belief factors.
8. The method of claim 1 wherein said first text prediction 40 sented by said second identification number comprises
selecting said one of said second fields of entry which has
method comprises providing said first output text prediction
the first identification of the pair that is the same as the
in the field of entry that said input text was entered, and
identification number of the field of entry from which the
providing said first output text prediction based on text that
input text was entered.
was entered in a second field of entry.
17. The method of claim 14 wherein said step of providing
9. The method of claim 8 wherein said step of providing 45
said first output text prediction utilizing the text previously
said first output text prediction based on text that was
entered into said one of said second fields of entry repreentered in a second field of entry comprises utilizing a
sented by said second identification number comprises
second field of entry that is most likely to provide a correct
selecting said one of said second fields of entry which has
prediction.
10. The method of claim 8 wherein said first text predic- 50 the first identification of the pair that is the same as the
identification number of the field of entry from which the
tion method comprises:
input text was entered and said first identification number
accessing a list of pairs of identification numbers, each of
represents the first identification number that occurs most is
said identification numbers representing an input text
said list of pairs.
field of entry, the first of said identification numbers
18. In a computer system, a computer-implemented
representing the field of entry from which the input text 55
method for predicting text for presentation on a display
was entered and the second of said identification nummonitor, comprising the steps of:
bers representing said second field of entry; and
receiving input text from a text input device;
providing said first output text prediction utilizing the text
providing multiple text predictions for said input text;
previously entered into said second field of entry repproviding belief factors for each of said predictions, said
60
resented by said second identification number.
belief factors based on the number of successful pre11. The method of claim 10 wherein said step of providing
dictions provided within particular text fields of entry
said first output text prediction utilizing the text previously
from which said text prediction were provided; and
entered into said second field of entry represented by said
second identification number comprises utilizing said secdisplaying the text prediction having the highest belief
ond field of entry that is most likely to provide a correct 65
factor to said display monitor.
prediction for the field of entry from which the input text
19. In a computer system, a computer-implemented
was entered.
method of organizing text within a text prediction system,

5,805,911

27

28

said text prediction system operating within a computer
system having a first window and a second window, comprising the steps of:
receiving input text from a text input device;
storing said input text, entered within either said first
window or said second window, in a common text
history array; and
independently associating text entered within said first
window from text entered within said second window;
and
providing a first output text prediction based on text enter
within said first window, said first output text prediction
based on text stored in said common text history array
and providing a second output text prediction for text
entered within said second window, said second output
text prediction based on text stored in said common text
history array.
20. A computer-implemented method of processing text
for a word prediction system, comprising the steps of:
receiving a plurality of input character sequences in a
computer system;
inputting each of said input character sequences in
ordered positions in an array of text;
generating a number identifier representative of each of
said input character sequences;
using said number identifier as an address into a database;
storing, in said database at said address, the position of
said character sequence in said ordered array of text;
and
replacing, in said database at said address, the position of
said character sequence with the position of the most
recent occurrence said character sequence in said array
of text.
21. A computer-implemented method of locating text in a
text history array of a word prediction system, comprising
the steps of:
generating a pseudo random number identifier for an input
character sequence, said number identifier being an
address location for a database operable to store
pointers, said stored pointers pointing to characters
previously entered into said text history array of characters;
determining whether a pointer exists at said address
location for said input character sequence, said pointer
pointing to the most recent occurrence of said input
character sequence in said text history array;

locating in said text history array of characters the position of the longest most recent occurrence of said
character sequence; and
displaying a text prediction which completes the word
beginning with said longest most recent occurrence of
said character sequence.
22. In a computer system, a computer-implemented
method for storing text utilized for predicting text for
presentation on a display monitor, comprising the steps of:
storing character sequences in a text history array in the
order in which said character sequences are input;
in response to characters being input to the history array,
calculating a database address that is representative of
the current input character sequence;
accessing said database with said database address to
determine if a valid position for the text history array is
stored at said database address, thereby indicating that
said character sequence has previously occurred in said
text history array;
storing the position of the character sequence of the text
history array in the database at the calculated address
for said input character sequence, if the character
sequence has not previously occurred in the text history
array;
if the character sequence has previously occurred, storing
the position of the current input character sequence in
the database at said calculated database address so as to
replace the position of the text history array stored for
the previous occurrence of the input sequence located
at said database address;
after locating the position in the history array for which
the current character sequence has previously occurred,
comparing the adjacent preceding characters from the
most recent occurrence position in the history array
against the adjacent preceding characters of said input
character sequence of the history array to locate the
character and the position at which the sequence does
not match thereby identifying a non-matching character
sequence which begins with the current input character
sequence;
calculating a database address for the non-matching
sequence that is representative of the non-matching
character sequence input character sequence; and
storing the position of the non-matching sequence to the
database at the address calculated for the non-matching
sequence.

5

10

15

20

25

30

35

40

45

* * * * *