Ich habe eine Sammlung von Sets, die ich in einen trie einfügen möchte.
Normale Versuche bestehen aus Strings von Elementen - das heißt, die Reihenfolge der Elemente ist wichtig. Die Sets haben keine definierte Reihenfolge, daher besteht die Möglichkeit einer größeren Komprimierung.
Wenn ich beispielsweise die Zeichenfolgen "abc" , "bc" und "c" verwende, würde ich den Trie erstellen:
Aber mit den Mengen { 'a', 'b', 'c' } , { 'b', 'c' } , { 'c' } , könnte ich den obigen Trie oder eines dieser elf erzeugen:
Also gibt es offensichtlich Platz für die Komprimierung (7 Knoten bis 4).
Ich verdächtige eine lokale Reihenfolge an jedem Knoten abhängig von der relativen Häufigkeit seiner Kinder zu definieren würde es tun, aber ich bin mir nicht sicher, und es könnte zu teuer sein.
Bevor ich also auf das Whiteboard stoße und anfange, meinen eigenen Komprimierungsalgorithmus aufzubrechen, gibt es einen bestehenden? Wie teuer ist das? Ist es ein Massenprozess oder kann es per Einfügen / Löschen durchgeführt werden?
Ich denke, du solltest ein Set nach Itemhäufigkeit sortieren und das erhält eine gute Heuristik wie du vermutest. Derselbe Ansatz verwendet FP-growth (häufiges Muster-Mining), um die Objektgruppen kompakt darzustellen.
Grundsätzlich sollten Sie einen Abhängigkeitsgraphen konstruieren. Wenn das Element y nur auftritt, wenn x auftritt, ziehe eine Kante von x nach y (im Falle der Gleichheit lexikographisch ordnen). Das resultierende Diagramm ist eine DAG. Führen Sie nun eine topologische Sortierung dieses Graphen durch, um die Reihenfolge der Elemente mit einer Drehung zu erhalten. Wann immer Sie eines der beiden (oder mehrere Elemente) auswählen können, wählen Sie dasjenige mit der höheren Anzahl von Vorkommen.
Meine Vermutung ist, dass die maximale Komprimierung die häufigsten Elemente oben behalten würde (wie in Ihrem letzten Beispiel).
Der Komprimierungsalgorithmus würde mit der gesamten Sammlung von Mengen und dem obersten Knoten beginnen und rekursiv Knoten für jede Teilmenge mit den gebräuchlichsten Elementen erstellen
%Vor%Der resultierende Baum würde eine spezielle Markierung am Ende des Satzes haben, um anzuzeigen, dass ein vollständiger Satz an diesem Knoten endet. Für Ihr Beispiel wäre es
%Vor%Löschen eines Sets ist einfach, entfernen Sie einfach seine EOS-Marker (und alle Elternknoten, die leer werden). Sie können > im Handumdrehen einfügen - an jedem Knoten zum passenden Element mit den meisten untergeordneten Elementen hinabsteigen, bis keine Übereinstimmungen mehr vorhanden sind, dann den oben genannten Algorithmus verwenden - es wäre jedoch schwierig, sie maximal komprimiert zu halten. Wenn Element B mehr Kinder gewinnt als Element A, müssen Sie alle Sets verschieben, die A & amp; B in den B-Knoten, was eine vollständige Suche aller Kinder von A beinhalten würde. Wenn Sie es jedoch nicht komprimiert halten, sind die Inklusionssuchen nicht mehr linear mit der festgelegten Größe.
Tags und Links algorithm language-agnostic trie compression