llllll|||||||||||lllllllllllllllliilliilllllllllllll||||||l|ll|||ll||li||ll
`US005625814A
`
`United States Patent
`[19]
`[11] Patent Number:
`5,625,814
`
`Luciw
`[45] Date of Patent:
`Apr. 29, 1997
`
`[54] METHOD AND APPARATUS FOR
`PROCESSING NATURAL LANGUAGE WITH
`A HIERARCHY OF MAPPING ROUTINES
`Inventor: William W. Luciw, Morgan Hill, Calif.
`
`[75]
`
`FOREIGN PATENT DOCUMENTS
`0441039742
`3/1991 European Pat. on.
`..................... 3/23
`932164 of 1989
`Japan I
`OTHER PUBLICAHONS
`
`[73] Assignee: Apple Computer, Inc., Cupertino,
`Calif.
`
`[21] Appl. No.2 441,225
`.
`[22] Ffled:
`
`May 15’ 1995
`’
`Related US. Application Data
`[60] Division of Ser. No. 215,064, Mar. 18, 1994, Pat. No.
`
`Aahmed et a1, “Intelligent Natural Language Query Proces-
`501i”, TENCON ’89, Fourth lEEE Region 10 International
`Conference 22—24 Nov. 89, pp. 47—49.
`Beck et al, “Integratiang Natural Language. Query Process—
`ing, and Semantic Data Models”, COMCON Spring ’90.
`[SEE Computer Society International Conference, 1990. PP.
`538—543’ 26 Bah—2 Man 1990'
`(List continued on next page.)
`
`
`
`.................... G06F 17/30
`__ 395/605; 364/1316 1;
`364/282.1
`,
`[58] Field of Search .............................. 395/600; 364/419
`7
`References Cited
`
`[56]
`
`Primary Emminer_wayne Amsbury
`5,434,777, which is a continuation-in-part of Sen No.
`.
`.
`99,361, Jul. 30, 1993, Pat. No. 5,477,447, and a coutiuua—
`tion—in-part of Ser. No. 889,225, May 27, 1992, Pat No. Mame» Agent, 0' Firm—11101911811 Beyer & Weaver
`543902“:
`[57]
`ABSTRACT
`......
`[51]
`Int. Cl.
`.
`[52] U.S.C1. .......
`A method and apparatus for processmg natural language and
`deducing meaning from a natural language input character—
`.
`.
`.
`.
`ized by the ste s of (a)rece1v1ng an ordered stung of word
`objects having, mm language meaning. 0,) selecting a
`word window length, 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 repeated until only an unrecognized residual
`of the ordered string remains. The meaning of the substn'ng
`is analyzed by mapping 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 subslring when a
`previous mapping routine in the hierarchy cannot map the
`substring. A computer—implemented task is determined from
`the recognized substrings and performed by the computer
`system. The apparatus of the present invention 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
`395/68
`395/600 mm a “’wml’hone “9697198 SPEC?“ HIP“?
`20 Claims, 12 Drawing Sheets
`
`U-S- Pm DOCUMENTS
`6/1987 Schmmm ...............
`4,670,848
`364,513
`
`8/1987 Thompson et a1.
`4,688,195
`395/12
`4,713,775 12/1987 Scott et 91
`. 354/513
`
`. 364/419
`.
`4,736,296
`4/1988 Kalayama et a1.
`4,750,122
`6/1988 Kaji et al.
`..
`. 354/419
`
`4,785,413
`11/1988 Atsumi
`_ 364/900
`4,875,187
`10/1989 Smith .........
`. 364/900
`4,887,212 12/1989 Zamora et a1.
`. 364/419
`4,918,723
`4/1990 Iggulden et 31.
`. 379/100
`4,945,504
`7/1990 Nakama et a1.
`- 364/709
`4,953,106
`8/1990 Gansner et :11.
`364/521
`4,965,763 10/1990 Zamora ..........
`364/41919
`4,974,191
`11/1990 Amirghodsi
`364/900
`4,994,966
`2/1991 Hut/chins
`' 364,419
`gflemvephm[get
`'
`.
`rbe
`......
`4,1992 Lamar et 31. "
`..
`4/1992 Kayatama et a1.
`(List continued on next page.)
`
`
`
`
`
`,
`,
`5,103,498
`5,109,509
`
`
`
` mama: mmums muss
`m mewcw
`
`96
`0mm
`
`summu uNmes m
`
`
`
`
`as
`
`
`
`
`Na
`unxumwr
`(imam mstas'm'
`
`[.1
`
`1 mum5
`
`
`
`
` suasmns
`we. was my
`
`‘ mamu:05K
`same wan
`mvans
`
`10,
`
` six-lemme AND
`STORE vamc
`
`
`MICROSOFT CORP. EX. 1014
`
`Page 1 of 25
`
`MICROSOFT CORP. EX. 1014
`Page 1 of 25
`
`

`

`5,625,814
`Page 2
`
`Elofson, G. et 31.. “Delegation Technologies: Environmental
`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 Simula-
`tion 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. et al., “A Computational Model of an Intelligent
`Agent Who Talks with a Person,” Research Reports on
`Information Sciences, Series C, Apr. 1989, No. 92, pp. 1—18.
`Ratclifi‘e, 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 Wmdows Graphi—
`cal Environment,” version 3.0, Microsoft Press, copyright
`1985—1990, pp. 33—41 & 70—74.
`R. Wilensky et al., "Talking to UNIX in English: an Over-
`view of UC,” Communications of the ACM, Jun. 1984. Vol.
`27, No. 6.
`Tello, Ernest R., “Natural—Language Systems,” Mastering
`AI Tools and Techniques, Howard W. Sams & Company,
`1988.
`Knight, Kevin, & Rich, Elaine, “Heuristic Search,” Produc—
`tion Systems, Artificial Intelligence, 2nd ed., McGraw—Hill,
`Inc., 1983—1991.
`Miastkowski. Stan, “PaperWorks Makes Paper Intelligent,”
`Byte Magazine, Jun. 1992.
`Dickinson et al., “Palmtips: Tiny Containers for All Your
`Data,” PC Magazine, Mar. 1990, Vol. 9, p. 218(3).
`Bajarin, Tirn, “With Low End Launched, Apple Turns to
`Portable Future”, PC Week, Oct. 1990, Vol. 7, p. 153(1).
`Corporate Ladder, BLOC Pulishing Corp., 1991.
`Diagrammaker, Action Software, 1989.
`Diagram—Master. Ashton—Tate, 1989.
`Microsoft MS—DOS Operating System User’s Guide,
`Microsoft Corporation, 1982. pp. 4—1 to 4—16, 5—1 to 5—19.
`
`U.S. PATENT DOCUMENTS
`..
`6/1992 Ohtaki et a1.
`5,123,103
`395/161
`5,175,814 12/1992 Anick et a1.
`364/419.01
`5,237,502
`8/1993 White et al.
`395/600
`5,278,980
`1/1994 Pedetsen
`395/12
`5,282,265
`1/1994 Suda etal
`..... 364/419
`5,327,342
`7/1994 Roy ............
`364/419.13
`..
`5,357,431
`10/1994 Nakada et a].
`364/419.08
`5,369,575
`11/1994 Lamberti et al.
`.. 364/419.19
`5,369,577
`11/1994 Kadashevich et a1.
`364/419.13
`5,434,777
`7/1995 Luciw ................
`395/600
`5,442,780
`8/1995 Takanashi et a1
`
`364/419.08
`.
`5,477,451
`12/1995 Brown et a1.
`.......
`O’Connor, Rory J., “Apple Banking on Newton’s Brain”,
`San Jose Mercury News, Apr. 22, 1991.
`Hendrix, Gary G. and Walter. Brett A., "The Intelligent
`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—122.
`Goldberg, Cheryl, “IBM Drawing Assistant: Graphics for
`the EGA”, PC Magazine, Dec. 24, 1985, V01. 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.
`G1inerhStevens. 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 SmartForm Assis-
`tant).
`Berry, Deanne et al., Apr. 10, 1990 news release, Symantec,
`(announced new version of MORETM).
`
`
`
`MICROSOFT CORP. EX. 1014
`
`Page 2 of 25
`
`MICROSOFT CORP. EX. 1014
`Page 2 of 25
`
`

`

`US. Patent
`
`Apr. 29, 1997
`
`Sheet 1 of 12
`
`5,625,814
`
`OKON
`
`.vN
`
`Fan—Z.w><._mm_n_
`
`>4m2mmm<
`
`NNMESH—Ohm
`
`0V
`
`NZOIn—OEQE
`
`mm_n=u_n=2<
`
`D<n_>mv_
`
`.3,
`
`
`
`hEOn.._<_m_mw
`
`mmhmOmm5
`
`mu¥<mam
`
`mm_n=.._n=>_<
`
`NV
`
`WV
`
`9»
`
`Eu
`
`Ox_
`
`mm.
`
`ms
`
`Nu
`
`x0040
`
`Om.
`
`
`
`Wm.NM.
`
`m“3
`
`MICROSOFT CORP. EX. 1014
`
`Page 3 of 25
`
`MICROSOFT CORP. EX. 1014
`Page 3 of 25
`
`
`
`
`

`

`US. Patent
`
`Apr. 29, 1997
`
`Sheet 2 of 12
`
`5,625,814
`
`_|=ungn_w1tl_1_|31||_medal/lam p_m_a.t__
`
`'m I
`
`Chez Sovan
`
`MICROSOFT CORP. EX. 1014
`
`Page 4 of 25
`
`MICROSOFT CORP. EX. 1014
`Page 4 of 25
`
`

`

`US. Patent
`
`Apr. 29, 1997
`
`Sheet 3 of 12
`
`5,625,814
`
`72\
`
`/
`SUBSTRING
`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 r
`
`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
`
`LENGTH=6, POS=1
`
`LENGTH=6, POS=2
`
`LENGTH=6, POS=3
`
`Monday 12:30 pm at Chez Sovan
`
`LENGTH=6, POS=4
`
`Lunch with Bill
`
`with Bill Monday
`Bill Monday 12:30 /
`[Monday 12:30 pm]
`
`74
`
`[Lunch with]
`f Bill
`/
`[Bilfl
`
`76
`
`78
`
`at Chez Sovan
`
`at
`at Chez
`[Chez Sovan]
`\
`
`at
`
`78
`
`80}
`
`{figure 3
`
`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
`
`LENGTH=1, POS=1
`
`MICROSOFT CORP. EX. 1014
`
`Page 5 of 25
`
`MICROSOFT CORP. EX. 1014
`Page 5 of 25
`
`

`

`US. Patent
`
`Apr. 29, 1997
`
`Sheet 4 of 12
`
`5,625,814
`
`80
`
`\ ® 7151‘” 4
`
`82
`
`‘
`
`STRING
`
`NWORDS
`
`90
`
`ARRANGE NMAP
`MAPPING ROUTINES
`
`IN HIERARCHY
`
`is NWORDS?
`
`N)
`
`ANALYZED?
`
`2 TRING FULLY
`
`
`MARK HITARRAY
`
`(LENGTH, POS) AS "HIT"
`
`
`
`
`
` SUBSTRING
`
`102
`
`MAPS USING MAP
`
`ROUTINE(J)?
`
`104
`
` REMOVE
`SUBSTRING AND
`STORE MAPPING
`
`DETERMINE TASK
`BASED UPON
`MAPPINGS
`
`108
`
`PERFORM TASK
`
`110
`
`® 1 12
`
`MICROSOFT CORP. EX. 1014
`
`Page 6 of 25
`
`MICROSOFT CORP. EX. 1014
`Page 6 of 25
`
`

`

`US. Patent
`
`Apr. 29, 1997
`
`Sheet 5 of 12
`
`5,625,814
`
`118
`
`figure 5
`
`120
`
`VINPUT
`
`DELINEATE A
`STRING FROM
`RECOGNIZED
`
`122
`
`126
`
`\A
`
`128
`
`A/
`
`/
`MAPPING R
`
`130
`
`TIN
`
`LEVE
`
`132
`
`'
`
`/
`*
`COMPUTATIONAL
`w
`
`1
`
`2
`
`3
`
`PHRASAL PROCESSOR
`
`LOW
`
`PATTERN PROCESSING
`
`MEDIUM
`
`DATABASE PROCESSING
`
`HIGH
`
`figure 6
`
`MICROSOFT CORP. EX. 1014
`
`Page 7 of 25
`
`MICROSOFT CORP. EX. 1014
`Page 7 of 25
`
`

`

`US. Patent
`
`Apr. 29, 1997
`
`Sheet 6 of 12
`
`5,625,814
`
`(96
`
`®
`
`1 38
`YES
`
`1 40
`
`LENGTH =
`N ULL
`
`N0
`
`CHECK HITARRAY
`MATRIX FOR POS
`AND SUBPHRASE
`
`142
`
`
`
`
`156
`
`POS=P08+1
`
`
`
`
`
`POS+LENGTH
`> NWORDS+1?
`
`
`
`NO
`
`1
`
`YES
`
`NO
`
`158
`
`YES
`
`POS = 1
`LENGTH =
`
`160 LENGTH - 1
`
`‘
`
`'
`
`1 54
`
`SUBSTRING = STRING (POS,
`LENGTH)
`-
`
`figure 7
`
`MICROSOFT CORP. EX. 1014
`
`Page 8 of 25
`
`MICROSOFT CORP. EX. 1014
`Page 8 of 25
`
`

`

`US. Patent
`
`Apr. 29, 1997
`
`Sheet 7 of 12
`
`5,625,814
`
`147\
`
`148
`
`HITARRAY 15o
`
`152
`
`POSITION
`
`LENGTH
`
`
`VALUE
`
`\lmm-hmm-nooxloamhwm—ncomxxmm-bwma
`
`AN—‘OJN—k-P-CON—l-
`
`WWwCOOJOJCDNNNNNNNN—L—L—l—l—L—L—L—b—h
`
`mmmxlxlxlcnouovo:
`
`OOOOOOOOOOOOOOOOOOOOOOOO
`OOOOOOOOOO°.'
`
`figure 7a
`
`MICROSOFT CORP. EX. 1014
`
`Page 9 of 25
`
`MICROSOFT CORP. EX. 1014
`Page 9 of 25
`
`

`

`US. Patent
`
`Apr. 29, 1997
`
`Sheet 8 of 12
`
`5,625,814
`
`104
`
`STORE MAPPING, MAPPED
`SUBSTRING OBJECT AND
`REMOVE SUBSTRING
`
`164
`
`figure 8
`
`NWORDS = NWORDS - #
`WORDS IN REMOVED
`SUBSTHING
`
`166
`
`MARK
`
`HITARRAY(LENGTH,POS)
`AS "POSSIBLE"
`
`168
`
`220
`222
`
`FILL IN TASK
`TEMPLATE
`
`figure 13
`
`
`
`
`
`
`
`CAN TASK BE
`EXECUTED?
`
`EXECUTE TASK
`
`226
`
`MICROSOFT CORP. EX. 1014
`
`Page 10 of 25
`
`MICROSOFT CORP. EX. 1014
`Page 10 of 25
`
`

`

`US. Patent
`
`Apr. 29, 1997
`
`Sheet 9 of 12
`
`5,625,814
`
`172
`
`\
`
`figureB
`
`PHRASE LOOK—UP TABLE
`
`PHRASES
`
`INSTANCES
`
`
`
`
`
`1 74
`
`<COMPANY— 1>
`
`< FOOD-1>
`
`
`176
`<COUNTRY— 1 > "ICELAND"
`"ISAAC"
`<PERSON~1>
`<PERSON-2>
`
`
`<PERSON-3>
`
`
`
` "ITALY" <COUNTRY-2>
`
`
`
`
`
`<MEET— 1>
`<MEET—2>
`
`"LUNCH WITH"
`"SCHEDULE
`LUNCH WITH"
`
`
`
`
`
`180
`
` "ZORRO"
`<HERO— 1 >
`
`178
`
`<MEET— 1 >
`
`
`
`
`"LUNCH WITH"
`
`MICROSOFT CORP. EX. 1014
`
`Page 11 of 25
`
`MICROSOFT CORP. EX. 1014
`Page 11 of 25
`
`

`

`US. Patent
`
`Apr. 29, 1997
`
`Sheet 10 of 12
`
`5,625,814
`
`figure 10
`
`PATFERN LOOK—UP TABLE
`PATTERN
`INSTANCE /
`
`184
`
`
`
`ll
`
`
`<Timeslot>
`
`<I‘imeslot>
`
`186
`
`
`
`<num>
`pm
`
`<num> .
`"°" <num>
`
`
`
`(1‘IMESLOT>
`
`1
`
`
`
`"12:30 pm"
`12:30:00
`
` TIME = 1015
`LOCATION (12,7-12)
`
`MICROSOFT CORP. EX. 1014
`
`Page 12 of 25
`
`MICROSOFT CORP. EX. 1014
`Page 12 of 25
`
`

`

`US. Patent
`
`Apr. 29, 1997
`
`Sheet 11 of 12
`
`5,625,814
`
`<PERSON>
`
`
`
`
`
`
`
`NAME:
`BIRTHDAY:
`TELEPHONE:
`FAX:
`ADDRES S :
`HEIGHT:
`WEIGHT:
`
`192
`
`‘K/’
`
`
`
`INSTANCES: <PERSON-1> <PERS ON—2> <PERS ON-3>
`
`
`
`1946
`
`\
`
`
`
`NAME: BILL JONES
`
`1941N
`
`
`<PERSON—2> <BILL-2>
`NAME: BILL RIKER
`
`<PERSON- l > <BILL-1>
`
`NAME: BILL SETAG
`BIRTHDAY: NULL
`TELEPHONE: 408-555-1212
`FAX: NULL
`
`
`
`196
`
`194a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ADDRESS: 123 MAIN STREET,
`CUPERTINO, CA
`HEIGHT: NULL
`WEIGHT: NULL
`
`
`
`<RESTAURANT— 1 >
`
`
`
`{Figure 11
`
`200
`
`/
`
`RESTAURANT: CI-IEZ SOVAN
`ADDRESS: 436 STEVENS CREEK BLVD.
`CUPERTINO, CA.
`
`RATING: 4 STAR
`
`MICROSOFT CORP. EX. 1014
`
`Page13of25
`
`MICROSOFT CORP. EX. 1014
`Page 13 of 25
`
`

`

`US. Patent
`
`Apr. 29, 1997
`
`Sheet 12 0f 12
`
`5,625,814
`
`208
`
`\
`
`210
`
`212
`
`214
`
`
`
`
`
`
`
`Scheduling
`
`Meet
`
`
`
`
`
`
`
`
`
`
` a
`
`6 7 3
`
`10
`
`
`
`
`
`
`
`
`Fax#
`Place
`Fax
` Print
`
`
`
`Calling
`
`Call
`
`
`
`
`
`
`
`
`
`(figure 12
`
`MICROSOFT CORP. EX. 1014
`
`Page14of25
`
`MICROSOFT CORP. EX. 1014
`Page 14 of 25
`
`

`

`5,625,814
`
`1
`METHOD AND APPARATUS FOR
`PROCESSING NATURAL LANGUAGE WITH
`. A HIERARCHY 0F MAPPING ROUTINES
`
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`
`This application is a divisional of application Ser. No.
`08/215,064 filed on Mar. 18, 1994, now U.S. Pat. No.
`S.434,777, which is a continuation—in—part of parent patent
`applications Ser. No. 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 U.S. Pat. No. 5,390,281, and Ser. No.
`08/099,861, filed Jul. 30, 1993 on behalf of Luciw et al.,
`entitled, “Method and Apparatus for Providing Computer-
`Implemented Assistance,” now U.S. Pat. No. 5.477.477
`which are hereby incorporated by reference herein.
`BACKGROUND OF THE INVENTION
`
`invention relates generally to computer
`The present
`systems, and more particularly to methods for processing
`natural language input from users of computer systems.
`Computerized personal organizers are becoming increas-
`ineg 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 provided by personal
`organizers which are relatively inexpensive, small, and
`lightweight (i.e. portable). Personal organizers are available
`from such companies as Sharp and Casio of Japan.
`A relativer new form of computer, the pen-based com-
`puter 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 com-
`puter system is typically a small, hand-held computer where
`the primary method for inputting data includes a “pen” or
`stylus. Apen-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
`assembly senses the position of the tip of a stylus on the
`viewing 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 display assembly presents
`computer-generated images on the screen.
`The dual-function displays of pen-based computer sys-
`tems permit users to operate the computers as computerized
`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 generates 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.
`including pen-based computer
`Computer systems,
`systems, can also incorporate speech recognition. Although
`still mostly in the developmental stage, speech recognition
`has many potential uses in computer systems. For example,
`in a portable pen—based computer, speech input and recog—
`nition can be used to conveniently record dictated mes sages
`
`2
`or other spoken documents 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.c. an “utterance.”
`Natural language is written or spoken input that is in a
`natural form that a person would use as if speaking 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 interface
`with a computer system using well—known language. One
`area in computer systems which is particularly well—adapted
`for natural language input is computerized assistance. Com—
`puters systems that use computerized assistance deduce or
`hypothesize a user’s intent and automatically provide a
`service based on the deduced intent. For example, a tasks
`such as printing a document or scheduling an appointment
`can be implemented 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 ditficult due to the complex and shifting “rules” of
`human natural language. A user may input a natural lan-
`guage 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 recog-
`nize the meaning of the entire phrase. However, by recog—
`nizing 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. Along command is typically processed by match—
`ing 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 database.
`The abovementioned processes have typically been used
`with a fixed set of rules to interpret natural language. An a
`priori specification of known linguistic structures and their
`meaning is used to perform semantic interpretation. Each of
`the abovementioned processes has limitations in versatility
`and the time required to match a phrase. Natural language
`processing of the prior art has thus been inefiicient and rigid
`in its ability to recognize the meaning of natural language
`utterances.
`
`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 according to a dynamic set
`of rules and data.
`
`SUMMARY OF THE INVENTION
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`65
`
`The present invention provides a natural language pro-
`cessor for the user of a computer system. The method of the
`present invention analyzes portions or substrings of a natural
`language input string to determine the meaning of the input
`
`MICROSOFT CORP. EX. 1014
`
`Page 15 of 25
`
`MICROSOFT CORP. EX. 1014
`Page 15 of 25
`
`

`

`5,625,814
`
`3
`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
`identifying 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 repeated
`until only an unrecognized residual of the ordered string
`remains. The ordered string is preferably received from
`strokes entered by a stylus on a display screen of apen-based
`computer or from a microphone receiving audible speech
`input. The step of analyzing the meaning of the substring
`preferably includes mapping 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
`substring. The method preferably further includes a step of
`determining a computer-implemented task specified by the
`ordered string using the recognized substrings and perform-
`ing the computer-implemented task.
`A method for recognizing meanings of natural language
`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. 3 step of attempting to map the portion into a
`database according to a pattern mapping routine is accom-
`plished. 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 tablet-and-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 determined. In addition.
`the present invention uses three dynamic natural language
`processors in succession to allow greatly increased sensi-
`tivity to the context of natural language input and enhanced
`capability in interpreting 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.
`
`4
`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 developing
`a string of FIG. 4;
`FIG. 6 is a table illustrating a hierarchy of mapping
`routines used in the present invention;
`FIG. 7A is a flow diagram illustrating the step of obtaining
`a substring of FIG. 4;
`FIG. 7B is a table showing the contents of the matrix
`HITARRAY;
`FIG. 8 is a flow diagram illustrating the step of removing
`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 ENIBODIMENT
`
`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 recognition. For the
`purposes of illustration. the invention will be described in
`connection with a pen—based system incorporating voice
`input However, the present invention 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 (IIO) cir—
`cuitry 18. and a display assembly 20. The pen-based com-
`puter 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) chips which are known to
`be of generally higher performance 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
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`MICROSOFT CORP. EX. 1014
`
`Page 16 of 25
`
`MICROSOFT CORP. EX. 1014
`Page 16 of 25
`
`

`

`5,625,814
`
`5
`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 circuin 18 is to provide an interface between
`CPU 12 and such peripheral devices as display assembly 20,
`mass storage 22, amplifier 23, keypad 24, serial port 26, I/R
`port 28. and amplifier 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 available 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 avail-
`able 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 circuitry 18
`by a bi-directional data bus 40. However, the mass storage
`22 can be eliminated by providing a sufficient amount of
`RAM 16 to store user application programs and data. In that
`case. the RAM 16 can be provided 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
`commercially available miniature hard disk drive, nonvola-
`tile 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, stan—
`dard QWERTY keyboard In the present embodiment, a
`separate keypad 24 is not used in favor of a “pseudo” keypad
`24'. This “pseudo” keypad 24' comprises “button” areas
`which are associated with a bottom 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 transpar-
`ent membrane of the input tablet. When the “buttons” are
`selected by engaging the stylus 38 with the membrane over
`these printed icons, the membrane senses the pressure and
`communicates 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.
`
`6
`Infrared (I/R) port 28 is coupled to I/O circuitry by a
`bi-directional bus 46. The HR 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/Opircuitry by a bus
`47. Amplifier 27 is used to drive a speaker 29 with signals
`output by CPU 12 and can also include components 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 pro-
`vide real-time information to the system 10. Alternatively.
`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 display
`assembly 20 with the stylus 38. Information concerning 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 Car-
`tesian (i.e. x & y) coordinates of a pixel of the screen of
`display assembly 20 over which th