I'm interested in analyzing the randomness of strings using relative count for 1-, 2-, etc tuples.
E.g. for a long string "abbccba.." with an alphabet ["a", "b", "c"] , the quantities ["a", "b", "c"], ["aa", "ab", "ba", "bb", "ac", "ca", "cc", "bc", "cb"] etc should be approximately equal for every kind of tuples.
Of course it is convenient to encode the string in binary form with the alphabet ["0", "1"] (the number of tuples will be minimal), but how to do it correctly?
The primitive coding scheme {"a"→"00", "b"→"01", "c"→"10"]} (or similar) gives even a different number of "0" and "1"!
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ Please state your problem more clearly. What are your input and output? I also don't understand where binary encoding comes from. $\endgroup$– DmitryCommented Dec 26, 2022 at 19:13
-
$\begingroup$ What is the test for "correct"ness? $\endgroup$– Ray ButterworthCommented Dec 27, 2022 at 1:38
-
1$\begingroup$ Are you trying to encode strings from one alphabet with strings from another alphabet such that the resulting encoding is itself just as random as original string in some sense? I think the sense you're using is the frequency counts of n-grams? I suspect that such an encoding does not exist but perhaps you can preserve n+k-gram distributions assuming your input strings have a certain n-gram distribution. For instance you could have a = 0101, b = 1100, c = 1001 and that might be the sort of thing that could work. It's hard for me to say without much more work than I'm willing to put into this $\endgroup$– JakeCommented Dec 27, 2022 at 4:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Take a look at Huffman coding - efficient algorithm for finding optimal (as short as possible) binary coding for given string. This algorithm takes alphabet and weights (usually probabilities of each letter in your text) of each symbol in alphabet, as input. Then computes for each symbol in alphabet optimal coding.
I don't really understand your problem, but this might be helpful.
