The Smallest Grammar Problem
Here is a write-up for the main site.
Some changes I want to add are:
- You can use any language.
- You must formally prove the Big-O of the worst case of your algorithm in your answer.
- You must formally prove the correctness of your algorithm as well.
As far as running the code, that's up to the viewers of the page who wish to run the algorithm, as I can't reasonably be expected to compile code from so many different languages.
Before I post to main, I will have a solution to the problem which provides correct answers and can check if an output of your algorithm is correct. It will be coded in Python 3.x. But since the question is about fastest algorithm, that shouldn't matter.
Your algorithm only needs to provide one correct smallest grammar to a given input string (there are usually many), and it must be in standard form (see below).
Therefore my Python 3.x code will enumerate all smallest grammars up to standard form.
I will provide an example formal proof of my algorithm, both so that you can see what a formal proof entails and also so that we know that the solutions we're computing are indeed correct.
How does this all sound to you all? Where would you like to see improvements in the write-up? I am okay with rewriting the whole thing :)
The Smallest Grammar Problem (SGP), is defined as:
Given an input string s, compute a smallest CFG g such that L(g) = {s} generates the string and only the string s itself. Grammar size is defined as:
$$
|g| = \sum_{A \in \text{Vars}(g)} |g(A)|
$$
Where the grammar is $$g = \{ A \to g(A), B \to g(B), C \to g(C), \dots \}, \\ \text{ and, } |g(A)|$$ simply takes the string length.
So the size of the grammar g is the sum of the lengths of all right hand sides (RHS's) of the production rules making up g.
All literature on this problem talks about approximation algorithms, and not one article demonstrates a decent exact smallest grammar algorithm. That is to say, computing the very thing the article is about in the first place. I would personally like to see what an exact SGP algorithm looks like. How optimal can we make it, and so on...
I have had many ideas on how to solve the problem. Every one of my attempts ended up with inefficient (exponential running time code). The question is can you make a speedy SGP algorithm.
The language of choice for speed of development is of course Python. Though these resulting programs should not be used in a production compressor for large data. Still, an exponential algoritm remains inefficient even if ported to C++.
So, the benchmark will be running time. You are to use standard Python 3.x, and not Cython, etc.
I have included below some relatively bug-free boilerplate utility code that you may wish to use. It handles the methods for enumerating substrings of a grammar and so on.
These are methods I will use in my own answer, which I am currently still designing. My approach will use what I call the "Groupoid of smallest grammars". Groupoids are heavily involved in combinatorial optimization problems at an advanced level, so from that heuristic they seem like the right structure to use. Another way to code this problem is translating it into a linear integer programming problem and representing substring conflicts using summation modulo 2 (or something like that). Though, linear programming problems open another can of worms since a lot of those problems also have hard running times.
To teach you about the problem, let's inspect some examples. Though we cannot prove that the examples are indeed smallest grammars - there are no theorems out there that tell whether a certain grammar is indeed minimal. A proven algorithm however, tells you whether or not your grammar is minimal. You will need to provide a proof of your algorithm in English / math text accompanied by relavent chunks of your algorithm.
Example 1. Take the string s = aaaa. Reduce it with B -> aa to get the CFG g = { A -> BB, B -> aa}$. Measure its size: |g| = 4 which is the same size as s and so therefore no compression happened.
Example 2. Take the string s = aaaaaa. Reduce using either B -> aaa, or C -> aa to get two smallest grammars:
$$
g = \{A \to BB, B \to aaa\} \\
g' = \{A \to CCC, C \to aa\}
$$
Those, by experience and inspection, are precisely the full set of smallest grammars of the string of 6 $a$'s.
Example 3. Let s = abababab. Reduce using first B -> bab then C -> ab.
You get:
$$
g = \{A \to aBaB, B \to bab \}, |g| = 7 \\
g' = \{A \to CCCC, C \to ab \}, |g| = 6 \\
$$
So as you can see, a naive greedy algorithm can quite easily make wrong min / max guesses and come up with a resulting grammar that is not optimal.
Define a grammar to be reduced if no substring of length 2 or more occuring within it occurs more than once.
Reduced does not imply smallest and smallest does not imply reduced. However, every smallest grammar can be reduced, without a change to its size. Thus we will call a reduced smallest grammar the standard form of the smallest grammar.
Rules
1. Your algorithm must not only solve the SGP (which is to compute at least one smallest grammar), but it must enumerate all smallest grammars, in standard form, of a given input string.
- You must provide a formal proof of your algoritm in your answer. I.e. a mathematical argument that it does indeed compute the output describe in rule 1.
3. Python 3.x, no Cython or C++.
The standard form requirement reduces the total number of result smallest grammars that you must list.
Code to get you started:
# pip install bidict
from bidict import bidict
# Any involved grammar in a smallest grammar algorithm will usually have unique RHS's and unique
# variables on the left. So it's a perfect use case for a bidirectional dictionary. Using
# one should speed up the code greatly, otherwise we have to loop through dict values or create
# an inverse dictionary on the fly.
class Grammar:
def __init__(self, s:str):
"""
Start out with the trivial grammar g = {S -> s}.
"""
self._alphabet = set(s)
self._previousVar = 'A'
A = self.new_variable()
self._start = A
self._definition = bidict({ A : s }) # Bidict is useful, we do use the inverse lookup
def grammar_size(self):
"""
This is the standard definition of grammar size (cost) used in all literature
with regards to the smallest grammar problem. Minimizing this means you've found
a smallest grammar for the given input string s.
"""
size = 0
for A, rhs in self._definition.items():
size += len(rhs)
return size
def __getitem__(self, A):
"""
Compute one iteration of expansion at a variable only.
"""
return self._definition[A]
def fully_expanded_string(self, s=None, memo=None):
"""
Fully expand the a string passed in. Could be a variable or a string of mixed
variables and terminals. Any string really. If variables of this grammar
occur within the string, they are fully expanded to what the grammar defines
them to be expanded to, recursively.
"""
if memo is None:
memo = {}
if s is None:
s = self._start
exp = ''
for x in self._definition[s]:
if x in self._definition:
exp += self.fully_expanded_string(x)
else:
exp += x
memo[s] = exp
return exp
def __repr__(self):
"""
The obvious representation for debugging / showing results.
"""
rep = ''
for A, rhs in self._definition.items():
rep += A + ' ---> ' + rhs + '\n'
rep = rep[:-1] # remove last newline
return rep
def __str__(self):
return repr(self)
def new_variable(self):
"""
Take the first unicode character that is not already in the grammar's alphabet.
So it will eventually take weird-appearing characters, but who cares. I think this
methodology beats escape or delimit characters. However, you're also limited to a
maximal alphabet size that is the Unicode character set. That's usually just fine.
If not, then what on Earth are you compressing ? :)
"""
X = self._previousVar
while X in self._alphabet:
X = chr(ord(X) + 1)
self._alphabet.add(X)
self._previousVar = X
return X
def greedily_reduce(self):
"""
A grammar is defined to be reduced if no substring of length >= 2 occurs twice, anywhere
within the grammar. There are many paths to a reduced grammar. The smallest grammar
problem involves taking the correct reduction path such that the resulting grammar is
indeed minimal in size. Greedy algorithms are known not to work in general for producing
a smallest grammar. However, they can easily produce a reduced grammar as you can witness.
A smallest grammar is not necessarily reduced, though there exists a smallest grammar which
is the reduction of that smallest grammar. Reducing a smallest grammar would involve
compressing all substrings of length 2 that occur exactly twice. g = {S -> abab} has the
same size as g' = {S -> AA, A -> ab}, namely 4. Thus reducing a smallest grammar does not
reduce the size (obviously), but instead puts it into a "standard form", which might be
useful to your algorithm.
"""
R = self.repeating_disjoint_substring_indices()
while len(R) > 0:
m = self.arbitrary_greedy_max_function(R)
if m not in self._definition.inv:
M = self.new_variable()
else:
M = self._definition.inv[m]
for A, indices in R[m].items():
subtract = 0
for i in indices:
rhs = self._definition[A]
self._definition[A] = rhs[0:i-subtract] + M + rhs[i+len(m)-subtract:]
subtract += len(m) - 1
self._definition[M] = m
R = self.repeating_disjoint_substring_indices()
def arbitrary_greedy_max_function(self, R:dict):
"""
Seems like a good choice. The total coverage of a substring if you were to compress it
into a grammar rule.
For example:
If g = {A -> BaBaBaCC, B -> CCC, C -> aaa} then (3 Ba's) * |Ba| = 3 * 2 = 6 is maximal.
"""
total_indices = lambda rule_indices: sum(len(x) for x in rule_indices.values())
return max(R.keys(), key=lambda x: len(x) * total_indices(R[x]))
def repeating_disjoint_substring_indices(self, min_len=2):
"""
If there is overlap, this algorithm clearly does a leftmost packing.
Same as `disjoint_substring_indices()` except we compute only the
substrings that occur >= 2 times within the same rule or in two
separate rules.
Output form:
{
'substring1' : {
'A': [0, 3, 7],
'B': [1, 4, 8],
},
'substring2' : ...
}
where 'A' indicates the rule in which the indices occur, and the list is the list
of indices within the rule RHS string where you'll find the substring occuring.
The indices returned are such that the substrings occuring at those indices are mutually
disjoint (they don't overlap).
"""
return self._repeatingSubstringIndices(min_len, lambda t, indices: indices)
def repeating_substring_indices_all(self, min_len=2):
"""
Return all substring indices even if there is overlaps among them.
Output form:
{
'substring1' : {
'A': [0, 3, 7],
'B': [1, 4, 8],
},
'substring2' : ...
}
where 'A' indicates the rule in which the indices occur, and the list is the list
of indices within the rule RHS string where you'll find the substring occuring.
This includes all occurences even if two occurences overlap.
"""
return self._repeatingSubstringIndices(min_len, lambda t, indices: self.all_substring_indices(t))
def _repeatingSubstringIndices(self, min_len=2, rule_indices_func=None):
"""
Output form:
{
'substring1' : {
'A': [0, 3, 7],
'B': [1, 4, 8],
},
'substring2' : ...
}
where 'A' indicates the rule in which the indices occur, and the list is the list
of indices within the rule RHS string where you'll find the substring occuring. Overlap
or disjoint is governed by the rule_indices_func passed in.
"""
S = {}
for A, rhs in self._definition.items():
T = self.disjoint_substring_indices(rhs, min_len)
for t, indices in T.items():
if t not in S:
S[t] = { A : indices }
else:
S[t][A] = indices
R = {}
for t, rule_indices in S.items():
if len(rule_indices) >= 2:
R[t] = rule_indices_func(t, rule_indices)
else:
for var, indices in rule_indices.items():
if len(indices) >= 2:
R[t] = rule_indices_func(t, rule_indices)
break
return R
@staticmethod
def disjoint_substring_indices(s:str, min_len=2, max_len=None):
"""
Leftmost-first packed indices of all substrings of the string s. The substring
occurences (indexes) are guaranteed to be of disjointly occuring substrings.
If two occurences overlap, by for-loop logic we're taking the leftmost. Hence
"leftmost-first packed".
Output form:
{
'substring1' : {
'A': [0, 3, 7],
'B': [1, 4, 8],
},
'substring2' : ...
}
where 'A' indicates the rule in which the indices occur, and the list is the list
of indices within the rule RHS string where you'll find the substring occuring.
The indices are such that the substrings occuring at those indices are disjoint
(they don't overlap).
"""
if max_len is None:
max_len = int(len(s)/2) # Maximum length of a repeated substring
S = {}
for i in range(0, len(s)-min_len+1):
for j in range(i+min_len, i+min(max_len, len(s))+1):
t = s[i:j]
if t in S:
if i >= max(S[t]) + len(t):
S[t].append(i)
else:
S[t] = [i]
return S
def all_substring_indices(self, t:str):
"""
The indices of all occurences of the given substring. Output form:
{
'A' : [0, 3, 7],
'B' : [1, 4, 8],
...
}
where 'A' indicates the rule in which the indices occur, and the list is the list
of indices within the rule RHS string where you'll find the substring occuring.
This includes all occurences even if two occurences overlap.
"""
R = {}
for A, rhs in self._definition.items():
for i in range(0, len(rhs)-len(t)):
if rhs[i:].startswith(t):
if A not in R:
R[A] = [i]
else:
R[A].append(i)
return R
def include_all_possible_rules(self):
"""
A possible rule is one such that the length of its RHS is >= 2 and fully
expanded it occurs at least twice in the input string s. Including all possible
rules does not change the fact that the grammar expands to s for some starting
variable. In other words we still have a grammar for s, by definition, though
some of its rules may be unused.
"""
# So first get all disjointly repeating substrings:
R = self.repeating_disjoint_substring_indices()
# To "include all rules" we form a rule for each repeating substring:
for r in R:
A = self.new_variable()
if r not in self._definition.inv:
self._definition[A] = r
if __name__ == '__main__':
s = 'aaaaaa'
g = Grammar(s)
g.greedily_reduce()
print(g)
print('The canonical example on a singleton alphabet. The smallest example such that the smallest '
f'grammar is indeed smaller than the input {s}')
print('-----------')
s = 'ababab'
g = Grammar(s)
g.greedily_reduce()
print(g)
print(f"This is known to indeed be a smallest grammar of {s}, by inspection.")
print('-----------')
s = 'abcabcabababc'
g = Grammar(s)
g.greedily_reduce()
print(g)
print(f"Similarly, this too also is probably a smallest grammar for {s}")
print('-----------')
s = 'ababababbaaaaaaaabbbbaa'
print(s)
g = Grammar(s)
g.include_all_possible_rules()
g.greedily_reduce()
s1 = g.fully_expanded_string()
print(g)
assert (s1 == s)
print('A more complicated example demonstrating "including all possible rules" and then greedily reducing '
'everything.')
print('-----------')
Which prints:
A ---> BBB
B ---> aa
The canonical example on a singleton alphabet. The smallest example such that the smallest grammar is indeed smaller than the input aaaaaa
-----------
A ---> BBB
B ---> ab
This is known to indeed be a smallest grammar of ababab, by inspection.
-----------
A ---> CCBBC
B ---> ab
C ---> Bc
Similarly, this too also is probably a smallest grammar for abcabcabababc
-----------
ababababbaaaaaaaabbbbaa
A ---> DDOLLLbbbO
B ---> ab
C ---> aba
D ---> BB
E ---> ba
F ---> bab
G ---> abb
H ---> bb
I ---> bba
J ---> bbL
K ---> baa
L ---> aa
M ---> aaa
N ---> LL
O ---> bL
A more complicated example demonstrating "including all possible rules" and then greedily reducing everything.
-----------
