Минимизация записей в хэш-таблице "многие ко многим"

Question

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

Данные изначально поступают как ввод одного ключа для одной записи ( представляет одну ссылку в отношении "многие ко многим").

Примерно:

A-1, B-1, B-2, B-3, C-2, C-3

Простой способ обработки данных - связать их один со многими:

A: 1
B: 1,2,3
C: 2,3

Однако количество записей является основным вычислительные затраты для более позднего процесса, так как файл нужно будет сгенерировать и отправить через inte rnet для каждой записи (это совсем другая история), и, скорее всего, будут тысячи записей в взаимно многие реализации.

Таким образом, более оптимизированным ha sh будет:

[A, B]: 1
[B, C]: 2,3

Эта таблица будет отброшена после использования, поэтому ремонтопригодность не является проблемой, единственное беспокойство - время -сложность сокращения записей (время, которое требуется алгоритму для сокращения записей, не должно превышать время, которое алгоритм сэкономил бы при сокращении записей из базовой таблицы «один ко многим»).

Теперь я Я почти уверен, что хоть кто-то сталкивался с этой проблемой, это похоже на проблему прямо из моего урока алгоритмов в колледже. Однако у меня возникают проблемы с поиском подходящих алгоритмов, так как я не могу найти подходящие условия поиска. Я собираюсь попытаться создать алгоритм для этого с нуля, но я подумал, что не помешает поспрашивать, чтобы узнать, не могут ли люди идентифицировать это как проблему, обычно решаемую модифицированным [вставить хорошо известный алгоритм здесь].

Я лично считаю, что лучше всего начать с создания «один ко многим» ha sh, а затем изучить подмножества значений в каждой записи, создав запись в решении ha sh для максимального идентифицированного набор общих ценностей. Но я не уверен, как гарантировать меньшее количество подмножеств, чем просто базовая реализация «один ко многим».

Answer 1

Давайте go вернемся к вашему неоптимизированному словарю букв к наборам чисел:

A: 1
B: 1,2,3
C: 2,3

Там - в данном случае - дерево шагов рефакторинга с двумя ветвями, которое вы могли бы выполнить:

                       A:1  B:1,2,3  C:2,3
                      /                   \
           factor using set 2,3    factor using set 1
                    /                       \
           A:1 B:1 B,C:2,3            A,B:1 B:2,3 C:2,3
                  /                           \
         factor using set 1            factor using set 2,3
                /                               \
           A,B:1 B,C:2,3                   A,B:1 B,C:2,3

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

Проведение исчерпывающего исследования дерева звучит дорого, поэтому вы, возможно, захотите этого избежать, но если бы мы могли выбрать оптимальный путь или, по крайней мере, вероятный хороший путь, это были бы относительно низкие вычислительные затраты. Вместо случайного ветвления, мой инстинкт подсказывает, что было бы быстрее и ближе к оптимальному, если бы вы попытались сделать возможное изменение факторинга с наибольшим набором в каждой точке дерева. Например, рассматривая дерево с двумя ветвями выше, вы бы предпочли первоначальное разложение 2,3 над исходным разложением 1 в вашем дереве, потому что 2,3 имеет больший набор размера два. Более драматичный c рефакторинг предполагает, что количество рефакторингов, прежде чем вы получите стабильный результат, будет меньше. одинаковой длины), ища возможности для рефакторинга.

Во многом как пузырьковая сортировка, после каждого рефакторинга подход будет выглядеть так: «Я внес изменение; оно еще не стабильно; давайте повторим». Начните с итерации от второго самого длинного набора к самому короткому, проверяя возможности оптимизации, как вы go.

(я не уверен насчет python, но в целом сравнение наборов может быть дорогостоящим, вы можете хотите сохранить значение для каждого набора, которое является XOR хешированных значений в наборе - это легко и дешево обновить, если несколько элементов набора изменяются, и тривиальное сравнение может сказать вам, что большие наборы неравны, что экономит время сравнения; он не скажет вам, равны ли наборы: несколько наборов могут иметь одинаковое значение XOR-of-hashes).