Algoritmos para la compresión de conjuntos de intentos

Question

Tengo una colección de conjuntos que me gustaría colocar en un trie.

Los intentos normales están hechos de cadenas de elementos, es decir, el orden de los elementos es importante. Los conjuntos carecen de un orden definido, por lo que existe la posibilidad de una mayor compresión.

Por ejemplo, dadas las cuerdas "abc", "bc" y "c", que crearía el trie:

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

pero teniendo en cuenta los conjuntos { 'a', 'b', 'c' }, { 'b', 'c' }, { 'c' }, que podría crear el trie anteriormente, o cualquier de estos once:

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

Así que obviamente hay espacio para la compresión (7 nodos a 4).

I sospechoso definir un pedido local en cada nodo depende de la frecuencia relativa de sus hijos lo haría, pero no estoy seguro, y podría ser demasiado caro.

Entonces, antes de presionar la pizarra, y comenzar a descifrar mi propio algoritmo de compresión, ¿existe uno existente? ¿Qué tan caro es? ¿Es un proceso masivo, o puede hacerse por inserción/eliminación?

Answer 1

Básicamente debe construir un gráfico de dependencia. Si el elemento y ocurre solo si ocurre x, dibuje un borde de xa y (en caso de igualdad, simplemente solicite lexicográficamente). El gráfico resultante es un DAG. Ahora, haga una clasificación topológica de este gráfico para obtener el orden de los elementos con un giro. Siempre que pueda elegir uno de los dos (o más elementos) elija el que tenga mayor cantidad de ocurrencias.

Answer 2

Creo que debe ordenar un conjunto de acuerdo a la frecuencia del artículo y esto le dará una buena heurística como sospecha. El mismo enfoque usando en FP-growth (mining de patrones frecuentes) para representar de manera compacta los conjuntos de elementos.

Answer 3

Mi sospecha es que la compresión máxima mantendría los elementos más comunes en la parte superior (como en su último ejemplo).

El algoritmo de compresión comenzaría con toda la colección de conjuntos y el nodo superior, y de forma recursiva crear nodos para cada subconjunto que contiene los elementos más comunes

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 

El árbol resultante tendría un especial de final de vida establecer marcador para indicar que un conjunto completo termina en ese nodo. Para su ejemplo sería

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

Eliminación de un conjunto es fácil, basta con retirar su marcador EOS (y los nodos padres que se convierten en vacío). Usted podría inserte sobre la marcha - en cada nodo, desciende al elemento coincidente con la mayoría de los niños hasta que no haya coincidencias, luego use el algoritmo anterior, pero mantenerlo comprimido al máximo sería complicado. Cuando el elemento B ganara más hijos que el elemento A, tendría que mover todos los conjuntos que contengan A & B al nodo B, lo que implicaría una búsqueda completa de todos los hijos de A. Pero si no lo mantiene comprimido, las búsquedas de inclusión ya no son lineales con el tamaño establecido.