# Thread: Finding most frequency sequences in data?

1. ## Finding most frequency sequences in data?

Given a sequence of bytes S, find a sub-sequence X which has maximum value of (Len(X)-1)*(Count(X)-1)... Then we can use shorter symbol to replace X in S.
Is there any algorithm for that? (with acceptable time and memory usage)

I've read XWRT's code, but it seems to seperate words by semantic, not for generic data? 2. Do you mean text preprocessor? You should check dict in FreeArc. 3. Originally Posted by Fu Siyuan Do you mean text preprocessor? You should check dict in FreeArc.
For generic data, we cannot use semantic information. For example, you can seperate English words by "," "."... but what if the input stream is a Chinese article? 4. Firstly do suffix sorting and compute LCP array (it could be done in one step).

Then you can apply following algorithm (assuming input has length N):
- prepare integer array of length N and initalize with zeros,
- initialize variable max to 0,
- for every item from LCP array (assuming you are iterating from beginning to end and keep current index in variable `index`):
-- if item == max do nothing
-- if item > max then do: while (max < item) { max++; array[max] = index; }
-- if item < max then do: while (max > item) { try((index - array[max]) * (max - 1), sa[index], max); max--; }

Where sa[] is an suffix array and try(weight, start, length) is a function that tracks the best subsequence (ie a simple max function inside).

Or something like that, probably this is slightly broken but general idea should work. 5. Originally Posted by RichSelian For generic data, we cannot use semantic information. For example, you can seperate English words by "," "."... but what if the input stream is a Chinese article?
I assume one would report the frequencies of the unicode characters and dump the contents as hex? Or maybe Google translate  6. Originally Posted by Karhunen Or maybe Google translate Prepare for a lossy transform ...  #### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•