# Finding short readable representation of words

I am looking for Input/Literature on

1. a readable way to represent words (which are accepted by automata)
2. an Algorithm, that constructs the Representation

For example, a word $w$ might contain a subsequence $v$ which is repeated $m$ times, i.e. $w= u \, \underbrace{v\cdots v}_{100} \,x$ where $u,v,w,x \in \Sigma^*$

In a readable representation, I would expect this subsequence to occur only once, together with the information about the 100 repetitions.

Motivation:

I am working on an interactive input interface for a tool, that works with words that are accepted by automata. It requires the user to interact with possibly long words

• generated by the system
• or select words interactively himself

My Approach:

The representation I currently use structurally can be understood is an ordered tree, where

• the leaves are symbols $a \in \Sigma$
• the inner nodes are repetition counters $i \in \mathbb{N}$

Example:

$w = ABABAC \, ABABACAC \,ABABACAC \,ABABACAC$

Representations

1. $\overbrace{AB}^{2}AC\overbrace{\overbrace{AB}^{2}\overbrace{AC}^{2}}^{3}$
2. $\overbrace{\overbrace{AB}^{2}AC}^{2}\overbrace{AC\overbrace{AB}^{2}AC}^{2}AC$

I have implemented an algorithm which, given $w$, finds the 2. representation. I would consider 1. more appealing, and I assume, that I would generally prefer representations that are minimal with respect to length (where length is the total amounts of symbols/tree-leaves)

My Questions:

1. Is there a good algorithm to find representations minimal with respect to length?
2. Does that have a name? Is there Literature on the topic? (I couldn't find anything useful)
3. Can someone think of an alternative/better approach?
• You seem do have re-invented a subset of (extended) regular expressions. What you have in 1. what commonly be written as $(AB)^2AC ((AB)^2(AC)^2)^3$. You can add spaces for readibility, or use a tree representation. – Raphael May 6 '17 at 7:24
• True, thanks for pointing that out - I guess its just the same, but without the Kleene star (unless there are more operations that represent more than a single specified number of repetitions) I am however not familiar with any research on this. – IARI May 6 '17 at 9:39

Given a string $S$ of length $n$, one can find the minimal representation in $O(n^3)$ time using dynamic programming.

Let's consider a representation as a binary tree. Each node of the tree generates a string (a substring of $S$). Each leaf generates to a single letter. The tree has two types of internal nodes: a concatenation node, which generates the concatenation of the strings generated by its two children; and a repetition node, which takes the string generated by its only child and repeats it $r$ times, where $r$ is an integer stored in the node. Your diagrams can all be represented in this form.

Now given a string $S$, we can find the minimal binary tree that generates it, using dynamic programming. We'll let $A[i,j]$ denote the minimal binary tree that generates the substring $S[i..j-1]$.

We can derive a recursive expression for $A[i,k]$. In particular, consider all of the following trees:

• a tree with a concatenation node at the root, and a left child $A[i,j]$ and a right child $A[j,k]$ (one such tree for each $j$)

• a tree with a repetition node at the root, holding the integer $r$, and a single child $A[i,i+(j-i)/r]$ (one such tree for each divisor $r$ of $j-i$)

We will find the smallest of these trees, and store the result in $A[i,k]$.

By evaluating this recursive relation in a bottom-up fashion (i.e., fill in entries of $A[i,j]$ in order of increasing value of $j-i$), we can fill in the entire table. There are $O(n^2)$ entries in the table, and each entry takes $O(n)$ time to fill in, so the total running time is $O(n^3)$.

As far as related concepts, your idea is similar to a context-free grammar, augmented with the notion of repetition (e.g., we add a production $A \to r \otimes B$, which means that if a word $w$ that can be produced by $B$, then $w^r$ can be produced by $A$). I haven't seen that particular notion explored, but context-free grammars are well-explored.

If you want heuristics to find a relatively small representation, but not necessarily the minimal one, you might be interested in the Sequitur algorithm and other uses of context-free grammars for data compression. I think that the Sequitur algorithm can be modified to work in your setting: i.e., given a string, find a (hopefully small) representation of that string.

• Isn't repetition part of EBNF? – Raphael May 6 '17 at 7:25
• @Raphael, it's a different kind of repetition. Here we want all of the repeats to be the same exact string (which must be produced by the terminal $B$). EBNF allows each repeat to be a different string, as long as it matches the terminal $B$. (Also I think EBNF doesn't let you specify the number of repetitions, so it's basically like $*$ in a regular expression.) – D.W. May 6 '17 at 16:40
• I suppose its worth to mention, that minimal representations are not unique in general: consider the word $ABABCBC$. Thanks to Matthias Heizman for raising the question. – IARI May 7 '17 at 19:08
• @D.W. Ah, right. I thought that since regexps usually have fixed-range repetition EBNF would have it, too. – Raphael May 7 '17 at 19:23