Clustering strings using N-grams
View Patent ↗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.
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.