Software
Data structures
- LSet: sets as ordered
polymorphic lists ( lSet.ml )
This module implements polymorphic sets as polymorphic lists whose
elements are ordered according to the reverse of the OCaml function
Pervasives.compare. Most set operations are in linear time in the size
of sets, and iterations on lists are available.
- Cis: compact integer sets
( cis.mli | cis.ml
)
This module implements compact integer sets, represented as a (custom)
list of integer intervals. Usual set operations are provided. The
advantage compared to ordered lists is that the actual size may be
smaller than the cardinal of a set when many elements are contiguous.
Most set operations are linear w.r.t. the size of the structure, not
the cardinal of the set.
- Suffix_tree: generalized
suffix trees ( suffix_tree.ml )
[ depends on LSet, Cis ]
This module implements generalized suffix trees (GST). A GST is defined
by a set of strings, in which strings can be added or removed, and is
represented as the compact lexical tree of all suffixes of these
strings. Every node of the tree corresponds to a substring that is
present in one or more strings. Some of these substrings are said
maximal when every other substring or string that contains it is
present in fewer strings. The construction of a GST is in linear time
and linear space w.r.t. the cumulated size of strings, with a rather
high constant factor for space though (about 10-20). It supports the
incremental addition or removal of a string. Many low- and high-level
access functions are provided. A readable simplified form of GSTs is
provided for toplevel use.
Algorithms
- Iceberg: a program for
computing all frequent formal concepts from a formal context (iceberg-1.0.tar.gz)
This program uses an adaptation of Bordat's algorithm for computing the
concept lattice. This adaptation can use a minimum size for extents
(a.k.a. minimum support), and is programmed as a fold function through
all frequent concepts. Iceberg can output the intent, extent, and/or
support of each concept, gives some simple statistics about the
context, and also outputs at the end the number of computed concepts,
and the execution time for the folding (not counting the reading and
preprocessing stages).
It is accompanied by a utility program that converts a CSV file
representing a multi-valued context to a context file acceptable by
Iceberg.
Libraries
- Logfun:
a library of logic functors
A logic functor is a
function that can be applied to zero, one or several logics so as to
produce a new logic as a combination of argument logics. Each argument
logic can itself be built by combination of logic functors. The
signature of a logic is made of a parser and a printer of formulas,
logical operations such as a theorem prover for entailment between
formulas, and more specific operations required by Logical Information
Systems (LIS). Logic functors can be concrete domains like integers,
strings, or algebraic combinators like product or sum of logics.
Applications
- Camelis:
an implementation of Logical
Information Systems (LIS)
A LIS allows to automatically organize data given an indexation of
objects by logical properties, and to combine boolean querying and
non-hierarchical navigation when
searching information.
Last update: 27/08/2007.