US6466901B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multi-language document search and retrieval system
Assignee: Apple Inc
•
Filing: 1998-11-30
•
Granted: 2002-10-15
•
Expires: 2018-11-30
Abstract
Abstract A multi-lingual indexing and search system performs tokenization and stemming in a manner which is independent of whether index entries and search terms appear as words in a dictionary. During the tokenization phase of the process, a string of text is separated into individual word tokens, and predetermined types of tokens are eliminated from further processing. The stemming phase of the process reduces words to grammatical stems by removing known word-endings associated with the various languages to be supported. Known word endings are removed from the word tokens without any effort to guarantee that the remaining stem is contained in a dictionary. In a preferred implementation, the stemming process is only applied to nouns.
Inventors
- 👤 Wayne Loofbourrow
- 👤 David Cásseres
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 00:31
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/33; G06F16/3331; G06F16/3332; G06F16/3335; G06F16/31; G06F16/313; G06F40/00; G06F40/20; G06F40/268; G06F40/279; G06F40/284; G06F40/289
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
77 words
A method for indexing textual content in any of a plurality of languages for searching purposes, comprising the steps of: separating a string of text into individual word tokens; reducing the word tokens to grammatical stems by removing word endings which are associated with any one or more of the languages, without regard to whether the remaining stem is a recognized word in any combination of the plurality of languages; and storing the stems in an index.
Claim 2
Independent Claim
77 words
A method for indexing textual content in any of a plurality of languages for searching purposes, comprising the steps of: separating a string of text into individual word tokens; reducing the word tokens to grammatical stems by removing word endings which are associated with any one or more of the languages, without regard to whether the remaining stem is a recognized word in any combination of the plurality of languages; and storing the stems in an index.
Claim 3
Dependent Claim
23 words
The method of claim 1 wherein the word endings which are removed are limited to only those endings which are associated with nouns.
Claim 4
Dependent Claim
22 words
The method of claim 1 wherein a word ending is not removed if the resulting stem is less than a predetermined length.
Claim 5
Dependent Claim
12 words
The method of claim 3 wherein said predetermined length is four characters.
Claim 6
Dependent Claim
17 words
The method of claim 1 wherein the reducing step is only carried out once per word token.
Claim 7
Dependent Claim
42 words
The method of claim 5 wherein said reducing step is performed by first examining each word token for the longest known endings, and examining the token for successively shorter endings until a known ending is identified in the word token and removed.
Claim 8
Dependent Claim
48 words
The method of claim 1 further including the step of disregarding stopwords during said removing and storing steps, wherein stopwords are words which occur with relatively high frequency in at least one of said languages and which are not also significant nouns in another one of said languages.
Claim 9
Independent Claim
177 words
A method for searching for documents which may contain text in any of a plurality of languages, comprising the steps of: separating text in each document to be searched into individual word tokens; reducing the word tokens to grammatical stems by removing word endings which are associated with any one or more of the languages, without regard to whether the remaining stem is a recognized word in any of the plurality of languages; storing the stems in an index which identifies the documents in which words containing the stems appeared; receiving a query containing a string of text to be searched; parsing the string of text into individual word tokens; reducing the word tokens from said query to grammatical stems by removing word endings which are associated with any one or more of the languages, without regard to whether the remaining stem is a recognized word in any of the plurality of languages; searching the index for entries which match the stems obtained from said query; and displaying an identification of the documents which contained matching entries.
Claim 10
Independent Claim
177 words
A method for searching for documents which may contain text in any of a plurality of languages, comprising the steps of: separating text in each document to be searched into individual word tokens; reducing the word tokens to grammatical stems by removing word endings which are associated with any one or more of the languages, without regard to whether the remaining stem is a recognized word in any of the plurality of languages; storing the stems in an index which identifies the documents in which words containing the stems appeared; receiving a query containing a string of text to be searched; parsing the string of text into individual word tokens; reducing the word tokens from said query to grammatical stems by removing word endings which are associated with any one or more of the languages, without regard to whether the remaining stem is a recognized word in any of the plurality of languages; searching the index for entries which match the stems obtained from said query; and displaying an identification of the documents which contained matching entries.
Claim 11
Dependent Claim
42 words
The method of claim 8 further including the step of displaying a matching entry along with the identification of the document in which it appears, wherein a stem is displayed together with an ending to present a full word to the user.
Claim 12
Dependent Claim
47 words
The method of claim 8 wherein a stem is stored in said index together with the ending that was removed from a word token to form that stem, and an entry in the index that matches a stem from a query is displayed with said stored ending.
Claim 13
Independent Claim
136 words
A system for searching for documents which may contain text in any of a plurality of languages, comprising: a tokenizer which receives text strings from documents to be searched and user queries, and separates the text into individual word tokens; a stemmer which reduces the word tokens to grammatical stems by removing word endings which are associated with any one or more of the plurality of languages, without regard to whether the remaining stem is a recognized word in any of the plurality of languages; an index which stores the stems from documents and identifies the documents in which words containing the stems appeared; a search engine which searches the index for entries which match the stems obtained from user queries; and a display system which displays an identification of the documents which contain matching entries.
Claim 14
Independent Claim
136 words
A system for searching for documents which may contain text in any of a plurality of languages, comprising: a tokenizer which receives text strings from documents to be searched and user queries, and separates the text into individual word tokens; a stemmer which reduces the word tokens to grammatical stems by removing word endings which are associated with any one or more of the plurality of languages, without regard to whether the remaining stem is a recognized word in any of the plurality of languages; an index which stores the stems from documents and identifies the documents in which words containing the stems appeared; a search engine which searches the index for entries which match the stems obtained from user queries; and a display system which displays an identification of the documents which contain matching entries.
Claim 15
Dependent Claim
44 words
The system of claim 11 wherein said display system displays a matching entry from said index along with the identification of the document in which it appears, and a stem is displayed together with an ending to present a full word to the user.
Claim 16
Dependent Claim
47 words
The system of claim 12 wherein a stem is stored in said index together with an ending that was removed from a word token to form that stem, and an entry in the index that matches a stem from a query is displayed with said stored ending.
Claim 17
Dependent Claim
27 words
The system of claim 12 wherein the ending that is displayed with the stem is an ending that was removed from a word token in the query.
Claim 18
Dependent Claim
67 words
A computer-readable medium containing a program which executes the steps of: separating a string of text into individual word tokens; reducing the word tokens to grammatical stems by removing word endings which are associated with any one or more of the languages, without regard to whether the remaining stem is a recognized word in any of the plurality of languages; and storing the stems in an index.
Claim 19
Dependent Claim
67 words
A computer-readable medium containing a program which executes the steps of: separating a string of text into individual word tokens; reducing the word tokens to grammatical stems by removing word endings which are associated with any one or more of the languages, without regard to whether the remaining stem is a recognized word in any of the plurality of languages; and storing the stems in an index.
Claim 20
Dependent Claim
24 words
The computer-readable medium of claim 15 wherein the word endings which are removed are limited to only those endings which are associated with nouns.
Claim 21
Dependent Claim
23 words
The computer-readable medium of claim 15 wherein a word ending is not removed if the resulting stem is less than a predetermined length.
Claim 22
Dependent Claim
43 words
The computer-readable medium of claim 15 wherein said reducing step is performed by first examining each word token for the longest known endings, and examining the token for successively shorter endings until a known ending is identified in the word token and removed.
References Cited (Backward Citations)
US5276616A
Cited
US5301109A
Cited
US5369577A
Cited
US5475587A
Cited
US5594641A
Cited
US6038527A
Cited
US6006221A
Cited
US5983171A
Cited
US6101492A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-10-14 | 2006-04-15 | 2006-10-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-10-14 | 2010-04-15 | 2010-10-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-10-14 | 2014-04-15 | 2014-10-15 | $7700.00 | Window Closed / Lapsed |