How to separate binary sequence into periodic binary sequences

Question

For example I want to separate this sequence

1 1 1 1 0 1 1 1 0 1

It can be done this way

Example of separation

where | is a binary OR. The first sequence has period 3 and offset 0, the second has period 4 and offset 1, the third has offset 2 and period 5.

It is better that they have the smallest possible period, and any offset less than the period. Is there any algorithm that can do it?

It seems that I can use Fourier Series somehow.

I expect to get an example of an algorithm, or the name of an existing algorithm that can do the job, preferably in C++

Answer 1

Algorithm

The following algorithm greedily adds bit sequences starting with the smallest periods and growing to cover all of the bits in the input sequence.

• Start with input sequence I of length N.
• Iterate period from 1 to N / 2
  • Iterate offset from 0 to period - 1
    • Generate a trial bitset T of the given period and offset
    • If T bitand ~I is not null, discard T and continue with the next offset
    • Record the bitset and the number of bits M in the bitset T bitand I.
  • If no bitsets were recorded, continue with the next period.
  • Add the bitset with the largest M to the output O.
  • Update the input with added bitset: I = I bitand ~T.
• The bitor of the output bitsets O is equal to I.

Sample Code

You can find the code and build instruction on GitHub in directory 76185918.

#include <bitset>
#include <iostream>
#include <random>

using BitSet = std::bitset<20>;

BitSet generate_periodic(size_t period, size_t offset) {
    BitSet bits;
    for (auto i = offset; i < bits.size(); i += period)
        bits[i] = true;
    return bits;
}

int main(int argc, const char *argv[]) {
    BitSet input;
    std::uniform_int_distribution<uint64_t> d;
    std::mt19937 rng;
    for (auto i = 0; i < input.size(); ++i)
        input[i] = d(rng) % 2;

    std::cout << "input : " << input << std::endl;

    std::vector<BitSet> series;

    for (auto i = 1; i < input.size(); ++i) {
        std::optional<BitSet> best_bits;
        size_t max{};
        for (auto j = 0; j < i; ++j) {
            auto bits = generate_periodic(i, j);
            auto common = (input bitand bits).count();
            auto excess = (~input bitand bits).count();
            if (excess == 0 and common > max) {
                best_bits = bits;
                max = common;
            }
        }

        if (best_bits) {
            input &= ~*best_bits;
            series.push_back(*best_bits);
        }
    }

    BitSet check;
    for (const auto& bits : series) {
        std::cout << "series: " << bits << std::endl;
        check |= bits;
    }
    std::cout << "check : " << check <<  std::endl;
    return 0;
}

The output.

input : 01101110110000111110
series: 00100000100000100000
series: 01000000010000000100
series: 00000010000000010000
series: 00000100000000001000
series: 00001000000000000010
check : 01101110110000111110