Pattern searching methods and apparatuses

• US 7,912,828 B2
• Filed: 02/23/2007
• Issued: 03/22/2011
• Est. Priority Date: 02/23/2007
• Status: Expired due to Fees

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: De Jaeger, Frédéric, Bonnet, Olivier, Paterson, Toby
• Primary Examiner(s): Mofiz; Apu M
• Assistant Examiner(s): Nguyen; Cindy
• Application Number:
  US11/710,182
• Publication Number:
  US 20080243841A1
• Time in Patent Office: 1,488 Days
• Field of Search: 707/6, 707/102, 709/246, 704/243, 704/244
• US Class Current: 707/706
• 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 fixed weighting to each structure and each definition item in each structure, each fixed weighting being an integer multiple of the same integer;

searching the 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 definition items making up said particular structure that have been identified in the provisionally identified pattern;

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

assessing whether the single quantity fulfils a given condition; and

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 fixed weightings using one or more arithmetic operations.

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

5. The method of claim 1, each fixed 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.

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

7. 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-4 or 5-6.

8. An apparatus 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 apparatus comprising:

a processing system coupled to memory;

means for assigning a fixed weighting to each structure and each definition item in each

structure, each fixed weighting being an integer multiple of the same integer;

means for searching the 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, means for determining definition items making up said particular structure that have been identified in the provisionally identified pattern;

means for combining the fixed weightings of the determined definition items and the

fixed weighting of the particular structure to a single quantity;

means for assessing whether the single quantity fulfils a given condition; and

depending on the result of said assessment, means for rejecting or confirming the

provisionally identified pattern.

9. The apparatus of claim 8, wherein the given condition corresponds to the single quantity being above or below a given threshold.

10. The apparatus of claim 8, wherein the single quantity is obtained by the means for combining the fixed weightings using one or more arithmetic operations.

11. The apparatus of claim 8, wherein the arithmetic operation is a summation over all fixed weightings, the single quantity being the sum of all the weightings.

12. The apparatus of claim 8, each fixed 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.