Предложения по структуре данных для связанных функций

Question

У нас есть набор документов, каждый из которых имеет набор функций.Учитывая функцию A, мы должны знать, какова вероятность наличия функции B в том же документе.

Я думал о построении матрицы вероятностей, st: M (i, j) = Вероятность наличия функции B в документе, учитывая, что функция A есть.

Однако у нас есть дополнительное требование: данная функция A находится в документе, каковы все функции, которые имеют вероятность> P в том же документе.

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

Эта сложность пространства довольно велика (наихудший случай: N ^ 2 и N велика!), А сложность времени для каждого поискаO (N).

Есть идея получше?

Answer 1

Если количество объектов сопоставимо с количеством документов или более, рассмотрите возможность хранения инвертированного индекса: для каждого объекта хранятся (например, отсортированный список) документы, в которых он присутствует.Затем вы можете определить вероятность B, заданную A, запустив слияние в отсортированных списках для функций A и B.

Для вопроса «общие характеристики ожидаются, учитывая A», я не могу придумать ничего лучше, чем предварительно-считать ответ для каждого А и надеяться, что результирующий список функций не будет слишком длинным.