String pattern conceptualization from detection of related concepts by analyzing substrings with common prefixes and suffixes

1. A string pattern conceptualization method, particularly for a pattern of words, comprising:

setting, via a processor, a reference set (SET_r_i) comprising a plurality of strings (STR_n_i);

inside the reference set (SET_r_i), finding specific N-tuples ([Y 1 _i|Y 2 _i| . . . |Ym_i]) of substring triples (X_i,Y 1 _i,Z_i; X_i,Y 2 _i,Z_i; . . . ; X_i,Ym_i,Z_i) with N≧2 and m=1 . . . N; and

considering each N-tuple ([Y 1 _i|Y 2 _i| . . . |Ym_i]) as a candidate for representing related concepts;

where:

each concatenation (X_i Y 1 _i Z_i; X_i Y 2 _i Z_i; . . . ; X_i Ym_i Z_i) of the substrings triples (X_i,Y 1 _i,Z_i; X_i,Y 2 _i,Z_i; . . . ; X_i,Ym_i,Z_i) is an explicit member of the reference set (SET_r_i);

each middle substring (Y 1 _i, Y 2 _i, . . . , Ym_i) out of middle substrings (Y 1 _i, Y 2 _i, . . . , Ym_i) is unequal to another middle substring (Y 1 _i, Y 2 _i, . . . ,Ym_i) out of middle substrings (Y 1 _i, Y 2 _i, . . . ,Ym_i) within the substring triples (X_i,Y 1 _i,Z_i; X_i,Y 2 _i,Z_i; . . . ; X_i,Ym_i,Z_i) found inside the reference set (SET_r_i);

each prefix substring (X_i) is equal to all other prefix substrings (X_i) within the substring triples (X_i,Y 1 _i,Z_i; X_i,Y 2 _i,Z_i; . . . ; X_i,Ym_i,Z_i) found inside the reference set (SET_r_i);

each suffix substring (Z_i) is equal to all other prefix substrings (Z_i) within the substring triples (X_i,Y 1 _i,Z_i; X_i,Y 2 _i,Z_i; . . . ; X_i,Ym_i,Z_i) found inside the reference set (SET_r_i); and

either the prefix substring (X_i) or the suffix substring (Z_i) is not empty.

2. The method of claim 1 , further comprising ranking candidates according to attributes of at least one of the prefix substring (X_i) and the suffix substring (Z_i).

3. The method of claim 2 , further comprising replacing one or more occurrences of the concepts in the string pattern with a most frequently occurring concept yielding an altered string pattern.

4. The method of claim 3 , further comprising doing the following steps in the altered string pattern:

setting the reference set (SET_r_i) of strings (STR_n_i);

denoting each string (STR_n_i) with its occurrence count (OCC_n_i);

inside the reference set (SET_r_i), finding specific substring triples (X_i,Y 1 _i,Z_i; X_i,Y 2 _i,Z_i; . . . ; X_i,Ym_i,Z_i) of the substring N-tuples ([Y 1 _i|Y 2 _i| . . . |Ym_i]) with N≧2 and m=1 . . . N;

considering each N-tuple ([Y 1 _i|Y 2 _i| . . . Ym_i]) as the candidate for representing related concepts;

where:

each prefix substring (X_i) and each suffix substring (Z_i) of each substring triple (X_i,Y 1 _i,Z_i; X_i,Y 2 _i,Z_i; . . . ; X_i,Ym_i,Z_i) is an explicit member of the reference set (SET_r_i),

each concatenation (X_i Y 1 _i Z_i; X_i Y 2 _i Z_i; . . . ; X_i Ym_i Z_i) of the substrings triples (X_i,Y 1 _i,Z_i; X_i,Y 2 _i-Z_i, . . . ; X_i,Ym_i,Z_i) is an explicit member of the reference set (SET_r_i);

each middle substring (Y 1 _i, Y 2 _i, . . . , Ym_i) is unequal to another middle substring (Y 1 _i, Y 2 _i, . . . ,Ym_i) within the substring triples (X_i,Y 1 _i,Z_i;

X_i,Y 2 _i,Z_i; . . . ; X_i,Ym_i,Z_i) found inside the reference set (SET_r_i);

either the prefix substring (X_i) or the suffix substring (Z_i) is not empty.

5. The method of claim 1 , further comprising filtering a result of one or more N-tuples ([Y 1 _i|Y 2 _i| . . . |Ym_i]) found as candidates for representing related concepts considering specific types of a desired result.

6. The method of claim 5 , said filtering comprising at least one of the following steps:

using a minimum length for middle substrings (Y 1 _i, Y 2 _i, . . . , Ym_i);

using a maximum length for the middle substrings (Y 1 _i, Y 2 _i, . . . , Ym_i);

using a minimum length for at least one of the prefix and suffix substring (X_i, Z_i);

requesting that the prefix substring (X_i) ends with a particular regular expression;

requesting that the suffix substring (Z_i) starts with a particular regular expression; and

requesting that at least one of the middle substrings (Y 1 _i, Y 2 _i, . . . , Ym_i) has a certain value (V).

7. The method of claim 1 , further comprising comparing at least two occurrence counts (Occ — 1, Occ — 2, . . . , Occ_m) if at least one of two or more of the middle substrings (Y 1 _i, Y 2 _i, . . . , Ym_i) and two or more concatenations of the prefix and middle substrings (X_i Y 1 _i; X_i Y 2 _i; . . . ; X_i Ym_i) are explicit members of the reference set (SET_r_i).

8. The method of claim 7 , further comprising at least one of the following steps:

if the occurrence count (Occ — 1, Occ — 2, . . . , Occ_m) of a first respective middle substring (Y 1 _i, Y 2 _i, . . . , Ym_i) is significantly less than the occurrence count (Occ — 1, Occ — 2, . . . , Occ_m) of another middle substring (Y 1 _i, Y 2 _i, . . . , Ym_i) being compared with, considering the respective first middle substring (Y 1 _i, Y 2 _i, . . . , Ym_i) being a specialized concept of the other middle substring (Y 1 _i, Y 2 _i, . . . , Ym_i); and

if the occurrence count (Occ — 1, Occ — 2, . . . , Occ_m) of the first respective middle substring (Y 1 _i, Y 2 _i, . . . , Ym_i) is significantly greater than the occurrence count (Occ — 1, Occ — 2, . . . , Occ_m) of another middle substring (Y 1 _i, Y 2 _i, . . . , Ym_i) being compared with, considering the respective first middle substring (Y 1 _i, Y 2 _i, . . . , Ym_i) being a generalized concept of the other middle substring (Y 1 _i, Y 2 _i, . . . , Ym_i).

9. The method of claim 1 , further comprising using a string-pattern analysis method, particularly for a pattern of words or a genome pattern, for providing maximum substrings (STR_A_C) as an input for the conceptualization method, comprising the following steps for at least one iteration (A):

defining a subset (SET_A) of substrings (STR_A_B) in said pattern;

keeping track of all said substrings (STR_A_B) and their occurrence counts (Occ_A_B) in said subset (SET_A) of substrings (STR_A_B); and

pruning away each substring (STR_A_B) if said substring (STR_A_B) is subsumed by a longer substring (STR_A_C) in said subset (SET_A) of substrings (STR_A_B) with a same occurrence count (Occ_A_C).

10. A computer program product comprising a computer useable storage device that stores a computer readable program, wherein the computer readable program when executed on a computer causes the computer to do the following steps at least one time:

setting a reference set (SET_r_i) comprising a plurality of strings (STR_n_i);

inside the reference set (SET_r_i), finding specific N-tuples ([Y 1 _i|Y 2 _i| . . . Ym_i]) of substring triples (X_i,Y 1 _i,Z_i; X_i,Y 2 _i,Z_i; . . . ; X_i,Ym_i,Z_i) with N≧2 and m=1 . . . N;

considering each N-tuple ([Y 1 _i|Y 2 _i| . . . Ym_i]) as a candidate for representing related concepts;

where:

each concatenation (X_i Y 1 _i Z_i; X_i Y 2 _i Z_i; . . . ; X_i Ym_i Z_i) of the substrings triples (X_i,Y 1 _i,Z_i; X_i,Y 2 _i,Z_i; . . . ; X_i,Ym_i,Z_i) is an explicit member of the reference set (SET_r_i);

each middle substring (Y 1 _i, Y 2 _i, . . . , Ym_i) out of the middle substrings (Y 1 _i, Y 2 _i, . . . , Ym_i) is unequal to another middle substring (Y 1 _i, Y 2 _i, . . . ,Ym_i) out of the middle substrings (Y 1 _i, Y 2 _i, . . . ,Ym_i) within the substring triples (X_i,Y 1 _i,Z_i; X_i,Y 2 _i,Z_i; . . . ; X_i,Ym_i,Z_i) found inside the reference set (SET_r_i);

each prefix substring (X_i) is equal to all other prefix substrings (X_i) within the substring triples (X_i,Y 1 _i,Z_i; X_i,Y 2 _i,Z_i; . . . ; X_i,Ym_i,Z_i) found inside the reference set (SET_r_i);

each suffix substring (Z_i) is equal to all other prefix substrings (Z_i) within the substring triples (X_i,Y 1 _i,Z_i; X_i,Y 2 _i,Z_i; . . . ; X_i,Ym_i,Z_i) found inside the reference set (SET_r_i);

either the prefix substring (X_i) or the suffix substring (Z_i) is not empty.

11. A data processing system, comprising:

a memory element adapted to store strings; and

a processor programmed to:

set a reference set (SET_r_i) of strings (STR_n_i);

inside the reference set (SET_r_i), find specific N-tuples ([Y 1 _i|Y 2 _i| . . . |Ym_i]) of substring triples (X_i,Y 1 _i,Z_i; X_i,Y 2 _i,Z_i; . . . ; X_i,Ym_i,Z_i) with N≧2 and m=1 . . . N; and

consider each N-tuple ([Y 1 _i|Y 2 _i| . . . |Ym_i]) as a candidate for representing related concepts;

where the processor is further programmed to provide that:

each concatenation (X_i Y 1 _i Z_i; X_i Y 2 _i Z_i; . . . ; X_i Ym_i Z_i) of the substrings triples (X_i,Y 1 _i,Z_i; X_i,Y 2 _i,Z_i; . . . ; X_i,Ym_i,Z_i) is an explicit member of the reference set (SET_r_i);

each middle substring (Y 1 _i, Y 2 _i, . . . , Ym_i) out of the middle substrings (Y 1 _i, Y 2 _i, . . . , Ym_i) is unequal to another middle substring (Y 1 _i, Y 2 _i, . . . ,Ym_i) out of the middle substrings (Y 1 _i, Y 2 _i, . . . ,Ym_i) within the substring triples (X_i,Y 1 _i,Z_i; X_i,Y 2 _i,Z_i; . . . , X_i,Ym_i,Z_i) found inside the reference set (SET_r_i);

each prefix substring (X_i) is equal to all other prefix substrings (X_i) within the substring triples (X_i,Y 1 _i,Z_i; X_i,Y 2 _i,Z_i; . . . ; X_i,Ym_i,Z_i) found inside the reference set (SET_r_i);

each suffix substring (Z_i) is equal to all other suffix substring (Z_i) within the substring triples (X_i,Y 1 _i,Z_i; X_i,Y 2 _i,Z_i; . . . ; X_i,Ym_i,Z_i) found inside the reference set (SET_r_i); and

either the prefix substring (X_i) or the suffix substring (Z_i) is not empty.

12. The data processing system according to claim 11 , further comprising at least one input/output controller and at least one system bus.