Finding most frequency sequences in data?

[RichSelian]

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?

[Fu Siyuan]

Do you mean text preprocessor? You should check dict in FreeArc.

[RichSelian]

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?

[Piotr Tarsa]

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.

[Karhunen]

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

[Cyan]

Or maybe Google translate

Prepare for a lossy transform ...