login
Maximum, over all binary strings w of length n, of the size of the smallest string attractor for w.
3

%I #33 Jan 09 2021 00:42:18

%S 1,2,2,2,2,3,3,3,3,3,3,4,4,4,4,5,5,5,5

%N Maximum, over all binary strings w of length n, of the size of the smallest string attractor for w.

%C A set S of positions of a string w[1..n] is called a "string attractor" if every nonempty contiguous block occurring in w has an occurrence in w that touches at least one of the positions of S. For example, "alfalfa" has a string attractor of size 3: {3,4,5}.

%C 0 has smallest string attractor size 1;

%C 01 has smallest string attractor size 2;

%C 001011 has smallest string attractor size 3;

%C 000100101011 has smallest string attractor size 4;

%C 0001001010110111 has smallest string attractor size 5.

%C These are the shortest binary strings achieving this minimum attractor size.

%H D. Kempa and N. Prezza. <a href="https://dl.acm.org/doi/abs/10.1145/3188745.3188814">At the roots of dictionary compression: string attractors</a>. In STOC'18 Proceedings, ACM Press, 2018, pp. 827-840.

%o (Python)

%o from itertools import product, combinations

%o def blocks_ranges(w):

%o blocks = dict()

%o for i in range(len(w)):

%o for j in range(i+1, len(w)+1):

%o wij = w[i:j]

%o if wij in blocks: blocks[wij].append(set(range(i, j)))

%o else: blocks[wij] = [set(range(i, j))]

%o return blocks

%o def is_attractor(S, w):

%o br = blocks_ranges(w)

%o for b in br:

%o for i in range(len(br[b])):

%o if S & br[b][i]: break

%o else: return False

%o return True

%o def lsa(w): # length of smallest attractor of w

%o for r in range(1, len(w)+1):

%o for s in combinations(range(len(w)), r):

%o if is_attractor(set(s), w): return r

%o def a(n): # only search strings starting with 0 by symmetry

%o return max(lsa("0"+"".join(u)) for u in product("01", repeat=n-1))

%o print([a(n) for n in range(1, 12)]) # _Michael S. Branicky_, Dec 20 2020

%K nonn,more

%O 1,2

%A _Jeffrey Shallit_, Dec 12 2020

%E (17)-a(19) from _Michael S. Branicky_, Dec 20 2020