•  21-08-2019
  •  | 
  •  

Frage

Ich wette jemand dies vor gelöst hat, aber meine Suche haben ging leer aus.

Ich möchte eine Liste von Wörtern in einen Puffer packen, der Startposition und Länge jedes Wortes zu verfolgen. Der Trick besteht darin, dass ich den Puffer effizient packen mag, dass durch die Redundanz beseitigt wird.

Beispiel: Puppe Puppenhaus Haus

Diese können in die Puffer einfach als dollhouse verpackt werden, dass doll Erinnerung an vier Buchstaben sind, beginnend an Position 0, dollhouse sind neun Buchstaben bei 0 und house ist fünf Buchstaben auf 3.

Was habe ich mit so weit kommen wird:

  1. Sortieren Worte längste kürzeste: (Puppenhaus, Haus, Puppe)
  2. den Puffer Scan, um zu sehen, wenn die Zeichenfolge bereits als Teil vorhanden ist, wenn die Lage zu beachten.
  3. Wenn es nicht bereits vorhanden ist, fügen Sie es bis zum Ende des Puffers.

Da oft lange Wörter kürzer Wörter enthalten, das funktioniert ziemlich gut, aber es sollte möglich sein, wesentlich besser zu machen. Zum Beispiel, wenn ich das Wort Liste aufzunehmen ragdoll erweitern, dann kommt mein Algorithmus mit dollhouseragdoll auf, die als ragdollhouse weniger effizient ist.

Dies ist ein Vorverarbeitungsschritt, also bin ich nicht sehr besorgt über die Geschwindigkeit. O (n ^ 2) ist in Ordnung. Auf der anderen Seite, hat meine aktuelle Liste Zehntausende von Worten, so O (n!) Wahrscheinlich indiskutabel ist.

Als Randbemerkung, dieses Speicherschema für die Daten im `Namen‘ Tabelle eines Truetype-Schriftart, vgl verwendet http://www.microsoft.com/typography/otspec/name.htm

War es hilfreich?

Lösung

Dies ist das kürzeste Superstring-Problem : Finden Sie die kürzeste Zeichenfolge, die einen Satz von gegebenen Strings als Teil enthält. Nach diesem IEEE Papier (die Sie keinen Zugang zu leider haben ), um dieses Problem zu lösen genau ist NP-vollständig . Allerdings heuristische Lösungen stehen zur Verfügung.

Als erster Schritt sollten Sie alle Saiten finden, die Teil anderer Strings sind und löschen Sie sie (natürlich müssen Sie noch ihre Positionen relativ zu den enthaltenden Saiten aufnehmen irgendwie). Diese vollständig geschlossenen Strings effizient gefunden werden, um ein Suffixbaum verallgemeinert.

, dann durch wiederholte die beiden Saiten längste Überlappung Verschmelzung, werden Sie garantieren eine Lösung, deren Länge nicht schlechter als 4 mal die minimal mögliche Länge zu produzieren. Es sollte möglich sein, Überlappung Größen schnell unter Verwendung von zwei Radix Bäumen zu finden, wie durch einen Kommentar von Zifre auf vorgeschlagen Konrad Rudolph Antwort . Oder könnten Sie in der Lage sein, irgendwie die verallgemeinerte Suffix-Baum zu verwenden.

Ich tue mir leid ich kann nicht einen anständigen Link für Sie ausgraben - es keine Wikipedia-Seite, oder eine öffentlich zugänglichen Informationen zu diesem Problem zu sein scheint. Es wird kurz erwähnt hier , wenn auch nicht vorgeschlagen Lösungen werden zur Verfügung gestellt.

Andere Tipps

Ich glaube, Sie können Radix Baum . Es kostet etwas Speicher, weil von Zeigern auf Blätter und Eltern, aber es ist einfach Strings zusammenpassen (O (k) (wobei k die längste Zeichenfolge Größe).

Mein erster Gedanke ist hier: eine Datenstruktur verwenden, um gemeinsame Präfixe und Suffixe Ihrer Strings zu bestimmen. Dann sortieren Sie die Wörter unter Berücksichtigung dieser Präfixe und Postfix. Dies würde in der gewünschten ragdollhouse zur Folge hat.

Sieht ähnlich dem Knapsackproblem , die NP-vollständig ist, so gibt es nicht ein "endgültiger" Algorithmus.

ich ein Labor zurück in der Schule haben, wo wir mit der Implementierung eines einfachen Komprimierungsprogramm beauftragt.

Was wir taten, wurde die Reihe nach diesen Techniken Text anwenden:

  • BWT ( Burrows-Wheeler-Transformation ): hilft Buchstaben in Sequenzen von identischen neu ordnen Buchstaben (Hinweis * gibt es mathematische Substitutionen die Buchstaben anstatt wirklich tun, um die Rotationen für immer)
  • MTF ( Move To Front ): Schreibt die Buchstabenfolge als eine Folge von Indizes einer dynamischen Liste.
  • Huffman-Codierung : Eine Form der Entropiecodierung, die einen Code mit variabler Länge konstruiert Tabelle, in der kürzere Codes gegeben sind häufig anzutreffende Symbole und längere Codes zu werden gegeben, um Symbole selten angetroffen

Hier fand ich die Zuordnung .

Ihren Originaltext zurück, was Sie tun (1) Huffman-Decodierung, (2) inversen MTF, und dann (3) inverse BWT. Es gibt mehrere gute Ressourcen auf all dies auf dem Interwebs.

verfeinert Schritt 3.

  • Schauen Sie durch aktuelle Liste und sehen, ob ein Wort in der Liste beginnt mit einem Suffix des aktuellen Wortes. (Sie können das Suffix länger als eine gewisse Länge behalten wollen - mehr als 1, zum Beispiel).
  • Wenn ja, dann den eindeutigen Präfix hinzufügen zu diesem Wort als Präfix an das bestehende Wort und stellen Sie alle vorhandenen Referenzen in geeigneter Weise (langsam!)
  • Wenn nicht, fügt Wort der Liste zu beenden, wie in aktuellem Schritt 3.

Dies würden Sie wie die gespeicherten Daten in Ihrem Beispiel ‚ragdollhouse‘. Es ist nicht klar, ob es immer optimal funktionieren wird (wenn man auch ‚barbiedoll‘ hat und ‚Dollar‘ in der Wortliste, zum Beispiel).

Nicht verbunden mit StackOverflow
scroll top