Clustering strings using N-grams

• US 7,644,076 B1
• Filed: 09/12/2003
• Issued: 01/05/2010
• Est. Priority Date: 09/12/2003
• Status: Expired due to Term

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: Teradata US, Inc. (Teradata Corporation)
• Inventors: Ramesh, Bhashyam, Watzke, Michael W.
• Primary Examiner(s): Corrielus; Jean M
• Application Number:
  US10/661,245
• Time in Patent Office: 2,307 Days
• Field of Search: 707/101, 707/3, 707/4, 707/5, 707/6, 707/102, 704/9, 704/7
• US Class Current: 1/1
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method and computer program for clustering a string are described. The string includes a plurality of characters. R unique n-grams T_{1 . . . R} are identified in the string. For every unique n-gram T_S, if the frequency of T_S in a set of n-gram statistics is not greater than a first threshold, the string is associated with a cluster associated with T_S. Otherwise, for every other n-gram T_V in the string T_{1 . . . R, except S}, if the frequency of n-gram T_V is greater than the first threshold, and if the frequency of n-gram pair T_S-T_V is not greater than a second threshold, the string is associated with a cluster associated with the n-gram pair T_S-T_V. Otherwise, for every other n-gram T_X in the string T_{1 . . . R, except S and V}, the string is associated with a cluster associated with the n-gram triple T_S-T_V-T_X. Otherwise, nothing is done.

Claims

1. A method implemented in a computer system said computer system having a memory and processor, for clustering a string, the string including a plurality of characters, the method including:

identifying R unique n-grams T_{1 . . . R} in the string;

for every unique n-gram T_S;

if the frequency of T_S in a set of n-gram statistics is not greater than a first threshold;

clustering the string with a cluster associated with T_S;

otherwise;

for every other n-gram T_V in the string T_{1 . . . R, except S};

concluding that the frequency of n-gram T_V is greater than the first threshold, and in response;

if the frequency of n-gram pair T_S-T_V is not greater than a second threshold;

 

clustering the string with a cluster associated with the n-gram pair T_S-T_V;

otherwise;

 

for every other n-gram T_X in the string T_{1 . . . R, except S and V};

 

clustering the string with a cluster associated with the n-gram triple T_S-T_V-T_X;

where T_{1 . . . R} is a set of n-grams, R is the number of elements in T_{1 . . . R}, and T_S, T_V, and T_X are members of T_{1 . . . R}, and S, V, and X are integer indexes to identify members of T_{1 . . . R}.

2. The method of claim 1 further including compiling n-gram statistics.

3. The method of claim 1 further including compiling n-gram pair statistics.

4. A method implemented in a computer system said computer system having a memory and processor, for clustering a string, the string including a plurality of characters, the method including:

identifying R unique n-grams T_{1 . . . R} in the string;

for every unique n-gram T_S;

if the frequency of T_S in a set of n-gram statistics is not greater than a first threshold;

clustering the string with a cluster associated with T_S;

otherwise;

for i=1 to Y;

for every unique set of i n-grams T_U in the string T_{1 . . . R, except S};

if the frequency of the n-gram set T_S-T_U is not greater than a second threshold;

 

clustering the string with a cluster associated with the n-gram set T_S-T_U;

if the string has not been associated with a cluster with this value of T_S;

for every unique set of Y+1 n-grams T_UY in the string T_{1 . . . R, except S};

clustering the string with a cluster associated with the Y+2 n-gram group T_S-T_UY,

where T_{1 . . . R} is a set of n-grams, R is the number of elements in T_{1 . . . R}, and T_S, T_V, and T_X are members of T_{1 . . . R}, and S, V, and X are integer indexes to identify members of T_{1 . . . R}.

5. The method of claim 4 where Y=1.

6. The method of claim 4 further including compiling n-gram statistics.

7. The method of claim 4 further including compiling n-gram group statistics.