US5778361A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for fast indexing and searching of text in compound-word languages
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1995-09-29
•
Granted: 1998-07-07
•
Expires: 2015-09-29
Abstract
Abstract A method and system for fast indexing and searching of text in compound-word languages such as Japanese, Chinese, Hebrew, and Arabic. Computer codings of such compound-word languages often contain different character types, e.g. the shift-JIS coding of Japanese represents kanji, katakana, hiragana, and roman characters with different codings in the same character set, to form index terms and search terms. In a preferred embodiment, a content-index search system is invoked in response to a query on a collection of objects. The collection of objects is indexed by the content-index and may, for example, be a corpus of documents indexed by the terms contained in the documents. A content-index search system uses the content-index to generate and store an initial search result in response to the query; a direct search system is used in certain situations. The content-index contains, for each of a plurality of terms, a reference to each object. The content-index is created by first creating a preliminary index term for each plurality of terms delimited by a word separator or a character type transition in a string of characters to be indexed. For each preliminary index term of a first type, e.g. katakana or roman, the preliminary index term is utilized as an index term. For each preliminary index term of a second type, e.g. kanji, the preliminary index term is step-indexed to create a plurality of index terms of a length less than a predetermined step size. The index terms are then added to the content-index in association with the object being indexed. A string of text entered into a search engine as a search term is processed into preliminary search terms and search terms in a similar manner.
Inventors
- 👤 Tsutomu Nanjo
- 👤 William Jones
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 21:50
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/31; G06F16/316; G06F16/319; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99935
Claims Analysis
Total Claims: 47
Claim 1
Independent Claim
256 words
A method in a computer system for generating a search result that identifies objects that satisfy a search criteria, the computer system having a collection of objects and a plurality of terms, each object containing one or more of the terms, the objects being represented in different tyes of symbols in a compound word language such as Japanese or Chinese, the method comprising the computer-implemented steps of: creating a content-index that contains, for each of the plurality of terms, a reference to each object that contains the term, by: creating a preliminary index term of a first or second type of symbol for each plurality of terms delimited by a word separator or a character type transition; for each preliminary index term of the first type, utilizing the preliminary index term as an index term; for each preliminary index term of the second type, step indexing the symbols in the preliminary index term to create a plurality of index terms of a length equal to or less than a predetermined step size, the plurality of index terms comprising a collection of substrings of symbols selected from the preliminary index term that begins with one of the symbols in the preliminary index term and extends to a length of either the end of the preliminary index term or to the number of symbols of the predetermined step size, whichever is smaller; creating the content-index by associating the object with each of its index terms; and after creating the content-index, using the content-index to generate the search result.
Claim 2
Independent Claim
256 words
A method in a computer system for generating a search result that identifies objects that satisfy a search criteria, the computer system having a collection of objects and a plurality of terms, each object containing one or more of the terms, the objects being represented in different tyes of symbols in a compound word language such as Japanese or Chinese, the method comprising the computer-implemented steps of: creating a content-index that contains, for each of the plurality of terms, a reference to each object that contains the term, by: creating a preliminary index term of a first or second type of symbol for each plurality of terms delimited by a word separator or a character type transition; for each preliminary index term of the first type, utilizing the preliminary index term as an index term; for each preliminary index term of the second type, step indexing the symbols in the preliminary index term to create a plurality of index terms of a length equal to or less than a predetermined step size, the plurality of index terms comprising a collection of substrings of symbols selected from the preliminary index term that begins with one of the symbols in the preliminary index term and extends to a length of either the end of the preliminary index term or to the number of symbols of the predetermined step size, whichever is smaller; creating the content-index by associating the object with each of its index terms; and after creating the content-index, using the content-index to generate the search result.
Claim 3
Dependent Claim
24 words
The method of claim 1, further comprising the step of normalizing any two-byte representations of symbols comprising an index term to a single-byte representation.
Claim 4
Dependent Claim
18 words
The method of claim 2, wherein the step of normalizing is carried out on the preliminary index terms.
Claim 5
Dependent Claim
27 words
The method of claim 1, wherein the object to be indexed is stored in text buffer, and the preliminary index terms are stored in a key buffer.
Claim 6
Dependent Claim
42 words
The method of claim 4, wherein the preliminary index terms are represented by a plurality of key buffer entries, wherein each key buffer entry comprises a tuple containing a key length parameter and a key offset parameter relative to the text buffer.
Claim 7
Dependent Claim
20 words
The method of claim 1, wherein the preliminary index term of the first type is katakana in a shift-JIS representation.
Claim 8
Dependent Claim
20 words
The method of claim 1, wherein the preliminary index term of the first type is roman in a shift-JIS representation.
Claim 9
Dependent Claim
20 words
The method of claim 1, wherein the preliminary index term of the second type is kanji in a shift-JIS representation.
Claim 10
Dependent Claim
175 words
The method of claim 1, wherein the step of step indexing comprises the steps of: (a) creating an index term of a length equal to or less than the predetermined step size, beginning with the first symbol in the preliminary index term of the second type and extending for the predetermined step size, (b) eliminating th e first symbol in the preliminary index term to create a reduced preliminary index term, (c) creating an index term of a length equal to predetermined step size, beginning with the first symbol in the reduced preliminary index term of the second type and extending for the predetermined step size, (d) repeating the steps (b) and (c) until the last symbol in the reduced preliminary index term coincides with the last symbol in preliminary index term; (e) decrementing the predetermined step size; (f) creating an index term of a length equal to the decremented step size; and (g) repeating the steps (e) and (f) until creating a last index term comprising the last symbol in the preliminary index term.
Claim 11
Dependent Claim
15 words
The method of claim 1 wherein the collection of objects comprises a corpus of documents.
Claim 12
Independent Claim
242 words
A method in a computer system for generating a search result that identifies objects that satisfy a search criteria, the computer system having a collection of objects and a plurality of terms, each object containing one or more of the terms, the objects being represented in different types of symbols in a compound word language such as Japanese or Chinese, and an index associating terms and objects, the method comprising the computer-implemented steps of: receiving a string of text as a preliminary search string; creating a preliminary search term of a first or second type of symbol for each plurality of terms in the preliminary search string delimited by a word separator or a character type transition; for each preliminary search term of the first type, utilizing the preliminary search term as a search term; for each preliminary search term of the second type, step indexing the symbols in the preliminary search term to create a plurality of search terms of a length equal to or less than a predetermined step size, the plurality of search terms comprising a collection of substrings of symbols selected from the preliminary search term that begins with one of the symbols in the preliminary search term and extends to a length of either the end of the preliminary search term or the number of symbols of the predetermined step size, whichever is smaller; and using the search terms in the index to generate the search result.
Claim 13
Independent Claim
242 words
A method in a computer system for generating a search result that identifies objects that satisfy a search criteria, the computer system having a collection of objects and a plurality of terms, each object containing one or more of the terms, the objects being represented in different types of symbols in a compound word language such as Japanese or Chinese, and an index associating terms and objects, the method comprising the computer-implemented steps of: receiving a string of text as a preliminary search string; creating a preliminary search term of a first or second type of symbol for each plurality of terms in the preliminary search string delimited by a word separator or a character type transition; for each preliminary search term of the first type, utilizing the preliminary search term as a search term; for each preliminary search term of the second type, step indexing the symbols in the preliminary search term to create a plurality of search terms of a length equal to or less than a predetermined step size, the plurality of search terms comprising a collection of substrings of symbols selected from the preliminary search term that begins with one of the symbols in the preliminary search term and extends to a length of either the end of the preliminary search term or the number of symbols of the predetermined step size, whichever is smaller; and using the search terms in the index to generate the search result.
Claim 14
Dependent Claim
27 words
The method of claim 11, further comprising the step of removing Boolean terms from the preliminary search string prior to the step of creating the search terms.
Claim 15
Dependent Claim
24 words
The method of claim 11, further comprising the step of normalizing any two-byte representations of symbols comprising a search term to a single-byte representation.
Claim 16
Dependent Claim
20 words
The method of claim 11, wherein the preliminary search term of the first type is katakana in a shift-JIS representation.
Claim 17
Dependent Claim
20 words
The method of claim 11, wherein the preliminary search term of the first type is roman in a shift-JIS representation.
Claim 18
Dependent Claim
20 words
The method of claim 11, wherein the preliminary search term of the second type is kanji in a shift-JIS representation.
Claim 19
Dependent Claim
174 words
The method of claim 11, wherein the step of step indexing comprises the steps of: (a) creating a search term of a length equal to or less than the predetermined step size, beginning with the first symbol in the preliminary search term of the second type and extending for the predetermined step size, (b) eliminating the first symbol in the preliminary search term to create a reduced preliminary search term, (c) creating a search term of a length equal to predetermined step size, beginning with the first symbol in the reduced preliminary search term of the second type and extending for the predetermined step size, (d) repeating the steps (b) and (c) until the last symbol in the reduced preliminary search term coincides with the last symbol in preliminary search term; (e) decrementing the predetermined step size; (f) creating a search term of a length equal to the decremented step size; and (g) repeating the steps (e) and (f) until creating a last search term comprising the last symbol in the preliminary search term.
Claim 20
Independent Claim
303 words
A method in a computer system for providing a search result that identifies objects in a compound word language such as Japanese or Chinese that satisfy a search criteria, the objects contained in a collection of objects, the search criteria having a content-index search portion used with a content-index to determine a set of objects of the collection that satisfy the content-index search portion, the search criteria having a direct search portion, the direct search portion further restricting the set of objects that satisfy the content-index search portion in order to satisfy the search criteria, the method comprising the computer-implemented steps of: receiving a string of text in a compound word language such as Japanese or Chinese as a preliminary search string, the compound word language having symbols of a first type such as kanji, katakana, and roman and symbols of a second type such as hiragana; creating a preliminary search term for each plurality of terms in the preliminary search string delimited by a word separator or a character type transition; for each preliminary search term of the first type, utilizing the preliminary search term as a search term in the search criteria; for each preliminary search term of the second type, setting a direct search indicator; in response to the direct search indicator, generating a proposed list of references to objects that satisfy the direct search portion of the search criteria by directly searching the collection of objects with the preliminary search term of the second type; generating a proposed list of references to objects that satisfy the content-index portion of the search criteria by searching the content-index with the search term of the first type; and providing the search result by listing the collection of objects that match the search criteria of the content-index searching and of the direct searching.
Claim 21
Independent Claim
303 words
A method in a computer system for providing a search result that identifies objects in a compound word language such as Japanese or Chinese that satisfy a search criteria, the objects contained in a collection of objects, the search criteria having a content-index search portion used with a content-index to determine a set of objects of the collection that satisfy the content-index search portion, the search criteria having a direct search portion, the direct search portion further restricting the set of objects that satisfy the content-index search portion in order to satisfy the search criteria, the method comprising the computer-implemented steps of: receiving a string of text in a compound word language such as Japanese or Chinese as a preliminary search string, the compound word language having symbols of a first type such as kanji, katakana, and roman and symbols of a second type such as hiragana; creating a preliminary search term for each plurality of terms in the preliminary search string delimited by a word separator or a character type transition; for each preliminary search term of the first type, utilizing the preliminary search term as a search term in the search criteria; for each preliminary search term of the second type, setting a direct search indicator; in response to the direct search indicator, generating a proposed list of references to objects that satisfy the direct search portion of the search criteria by directly searching the collection of objects with the preliminary search term of the second type; generating a proposed list of references to objects that satisfy the content-index portion of the search criteria by searching the content-index with the search term of the first type; and providing the search result by listing the collection of objects that match the search criteria of the content-index searching and of the direct searching.
Claim 22
Dependent Claim
95 words
The method of claim 18, further comprising the step of step indexing the symbols in the preliminary search term to create a plurality of search terms of a length equal to or less than a predetermined step size, the plurality of search terms comprising a collection of substrings of symbols selected from the preliminary search term that begins with one of the symbols in the preliminary search term and extends to a length of either the end of the preliminary search term or the number of symbols of the predetermined step size, whichever is smaller.
Claim 23
Dependent Claim
34 words
The method of claim 18, further comprising the step of examining each object in the proposed list of references from the content-index portion to determine whether the object also satisfies the direct search portion.
Claim 24
Dependent Claim
15 words
The method of claim 18 wherein the collection of objects is a plurality of documents.
Claim 25
Dependent Claim
62 words
The method of claim 18, further comprising the step of: for each preliminary search term of the second type, setting the direct search indicator if the preliminary search term is longer than a predetermined length, and creating a search term comprising the preliminary search term appended with a wildcard character if the preliminary search term is not longer than the predetermined length.
Claim 26
Dependent Claim
265 words
A computer system for generating a search result that identifies objects that satisfy a search criteria, the computer system storing a collection of objects and a plurality of terms, each object containing one or more of the terms, the objects being represented in different types of symbols in a compound word language such as Japanese or Chinese, comprising: a content-index that contains, for each of the plurality of terms, a reference to each object that contains the term; a preliminary index term generator that generates, for each plurality of terms delimited by a word separator or a character type transition, a preliminary search term of a first or second type of symbol; an indexer that, for each preliminary index term of the first type, utilizes the preliminary index term as an index term; the indexer, for each preliminary index term of the second type, also step indexing the symbols in the preliminary index term to create a plurality of index terms of a length equal to or less than a predetermined step size, the plurality of index terms comprising a collection of substrings of symbols selected from the preliminary index term that begins with one of the symbols in the preliminary index term and extends to a length of either the end of the preliminary index term or the number of symbols of the predetermined step size, whichever is smaller; an object/index term associator that creates the content-index by associating the object with each of its index terms; and a search engine that, after creating the content-index, uses the content-index to generate the search result.
Claim 27
Dependent Claim
265 words
A computer system for generating a search result that identifies objects that satisfy a search criteria, the computer system storing a collection of objects and a plurality of terms, each object containing one or more of the terms, the objects being represented in different types of symbols in a compound word language such as Japanese or Chinese, comprising: a content-index that contains, for each of the plurality of terms, a reference to each object that contains the term; a preliminary index term generator that generates, for each plurality of terms delimited by a word separator or a character type transition, a preliminary search term of a first or second type of symbol; an indexer that, for each preliminary index term of the first type, utilizes the preliminary index term as an index term; the indexer, for each preliminary index term of the second type, also step indexing the symbols in the preliminary index term to create a plurality of index terms of a length equal to or less than a predetermined step size, the plurality of index terms comprising a collection of substrings of symbols selected from the preliminary index term that begins with one of the symbols in the preliminary index term and extends to a length of either the end of the preliminary index term or the number of symbols of the predetermined step size, whichever is smaller; an object/index term associator that creates the content-index by associating the object with each of its index terms; and a search engine that, after creating the content-index, uses the content-index to generate the search result.
Claim 28
Dependent Claim
24 words
The system of claim 23, further comprising a normalizer that normalizes any two-byte representations of symbols comprising an index term to a single-byte representation.
Claim 29
Dependent Claim
16 words
The system of claim 24, wherein the normalizing is carried out on the preliminary index terms.
Claim 30
Dependent Claim
34 words
The system of claim 23, further comprising a text buffer, and wherein the object to be indexed is stored in the text buffer, and the preliminary index terms are stored in a key buffer.
Claim 31
Dependent Claim
42 words
The system of claim 26, wherein the preliminary index terms are represented by a plurality of key buffer entries, wherein each key buffer entry comprises a tuple containing a key length parameter and a key offset parameter relative to the text buffer.
Claim 32
Dependent Claim
20 words
The system of claim 23, wherein the preliminary index term of the first type is katakana in a shift-JIS representation.
Claim 33
Dependent Claim
20 words
The system of claim 23, wherein the preliminary index term of the first type is roman in a shift-JIS representation.
Claim 34
Dependent Claim
20 words
The system of claim 23, wherein the preliminary index term of the second type is kanji in a shift-JIS representation.
Claim 35
Dependent Claim
170 words
The system of claim 23, wherein the indexer is operative for: (a) creating an index term of a length equal to or less than the predetermined step size, beginning with the first symbol in the preliminary index term of the second type and extending for the predetermined step size, (b) eliminating the first symbol in the preliminary index term to create a reduced preliminary index term, (c) creating an index term of a length equal to predetermined step size, beginning with the first symbol in the reduced preliminary index term of the second type and extending for the predetermined step size, (d) repeating the steps (b) and (c) until the last symbol in the reduced preliminary index term coincides with the last symbol in preliminary index term; (e) decrementing the predetermined step size; (f) creating an index term of a length equal to the decremented step size; and (g) repeating the steps (e) and (f) until creating a last index term comprising the last symbol in the preliminary index term.
Claim 36
Dependent Claim
15 words
The system of claim 23 wherein the collection of objects comprises a corpus of documents.
Claim 37
Dependent Claim
221 words
A computer system for generating a search result that identifies objects that satisfy a search criteria, the computer system storing a collection of objects in a compound word language such as Japanese or Chinese and a plurality of terms, each object containing one or more of the terms, and an index associating terms and objects, comprising the: an input device for providing a string of text as a preliminary search string; a preliminary search term generator that generates a kanji preliminary search term for each plurality of kanji terms in the preliminary search string delimited by a word separator or a character type transition; a search term generator that provides, for each kanji preliminary search term, a plurality of search terms of a length equal to or less than a predetermined step size by step indexing the symbols in the preliminary kanji search term, the plurality of search terms comprising a collection of substrings of symbols selected from the preliminary kanji search term that begins with one of the symbols in the preliminary kanji search term and extends to a length of either the end of the preliminary kanji search term or the number of symbols of the predetermined step size, whichever is smaller; and a search engine that uses the search terms in the index to generate the search result.
Claim 38
Dependent Claim
221 words
A computer system for generating a search result that identifies objects that satisfy a search criteria, the computer system storing a collection of objects in a compound word language such as Japanese or Chinese and a plurality of terms, each object containing one or more of the terms, and an index associating terms and objects, comprising the: an input device for providing a string of text as a preliminary search string; a preliminary search term generator that generates a kanji preliminary search term for each plurality of kanji terms in the preliminary search string delimited by a word separator or a character type transition; a search term generator that provides, for each kanji preliminary search term, a plurality of search terms of a length equal to or less than a predetermined step size by step indexing the symbols in the preliminary kanji search term, the plurality of search terms comprising a collection of substrings of symbols selected from the preliminary kanji search term that begins with one of the symbols in the preliminary kanji search term and extends to a length of either the end of the preliminary kanji search term or the number of symbols of the predetermined step size, whichever is smaller; and a search engine that uses the search terms in the index to generate the search result.
Claim 39
Dependent Claim
27 words
The system of claim 33, further comprising a filter for removing Boolean terms from the preliminary search string prior to the step of creating the search terms.
Claim 40
Dependent Claim
24 words
The system of claim 33, further comprising a normalizer for normalizing any two-byte representations of symbols comprising a search term to a single-byte representation.
Claim 41
Dependent Claim
180 words
The system of claim 33, wherein the indexer is operative for step indexing by: (a) creating a search term of a length equal to or less than the predetermined step size, beginning with the first symbol in the kanji preliminary search term of the second type and extending for the predetermined step size, (b) eliminating the first symbol in the kanji preliminary search term to create a reduced kanji preliminary search term, (c) creating a search term of a length equal to predetermined step size, beginning with the first symbol in the reduced kanji preliminary search term of the second type and extending for the predetermined step size, (d) repeating the steps (b) and (c) until the last symbol in the reduced kanji preliminary search term coincides with the last symbol in kanji preliminary search term; (e) decrementing the predetermined step size; (f) creating a search term of a length equal to the decremented step size; and (g) repeating the steps (e) and (f) until creating a last search term comprising the last symbol in the kanji preliminary search term.
Claim 42
Dependent Claim
325 words
A computer system for providing a search result that identifies objects n a compound word language such as Japanese or Chinese that satisfy a search criteria, the objects contained in a collection of objects, the search criteria having a content-index search portion used with a content-index to determine a set of objects of the collection that satisfy the content-index search portion, the search criteria having a direct search portion, the direct search portion further restricting the set of objects that satisfy the content-index search portion in order to satisfy the search criteria, comprising: an input device for providing a string of text in a compound word language such as Japanese or Chinese as a preliminary search string, the compound word language having symbols of a first type such as kanji, katakana, and roman and symbols of a second type such as hiragana; a preliminary search term generator for creating a preliminary search term for each plurality of terms in the preliminary search string delimited by a word separator or a character type transition; a search term generator that, for each preliminary search term of the first type, utilizes the preliminary search term as a search term in the search criteria; the search term generator, for each preliminary search term of the second type, setting a direct search indicator; a search engine that, in response to the direct search indicator, generates a proposed list of references to objects that satisfy the direct search portion of the search criteria by directly searching the collection of objects with the preliminary search term of the second type; the search engine also generating a proposed list of references to objects that satisfy the content-index portion of the search criteria by searching the content-index with the search term of the first type; and an output device that provides the search results by listing the collection of objects that match the search criteria of the content-index searching and of the direct searching.
Claim 43
Dependent Claim
325 words
A computer system for providing a search result that identifies objects n a compound word language such as Japanese or Chinese that satisfy a search criteria, the objects contained in a collection of objects, the search criteria having a content-index search portion used with a content-index to determine a set of objects of the collection that satisfy the content-index search portion, the search criteria having a direct search portion, the direct search portion further restricting the set of objects that satisfy the content-index search portion in order to satisfy the search criteria, comprising: an input device for providing a string of text in a compound word language such as Japanese or Chinese as a preliminary search string, the compound word language having symbols of a first type such as kanji, katakana, and roman and symbols of a second type such as hiragana; a preliminary search term generator for creating a preliminary search term for each plurality of terms in the preliminary search string delimited by a word separator or a character type transition; a search term generator that, for each preliminary search term of the first type, utilizes the preliminary search term as a search term in the search criteria; the search term generator, for each preliminary search term of the second type, setting a direct search indicator; a search engine that, in response to the direct search indicator, generates a proposed list of references to objects that satisfy the direct search portion of the search criteria by directly searching the collection of objects with the preliminary search term of the second type; the search engine also generating a proposed list of references to objects that satisfy the content-index portion of the search criteria by searching the content-index with the search term of the first type; and an output device that provides the search results by listing the collection of objects that match the search criteria of the content-index searching and of the direct searching.
Claim 44
Dependent Claim
91 words
The system of claim 37, further comprising a step indexer for providing the symbols in the preliminary search term as a plurality of search terms of a length less than a predetermined step size, the plurality of search terms comprising a collection of substrings of symbols selected from the preliminary search term that begins with one of the symbols in the preliminary search term and extends to a length of either the end of the preliminary search term or the number of symbols of the predetermined step size, whichever is smaller.
Claim 45
Dependent Claim
38 words
The system of claim 37, further comprising a component in the search engine for examining each object in the proposed list of references from the content-index portion to determine whether the object also satisfies the direct search portion.
Claim 46
Dependent Claim
15 words
The system of claim 37, wherein the collection of objects is a plurality of documents.
Claim 47
Dependent Claim
65 words
The system of claim 37, wherein the search term generator is operative for: for each preliminary search term of the second type, setting the direct search indicator if the preliminary search term is longer than a predetermined length, and creating a search term comprising the preliminary search term appended with a wildcard character if the preliminary search term is not longer than the predetermined length.
References Cited (Backward Citations)
US4064983A
Cited
US4679951A
Cited
US4602878A
Cited
US5148541A
Cited
US5109352A
Cited
US5187480A
Cited
US5168533A
Cited
US5276616A
Cited
US5329506A
Cited
US5337233A
Cited
US5416898A
Cited
US5590317A
Cited
US5384700A
Cited
US5542090A
Cited
US5331557A
Cited
US5544352A
Cited
US5586198A
Cited
US5642520A
Cited
US5537431A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-07-06 | 2002-01-05 | 2002-07-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-07-06 | 2006-01-05 | 2006-07-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-07-06 | 2010-01-05 | 2010-07-07 | $7700.00 | Window Closed / Lapsed |