commons/ocamlextra/suffix_tree.mli

   1 (**
   2    Generalized suffix trees (GSTs).
   3
   4    Computes generalized suffix trees from list of strings. A terminal symbol is
   5    implicitly added to them, but is not returned in the word labeling nodes and
   6    leaves. This should allow a rather transparent handling of GSTs.
   7
   8    Node-based accesses are provided (sequences, root, children, suffix links,
   9    node labels, index), as well as a functional for synthesizing attributes from
  10    a GST. A readable representation of GSTs is derived from the later.
  11 *)
  12 (* made by Sebastien Ferre *)
  13
  14 type node
  15       (** Type of nodes in GSTs. *)
  16
  17 type t
  18       (** Type of GSTs. *)
  19
  20 val make : string list -> t
  21     (** [make l_str] computes a GST based on the set of strings given in [l_str]. *)
  22
  23 val string_list : t -> string list
  24     (** [string_list gst] returns the list of strings from which [gst] was computed. *)
  25
  26 val string : t -> int -> string
  27     (** [string gst k] returns the sequence number [k] (starting from 0). *)
  28
  29 val root : t -> node
  30     (** [root gst] returns the root node of the gst. *)
  31
  32 val word : t -> node -> string
  33     (** [word gst n] returns the word labeling node [n] in [gst]. *)
  34
  35 val children : t -> node -> node list
  36     (** [children gst n] returns a list of the children nodes of [n] in [gst]. *)
  37
  38 val linked_node : t -> node -> node
  39     (** [linked_node gst n] returns the node pointed by the suffix link from [n] in [gst]. *)
  40
  41 val index : t -> node -> int * int
  42     (** [index gst n] returns the index of a leaf [n] in [gst].
  43           This index is a pair [(k,i)], where [k] is the number of the sequence (as used by [string]), and
  44           [i] is the position of the related suffix (starting from [0] as usual in strings).
  45        @raise Invalid_argument "Suffix_tree.index: not a leaf" if [n] is not a leaf (has some child). *)
  46
  47 val implicit_node : t -> string -> node * string * node
  48     (** [implicit_node gst word] returns an implicit_node [(node,word',child)], where [node] is the lowest
  49        node in the suffix tre such that the concatenation of the word recognized by [node] and [word'] is
  50        equal to [word], if [word'] is not the empty string, then [child] is the child node of [node], whose
  51        label has [word'] as a prefix.
  52        @raise Not_found when [word] is not a substring of [string_list gst]. *)
  53
  54
  55 val fold : t -> ('h -> node -> bool) -> ('h -> node -> 'h) -> ('s list -> 'h -> node -> 's) -> 'h -> 's
  56     (** [fold gst filter herit synth init] computes some attribute(s) over a GST by using the 3 functions
  57        [filter], [herit], [synth], and the initial value [init] inherited by the root node. ['h] is the type
  58        of inherited attributes, and ['s] is the type of synthesized attributes, and so the type of the result.
  59
  60        The meaning of 3 functions is as follows:
  61        - [filter h child] returns [true] if the node [child] must be explored given the inherited value of the current
  62          node (parent of [child]),
  63        - [herit h child] returns the value inherited by [child] given the inherited value of the current node
  64          (parent of [child]),
  65        - [synth l h node] returns the synthesized value of the current node, given its inherited value [h], and
  66          the list [l] of synthesized values of explored children of [node] (according to [filter]).
  67
  68      *)
  69
  70 val fold_node : t -> ('h -> node -> bool) -> ('h -> node -> 'h) -> ('s list -> 'h -> node -> 's) -> 'h -> node -> 's
  71     (** Same as [fold], except the computation starts and finishes at the last argument node. *)
  72
  73 val fold_s : t -> ('s list -> node -> 's) -> 's
  74     (** [fold_s gst synth] is equivalent to [fold gst filter herit synth init], where there is no filtering, and
  75        no inherited values: purely synthetic. *)
  76
  77 val fold_s_node : t -> ('s list -> node -> 's) -> node -> 's
  78     (** Same as [fold_s], except the computation starts and finishes at the last argument node. *)
  79
  80 val fold_fs : t -> (node -> bool) -> ('s list -> node -> 's) -> 's
  81     (** [fold_fs gst filter synth] is equivalent to [fold gst filter herit synth init], where there is no inherited
  82        values. *)
  83
  84 type tree = Node of string * tree list | Leaf of string * (int * int)
  85 val readable : t -> tree
  86     (** [readable gst] returns a (more) readable representation of [gst].
  87        Each node and leaf is decorated by its word label, and leaves are
  88        also decorated by their index. *)
  89
  90 val exact_matches : t -> string -> (int * int) list