Method and system for fast indexing and searching of text in compound-word languages

• US 5,778,361 A
• Filed: 09/29/1995
• Issued: 07/07/1998
• Est. Priority Date: 09/29/1995
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jones, William, Nanjo, Tsutomu
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US08/537,366
• Time in Patent Office: 1,012 Days
• Field of Search: 395/602, 395/603, 395/600, 395/150, 395/605, 364/419.14, 364/419.09, 382/185, 341/22, 400/110, 707/2, 707/3, 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

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.

Claims

1. 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.

2. 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.

3. The method of claim 2, wherein the step of normalizing is carried out on the preliminary index terms.

4. 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.

5. 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.

6. The method of claim 1, wherein the preliminary index term of the first type is katakana in a shift-JIS representation.

7. The method of claim 1, wherein the preliminary index term of the first type is roman in a shift-JIS representation.

8. The method of claim 1, wherein the preliminary index term of the second type is kanji in a shift-JIS representation.

9. 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.

10. The method of claim 1 wherein the collection of objects comprises a corpus of documents.

11. 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.

12. 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.

13. 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.

14. The method of claim 11, wherein the preliminary search term of the first type is katakana in a shift-JIS representation.

15. The method of claim 11, wherein the preliminary search term of the first type is roman in a shift-JIS representation.

16. The method of claim 11, wherein the preliminary search term of the second type is kanji in a shift-JIS representation.

17. 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.

18. 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.

19. 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.

20. 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.

21. The method of claim 18 wherein the collection of objects is a plurality of documents.

22. 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.

23. 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.

24. 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.

25. The system of claim 24, wherein the normalizing is carried out on the preliminary index terms.

26. 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.

27. 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.

28. The system of claim 23, wherein the preliminary index term of the first type is katakana in a shift-JIS representation.

29. The system of claim 23, wherein the preliminary index term of the first type is roman in a shift-JIS representation.

30. The system of claim 23, wherein the preliminary index term of the second type is kanji in a shift-JIS representation.

31. 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.

32. The system of claim 23 wherein the collection of objects comprises a corpus of documents.

33. 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.

34. 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.

35. 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.

36. 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.

37. 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.

38. 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.

39. 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.

40. The system of claim 37, wherein the collection of objects is a plurality of documents.

41. 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.