Алгоритмы сжатия множества попыток - PullRequest
Новая
       16

Алгоритмы сжатия множества попыток

9 голосов
/ 23 февраля 2012

У меня есть коллекция наборов, которые я хотел бы поместить в три .

Обычные попытки состоят из строк элементов, то есть порядок элементовважный.У наборов отсутствует определенный порядок, поэтому существует возможность большего сжатия.

Например, учитывая строки "abc", "bc" и "c", я бы создал три: 

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

Но учитывая наборы { 'a', 'b', 'c' }, { 'b', 'c' }, { 'c' }, я мог бы создать вышеупомянутый три или любой из этих одиннадцати: 

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

Так что, очевидно, есть место для сжатияОт 7 узлов до 4).

I подозреваю определение локального порядка в каждом узле зависит от относительной частоты его дочерних элементов, но я не уверен, и это может бытьчрезмерно дорогой.

Итак, прежде чем я ударю по доске и начну ломать голову над моим собственным алгоритмом сжатия, существует ли существующий?Насколько это дорого?Это массовый процесс, или это можно сделать для каждой вставки / удаления?

Ответы [ 3 ]

1 голос
/ 23 февраля 2012

Я думаю, вам следует отсортировать набор по частоте, и вы получите хорошую эвристику, как вы подозреваете. Тот же подход используется в FP-growth (поиск по частым шаблонам) для компактного представления наборов элементов

0 голосов
/ 24 февраля 2012

Мое подозрение в том, что максимальное сжатие будет держать самые распространенные элементы наверху (как в вашем последнем примере).

Алгоритм сжатия будет начинаться со всей коллекции множеств и верхнего узла и рекурсивно создавать узлы для каждого подмножества, содержащего наиболее распространенные элементы 

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

Результирующее дерево будет иметь специальный маркер конца набора для обозначения того, что полный набор заканчивается на этом узле. Для вашего примера это будет 

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

Удалить набор легко, просто удалите его маркер EOS (и любые родительские узлы, которые станут пустыми). Вы могли бы вставить на лету - в каждом узле спускаться к соответствующему элементу с наибольшим количеством потомков до тех пор, пока не будет найдено совпадений, а затем использовать приведенный выше алгоритм - но сохранить его максимально сжатым было бы сложно. Когда элемент B получил больше дочерних элементов, чем элемент A, вам пришлось бы переместить все наборы, содержащие A & B, в узел B, что потребовало бы полного поиска всех дочерних элементов A. Но если вы не держите его сжатым, то поиски включения больше не будут линейными с заданным размером.

0 голосов
/ 23 февраля 2012

В основном вы должны построить график зависимости.Если элемент y встречается только в случае появления x, нарисуйте ребро от x до y (в случае равенства просто упорядочите лексикографически)Полученный граф является DAG.Теперь выполните топологическую сортировку этого графа, чтобы получить порядок элементов с поворотом.Всякий раз, когда вы можете выбрать один из двух (или более элементов), выберите тот, с большим числом вхождений.

...