In elkaar passen van strings

[TheBlasphemer]

Ik ben momenteel bezig een klein compressie algoritme voor plaatjes te implementeren. Het werkt op regel/rij-basis, en het compressen van elke individuele rij heb ik al grotendeels optimaal klaar.
In het formaat dat ik probeer op te slaan (wat overigens geen publiekelijk formaat is) komt na de header voor elke rij een DWORD, welke aangeeft op welke offset de rij begint. De lengte van de rij is variabel, maar bekend (e.g. het programma zal nooit verder lezen dan de lengte van de betreffende rij).
Op dit moment gooi ik alle rijen nog simpelweg achter elkaar, en bereken de offset simpelweg door optellen.

Echter bedacht ik me net dat identieke rijen (bijvoorbeeld zwarte rijen) op zich maar 1 keer opgeslagen hoeven te worden, en ik op deze manier ruimte kan besparen. Dit is op zich al een hele ruimte besparing, maar ik geloof dat het nog compacter kan: sommige rijen zullen vrijwel hetzelfde eindigen als anderen beginnen, in principe zou dit dus "in elkaar gepast" kunnen worden.
Nu is mijn probleem: hoe doe ik dit zo efficient mogelijk?

Om een kort voorbeeld te geven met woorden: stel ik wil de volgende woorden opslaan:
tom
noot
aap
pa
ma

de simpele manier zou zijn: (14 karakters)
0 3 7 10 12
tomnootaappama

een ietwat efficientere zou bijvoorbeeld zijn: (13 karakters)
0 3 7 9 11 (de p in aap en pa wordt bij elkaar gevoegd).
tomnootaapama

Een (in mijn ogen vrij) optimale oplossing: (10 karakters)
3 0 6 8 5
nootomaapa

Ik zat zelf al te denken om vanaf het langste woord te beginnen en er telkens kortere woorden in te plakken (het zij in, voor, of na de huidige reeks).

Wat het een en ander eventueel nog ietsje uitdagender kan maken, maar wat waarschijnlijk vrij triviaal in te meten is in een simpelere oplossing, is dat in het laatste karakter van elke rij meestal slechts maar enkele bits worden gebruikt, en die andere dus kunnen worden aangepast.

[crisp]

Wat jij beschrijft staat bekend als run-length encoding

[TheBlasphemer]

crisp schreef op maandag 28 april 2008 @ 01:20:
Wat jij beschrijft staat bekend als run-length encoding

is RLE niet alleen het weghalen van herhalende data?
Wat ik probeer is niet het weghalen van herhalende karakters of woorden, maar het in elkaar passen van de woorden zonder de woorden zelf aan te passen.
Ik kan dus alleen de posities van woorden veranderen, en eventueel laten overlappen mits ze dezelfde karakters hebben...

EDIT:
Heb net even gepoogd het brute force te doen (alle mogelijke volgordes proberen), maar dat lukte niet echt.
Na even nadenken kwam ik erachter dat het eigenlijk een beetje onmogelijk is, aangezien die O(n!) zou zijn: bij 16 woorden al ruim 20922789888000 mogelijkheden. Toch iets te veel

[ Voor 21% gewijzigd door TheBlasphemer op 28-04-2008 03:56 ]

[.oisyn]

Was er niet ooit een got contest die zoiets deed? Maar dan op een 2d grid ipv een 1d grid zoals jij het nu probeert te doen.

[RobIII]

Programming Contest Nieuwe Stijl: Contest 2 *WINNAARS LEZEN*

[Hydra]

TheBlasphemer schreef op maandag 28 april 2008 @ 01:14:
de simpele manier zou zijn: (14 karakters)
0 3 7 10 12
tomnootaappama

een ietwat efficientere zou bijvoorbeeld zijn: (13 karakters)
0 3 7 9 11 (de p in aap en pa wordt bij elkaar gevoegd).
tomnootaapama

Een (in mijn ogen vrij) optimale oplossing: (10 karakters)
3 0 6 8 5
nootomaapa

Je mist ten eerste nog informatie om uit die string weer 'woorden' te halen. Ten tweede kun je, als je perse herhalende patronen efficient op wil slaan, gewoon een LZW implementatie maken.