C ++ FP-Tree oder Präfixbaum

Question

Ich habe einige Sequenzen als diese

(100) - (102) - (103) - (104,106) - (108)
(101) - (103)
(102) - (106)

Es gibt eine effiziente Implementierung, ein Präfixbaum oder FP-Baum oder ähnlich in C + +?

Answer 1

Ich verstehe nicht, was Sie sagen ... aber wenn Sie einen FP -Baum erstellen müssen, ist hier die beste Seite, die ich gefunden habe

FP -Baumalgorithmus

Answer 2

Es ist nicht genau klar, was Sie haben, da die angegebenen Daten in keiner Standardnotation zu sein scheinen.

Wenn es sich bei den Präfixen nur um ein paar gemeinsame Dezimalstellen zwischen den Ganzzahlwerten handelt, machen sie wahrscheinlich keinen signifikanten Unterschied in der Datenspeicherung. Sie könnten subtrahieren 100 Speichern Sie vor dem Einfügen von Werten in die Datenstruktur die Werte als char, und fügen Sie 100 zurück nach dem Abrufen hinzu, aber es ist wahrscheinlich nicht die Mühe wert.

Wahrscheinlich sollten Sie die Abfolge von Sequenzen als speichern std::deque< std::vector< int > > bei dem die vector Elemente werden sortiert. Es sei denn, es gibt ein Muster, das ich nicht sehen kann, oder ich habe das Problem falsch interpretiert. Die optimale Leistung bei der Feststellung, welche Sequenzen eine bestimmte Zahl enthalten .