Algorytmy kompresji zestawu prób

Question

Mam kolekcję zestawów, które chciałbym umieścić w trie.

Normalne próby są wykonane z ciągów elementów - to znaczy, kolejność elementów jest ważna. Zestawy nie mają zdefiniowanej kolejności, więc istnieje możliwość większej kompresji.

Na przykład, biorąc pod uwagę struny "abc", "bc" i "c", chciałbym stworzyć Trie:

(*,3) -> ('a',1) -> ('b',1) -> ('c',1) 
     -> ('b',1) -> ('c',1) 
     -> ('c',1) 

Ale biorąc pod uwagę zestawy { 'a', 'b', 'c' }, { 'b', 'c' }, { 'c' }, mogę tworzyć powyższy Trie lub dowolny z nich jedenaście:

(*,3) -> ('a',1) -> ('b',1) -> ('c',1) 
     -> ('c',2) -> ('a',1) 

(*,3) -> ('a',1) -> ('c',1) -> ('b',1) 
     -> ('b',1) -> ('c',1) 
     -> ('c',1) 

(*,3) -> ('a',1) -> ('c',1) -> ('b',1) 
     -> ('c',2) -> ('a',1) 

(*,3) -> ('b',2) -> ('a',1) -> ('c',1) 
       -> ('c',1) 
     -> ('c',1) 

(*,3) -> ('b',1) -> ('a',1) -> ('c',1) 
     -> ('c',2) -> ('b',1) 

(*,3) -> ('b',2) -> ('c',2) -> ('a',1) 
     -> ('c',1) 

(*,3) -> ('b',1) -> ('c',1) -> ('a',1) 
     -> ('c',2) -> ('b',1) 

(*,3) -> ('c',2) -> ('a',1) -> ('b',1) 
     -> ('b',1) -> ('c',1) 

(*,3) -> ('c',2) -> ('a',1) -> ('b',1) 
       -> ('b',1) 

(*,3) -> ('c',2) -> ('b',1) -> ('a',1) 
     -> ('b',1) -> ('c',1) 

(*,3) -> ('c',3) -> ('b',2) -> ('a',1) 

Więc nie ma oczywiście miejsca dla kompresji (7 węzłów do 4).

Podejrzewam definiowania zlecenie lokalne w każdym węźle zależy od względnej częstotliwości swoich dzieci zrobi to, ale nie jestem pewna, a to może być zbyt kosztowne.

Więc zanim uderzę w tablicę i zacznę łamać się przy moim własnym algorytmie kompresji, czy istnieje już jeden? Ile to kosztuje? Czy jest to proces zbiorczy, czy może być wykonywany za wstawieniem/usunięciem?

Answer 1

Zasadniczo powinieneś zbudować wykres zależności. Jeśli element y występuje tylko wtedy, gdy występuje x, narysuj krawędź od x do y (w przypadku równości, po prostu uporządkuj leksykograficznie). Powstały wykres to DAG. Teraz wykonaj topologiczne sortowanie tego wykresu, aby uzyskać porządek elementów z niespodzianką. Ilekroć możesz wybrać jeden z dwóch (lub więcej elementów), wybierz ten, który ma większą liczbę wystąpień.

Answer 2

Myślę, że powinieneś posortować zestaw zgodnie z częstotliwością przedmiotu, a to dostanie dobrą heurystykę, jak podejrzewasz. To samo podejście przy użyciu w FP-growth (częste wydobywanie wzorców) do reprezentowania w kompaktowy sposób zestawów przedmiotów.

Answer 3

Moja suspiscja jest taka, że ​​maksymalna kompresja zachowałaby najbardziej popularne elementy u góry (jak w twoim ostatnim przykładzie).

Algorytm kompresji ruszy z całej kolekcji zbiorów i górnego węzła i rekurencyjnie tworzyć węzły dla każdego podzbioru zawierającego najczęstsze elementy

Compress(collection, node): 
    while NOT collection.isEmpty? 
     e = collection.find_most_common_element 
     c2 = collection.find_all_containing(e) 
     collection = collection - c2 
     if e==NIL //empty sets only 
     node[END_OF_SET]=node 
     else 
     c2.each{set.remove(e)} 
     node[e]=new Node 
     Compress(c2,node[e]) 
     end 
    end 

Powstały drzewo musiałoby specjalny End-of Ustaw znacznik, aby zaznaczyć, że kompletny zestaw kończy się w tym węźle. Na swoim przykładzie byłoby

*->(C,3)->(B,2)->(A,1)->EOS 
       ->EOS 
      ->EOS 

Usuwanie zestawu jest proste, wystarczy usunąć to marker EOS (oraz wszelkie węzły macierzyste, które stają się puste). Ci mógłby wstawić na bieżąco - w każdym węźle, zejście do elementu dopasowującego z większości dzieci, dopóki nie znaleziono żadnego meczu, a następnie użyć algorytmu powyżej - ale utrzymywanie go maksymalnie sprężonego byłoby trudne. Gdy element B zyskał więcej dzieci niż element A, musiałbyś przenieść wszystkie zestawy zawierające A & B do węzła B, co wymagałoby pełnego przeszukiwania wszystkich dzieci A. Ale jeśli nie będziesz go kompresował, to wyszukiwania włączające nie będą już liniowe z ustawionym rozmiarem.