Multi-language document search and retrieval system

• US 7,174,290 B2
• Filed: 07/07/2003
• Issued: 02/06/2007
• Est. Priority Date: 11/30/1998
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Loofbourrow, Wayne, Casseres, David
• Primary Examiner(s): MCFADDEN, SUSAN IRIS
• Application Number:
  US10/612,936
• Publication Number:
  US 20040006456A1
• Time in Patent Office: 1,310 Days
• Field of Search: None
• US Class Current: 704/9
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/3335 Syntactic pre-processing, e.g. stopword elimination, stemming
• CPC Class Codes: G06F 40/268 Morphological analysis
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

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.

Claims

1. A computer-readable medium containing a computer program for searching for documents that may contain text in any of a plurality of languages, wherein the computer program performs 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 that 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 that identifies the documents in which words containing the stems appeared;

parsing a query containing a string of text into individual word tokens;

reducing the word tokens from the query to grammatical stems by removing word endings that 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 that match the stems obtained from the query; and

displaying an identification of the documents that contained matching entries.

2. The computer-readable medium of claim 1, wherein the computer program performs 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.

3. The computer-readable medium of claim 1, wherein a stem is stored in the 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 the stored ending.

4. A system for searching for documents which may contain text in any of a plurality of languages, comprising:

a tokenizer which separates text in each document to be searched 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 languages, without regard to whether the remaining stem is a recognized word in any of the plurality of languages;

an indexer which stores the stems in an index and which identifies the documents in which words containing the stems appeared;

a search engine which parses a query containing a string of text into individual word tokens, reduces 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, and searches the index for entries which match the stems obtained from said query; and

a display which displays an identification of the documents which contained matching entries.

5. The system of claim 4 wherein the display displays a matching entry along with the identification of the document in which it appears, and wherein a stem is displayed together with an ending to present a full word to the user.

6. The system of claim 4 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.

7. A system for determining a relevance ranking for documents that may contain text in any of a plurality of languages, comprising:

a tokenizer that parses a string of text in a received query into individual word tokens;

a stemmer that reduces the word tokens from the query to grammatical stems by removing word endings that 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;

a search engine that searches an index for entries that match the stems obtained from the query, wherein the index identifies the documents in which words containing the stems appeared, retrieves a summary for each document identified as containing matching entries, separates text in each summary into individual word tokens, reduces the word tokens from each summary to grammatical stems by removing word endings that 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 compares the stems obtained from the query with the stems obtained from each summary to determine the relevance ranking for each document identified as containing matching entries; and

a display that displays said relevance rankings.

8. The system of claim 7, wherein said display displays an identification of the documents that contained matching entries, in order of relevance ranking.

9. The system of claim 8, wherein said display displays 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.

10. The system of claim 8, wherein a stem is stored in the 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 the stored ending.

11. The system of claim 7, wherein the word endings that are removed are limited to those ending that are associated with nouns.

12. The system of claim 7, wherein a word ending is not removed if the resulting stem is less than a predetermined length.

13. The system of claim 12, wherein the predetermined length is four characters.

14. The system of claim 7, wherein the stemmer performs the reducing step once per word token.

15. The system of claim 14, wherein the stemmer performs the reducing step 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.

16. A system for determining a relevance ranking for documents that may contain text in any of a plurality of languages, comprising:

a tokenizer that parses the string of text in a received query into individual word tokens;

a stemmer that reduces the word tokens from the query to grammatical stems by removing word endings that 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;

a search engine that searches an index for entries that match the stems obtained from the query, wherein the index identifies the documents in which words containing the stems appeared, separates, into individual word tokens, text in each document identified as containing matching entries, reduces the word tokens to grammatical stems by removing word endings that 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 compares the stems obtained from the query with the stems obtained from each document identified as containing matching entries to determine the relevance ranking for each identified document; and

a display that displays said relevance rankings.

17. The system of claim 16, wherein said display displays an identification of the documents that contained matching entries, in order of relevance ranking.

18. The system of claim 17, wherein said display displays 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.

19. The system of claim 17, wherein a stem is stored in the 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 the stored ending.

20. The system of claim 16, wherein the word endings that are removed are limited to those ending that are associated with nouns.

21. The system of claim 16, wherein a word ending is not removed if the resulting stem is less than a predetermined length.

22. The system of claim 21, wherein the predetermined length is four characters.

23. The system of claim 16, wherein the stemmer performs the reducing step once per word token.

24. The system of claim 23, wherein the stemmer performs the reducing step 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.