SEARCHING APPARATUS AND SEARCHING METHOD

• US 20110264675A1
• Filed: 04/26/2011
• Published: 10/27/2011
• Est. Priority Date: 04/27/2010
• Status: Active Grant

• Current Assignee: Casio Computer Company Limited
• Original Assignee: Casio Computer Company Limited
• Inventors: SATOH, Katsuhiko
• Granted Patent: US 8,412,697 B2
• Time in Patent Office: Days
• US Class Current: 707/754
• CPC Class Codes: G06F 16/90344 by using string matching techniques

Abstract

A searching apparatus includes a memory unit which stores transposed indexes representing appearing positions of all n-grams in plural pieces of document data subjected to searching and appearing frequencies, an n-gram extracting unit that extracts all n-grams extractable from a searching character string, a smallest-frequency deriving unit which refers to the appearing frequency of the n-gram represented by the transposed index, and derives an n-gram with the smallest appearing frequency among all of the extracted n-grams, a searching n-gram selecting unit that selects, from all extracted n-grams, a plurality of searching n-grams which form the searching character string and include the n-gram with the smallest appearing frequency, and a document specifying unit that specifies, based on the plurality of selected searching n-grams and the appearing position of the searching n-gram represented by the transposed index, document data including the searching character string among the plural pieces of document data.

Claims

1. A searching apparatus comprising:

a memory unit which stores, for each of n-grams (where n is a natural number) extracted from plural pieces of document data subjected to searching, a transposed index representing an appearing position in the plural pieces of document data and an appearing frequency therein, the n-gram being a character string including n number of characters;

an n-gram extracting unit that extracts all n-grams which are extractable from a searching character string;

a smallest-frequency deriving unit which refers to the appearing frequency of the n-gram represented by the transposed index, and which derives an n-gram with a smallest appearing frequency among all of the n-grams extracted by the n-gram extracting unit;

a searching n-gram selecting unit that selects, from all of the n-grams extracted by the n-gram extracting unit, a plurality of searching n-grams which form the searching character string and which include the n-gram with the smallest appearing frequency derived by the smallest-frequency deriving unit; and

a document specifying unit that specifies, based on the plurality of searching n-grams selected by the searching n-gram selecting unit and the appearing position of the searching n-gram represented by the transposed index, document data including the searching character string among the plural pieces of document data.

2. The searching apparatus according to claim 1, wherein the searching n-gram selecting unit selects the searching n-grams from all of the n-grams extracted by the n-gram extracting unit, the number of selected searching n-grams being a number that is the minimum number of the n-grams forming the searching character string or the minimum number of the n-grams plus one.

3. The searching apparatus according to claim 1, wherein the searching n-gram selecting unit

(a) divides the searching character string n-gram by n-gram from the head of the searching character string so as not to overlap with another n-gram for all of the n-grams extracted by the n-gram extracting unit, and selects the divided n-grams,

(b) additionally selects an n-gram including a last character of the searching character string when the selected n-grams do not form the searching character string, and

(c) additionally selects an n-gram with the smallest appearing frequency when the n-gram with the smallest appearing frequency derived by the smallest-frequency deriving unit is not included in the n-grams selected through (a) and (b).

4. The searching apparatus according to claim 1, wherein the searching n-gram selecting unit

(a) selects an n-gram including a first or last character of the searching character string among all of the n-grams extracted by the n-gram extracting unit,

(b) additionally selects an n-gram with the smallest appearing frequency derived by the smallest-frequency deriving unit, and

(c) divides the searching character string n-gram by n-gram so as not to overlap with another n-gram with reference to a position of the n-gram with the smallest appearing frequency in the searching character string in a direction frontward or backward of that position, and additionally selects a divided n-gram not selected through (a).

5. The searching apparatus according to claim 1, wherein the document specifying unit specifies document data including the searching character string among the plural pieces of document data based on whether or not all of the other searching n-grams are present at an appearing position of the searching n-gram and at a following appearing position using the plurality of searching n-grams selected by the searching n-gram selecting unit in an order of smaller appearing frequency represented by the transposed index.

6. A searching method using a searching apparatus which stores, for each of n-grams (where n is a natural number) extracted from plural pieces of document data subjected to searching, a transposed index representing an appearing position in the plural pieces of document data and an appearing frequency therein, the n-gram being a character string including n number of characters, the searching method comprising:

an n-gram extracting step of extracting all n-grams which are extractable from a searching character string;

a smallest-frequency deriving step of referring to the appearing frequency of the n-gram represented by the transposed index, and of deriving an n-gram with a smallest appearing frequency among all of the n-grams extracted through the n-gram extracting step;

a searching n-gram selecting step of selecting, from all of the n-grams extracted through the n-gram extracting step, a plurality of searching n-grams which form the searching character string and which include the n-gram with the smallest appearing frequency derived through the smallest-frequency deriving step; and

a document specifying step of specifying, based on the plurality of searching n-grams selected through the searching n-gram selecting step and the appearing position of the searching n-gram represented by the transposed index, document data including the searching character string among the plural pieces of document data.

7. The searching method according to claim 6, wherein in the searching n-gram selecting step, the searching n-grams are selected from all of the n-grams extracted by the n-gram extracting step, the number of selected searching n-grams being a number that is the minimum number of the n-grams forming the searching character string or the minimum number of the n-grams plus one.

8. The searching method according to claim 6, wherein in the searching n-gram selecting step,

(a) the searching character string is divided n-gram by n-gram from the head of the searching character string so as not to overlap with another n-gram for all of the n-grams extracted by the n-gram extracting step, and the divided n-grams are selected,

(b) an n-gram including a last character of the searching character string is additionally selected when the selected n-grams do not form the searching character string, and

(c) an n-gram with the smallest appearing frequency is additionally selected when the n-gram with the smallest appearing frequency derived through the smallest-frequency deriving step is not included in the n-grams selected through (a) and (b).

9. The searching method according to claim 6, wherein in the searching n-gram selecting step,

(a) an n-gram including a first or last character of the searching character string is selected among all of the n-grams extracted through the n-gram extracting step,

(b) an n-gram with the smallest appearing frequency derived by the smallest-frequency deriving unit is additionally selected, and

(c) the searching character string is divided n-gram by n-gram so as not to overlap with another n-gram with reference to a position of the n-gram with the smallest appearing frequency in the searching character string in a direction frontward or backward of that position, and a divided n-gram not selected through (a) is additionally selected.

10. The searching method according to claim 6, wherein in the document specifying step, document data including the searching character string is specified among the plural pieces of document data based on whether or not all of the other searching n-grams are present at an appearing position of the searching n-gram and at a following appearing position using the plurality of searching n-grams selected through the searching n-gram selecting step in an order of smaller appearing frequency represented by the transposed index.

11. A recording medium storing a computer program that allows a computer including a memory unit which stores, for each of n-grams (where n is a natural number) extracted from plural pieces of document data subjected to searching, a transposed index representing an appearing position in the plural pieces of document data and an appearing frequency therein, the n-gram being a character string including n number of characters to function as;

an n-gram extracting unit that extracts all n-grams which are extractable from a searching character string;

a smallest-frequency deriving unit which refers to the appearing frequency of the n-gram represented by the transposed index, and which derives an n-gram with a smallest appearing frequency among all of the n-grams extracted by the n-gram extracting unit;

a searching n-gram selecting unit that selects, from all of the n-grams extracted by the n-gram extracting unit, a plurality of searching n-grams which form the searching character string and which include the n-gram with the smallest appearing frequency derived by the smallest-frequency deriving unit; and

a document specifying unit that specifies, based on the plurality of searching n-grams selected by the searching n-gram selecting unit and the appearing position of the searching n-gram represented by the transposed index, document data including the searching character string among the plural pieces of document data.

12. The recording medium storing the computer program according to claim 11, wherein the searching n-gram selecting unit selects the searching n-grams from all of the n-grams extracted by the n-gram extracting unit, the number of selected searching n-grams being a number that is the minimum number of the n-grams forming the searching character string or the minimum number of the n-grams plus one.

13. The recording medium storing the computer program according to claim 11, wherein the searching n-gram selecting unit

(a) divides the searching character string n-gram by n-gram from the head of the searching character string so as not to overlap with another n-gram for all of the n-grams extracted by the n-gram extracting unit, and selects the divided n-grams,

(b) additionally selects an n-gram including a last character of the searching character string when the selected n-grams do not form the searching character string, and

(c) additionally selects an n-gram with the smallest appearing frequency when the n-gram with the smallest appearing frequency derived by the smallest-frequency deriving unit is not included in the n-grams selected through (a) and (b).

14. The recording medium storing the computer program according to claim 11, wherein the searching n-gram selecting unit

(a) selects an n-gram including a first or last character of the searching character string among all of the n-grams extracted by the n-gram extracting unit,

(b) additionally selects an n-gram with the smallest appearing frequency derived by the smallest-frequency deriving unit, and

(c) divides the searching character string n-gram by n-gram so as not to overlap with another n-gram with reference to a position of the n-gram with the smallest appearing frequency in the searching character string in a direction frontward or backward of that position, and additionally selects a divided n-gram not selected through (a).

15. The recording medium storing the computer program according to claim 11, wherein the document specifying unit specifies document data including the searching character string among the plural pieces of document data based on whether or not all of the other searching n-grams are present at an appearing position of the searching n-gram and at a following appearing position using the plurality of searching n-grams selected by the searching n-gram selecting unit in an order of smaller appearing frequency represented by the transposed index.