Finden Sie das Präfix substring die beste Kompression gibt

Question

Problem:

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

Beispiel:

"foo", "fool", "bar"

Das Ergebnis ist: „foo“, wie die Basiszeichenfolge mit den Saiten "\0", "\0l", "bar" und eine Gesamtlänge von 9 Bytes. "\0" ist der Escape-Byte. Die Summe der Länge der ursprünglichen Strings ist 10, so dass in diesem Fall, dass wir 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

Das gibt uns die Antwort, 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, finden und garantieren es, durch (depth * frequency) maximiert, die mit Ihren Escape-Zeichen ersetzt werden. Sie können die Suche optimieren, indem eine Niederlassung und gebundene Tiefe erste Suche nach dem Maximum zu tun.

Auf der Komplexität: O (C), wie in Kommentar erwähnt, für den Aufbau von ihm, und die optimalen für die Suche, es hängt. Wenn Sie die ersten Elemente Frequenz (O (A) --Wo A ist die Größe der Sprache Alphabet) bestellen, dann werden Sie in der Lage sein, mehr Zweige zu schneiden, und hat eine gute Chance auf sublinear Zeit.

Ich denke, das ist klar, ich werde es nicht aufzuschreiben --was diese Zuordnung eine Hausaufgaben? ;)

Answer 2

Ich würde versuchen, durch die Sortierung der Liste zu starten. Dann einfach Sie von Saite zu Saite gehen, um das erste Zeichen auf die nächste Saite erste Zeichen zu vergleichen. Sobald Sie ein Spiel haben würden Sie beim nächsten Zeichen aussehen. Sie müßten einen Weg finden, so weit das beste Ergebnis zu verfolgen.

Answer 3

Nun, würde erster Schritt sein, um die Liste zu sortieren. Dann passieren eine durch die Liste, wobei jedes Element mit dem vorhergehenden, dem Verfolgen der längsten 2-Charakter, 3-Zeichens zu vergleichen, 4-Zeichen usw. läuft. Dann Figur ist die 20 3-Zeichen-Präfixe besser als die 15 4-Zeichen-Präfixe.