Pattern searching methods and apparatuses

• US 20080243841A1
• Filed: 02/23/2007
• Published: 10/02/2008
• Est. Priority Date: 02/23/2007
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Bonnet, Olivier, Paterson, Toby, De Jaeger, Frederic
• Granted Patent: US 7,912,828 B2
• Time in Patent Office: Days
• US Class Current: 707/6
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/279 Recognition of textual entities

Abstract

A computer-based method for identifying patterns in computer text using structures defining types of patterns which are to be identified, wherein a structure comprises one or more definition items, the method comprising assigning a weighting to each structure and each definition item; searching the computer text for a pattern to be identified on the basis of a particular structure, a pattern being provisionally identified if it matches the definition given by said particular structure; in a provisionally identified pattern, determining those of the definition items making up said particular structure that have been identified in the provisionally identified pattern; combining the weightings of the determined definition items and optionally, the weighting of the particular structure, to a single quantity; assessing whether the single quantity fulfils a given condition; depending on the result of said assessment, rejecting or confirming the provisionally identified pattern.

Claims

1. A machine-implemented method for identifying patterns in text using structures defining types of patterns which are to be identified, wherein a structure comprises one or more definition items, the method comprising:

assigning a weighting to each structure and each definition item;

searching the computer text for a pattern to be identified on the basis of a particular structure, a pattern being provisionally identified if it matches the definition given by said particular structure;

in a provisionally identified pattern, determining those of the definition items making up said particular structure that have been identified in the provisionally identified pattern;

combining the weightings of the determined definition items and optionally, the weighting of the particular structure, to a single quantity;

assessing whether the single quantity fulfils a given condition;

depending on the result of said assessment, rejecting or confirming the provisionally identified pattern.

2. The method of claim 1, wherein the given condition corresponds to the single quantity being above or below a given threshold.

3. The method of claim 1, wherein the single quantity is obtained by combining the weightings using one or more arithmetic operations.

4. The method of claim 3, wherein the arithmetic operation is a summation over all weightings, the single quantity being the sum of all the weightings.

5. The method of claim 1, each weighting being defined as a number.

6. The method of claim 5, each weighting taking the form of either a bonus in the form of a positive integer, or a malus in the form of a negative integer.

7. The method of claim 6, wherein a structure or definition item is assigned a bonus if it is well-defined, and a malus if it is ambiguous.

8. The method of claim 5, each weighting being an integer multiple of the same integer.

12. A program storage medium having a program stored therein for causing a data processing system to execute the method of any one of claims 1 to 10.

9. A machine-implemented method for identifying patterns in text using structures defining types of patterns which are to be identified, wherein a structure comprises one or more definition items, the method comprising:

searching a text data for a pattern to be identified on the basis of a particular structure, a pattern being identified if it matches the definition given by said particular structure, wherein said structures are automatically generated or extended on the basis of information available from a data source.

10. A machine-implemented method for identifying patterns in text using structures defining types of patterns which are to be identified, wherein a structure comprises one or more definition items, the method comprising:

searching a text data for a pattern to be identified on the basis of a particular structure, a pattern being identified if it matches the definition given by said particular structure, wherein the text data is indexed using the patterns identified in it.

11. The method of claim 10 wherein the text data is indexed for searching.