4

I have some DAGs (directed acylic graphs) and I want to merge them in order to minimize the number of nodes (we could say that every node has a cost, while edges are free).

These four different DAGs (directed from left to right)...

a-b-c
a-d-c
a-c
c-a

...should become:

 /---\
a--b--c-a
 \-d-/

This is not a real DAWG (directed acyclic word graph): I don't want to store information like "is 'adc' included?". My structure could only answer to this question: "it would be possible that 'adc' was one of the words?".

Is there an algorithm for this purpose?

Update (12/15/14) - Levenshtein distance

I tried something different: I used Levenshtein distance to find the minimum number of edits required in order to transform a string into another (node=character and chain=sequence of nodes/characters=word). My algorithm ignores deletion, and insert characters instead of replacing them. Here's the interesting part (Python code):

current = words[0]
for word in words[1:]:
    edit = editops(current, word)
    customEdit = [('insert', s, d) for op, s, d in edit if op != 'delete']
    current = apply_edit(customEdit, current, word)

Sometimes there are unneeded characters, so I remove them at the end of the process. If I change the words order I get different results, so I run my code many times shuffling words in order to find a shorter string (shuffling seems to provide better result with fewer iterations than permutations, even if words are sorted by length).

If every character is a node, and every word is a DAG, I can easily get a good approximation of the DAG I'm looking for.

The main problem with this approach is that I don't know how the best result will look like so I don't know when to stop (I can't check every result of my permutation: it will take too much time!).

Here's my code (tested with Python 2; python-Levenshtein is needed). The output looks like this:

ldoarmilpesouimtr (17)
iapmdsoeluiortem (16)
diolposarmieutm (15)
^C
Original size: 22
Compressed: 15

diolposarmieutm (lorem)
diolposarmieutm (ipsum)
diolposarmieutm (dolor)
diolposarmieutm (sit)
diolposarmieutm (amet)

Is it a good way to solve this problem? What it could be improved? Do you know if it's possible to know the minimum number of nodes/characters needed in order to stop the algorithm when I get the optimum?

  • When you say you want to merge them, this implies that you can string them together (e.g. a-b-c-a-b-c...). Is this correct? If so, this sounds like a regular expression to me (the theoretical type used to model FSAs, not the type included in software libraries). – user22815 Dec 14 '14 at 4:43
  • @Snowman I can string them together, but this makes sense to me only at the end of the process (if I merge a-b and c-d as c-d-a-b it's ok, but when I add a-f I get c-d-a-b-f while the correct result would be a-b-c-d-e-f) – Francesco Frassinelli Dec 14 '14 at 8:48
  • Do you care that it looks like i->e is valid in the output even though it's not in any of the words? If not, the output sounds like a string, not a DAG. – raptortech97 Dec 15 '14 at 21:58
  • @raptortech97 It looks like they are the same problem to me: from a DAG I can build many strings, and from one of those strings, using words, I can build the corresponding DAG. This is why I tried to use Levenshtein (which works on strings) to generate the optimum DAG, but this is just an experiment which seems to work better than my previous node-based approach. I can reply to you with "No, I don't care", because even in this case I should be able to build the DAG. – Francesco Frassinelli Dec 16 '14 at 9:42
  • I think you're looking for this: Optimal insertion in deterministic DAWGs: citeseerx.ist.psu.edu/viewdoc/… It details how to create an optimal dictionary-representing DAWG. It's not a particularly easy read. – DaleJ Jul 22 '15 at 20:00
1

I think your structure is the line graph of the minimal DAWG. I have generated these before, three years ago, by building the minimal DAWG, from that its line graph, then minimising the line graph. I searched the literature and Google extensively and never found this last step. I concluded that the DAWG was more useful, generally, but the line DAWG was better for display to those unaccustomed to DAWGs. There is another name for a DAWG used in natural language processing, a Word Something, the something elludes me right now.

Your adc example suggests a DAWG where everyone node has a # edge to the sink.

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.