2
$\begingroup$

I'm looking for an algorithm to construct a grammar which, given a set of words which can have multiple identical symbols, represents a compressed version of this set, that is, I can generate only the words of the set but the grammar will take less memory than the set himself.

Besides, I'm looking for an algorithm which can update the grammar when I want to remove a word of the set.

What type of algorithm is able to do that ?

I give a concrete example:

Consider a string S="abcdefghij", and then consider the finite set of words "cdhij", acdef", "fghi", "bcfgij", "defi".

I would like to construct a grammar which generates only this set of words (words which can be viewed as concatenation of various substrings of any length from the original string S).

Finally I would like to remove a word in the set and update subsequently the grammar.

Thank you.

$\endgroup$
  • $\begingroup$ Look at regular grammars, and closure properties of regular sets under boolean operations (union, intersection, complementation ...) ... I assume your set of words is simple enough, like finite for example. $\endgroup$ – babou Jun 20 '13 at 13:36
  • $\begingroup$ Thank you. "closure properties of regular sets under boolean operations (union, intersection, complementation ...)". By the operation "union", you mean that we can merge two grammar that describe/generate two sets ? $\endgroup$ – user7060 Jun 20 '13 at 14:07
2
$\begingroup$

it is not clear what you mean by "words which have multiple identical symbols". it sounds like you mean certain symbols are interchangeable. in that case, just replace all cases of an interchangeable symbol with a single representative symbol.

as to the more general question, there is an area of CS not-so-widely studied, called grammar based codes which is, roughly, focused on the idea of creating compressions of strings based on grammar expansions. in this way classic compression algorithms such as eg Lempel Ziv can be regarded as special cases of grammar compressions.

your problem is not so well defined unless you specify the type of grammar also, eg say CFG. if the grammar is generated by a recursive machine, then this problem is actually similar or almost identical to finding the Kolmogorov complexity of a string, which is undecidable in general.

$\endgroup$
  • $\begingroup$ Thank you. "it is not clear what you mean by "words which have multiple identical symbols". it sounds like you mean certain symbols are interchangeable. in that case, just replace all cases of an interchangeable symbol with a single representative symbol." I will edit my question to give an example. What I want is something like the algorithm Sequitur, except that sequitur compress one string in which there is similar structuration. I want to compress a set of words having similarities. The example will clarify what I want. Thank you again $\endgroup$ – user7060 Jun 21 '13 at 8:33
  • 1
    $\begingroup$ @user7060 looking over your clarification it appears you're dealing with a language with finite words, and indeed as babou suggests, FSMs/regular languages are sufficient, and have a concept of "compression" ie FSM minimization. RLs are a subset of all grammars so this is a special case of grammar compression. $\endgroup$ – vzn Jun 21 '13 at 15:23
  • $\begingroup$ Thank you, is an algorithm like sequitur adaptable to my case ? $\endgroup$ – user7060 Jun 21 '13 at 17:57
  • $\begingroup$ In fact not only my words are of finite lengths, but also the number of words... $\endgroup$ – user7060 Jun 21 '13 at 18:05
0
$\begingroup$

The keyword is "CFG induction": given several examples of words from a CFG, find the smallest/simplest context-free grammar (CFG) that generates those words. If you do a literature search with that phrase, you'll find prior work on this problem. It is a highly non-trivial problem, but you should be able to find some algorithms, e.g., the TBL algorithm. You might also find papers under the phrase "learning a CFG".

Another approach is to use regular languages (e.g., finite-state automata). There are known algorithms for learning regular languages, i.e., given one or more words from a regular language, find a small finite-state machine that accepts those words. See, e.g., the seminal algorithm by Angluin and this survey on the hardness of finding the absolutely smallest possible finite-state machine. For more, look for papers on "DFA learning" and related topics. You might also be interested in MERLIN and this book on learning grammars.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.