String processing of clickstream data

1. A method comprising:

assigning a plurality of unique symbols to a plurality of potential interactions with a website, respectively;

obtaining a plurality of asserted interaction 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 asserted interaction 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 asserted interactions with the website visited during the respective browsing session by the corresponding visitor;

generating a master string including the plurality of asserted interaction symbol sequences by concatenating the plurality of asserted interaction symbol sequences and a plurality of sentinel symbols together such that at least one sentinel symbol exists between each consecutive pair of asserted interaction symbol sequences in the master string;

generating a suffix array corresponding to the master string; and

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

2. The method of claim 1 further comprising:

monitoring the plurality of browsing sessions,

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

3. The method of claim 1 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.

4. The method of claim 3 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.

5. The method of claim 4 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.

6. The method of claim 5 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; 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.

7. The method of claim 6 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.

8. The method of claim 7 further comprising:

based on the suffix array and the LCP array, determining one or more most common n-step subsequences of asserted interactions from among the sequences of asserted interactions with 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; and

displaying the most common n-step subsequences to a user.

9. The method of claim 8 wherein the determining of the one or more most common n-step subsequences of asserted interactions 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 hardware storing computer-executable instructions; and

processor hardware configured to execute the instructions, wherein the instructions include:

assigning a plurality of unique symbols to a plurality of potential interactions with a website, respectively;

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

each browsing session corresponds to a visitor of the website;

for each browsing session, the interaction 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 interactions with the website visited during the browsing session by the corresponding visitor;

generating a master string including the plurality of interaction symbol sequences by concatenating the plurality of interaction symbol sequences and a plurality of sentinel symbols together such that at least one sentinel symbol exists between each consecutive pair of interaction symbol sequences in the master string;

generating a suffix array corresponding to the master string; and

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

12. The computer system of claim 11 wherein:

the instructions include monitoring the plurality of browsing sessions; and

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

13. The computer system of claim 11 wherein:

the 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.

14. The computer system of claim 13 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.

15. The computer system of claim 14 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.

16. The computer system of claim 15 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.

17. The computer system of claim 16 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.

18. The computer system of claim 17 the instructions include:

based on the suffix array and LCP array, determining one or more most common n-step subsequences of interactions from among the sequences of interactions 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; and

displaying the most common n-step subsequences to a user.

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.