"""A knowledge space represented by its base, without expanding all states.
Uses the finite union-span characterization of a base in Falmagne &
Doignon (2011), Learning Spaces, Chapter 3. Membership and fringes are
computed directly from this characterization, not by enumeration.
"""
from __future__ import annotations
from collections.abc import Collection
from typing import TYPE_CHECKING
from knowledgespaces.structures.knowledge_structure import KnowledgeStructure
from knowledgespaces.structures.surmise_function import SurmiseFunction
if TYPE_CHECKING:
from knowledgespaces.structures.set_family import SetFamily
[docs]
class KnowledgeBase:
"""Minimal union generators of a knowledge space on a nonempty domain.
``generators`` need not already be irredundant: duplicate/empty sets
and sets expressible as unions of smaller generators are removed.
Their union must equal the declared domain. Construction does not
enumerate the span; its subset checks are quadratic in the number of
input generators, with finite-set operation costs.
This representation describes union-closed knowledge spaces only.
A general knowledge structure must not be silently replaced by its
union closure. Use ``from_structure`` to check that hypothesis.
"""
__slots__ = ("_base", "_domain")
def __init__(self, domain: Collection[str], generators: Collection[Collection[str]]) -> None:
domain = frozenset(domain)
if not domain:
raise ValueError("KnowledgeBase requires a nonempty domain.")
family = {frozenset(g) for g in generators if g}
if any(not g <= domain for g in family):
raise ValueError("Base generators contain items outside the domain.")
if frozenset().union(*family) != domain:
raise ValueError("The union of the generators must equal the domain.")
self._domain = domain
self._base = frozenset(
g for g in family if frozenset().union(*(h for h in family if h < g)) != g
)
@property
def domain(self) -> frozenset[str]:
return self._domain
@property
def base(self) -> frozenset[frozenset[str]]:
"""The irredundant generating sets, excluding the empty set."""
return self._base
@property
def n_base_sets(self) -> int:
return len(self.base)
def __contains__(self, state: Collection[str]) -> bool:
state = frozenset(state)
return (
state <= self.domain
and frozenset().union(*(b for b in self.base if b <= state)) == state
)
def _state(self, state: Collection[str]) -> frozenset[str]:
state = frozenset(state)
if state not in self:
raise ValueError("Not a state of the knowledge space generated by this base.")
return state
[docs]
def outer_fringe(self, state: Collection[str]) -> frozenset[str]:
"""Items whose addition produces a state, computed from the base.
For a state K, q belongs to its outer fringe exactly when some
base set B satisfies B minus K = {q}. No span is materialized.
"""
state = self._state(state)
differences = (b - state for b in self.base)
return frozenset().union(*(d for d in differences if len(d) == 1))
[docs]
def inner_fringe(self, state: Collection[str]) -> frozenset[str]:
"""Items whose removal leaves a union of contained base sets.
This is a structural boundary, not an individual's learning history.
"""
state = self._state(state)
return frozenset(q for q in state if state - {q} in self)
[docs]
def neighbourhood(
self, state: Collection[str], *, include: bool = False
) -> frozenset[frozenset[str]]:
"""States one item away, computed without expanding the union span.
``include=True`` also returns the centre. The centre must belong to
the generated space. For larger symmetric-difference radii use an
explicitly materialized structure and its ``neighbourhood`` method.
"""
centre = self._state(state)
if not isinstance(include, bool):
raise ValueError("include must be a boolean.")
neighbours = {centre - {q} for q in self.inner_fringe(centre)} | {
centre | {q} for q in self.outer_fringe(centre)
}
if include:
neighbours.add(centre)
return frozenset(neighbours)
@property
def item_heights(self) -> dict[str, int]:
"""Minimum cardinality of a state containing each item, minus one.
Equivalent to ``kstMatrix::kmheights``: a minimum containing state
is a base set, so no span enumeration is needed. This is neither a
Hasse level nor the number of individually necessary prerequisites.
"""
return {q: min(len(b) for b in self.base if q in b) - 1 for q in sorted(self.domain)}
[docs]
def surmise_function(self) -> SurmiseFunction:
"""Recover clauses (atoms at each item) directly from the base."""
return SurmiseFunction(
self.domain,
{
q: [b for b in self.base if q in b and not any(q in h and h < b for h in self.base)]
for q in self.domain
},
)
[docs]
def to_knowledge_space(self, *, max_items: int | None = None) -> KnowledgeStructure:
"""Materialize the union span; may require exponentially many states."""
return self.surmise_function().to_knowledge_space(max_items=max_items)
[docs]
def as_family(self) -> SetFamily:
"""The base rows as an arbitrary family, without generating states."""
from knowledgespaces.structures.set_family import SetFamily
return SetFamily(self.domain, self.base)
[docs]
def join(self, other: KnowledgeBase) -> KnowledgeBase:
"""Base of the smallest knowledge space containing both spaces.
The domains must match. Merge and reduce generators; no state span
is materialized. The result need not be the raw union of the bases.
"""
return self.as_family().union_with(other.as_family()).to_knowledge_base()
[docs]
def intersection_with(
self, other: KnowledgeBase, *, max_candidates: int = 100_000
) -> KnowledgeBase:
"""Base of the intersection of the generated knowledge spaces.
This is not the intersection of the two base families. Canonical
clauses encode both requirements, without enumerating either span.
"""
return (
self.surmise_function()
.intersection_with(other.surmise_function(), max_candidates=max_candidates)
.to_knowledge_base()
)
[docs]
def projection(self, domain: Collection[str]) -> KnowledgeBase:
"""Base of the projected knowledge space, from projected generators."""
return self.as_family().projection(domain).to_knowledge_base()
[docs]
def refine(self, base: KnowledgeBase, *, max_sets: int = 100_000) -> KnowledgeBase:
"""Refine equivalent items in the generators and take their union span.
``base.domain`` must lie within a single equivalence class of this
base. The result is a base; call ``as_family().refine(base)`` instead
when only the unreduced replacement rows are wanted.
"""
return self.as_family().refine(base, max_sets=max_sets).to_knowledge_base()
[docs]
def quotient(self) -> tuple[KnowledgeBase, dict[str, frozenset[str]]]:
"""Base on representative items, plus the original equivalence classes."""
family, classes = self.as_family().quotient()
return family.to_knowledge_base(), classes
[docs]
@classmethod
def from_structure(cls, structure: KnowledgeStructure) -> KnowledgeBase:
"""Construct from an explicit knowledge space; reject non-union-closed input."""
if not structure.is_knowledge_space:
raise ValueError("A base representation requires a union-closed knowledge space.")
return cls(structure.domain, structure.base())
def __repr__(self) -> str:
return f"KnowledgeBase(n_items={len(self.domain)}, n_base_sets={self.n_base_sets})"