das beste Kompression

Question

Problem gibt:

eine Liste von Strings Gegeben, finden den Teil die, wenn sie von Anfang an von allen Saiten abgezogen, wo sie paßt und durch einen Escape-Byte ersetzt, gibt die kürzeste Gesamtlänge

Beispiel:

"foo", "fool", "bar"

Das Ergebnis ist: "foo", wie die Basiszeichenfolge mit den Zeichenfolgen "\0", "\0l", "bar" und einer Gesamtlänge von 9 Bytes. "\0" ist das Escape-Byte. Die Summe der Länge der ursprünglichen Strings ist 10, also haben wir in diesem Fall nur ein Byte gespeichert.

Ein naiver Algorithmus würde wie folgt aussehen:

for string in list 
    for i = 1, i < length of string 
     calculate total length based on prefix of string[0..i] 
     if better than last best, save it 
return the best prefix 

, die uns die Antwort geben wird, aber es ist so etwas wie O ((n * m)^2), die zu teuer ist.

Answer 1

Verwenden Sie einen Wald von Präfix Bäume (Trie) ...

f_2 b_1 
/  | 
o_2  a_1 
|  | 
o_2  r_1 
| 
l_1 

dann können wir das beste Ergebnis und garantieren, es finden, die von (depth * frequency) maximiert, die mit Ihrem Escape-Zeichen ersetzt werden. Sie können die Suche optimieren, indem Sie zuerst eine Verzweigung und eine gebundene Tiefe nach dem Maximum suchen.

Auf die Komplexität: O (C), wie in Kommentar erwähnt, für den Aufbau und für die Suche nach dem optimalen, es kommt darauf an. Wenn Sie die erste Elementhäufigkeit bestellen (O (A) - wobei A die Größe des Sprachenalphabets ist), können Sie mehr Zweige ausschneiden und haben eine gute Chance, eine sublineare Zeit zu erhalten.

Ich denke, das ist klar, ich werde es nicht aufschreiben - was ist das eine Hausaufgabe? ;)

Answer 2

Ich würde versuchen, indem Sie die Liste sortieren. Dann gehen Sie einfach von String zu String und vergleichen das erste Zeichen mit dem ersten Zeichen des nächsten Strings. Sobald Sie eine Übereinstimmung haben, würden Sie sich das nächste Zeichen anschauen. Sie müssen einen Weg finden, um das beste Ergebnis bisher zu verfolgen.

Answer 3

Nun, erster Schritt wäre, die Liste zu sortieren. Dann einen Durchlauf durch die Liste, wobei jedes Element mit dem vorherigen verglichen wird, wobei die längsten 2-Zeichen-, 3-Zeichen-, 4-Zeichen-usw.-Läufe verfolgt werden. Dann ist die Zahl der 20 3-stelligen Präfixe besser als die 15 4-stelligen Präfixe.