String processing of clickstream data

1. A method comprising:

assigning a plurality of unique symbols to a plurality of pages of a web site, respectively;

obtaining a plurality of page symbol sequences of a plurality of browsing sessions, respectively, wherein:

each browsing session corresponds to a visitor of the website and

for each browsing session, the page symbol sequence of the respective browsing session is a sequence of symbols, from among the plurality of unique symbols, that corresponds, respectively, to a sequence of pages of the website visited during the respective browsing session by the corresponding visitor;

generating a master string including the plurality of page symbol sequences;

generating a suffix array corresponding to the master string;

generating a longest common prefix (LCP) array corresponding to the suffix array; and

based on the suffix array and the LCP array, determining one or more most common n-step subsequences of pages from among the sequences of pages of the website visited during the plurality of browsing sessions by the visitors to which the plurality of browsing sessions correspond, n being an integer greater than 1.

2. The method of claim 1 , further comprising:

monitoring the plurality of browsing sessions,

wherein the monitoring includes obtaining the sequence of pages of the website visited during the browsing session by the corresponding visitor.

3. The method of claim 1 , wherein the generating of the master string comprises:

concatenating the plurality of page symbol sequences and a plurality of sentinel symbols together such that at least one sentinel symbol exists between each consecutive pair of page symbol sequences in the master string.

4. The method of claim 3 , further comprising:

defining a plurality of suffixes of the master string,

wherein each suffix is a substring of the master string and

wherein the defining the plurality of suffixes includes

assigning indexes to symbols included in the master string, respectively and

for each assigned index, defining a suffix corresponding to the assigned index.

5. The method of claim 4 , wherein, for each index, from among the assigned indexes, the suffix corresponding to the index is a substring including:

the symbol of the master string to which the index is assigned and

the symbols of the master string to which any subsequent indexes, from among the assigned indexes, are assigned.

6. The method of claim 5 , wherein the generating of the suffix array comprises:

arranging the plurality of suffixes lexicographically and

generating, as the suffix array, an array storing the assigned indexes in a same order as the suffixes, from among the lexicographically arranged plurality of suffixes, that correspond to the assigned indexes, respectively.

7. The method of claim 6 , wherein the generating of the LCP array comprises:

generating the LCP array such that the LCP array stores, for each consecutive pair of indexes from among the assigned indexes stored in the suffix array, a corresponding LCP value,

wherein, for each consecutive pair of indexes from among the assigned indexes stored in the suffix array, the corresponding LCP value in the LCP array indicates a size of an LCP of the consecutive pair of suffixes, from among the lexicographically arranged plurality of suffixes, that correspond to the consecutive pair of indexes.

8. The method of claim 7 , wherein each LCP value in the LCP array is a total number of symbols included in the consecutive pair of suffixes that correspond to the consecutive pair of indexes to which the LCP value corresponds.

9. The method of claim 8 , wherein the determining of the one or more most common n-step subsequences of pages comprises:

identifying, from among the LCP values stored in the LCP array, one or more consecutive runs of LCP values that are equal to or greater than n;

for each identified consecutive run of LCP values, determining a total number of LCP values in the identified consecutive run of LCP values;

determining, as one or more top consecutive runs of LCP values, one or more consecutive runs of LCP values, from among the identified consecutive runs of LCP values, having the highest total numbers of LCP values; and

identifying, as the one or more most common n-step subsequences, one or more n-step subsequences corresponding, respectively, to the one or more top consecutive runs of LCP values.

10. The method of claim 9 , wherein, for each of the top consecutive run of LCP values, the n-step subsequence corresponding to the top consecutive run of LCP values is a first n symbols held in common by the consecutive pairs of suffixes that correspond to the consecutive pairs of indexes to which the LCP values in the top consecutive run of LCP values correspond.

11. A computer system comprising:

memory storing computer-executable instructions and

a processor configured to execute the computer-executable instructions, wherein the computer-executable instructions include:

assigning a plurality of unique symbols to a plurality of pages of a website, respectively,

obtaining a plurality of page symbol sequences of a plurality of browsing sessions, respectively, wherein:

each browsing session corresponds to a visitor of the web site,

for each browsing session, the page symbol sequence of the browsing session is a sequence of symbols, from among the plurality of unique symbols, that corresponds, respectively, to a sequence of pages of the website visited during the browsing session by the corresponding visitor,

generating a master string including the plurality of page symbol sequences,

generating a suffix array corresponding to the master string,

generating a longest common prefix (LCP) array corresponding to the suffix array, and

based on the suffix array and LCP array, determining one or more most common n-step subsequences of pages from among the sequences of pages of the website visited during the plurality of browsing sessions by the visitors to which the plurality of browsing sessions correspond, n being an integer greater than 1.

12. The computer system of claim 11 , wherein:

the computer-executable instructions include monitoring the plurality of browsing sessions and

the monitoring includes obtaining the sequence of pages of the website visited during the browsing session by the corresponding visitor.

13. The computer system of claim 11 , wherein the generating of the master string includes:

concatenating the plurality of page symbol sequences and a plurality of sentinel symbols together such that at least one sentinel symbol exists between each consecutive pair of page symbol sequences in the master string.

14. The computer system of claim 13 , wherein:

the computer-executable instructions include defining a plurality of suffixes of the master string,

each suffix is a substring of the master string, and

the defining the plurality of suffixes includes:

assigning indexes to symbols included in the master string, respectively and

for each assigned index, defining a suffix corresponding to the assigned index.

15. The computer system of claim 14 , wherein, for each index, from among the assigned indexes, the suffix corresponding to the index is a substring that includes:

the symbol of the master string to which the index is assigned and

the symbols of the master string to which any subsequent indexes, from among the assigned indexes, are assigned.

16. The computer system of claim 15 , wherein generating the suffix array includes:

arranging the plurality of suffixes lexicographically and

generating, as the suffix array, an array storing the assigned indexes in a same order as the suffixes, from among the lexicographically arranged plurality of suffixes, that correspond to the assigned indexes, respectively.

17. The computer system of claim 16 , wherein:

generating the LCP array includes generating the LCP array such that the LCP array stores, for each consecutive pair of indexes from among the assigned indexes stored in the suffix array, a corresponding LCP value and

for each consecutive pair of indexes from among the assigned indexes stored in the suffix array, the corresponding LCP value in the LCP array indicates a size of an LCP of the consecutive pair of suffixes, from among the lexicographically arranged plurality of suffixes, that correspond to the consecutive pair of indexes.

18. The computer system of claim 17 , wherein each LCP value in the LCP array is a total number of symbols included in the consecutive pair of suffixes that correspond to the consecutive pair of indexes to which the LCP value corresponds.

19. The computer system of claim 18 , wherein determining the one or more most common n-step subsequences of pages includes:

identifying, from among the LCP values stored in the LCP array, one or more consecutive runs of LCP values that are equal to or greater than n,

for each identified consecutive run of LCP values, determining a total number of LCP values in the identified consecutive run of LCP values,

determining, as one or more top consecutive runs of LCP values, one or more consecutive runs of LCP values, from among the identified consecutive runs of LCP values, having the highest total numbers of LCP values, and

identifying, as the one or more most common n-step subsequences, one or more n-step subsequences corresponding, respectively, to the one or more top consecutive runs of LCP values.

20. The computer system of claim 19 , wherein, for each of the top consecutive run of LCP values, the n-step subsequence corresponding to the top consecutive run of LCP values is a first n symbols held in common by the consecutive pairs of suffixes that correspond to the consecutive pairs of indexes to which the LCP values in the top consecutive run of LCP values correspond.