задачка по алгоритмам: про подмножества

не заглядывая в умные книги, на ум приходит идея сортировать набор из подмн-в в котором надо искать...

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

Но как-то эвристика сплошная, может стандартный алгоритм какой есть?

будем считать, что исходное множество упорядочено, и обозначим его элементы 1, ..., N
Пронумеруем подмножества из заданного набора: B_i = {b_1, ..., b_m}
Теперь заведём вектор C[N]: C[k] = { i : k \in B_i } (т.е. элементы этого вектора - множество числ. Хранить лучше всего в списке).
Заполнение вектора C проводится один раз в начале работы.
Пусть нам предъявили множество X = {x_1, ..., x_n}
Алгоритм:
result = {1 .. m}
for each x_i \in X
  result := result \and C[x_i]

Сложность получается примерно O(mn)

Единственная оптимизация, которая приходит в голову - на этапе инициализации из начального списка подмножеств выкинуть те, которые являются подмножествами одного (или нескольких подмножеств). Ну и прицепить их к соответствующим подмножествам "снизу".

Хотя нет, тоже не подходит)

Есть ли для элементов множеств операция сравнения? Если есть, то ключевые слова такие: сортировка, бинарное дерево.

> Есть ли для элементов множеств операция сравнения? Если есть, то ключевые слова такие: сортировка, бинарное дерево.

Операцию сравнения можно ввести.

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

из набора подмн-в можно построить лес. Но подмн-во query может быть любым, поэтому дерево фактически нужно строить из всех подмн-в, а их много:) Возвращаемся к тому что нужно строить только для части, т.е. опять эвристика.

Навскидку:

> Есть некое базовое множество, кол-во элементов в нем измеряется в сотнях. Оно фиксировано.

Массивы чисел, представляющие битовые маски подмножеств BasicSet[i]:

N := max(i) == trunc(NumberOfElementsBasicSet / MaxLengthOfLogicOperatorNumber)+1

i=1..N

т.е. если элементов 801, а логические операторы понимают 32-байтовые числа, то N:=(trunc(801/32)+1 = 25+1 = 26), округление в большую сторону, и элементы массива [26] забить нулями.

> Есть набор подмножеств этого базового мн-ва. их могут быть тысячи. Этот набор тоже фиксирован.

M := max(j)

j=1..M

Далее, в цикле по набору подмножеств [j], внутри -- в цикле по элементам множества [i]:

Условия вхождения:
(( BasicSet[i]  OR  TestSet[i] )   == BasicSet[i] )
(( BasicSet[i]  OR  SubSet[i][j] ) == BasicSet[i] )     ( true|false )

Проверка:
(( TestSet[i]   OR  SubSet[i][j] ) == TestSet[i] )      ( true|false )    выбираем значение  -= j =-

**********************************************************************

Т.е., кратко, логика работы с числами:

Условия вхождения:
(( BasicSet  OR  TestSet )   == BasicSet )
(( BasicSet  OR  SubSet[j] ) == BasicSet )     ( true|false )

Проверка:
(( TestSet   OR  SubSet[j] ) == TestSet  )      ( true|false )    выбираем значение  -= j =-

???

P.S. На чём реализуешь-то? Случаем не на базах данных с SQL?

В некоторых случаях помогает такой прием.

Например, можно частично упорядочить подмножества по некоторому отношению, скажем, включения (А содержится в B). На основе этого построить бинарное дерево. В левой ветке находятся подмножества, которые содержаться внутри данного. В правой - все остальные. Если множества фиксированы, то можно попытаться построить достаточно сбалансированное дерево.

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

Примерно такая идея лежит в основе "четверья" (русский перевод Кнута) и "k-d tree".

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

В общем, попытаться ввести разбиение подмножеств по некоторому критерию и построить по нему бинарное дерево. Кстати, в узлах дерева можно использовать и искусственно вычисленные множества, так чтобы они задавали хорошее разбиение.

Не оно?

:-)

> "четверья" (русский перевод Кнута)

не подскажешь как это по-английски? а то гугл ничего не выдает ни про четверье, ни про four-tree..

> Далее, в цикле по набору подмножеств [j], внутри -- в цикле по элементам множества [i]:

ну я по моему что-то типа этого и имел в виду, когда писал: "пройдя по всему набору и посчитав битовые маски"

> На чём реализуешь-то? Случаем не на базах данных с SQL?

лето же, телепаты должны быть в отпуске:)

действительно, код с примерно такой функциональностью (если выделить содержательную часть) у нас есть реализованный на sql. А мне это для перла нужно:)

The terms are quadtree and k-d tree.

Здесь важна сама идея разбиения некоторого пространства с помощью бинарного дерева. Может быть, поможет :)

>> Далее, в цикле по набору подмножеств [j], внутри -- в цикле по элементам множества [i]:

> ну я по моему что-то типа этого и имел в виду, когда писал: "пройдя по всему набору и посчитав битовые маски"

Там смысл в том, что сравнением пары чисел (логические побитовые операции: результат побитовой операции OR между "эталонным множеством" и "тестируемым множеством" должен совпасть с "эталонным множеством", т.е. "не давать примесей") можно оперировать наборами по, например, 32 элемента (побитовая упаковка {присутствует|отсутствует} в беззнаковое число). Это удешевляет вычислительные операции и экономит память (2000 множеств, по 26 32-битных чисел на 801 элемент, весят чуть более 52000 байт).

> лето же, телепаты должны быть в отпуске:)

:) Ты легко оперируешь сотнями элементов множеств и тысячами множеств в наборе, что логично указывает, что должна применяться какая-либо База Данных.

> код с примерно такой функциональностью (если выделить содержательную часть) у нас есть реализованный на sql. А мне это для перла нужно:)

Просто, для SQL, более дешёвым будет иной алгоритм оперирования наборами, с точки зрения производительности. Впрочем, если SQL-код уже реализован и устраивает вас, то и рассматривать его смысла нет.

Реализация классификатора на Perl, без битовой упаковки или использования SQL на стороне сервера, может потребовать больших затрат памяти и траффика, что при большом количестве сессий будет накладно.

Подготовительные операции по упаковке множеств в битовые последовательности может оказаться процессом дорогим. Однако, реализация классификатора может оказаться ещё более дорогостоящим процессом... Если не делать их на стороне сервера, предварительно.

P.S. В общем, как заметил dave: "Нужно смотреть конкретную задачу.". Очень многое зависит от представления данных.

:-)

> Здесь важна сама идея разбиения некоторого пространства с помощью бинарного дерева.

IMHO, построение вменяемого классификатора -- задача нетривиальная и больше напоминает искусство... :-) Для нечётких сравнений -- это, действительно, необходимо. Но, будет ли этот метод приемлемым для, например, поиска количеств точных вхождений?

> Например, можно частично упорядочить подмножества по некоторому отношению, скажем, включения (А содержится в B). На основе этого построить бинарное дерево. В левой ветке находятся подмножества, которые содержаться внутри данного. В правой - все остальные. Если множества фиксированы, то можно попытаться построить достаточно сбалансированное дерево.

Разумеется, что построения такого классификатора -- задача сама по себе интересная (а, например, в расспознавании образов, вообще, является целью), если исходные данные это позволяют... Но, каковы будут критерии сегментации на, практически, абстрактных множествах, где может не быть "наследования" множеств в наборе?

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

Опять-таки зависит от задачи и её исходных данных. Если требуется определить соответствие тестируемого множества с некоторым набором (под-веткой), тогда "да". А если тестируемое множество "размажется" по критериям на несколько классов (под-веток), а "верхняя" иерархия окажется "слишком обобщённой", для применения?

P.S. Понимаю, что вопросы, достаточно, теоретические. Интересует Ваше мнение.

:-)

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

В случае такого описания множества и подмножеств, для решения задачи надо будет составить список всех множеств и удалить из него номера тех множеств, номера которых присутсвуют в этих списках, при том, что номер подмножества из условия там отсутствует. В случае если списки подмножеств отсортированы, то число операций будет порядка n*log(m), где n - число элементов множества, а m - число подмножеств.

Видимо, легче понять что я говорю на формулах.

Пусть A - исходное множество, а xi, i=1..n - i-ый элемент его, n - число его элементов. Пусть Pj, j=1..m - j-oe подмножество, где m - число элементов подмножеств. Наконец, пусть M - входное подмножество, и надо найти все Pj входящие в M.

Будем хранить A так: ( xi, ( j1, j2,...) ), где jk - k-ый номер подмножества P. Причем если k1>k2 => jk1 > jk2 (отсортированы).

Согласен, что построение такого классификатора - задача нетривиальная. Думаю, что универсального решения не существует. Нужно использовать дополнительную информацию. Частичная упорядоченность по отношению вложения годится для общего случае, но в частном может оказаться неэффективной.

Чтобы множества не "размазывались", можно попытаться ввести искусственные подмножества. Например, все исходные могут оказаться конечными листьями дерева, а узлы будут вычислены как объединения всех подмножеств своих левых под-веток.

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

Говоря кратко, у нас слишком мало информации :)

Между прочим, если вспомнить kd-деревья, то там как раз используются искусственные промежуточные множества. Только они задаются образом {x=(x_i): x_k<=a_k}. Их легко проверить и просто хранить. Использовать же слишком сложно-построенные множества будет расточительно и крайне неэффективно.

да, твой ход мыслей самый правильный.

Фактически, элементы базового мн-ва можно рассматривать как размерности пространства. Набор подмножеств -- это точки в нем. Каждая точка разбивает пространство на 2 многогранных части -- многогранный конус точек которые >= этой точки (по всем размерностям) и остальное. Теперь мы смотрим как эти многогранные конструкции пересекаются. Пересечения которые получаются -- их будет не очень много, во всяком случае кол-во результирующих многогранников-пересечений будет полиномиально ограничено. Каждый такой многогранник задает область пространства которая соответствует одному набору точек-подмножеств которые <= их.

А дальше строим decision tree, который быстренько определит в какой из многогранников мы попадаем. Любой сплит по переменной делит многогранники на 3 множества: L -- целиком по одну сторону гиперплоскости, R -- целиком по другую сторону, и M -- пересекающиеся с гиперплоскостью. Ну и можно выбрать лучший сплит который к примеру минимизирует max(L+M, M+R); Ну и так далее..