lllllllllllllllllllllllllllIllllIllllllllllllllllllllllllllllllllllllllllll
`USOOS434777A
`.
`5,434,777
`[11] Patent Number:
`_
`[19]
`Umted States Patent
`LuciW
`[45] Date of Patent:
`Jul. 18, 1995
`
`
`[75]
`
`[54] METHOD AND APPARATUS FOR
`PROCESSING NATURAL LANGUAGE
`.
`.
`.
`.
`-
`Inventor.
`2387;115:1111: W. Lucm, Morgan Hlll’
`'
`[73] Assignee: Apple Computer, Inc., Cupertino,
`Calif.
`
`OTHER PUBLICATIONS
`Microsoft MSDOS Operating System User’s Guide; pp.
`4—1 to 4—16, 5—1 to 5-19; 1982; 1983.
`O’Connor, Rory J., “Apple Banking on Newton’s
`Brain”, San Jose Mercury News, Apr. 22, 1991.
`Hendnx, Gary G. and Walter, Brett A., “The Intelll-
`(List continued on next page.)
`
`[21] Appl. NO“ 2158064
`.
`F1led:
`
`[22]
`
`Mar. 18’ 1994
`
`Primary Examiner—Gail O. Hayes
`Assistant Examiner-Stephen R. Tkacs
`Attorney, Agent, or Firm—Hickman & Beyer
`
`Related US. Application Data
`
`[57]
`
`ABSTRACT
`
`[56]
`
`[63]
`
`Continuation-impart of Ser. No. 889,225, May 27,
`1992, Pat. NO- 5,390,281, and Set. N0~ 99,861, Jul- 30,
`1993'
`.
`Eg El; Cclifi """""""""""" (3063-1;4159?? 3336/?13/0680
`‘
`'364/41911395/10 395/12, 395’/51_ 395/54:
`'
`’
`’
`’ 395/60- 395/62
`[58] Field of Search
`364/419 01’ 419 08
`364/4191 4191141912 41913. '395’/10 ‘12’
`’
`50’ ’51 54 6O 62 63 75 76 7-;
`,
`’
`,
`’
`’
`’
`’
`References Cited
`U S PATENT DOCUMENTS
`‘
`'
`:Chmmml ------------------------------ 33328
`2,373,331: 1323:;
`cott et a .
`............................
`,
`,
`4,736,296 4/1988 Katayama et al.
`............. 364/419.08
`4,750,122 6/1988 Kaji et al. ................ 364/419.13
`
`.. 364”19.13
`4,785 413 11/1988 Atsurni
`4,875,187 10/1989 Smith ................... 395/141
`4,887,212 12/1989
`Zamora et a1.
`.. 364/41908
`4,918,723 4/1990 Iggulden et al.
`..
`379/100
`
`4,945,504 7/1990 Nakama at 2.1.
`364/709
`4,953,106 8/1990 Gansner et a1.
`395/160
`
`4,974,191 11/1990 Amirghodsi ............. 395/275
`
`.. 364/419.08
`4,994,966 2/ 1991 Hutchins .......
`5,091,790 2/1992 Silverberg ........................... 358/434
`(List continued on next page.)
`FOREIGN PATENT DOCUMENTS
`
`'A method and apparatus for processing natural lan-
`guage and deducing meaning from a natural language
`input characterized by the steps of (a) receiving an
`ordered string of word objects having a natural lan-
`guage meaning, (b) selecting a word window length,
`and (c) successively moving the word window along
`the ordered string and analyzing the meaning of a sub-
`string of word objects that fall within the word win-
`dow. The substring is removed from the ordered string
`if the substring has a recognized meaning, until all sub-
`strings of the ordered string that fit within the window
`have beenanalyzed. In a step (d), the word window
`length is reduced and step (c) is repeated until only an
`unrecognized residual of the ordered string remains.
`The meaning of the substring is analyzed by mapping
`-
`-
`»
`_
`the 511mm.“g ag$fi5t a database “mg one or morfe mg?
`pmg rouimes’ .
`e mapping Townes are. pre em. y
`arranged In a hlerarchy, wherein a success1ve mapping
`routine is used to analyze the substring when a previous
`mapping routine in the hierarchy cannot map the sub-
`string. A computer-implemented task is determined
`from the recognized substrings and performed by the
`computer system. The apparatus of the present inven-
`tion implements the method on a pen-based computer
`system, and the ordered string is preferably received
`from strokes entered by a stylus on a display screen of
`the pen-based computer or from a microphone receiv-
`ing speech input.
`
`8/1991 European Pat. Off.
`0441089A2
`932164 5/1989 Japan .
`
`.................. 3/23
`
`27 Claims, 12 Drawing Sheets
`
`’Z\
`
`7:1
`
`SJBS'I'RLNG
`Lummmmtzflowmmsumn
`/
`umwlmwflmyiwmmmz
`mmmizwmuww
`Wmmmy‘lwmfi
`73
`mwlmmuwm
`F/wimE-lmwzaapmumz
`memylwpfi‘
`mwwiwmu
`simwzsounszom
`Wiwwalmm
`
`75
`
`LENGTH-9. 705.1
`LDCA‘nON )
`LENGTH-a. PCS-I
`LENGm-s, Pow
`LENGTH-7. PCS-1
`LENGTH-7. POS-Z
`LENGTHfl. Pas-a
`LENGTH-6. Poe-1
`ENGTH-G, PCS-.2
`LENGTH-6. Pom
`Lemmas. PCS-t
`
`LENGTH-n1, POS=1
`Lemmas. PCS-2
`Lemma. PCS-3
`LENGTH-3, pas-a
`LENGTHxS. Poe-4
`LENGTH-2.13054!
`LENGTH-2, Poe-1
`LENGTH-1P0”
`LENGTH-2, 1:054
`LENGTH-1. Poe-1
`mam-1, Poem
`
`
`
`SAMSUNG EX. 1014
`
`Luna! Mm as
`W Bil My
`521 Way 122:: /
`[My 1230 pm]
`.1 cm: Swan
`u
`new
`[ca-mew]
`75
`
`78
`
`u
`A
`80/
`
`[Lu-m vim]
`3111
`75
`
`f
`[541]
`
`SAMSUNG EX. 1014
`
`

`

`5,434,777
`
`Page 2
`
`US. PATENT DOCUMENTS
`5,103,498 4/1992 Lanier et a1. .......................... 395/68
`5,109,509 4/1992 Kayatama et a1.
`.
`..... 395/600
`5,123,103 6/ 1992 Ohtaki et a1. ............ 395/600
`5,282,265 1/1994 Rohra Suda et a1.
`....... 395/12
`
`5,327,342 7/1994 Roy ........................... 364/4191
`................. 364/419.13
`5,357,431 10/1994 Nakada et a1.
`
`
`
`OTHER PUBLICATIONS
`
`gent Assistant: Technical Considerations Involved in
`Designing Q&A’s Natural—Language Interface,” Byte
`Magazine, Dec. 1987, Issue 14, p. 25.
`Edwards, John R., “Q&A: Integrated Software with
`Macros and an Intelligent Assistant,” Byte Magazine,
`Jan. 1986, V. 11, Issue 1, pp. 120-422.
`Goldberg, Cheryl, “IBM Drawing Assistant: Graphics
`for the EGA”, PC Magazine, Dec. 24, 1985, vol. 4,
`Issue 26, p. 255.
`Garretson, R., “IBM Adds ‘Drawing Assistant Design
`Tool to Graphic Series,” PC Week, Aug. 13, 1985, V. 2,
`Issue 32, p. 8.
`Glinert—Stevens, Susan, “Microsoft Publisher: Desktop
`Wizardry,” PC Sources, Feb. 1992, V. 3, Issue 2, p. 357.
`Nilsson, B. A. “Microsoft Publisher is an Honorable
`Start for DTP Beginners,” Computer Shopper, Feb.
`1992, V. 12, Issue 2, p. 416.
`Poor, Alfred, “Microsoft Publisher,” PC Magazine,
`Nov. 26, 1991, V. 10, Issue 20, p. 40.
`Rampe, Dan et al., Jan. 9. 1989 news release, Claris
`Corp. (announced “SmartForm Designer” and “Smart-
`Form Assistant”.
`
`Berry, Deanne et al., Apr. 10. 1990 news release, Sy-
`mantec, (announced new version pf MORE TM).
`Elofson, G. et al., “Delegation Technologies: Environ-
`mental Scanning with Intelligent Agents,” Jour. of
`Management Info. Systems, Summer 1991, V. 8, Issue 1,
`pp. 37—62.
`
`Nadoli, Gajanana et al., “Intelligent Agents in the Simu-
`lation of Manufacturing Systems,” Proceedings of the
`SCS Multiconference on AI and Simulation, 1989.
`Sharif Heger et al., “KNOWBOT: An Adaptive Data
`Base Interface,” Nuclear Science and Engineering, Feb.
`1991, V. 107, No. 2, pp. 142—157.
`Ohsawa, I. eta1., “A Computational Model of an Intelli-
`gent Agent Who Talks with a Person,” Research Re—
`ports on Information Sciences, Series C, Apr. 1989, No.
`92, pp. 1—18.
`Ratcliffe, Mitch et al., “Intelligent Agents Take U.S.
`Bows,” MacWeek, Mar. 2, 1992, V. 6, No. 9, p. 1.
`Boy, Guy A., Intelligent Assistant Systems, Harcourt
`Brace Jovanovicy, 1991.
`“Microsoft Windows User’s Guide for the Windows
`Graphical Environment,” version 3.0, Microsoft Press,
`copyright 1985—1990, pp. 33-41 & 70—74.
`R. Wilensky et al., “Talking to UNIX in English: an
`Overview of UC,” Communications of the ACM, Jun.
`1984, vol. 27, No. 6.
`Tello, Ernest R., “Natural-Language Systems,” Mas-
`tering AI Tools and Techniques, Howard W. Sams &
`Company, 1988.
`Knight, Kevin, & Rich, Elaine, “Heuristic Search,”
`Production Systems, Artificial Intelligence, 2nd ed.,
`McGraw-Hill,‘Inc., 1983—1991.
`
`Miastkowski, Stan, “PaperWorks Makes Paper Intelli-
`gent,” Byte Magazine, Jun. 1992.
`Dickinson et al., “Palmtops: Tiny Containers for All
`Your Data,” PC Magazine, Mar. 1990, vol. 9, p. 218(3).
`Bajarin, Tim, “With Low End Launched, Apple Turns
`to Portable Future”, PC Week, Oct. 1990, vol. 7, p.
`153(1).
`Corporate Ladder, BLOC Publishing Corp., 1991.
`Diagrammaker, Action Software, 1989.
`Diagram—Master, Ashton—Tate, 1989.
`
`SAMSUNG EX. 1014
`
`SAMSUNG EX. 1014
`
`

`

`US. Patent
`
`July 18, 1995
`
`Sheet 1 of 12
`
`5,434,777
`
`mm.
`
`.VN
`
`Q»ON
`a.><.Em_n_
`
`>._m_>_mmm<
`
`:52.
`
`
`
`E.o<a>mx
`
`MZOIQOEQE
`
`ENE—4&5:
`
`I»
`
`N».
`
`
`
`mm.hmOQI:
`
`mv
`
`
`
`#5....._<_mmm
`
`0:
`
`mmm0<mohw
`
`9»
`
`mmxfiam
`
`mmtzasi
`
`RVEa
`
`iv20040
`
`SAMSUNG EX. 1014
`
`SAMSUNG EX. 1014
`
`
`
`

`

`US. Patent
`
`July 18, 1995
`
`Sheet 2 of 12
`
`5,434,777
`
`UNHLW
`
`l
`
`‘VW
`
`
`_Lungb_with_BiJLMend§y_12;’olq p.m_at__
`Chez Sovan
`
`/ Q . $ Q
`
`Names Dates
`
`E as
`
`Undo
`
`Find Assist
`
`figure 2
`
`SAMSUNG EX. 1014
`
`SAMSUNG EX. 1014
`
`

`

`US. Patent
`
`July 18, 1995
`
`Sheet 3 of 12
`
`5,434,777
`
`72\
`
`/
`SUBSTRlNG
`Lunch with Bill Monday 12:30 pm at Chez Sovan
`
`73
`
`75
`
`LOCATION 2
`
`LENGTH=9, POS=1
`
`Lunch with Bill Monday 12:30 pm at Chez
`
`LENGTH=8, POS=1
`
`with Bill Monday 12:30 pm at Chez Sovan
`
`LENGTH=8, POS=2
`
`Lunch with Bill Monday 12:30 pm at
`
`with Bill Monday 12:30 pm at Chez
`
`LENGTH=7, POS=1
`
`LENGTH=7, POS=2
`
`f
`
`73
`
`Bill Monday 12:30 pm at Chez Sovan
`
`LENGTH=7, POS=3
`
`Lunch with Bill Monday 12:30 pm
`
`with Bill Monday 12:30 pm at
`
`Bill Monday 12:30 pm at Chez
`
`Monday 12:30 pm at Chez Sovan
`.K
`
`Lunch with Bill
`
`with Bill Monday
`Bill Monday 12:30 /
`[Monday 12:30 pm]
`
`74
`
`[Lunch with]
`/ Bill
`/
`[Bin]
`
`76
`
`78
`
`at Chez Sovan
`
`at
`at Chez
`[Chez Sovarfl
`\
`
`at
`
`78
`
`80 /
`
`figure 3
`
`LENGTH=6, POS=1
`
`LENGTH=6, POS=2
`
`LENGTH=6, POS=3
`
`LENGTH=6, POS=4
`
`LENGTH=3, POS=1
`
`LENGTH=3, POS=2
`
`LENGTH=3, POS=3
`
`LENGTH=3, POS=4
`
`LENGTH=3, POS=4
`
`LENGTH=2, POS=1
`
`LENGTH=2, POS=1
`
`LENGTH=2, POS=2
`
`LENGTH=2, POS=3
`
`LENGTH=1, POS=1
`ILENGTH=1, POS=1
`
`SAMSUNG EX. 1014
`
`SAMSUNG EX. 1014
`
`

`

`US. Patent
`
`July 18, 1995
`
`Sheet 4 of 12
`
`5,434,777
`
`so
`
`\ ® {figure 4
`
`82
`
`.
`
`DEVELOP
`STRING
`
`84
`
`LENGTH = NWORDS
`POS = 1
`
`._
`
`is NWORDS?
`
`88
`
`90
`
`m
`
`9
`
`2
`
`ARRANGE NMAP
`MAPPING ROUTINES
`
`
`IN HIERARCHY
`
`as
`
`96
`
`OBTAIN A
`SUBSTRING
`
`STRING FULLY
`ANALYZED?
`
`
`
`
`MARK HITARRAY
`
`(LENGTH, POS) AS "HIT"
`
`I—
`
`
`- HITARRAYUJ)=0
`
`
`
`j=j + 1
`
`I < NWORDS
`- I + 1?
`
`
`
`
`
`MAPS USING MAP
`
`ROUTINE(J)?
`
`STORE RESIDUAL
`
`DETERMINE TASK
`BASED UPON
`MAPPINGS
`
`104
`
`PERFORM TASK
`
`-
`
` SUBSTRING
`
`
`
`106
`
`108
`
`1 1 O
`
` REMOVE
`SUBSTRING AND
`
`STORE MAPPING
`
`
`SAMSUNG EX. 1014
`
`SAMSUNG EX. 1014
`
`

`

`U.S. Patent
`
`July 18, 1995
`
`Sheet 5 of 12
`
`5,434,777
`
`84
`
`/
`
`116
`
`RECEIVE
`
`USER INPUT
`
`RECOGNIZE
`INPUT
`
`figure 5
`
` 118
`
` 120
`
`
`
`DELINEATE A
`STRING FROM
`
`RECOGNIZED
`INPUT
`
`122
`
`
`
`124
`
`\
`
`132
`
`/W C
`
`OST
`
`128
`
`130
`
`A/
`
`LEVEL
`
`/
`MAPPING ROUTINE
`
`1
`
`2
`
`3
`
`PHRASAL PROCESSOR
`
`LOW
`
`PATTERN PROCESSING
`
`MEDIUM
`
`DATABASE PROCESSING
`
`HIGH
`
`figure 6
`
`SAMSUNG EX. 1014
`
`SAMSUNG EX. 1014
`
`

`

`US. Patent
`
`July 18, 1995
`
`Sheet 6 of 12
`
`5,434,777
`
`96
`
`A/
`
`138
`
`140
`
`@ YES
`
`
`ND
`
`CHECK LHITARRAY
`MATRIX FOR POS
`AND SUBPHRASE
`
`LENGTH =
`NULL
`
`142
`
`156
`
`m
`
`1
`
`POS = P08 + 1
`
`POSSIBLE?
`
`.
`
`‘ YES
`
`1 54
`
`‘ SUBSTRING = STRING (POS,
`LENGTH)
`
`158
`
`
`
`
`POS+LENGTH
`> NWORDS+1?
`
`
`
`
`YES
`
`POS=1
`LENGTH:
`
`LENGTH — 1
`
`150
`
`figure 7
`
`SAMSUNG EX. 1014
`
`SAMSUNG EX. 1014
`
`

`

`US. Patent
`
`July 18, 1995
`
`Sheet 7 of 12
`
`5,434,777
`
`147
`
`\
`
`14§
`
`HITARRAY/ 150 /
`
`152
`
`POSITION
`
`LENGTH
`VALUE
`
`123456789123456781234567
`0o01234123121..
`
`111111111222222223333333
`0o066667770089
`
`OOOOOOOOOOOOOOOOOOOOOOOO
`...0000000000
`
`figure 7a
`
`SAMSUNG EX. 1014
`
`SAMSUNG EX. 1014
`
`

`

`US. Patent
`
`July 18, 1995
`
`Sheet 8 of 12
`
`5,434,777
`
`STORE MAPPING, MAPPED
`SUBSTRING OBJECT AND
`REMOVE SUBSTRING
`
`NWORDS = NWORDS - #
`WORDS IN REMOVED
`SUBSTRING
`
`164
`
`166
`
`AS "POSSIBLE" figure 8
`
`MARK
`HITARRAY(LENGTH,POS)
`
`168
`
`220
`
`FILL IN TASK
`TEMPLATE
`
`CAN TASK BE
`EXECUTED?
`
`
`
`
`
`
`EXECUTE TASK
`
`226
`
`figure 13
`
`SAMSUNG EX. 1014
`
`SAMSUNG EX. 1014
`
`

`

`US. Patent
`
`July 18, 1995
`
`Sheet 9 of 12
`
`5,434,777
`
`172
`
`\
`
`PHRASE LOOK—UP TABLE
`
`figure 9
`
`174
`
`<PERSON—3>
`
`"ITALY"
`
`<COUNTRY-2>
`
`PHRASES
`INSTANCES
`
` <COMPANY— 1>
`
`< FOOD- 1 >
`
`
` 176
`<COUNTRY— 1 >
`
`
`
`<PERSON- 1 >
`<PERSON-2>
`
`
`
`
`
`
`<MEET— 1 >
`
`"‘LUNCH WITH"
`"SCHEDULE
`<MEET—2>
`
`
`LUNCH WITH"
`
`
`
` "ZORRO"
`<HERO- 1>
`
`178
`
`180
`
`
`
`
`"LUNCH WITH"
`
`SAMSUNG EX. 1014
`
`SAMSUNG EX. 1014
`
`

`

`US. Patent
`
`July 18, 1995
`
`Sheet 10 of 12
`
`5,434,777
`
`figure 1 0
`
`PATTERN LOOK-UP TABLE
`
`PATTERN
`
`INSTANCE /
`
`1 84
`
`
`
`
`
`
`"pm"
`<num>
`<1‘imeslot>
`
`<num>
`<num>
`<fimeslot>
`
`
`1 86
`
`{1‘IMESLOT>
`
`
`
`
`
`
`<TIMESLOT— 1 >
`
`"12:30 pm"
`12:30:00
`
` TIME = 1015
`LOCATION (12,7-12)
`
`SAMSUNG EX. 1014
`
`SAMSUNG EX. 1014
`
`

`

`US. Patent
`
`July 18, 1995
`
`Sheet 11 of 12
`
`5,434,777
`
`NAME:
`BIRTHDAY:
`TELEPHONE:
`FAX:
`
`INSTANCES: <PERSON—1> <PERSON-2> <PERSON—3>
`
`ADDRESS:
`HEIGHT:
`WEIGHT:
`
`196
`
`1940
`
`\N
`
`
`
`1941:
`
`
`
`NAME: BILL JONES
`<PERSON-2> <BILL2>
`\ NAME: BILL RIKER
`<PERS ON-1> <BILL— 1>
`
`194a
`
`
`
`
`
`
`NAB/IE: BILL SETAG
`BIRTHDAY: NULL
`TELEPHONE: 408—555—1212
`FAX: NULL
`
`ADDRESS: 123 MAIN STREET,
`
`
`
`
`
`
`
`
`
`HEIGHT: NULL
`WEIGHT: NULL
`
`
`
`<RESTAURANT-1>
`
`$513325“:
`
`[figure 11
`
`RATING:
`
`
` RATING: 4 STAR
`
`<RESTAURANT— 1>
`
`RESTAURANT: CHEZ SOVAN
`ADDRESS: 436 STEVENS CREEK BLVD.
`
`SAMSUNG EX. 1014
`
`SAMSUNG EX. 1014
`
`

`

`US. Patent
`
`July 18, 1995
`
`Sheet 12 of 12
`
`5,434,777
`
`208
`
`N
`
`210 '
`
`212
`
`214
`
`‘ "new
`
`Formatting
`
`figure 12
`
`SAMSUNG EX. 1014
`
`SAMSUNG EX. 1014
`
`

`

`1
`
`5,434,777
`
`2
`
`METHOD AND APPARATUS FOR PROCESSING
`NATURAL LANGUAGE
`
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`
`This application is a continuation-in-part of parent
`patent application Ser. Nos. 07/889,225, filed May 27,
`1992 on behalf of Luciw et al., entitled, “Method and
`Apparatus for Deducing User Intent and Providing
`Computer Implemented Services,” now US. Pat. No.
`5,340,281, and 08/099,861, filed Jul. 30, 1993 on behalf
`of Luciw et al., entitled, “Method and Apparatus for
`Providing Computer-Implemented Assistance,” which
`are hereby incorporated by reference herein.
`
`BACKGROUND OF THE INVENTION
`
`5
`
`10
`
`15
`
`The present invention relates generally to computer
`systems, and more particularly to methods for process-
`ing natural language input from users of computer sys-
`tems.
`
`20
`
`Computerized personal organizers are becoming in-
`creasingly popular. They perform such functions as
`keeping a calendar, an address book, a to—do list, etc.
`While these functions can be provided by conventional
`computer systems,
`they are more conveniently pro-
`vided by personal organizers which are relatively inex-
`pensive, small, and lightweight (i.e. portable). Personal
`organizers are available from such companies as Sharp
`and Casio of Japan.
`A relatively new form of computer, the pen—based
`computer system, holds forth the promise of a marriage
`of the power of a general purpose computer with the
`functionality and small size of a personal organizer. A
`pen-based computer system is typically a small, hand-
`held computer where the primary method for inputting
`data includes a “pen” or stylus. A pen-based computer
`system is commonly housed in a generally rectangular
`enclosure, and has a dual—function display assembly
`providing a viewing screen along one of the planar sides
`of the enclosure. The dual-function display assembly
`serves as both an input device and an output device.
`When operating as an input device, the display assem-
`bly senses the position of the tip of a stylus on the view-
`ing screen and provides this positional information to
`the computer’s central processing unit (CPU). Some
`display assemblies can also sense the pressure of the
`stylus on the screen to provide further information to
`the CPU. When operating as an output device, the dis—
`play assembly presents computer—generated images on
`the screen.
`
`The dual-function displays of pen-based computer
`systems permit users to operate the computers as com-
`puterized notepads. For example, graphical images can
`be input into the pen-based computer by merely moving
`the stylus across the surface of the screen. As the CPU
`senses the position and movement of the stylus, it gener-
`ates a corresponding image on the screen to create the
`illusion that the stylus is drawing the image directly
`upon the screen, i.e. that the stylus is “inking” an image
`on the screen. With suitable recognition software, the
`“ink” can be identified as text and numeric information.
`Computer systems,
`including pen-based computer
`systems, can also incorporate speech recognition. Al-
`though still mostly in the developmental stage, speech
`recognition has many potential uses in computer sys-
`tems. For example, in a portable pen-based computer,
`speech input and recognition can be used to conve-
`
`25
`
`3O
`
`35
`
`45
`
`50
`
`55
`
`60
`
`65
`
`niently record dictated messages or other spoken docu-
`ments and to present the dictated words as an electronic
`text document for editing, printing, faxing, etc. or to
`input commands into the computer system.
`Stylus, speech, keyboard, and other forms of input
`can take the form of “natural language,” i.e. an “utter-
`ance.” Natural language is written or spoken input that
`is in a natural form that a person would use as if speak-
`ing or writing to another person. Non-natural language
`would be language, such as computer commands or
`programs, which is constrained by a limited syntax,
`structure, and/or scope.
`Natural language input permits a user to easily inter-
`face with a computer system using wellknown lan—
`guage. One area in computer systems which is particu-
`larly well-adapted for natural language input is comput-
`erized assistance. Computers systems that use comput~
`erized assistance deduce or hypothesize a user’s intent
`and automatically provide a service based on the de-
`duced intent. For example, a tasks such as printing a
`document or scheduling an appointment can be imple-
`mented by a computer system by deducing information
`from a user’s inputs or preferences. Natural language
`input allows a user to quickly specify a service or task to
`be implemented using a complex form and thus is well
`suited for use with computerized assistance.
`The recognition of natural language by computer
`systems has been difficult due to the complex and shift-
`ing “rules” of human natural language. A user may
`input a natural language phrase, such as, “meeting with
`Bill on Tuesday at lunch” to instruct the computer
`system to schedule the meeting in a calendar application
`program. The computer system typically recognizes the
`individual words to recognize the meaning of the entire
`phrase. However, by recognizing small portions of the
`input phrase separately, a complete, overall meaning for
`the phrase is often incorrect, inaccurate, or incomplete.
`Natural language input has been typically processed
`using one of several methods. A natural phrase or string
`can be matched to a known phrase in a phrase lexicon
`used by the computer. A long command is typically
`processed by matching individual words or smaller
`phrases to items in the lexicon. Another method used to
`process natural language is to examine parts of the input
`phrase for a standard pattern. For example, a number
`including a colon and followed by “am” or “pm” fits
`the pattern of a phrase indicating time. A different
`method used to process natural language is to query a
`database that stores a large number of phrases and
`match a phrase to one or more items stored in the data-
`base.
`
`The abovementioned processes have typically been
`used with a fixed set of rules to interpret natural lan-
`guage. An a priori specification of known linguistic
`structures and their meaning is used to perform seman-
`tic interpretation. Each of the abovementioned pro-
`cesses has limitations in versatility and the time required
`to match a phrase. Natural language processing of the
`prior art has thus been inefficient and rigid in its ability
`to recognize the meaning of natural language utter-
`ances.
`
`What is needed is a natural language processor that
`will quickly and accurately identify and map natural
`language input phrases. What is further needed is a
`natural language processor that identifies phrases ac-
`cording to a dynamic set of rules and data.
`
`SAMSUNG EX. 1014
`
`SAMSUNG EX. 1014
`
`

`

`3
`
`SUMMARY OF THE INVENTION
`
`5,434,777
`
`The present invention provides a natural language
`processor for the user of a computer system. The
`method of the present invention analyZes portions or
`substrings of a natural language input string to deter-
`mine the meaning of the input string. Large substrings
`are analyzed and reduced in size until the substrings can
`be mapped into a database using mapping routines.
`Three dynamic mapping routines are preferably used in
`sequence in the present invention: a phrasal processor, a
`pattern processor, and a database query processor.
`These processors provide a robust method of identify-
`ing the meaning of natural language input.
`More particularly, a method for deducing meaning
`from a natural language input comprises the steps of (a)
`receiving an ordered string of word objects having
`length and a natural language meaning, (b) selecting a
`word window length that is no greater than the length
`of the ordered string, and (c) successively moving the
`word window along the ordered string and analyzing
`the meaning of a substring of word objects that fall
`within the word window. The substring is removed
`from the ordered string if the substring has a recognized
`meaning, until all substrings of the ordered string that fit
`within the window have been analyzed. In a step (d),
`the word window length is reduced and step (c) is re-
`peated until only an unrecognized residual of the or-
`dered string remains. The ordered string is preferably
`received from strokes entered by a stylus on a display
`screen of a pen-based computer or from a microphone
`receiving audible speech input. The step of analyzing
`the meaning of the substring preferably includes map-
`ping the substring against a database using one or more
`mapping routines. The mapping routines are preferably
`arranged in a hierarchy, wherein a successive mapping
`routine is used to analyze the substring when a previous
`mapping routine in the hierarchy cannot map the sub-
`string. The method preferably further includes a step of
`determining a computer-implemented task specified by
`the ordered string using the recognized substrings and
`performing the computer-implemented task.
`A method for recognizing meanings of natural lan-
`guage phrases comprises the steps of attempting to map
`at least a portion of an ordered string of word objects
`into a database according to a phrasal mapping routine.
`If the string portion does not map into the database
`using the phrasal mapping routine, a step of attempting
`to map the portion into a database according to a pat-
`tern mapping routine is accomplished. If the pattern
`mapping routine is unable to map the string portion,
`then a database query mapping routine attempts to map
`the string portion. The mapping routines are preferably
`dynamic mapping routines referencing dynamic data
`structures. Remaining portions of the ordered string are
`preferably mapped according to the mapping routines
`until all word objects of the string have been analyzed.
`A preferred apparatus in accordance with the present
`invention implements the natural language processor on
`a computer system, and more preferably on a small,
`handheld computer system such as a personal digital
`assistant (PDA). The natural language can be input into
`the PDA by a variety of methods including a tableteand-
`stylus, an input microphone, a keypad, etc.
`Because the natural language processor first analyzes
`larger substrings of an input string and then reduces the
`size of the substrings, natural language input is more
`quickly and reliably processed and its meaning deter-
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`4O
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`mined. In addition, the present invention uses three
`dynamic natural language processors in succession to
`allow greatly increased sensitivity to the context of
`natural language input and enhanced capability in inter-
`preting the input.
`These and other advantages of the present invention
`will become apparent to those skilled in the art upon a
`reading of the following specification of the invention
`and a study of the several figures of the drawing.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a block diagram of a pen-based computer
`system in accordance with the present invention;
`FIG. 2 is a top plan view of the pen-based computer
`system of FIG. 1;
`FIG. 3 is a table illustrating the method of examining
`substrings of the present invention;
`FIG. 4 is a flow diagram illustrating the method of
`processing natural language of the present invention;
`FIG. 5 is a flow diagram illustrating the step of devel-
`oping a string of FIG. 4;
`FIG. 6 is a table illustrating a hierarchy of mapping
`routines used in the present invention;
`FIG. 7 is a flow diagram illustrating the step of ob—
`taining a substring of FIG. 4;
`FIG. 7a is a table showing the contents of the matrix
`HITARRAY;
`FIG. 8 is a flow diagram illustrating the step of re-
`moving a substring and storing a mapping of FIG. 4;
`FIG. 9 is a phrase look-up table used for the phrasal
`processor of the present invention;
`FIG. 10 is a pattern look-up table used for the pattern
`processor of the present invention;
`FIG. 11 is a type frame illustrating a database query
`processor of the present invention;
`FIG. 12 is a task template used for determining a task
`in the present invention; and
`FIG. 13 is a flow diagram illustrating the determine
`task and perform task steps of FIG. 4.
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`
`The present invention is well suited for pointer—based
`computer systems such as the pen-based, pen-aware and
`mouse controlled systems that are currently popular.
`The present invention is also well suited for computer
`systems implementing voice input and speech recogni-
`tion. For the purposes of illustration, the invention will
`be described in connection with a pen-based system
`incorporating voice input. However, the present inven-
`tion is also suitable for other types of computer systems,
`such as mainframe systems, keyboard based systems,
`etc.
`
`As shown in FIG. 1, a pen—based computer system 10
`in accordance with the present invention includes a
`central processing unit (CPU) 12, read only memory
`(ROM) 14, random access memory (RAM) 16, input-
`/output (I/O) circuitry 18, and a display assembly 20.
`The pen-based computer system 10 may also optionally
`include a mass storage unit 22, a microphone amplifier
`23, a microphone 25, a keypad (or keyboard) 24, a serial
`port 26, an infrared (I/R) port 28, a speaker amplifier
`27, a speaker 29, and a clock 30.
`The CPU 12 is preferably a commercially available,
`single chip microprocessor. While CPU 12 can be a
`complex instruction set computer (CISC) chip,
`it
`is
`preferable that CPU 12 be one of the commercially
`available, reduced instruction set computer (RISC)
`
`SAMSUNG EX. 1014
`
`SAMSUNG EX. 1014
`
`

`

`5,434,777
`
`5
`chips which are known to be of generally higher perfor-
`mance than CISC chips. CPU 12 is coupled to ROM 14
`by a unidirectional data bus 32. ROM ‘14 preferably
`contains the basic operating system for the pen-based
`computer system 10. CPU 12 is connected to RAM 16
`by a bi-directional data bus 34 to permit the use of RAM
`16 as scratch pad memory. ROM 14 and RAM 16 are
`also coupled to CPU 12 by appropriate control and
`address busses, as is well known to those skilled in the
`art. CPU 12 is coupled to the I/O circuitry 18 by bi-
`directional data bus 36 to permit data transfers with
`peripheral devices.
`I/O circuitry 18 preferably includes a number of
`latches, registers and direct memory access (DMA)
`controllers. The purpose of I/O circuitry 18 is to pro-
`vide an interface between CPU 12 and such peripheral
`devices as display assembly 20, mass storage 22, ampli-
`fier 23, keypad 24, serial port 26, FR port 28, and ampli-
`fier 27.
`
`Display assembly 20 of pen-based computer system
`10 is both an input and an output device. Accordingly,
`it is coupled to I/O circuitry 18 by a bi-directional data
`bus 38. When operating as an output device, the display
`assembly 20 receives data from I/O circuitry 18 via bus
`38 and displays that data on a suitable screen. The
`screen for display assembly 20 is preferably a liquid
`crystal display (LCD) of the type commercially avail-
`able from a variety of vendors. The input device of
`display assembly 20 is preferably a thin, clear membrane
`which covers the LCD display and which is sensitive to
`the position of a stylus 38 on its surface. With such a
`structure, the membrane of the display assembly 20 can
`serve as an input “tablet.” These position sensitive
`membranes are also readily available on the commercial
`market. Alternatively, other types of tablets can be
`used, such as inductively coupled tablets. Combination
`display assemblies such as display assembly 20 which
`include both the LCD and the input membrane are
`commercially available from such vendors as Scriptel
`Corporation of Columbus, Ohio.
`Some type of mass storage 22 is generally considered
`desirable. Mass storage 22 can be coupled to I/O cir-
`cuitry 18 by a bi-directional data bus 40. However, the
`mass storage 22 can be eliminated by providing a suffi-
`cient amount of RAM 16 to store user application pro-
`grams and data. In that case, the RAM 16 can be pro-
`vided with a backup battery to prevent the loss of data
`even when the pen—based computer system 10 is turned
`off. However,
`it is generally desirable to have some
`type of long term mass storage 22 such as a commer-
`cially available miniature hard disk drive, nonvolatile
`memory such as flash memory, battery backed RAM, a
`PCMCIA card, or the like.
`Microphone amplifier 23 is coupled to I/O circuitry
`by bus 41 and includes well-known components which
`convert a speech signal input in microphone 25 to an
`analog signal, such as amplifiers, preamplifiers, etc.
`Amplifier block 23 can also include components which
`convert the analog signal to digital signals that can be
`used with CPU 12, such as analog to digital converters
`(ADC’s). The recognition of words spoken by a user
`can be implemented in software executed by CPU 12,
`and is well known to those skilled in the art.
`The keypad 24 can comprise an array of mechanical
`buttons or switches coupled to I/O circuitry 18 by a
`data bus 42. Alternatively, keypad 24 can comprise an
`entire, standard QWERTY keyboard. In the present
`embodiment, a separate keypad 24 is not used in favor of
`
`6
`a “pseudo” keypad 24’. This “pseudo” keypad 24' com-
`prises “button” areas which are associated with a bot-
`tom edge of the tablet membrane that extends beyond
`the lower edge of the LCD display. These button areas
`are defined by a printed or silk-screened icons which
`can be seen through the transparent membrane of the
`input tablet. When the “buttons” are selected by engag-
`ing the stylus 38 with the membrane over these printed
`icons, the membrane senses the pressure and communi—
`cates that fact to the CPU 12 via data bus 38 and I/O 18.
`An example of pseudo keypad 24’ is shown in FIG. 2.
`Serial port 26 is coupled to I/O circuitry by a bi-
`directional bus 44. The serial port 26 can be used to
`couple the CPU to external devices and networks.
`Infrared (I/R) port 28 is coupled to I/O circuitry by
`a bi-directional bus 46. The UK port can be used for
`outgoing information (e.g. to control a printer or some
`other external device, or to communicate with other
`computer systems) or for incoming information from
`other computers or devices.
`Speaker amplifier 27 is coupled to I/O circuitry by a
`bus 47. Amplifier 27 is used to drive a speaker 29 with
`signals output by CPU 12 and can also include compo—
`nents such as filters, specialized sound chips, etc.
`Speaker 29 can be used for audio output such as sound
`effects, synthesized voice, and other user feedback.
`Clock 30 preferably comprises a real-time clock to
`provide real-time information to the system 10. Alterna—
`tively, clock 30 can simply provide regular clock pulses
`to, for example, an interrupt port of the CPU 12 which
`can count the clock pulses to provide the time function.
`However, this alternative clock embodiment tends to be
`wasteful of CPU processing power. Clock 30 is coupled
`to CPU 12 by a data bus 48.
`In operation, information is input into the pen-based
`computer system 10 by “writing” on the screen of dis-
`play assembly 20 with the stylus 38. Information con-
`cerning the location of the stylus 38 on the screen of the
`display assembly 20 is input into the CPU 12 via data
`bus 38 and I/O circuitry 18. Typically, this information
`comprises the Cartesian (i.e. x & y) coordinates of a
`pixel of the screen of display assembly 20 over which
`the tip of the stylus is positioned. Commercially avail-
`able combination display assemblies such as the afore-
`mentioned assemblies available from Scriptel Corpora-
`tion, Sharp, and others include appropriate circuitry to
`provide the stylus location information as digitally en—
`coded data to the I/O circuitry of the present invention.
`The CPU 12 then processes the data under control of an
`operating system and possibly an application program
`stored in ROM 14, RAM 16, or mass storage 22. The
`CPU 12 next produces data which is transferred to the
`display assembly 20 via I/O circuitry 18 and data bus 38
`to produce appropriate images on the screen portion of
`the display assembly 20.
`In FIG. 2, the pen-based computer system 10 of FIG.
`1 is shown housed within a generally rectangular enclo-
`sure 50. The CPU 12, ROM 14, RAM 16, I/O circuitry
`18, and clock 26 are preferably fully enclosed within the
`enclosure 50. The display assembly 20 (FIG. 1)
`is
`mostly enclosed within the enclosure 50