Algoritmi per la compressione dei tentativi impostati

Question

Ho una collezione di set che vorrei inserire in un trie.

I tentativi normali sono costituiti da stringhe di elementi, ovvero l'ordine degli elementi è importante. Gli insiemi mancano di un ordine definito, quindi c'è la possibilità di una maggiore compressione.

Ad esempio, date le stringhe "abc", "bc" e "c", mi piacerebbe creare il trie:

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

ma dato il set { 'a', 'b', 'c' }, { 'b', 'c' }, { 'c' }, ho potuto creare il trie superiore, o qualsiasi di questi undici:

(*,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) 

Quindi c'è ovviamente spazio per la compressione (7 nodi su 4).

ho sospetto definire un ordine locale in ogni nodo dipende dalla frequenza relativa dei suoi figli avrebbe fatto, ma non sono certo, e potrebbe essere eccessivamente costoso.

Quindi, prima di colpire la lavagna e iniziare a scricchiolare il mio algoritmo di compressione, ce n'è uno esistente? Quanto è costoso? È un processo di massa, o può essere fatto per-inserire/eliminare?

Answer 1

Fondamentalmente si dovrebbe costruire un grafico di dipendenza. Se l'elemento y si verifica solo se si verifica x, tracciare un bordo da x a y (in caso di uguaglianza, basta ordinare lessicograficamente). Il grafico risultante è un DAG. Ora, esegui uno smistamento topologico di questo grafico per ottenere l'ordine degli elementi con una svolta. Ogni volta che puoi scegliere uno dei due (o più elementi) scegli quello con un numero maggiore di occorrenze.

Answer 2

Penso che dovresti ordinare un set in base alla frequenza degli articoli e questo ottiene una buona euristica come sospetti. Lo stesso approccio usando in FP-growth (mining di pattern frequenti) per rappresentare in modo compatto gli insiemi di elementi.

Answer 3

Il mio sospetto è che la compressione massima manterrebbe gli elementi più comuni nella parte superiore (come nel tuo ultimo esempio).

L'algoritmo di compressione inizierebbe con l'intera collezione di set e il nodo superiore, e crea ricorsivamente nodi per ogni sottoinsieme contenente gli elementi più comuni

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 

L'albero risultante avrebbe un particolare end-di- imposta un marker per indicare che un set completo termina su quel nodo. Per il tuo esempio sarebbe

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

Eliminazione di un set è facile, basta rimuovere è marcatore EOS (ed eventuali nodi principali che diventano vuoto). Tu potresti inserire al volo - in ogni nodo, scendere all'elemento di corrispondenza con il maggior numero di bambini finché non ci sono corrispondenze, quindi usare l'algoritmo sopra - ma tenerlo al massimo compresso sarebbe complicato. Quando l'elemento B ha acquisito più figli dell'elemento A, dovresti spostare tutti i set contenenti A & B nel nodo B, il che comporterebbe una ricerca completa di tutti i figli di A. Ma se non lo si mantiene compresso, le ricerche di inclusione non sono più lineari con la dimensione impostata.