Module Sam

module Sam: sig .. end

Sparse Associative Memories

Module Sam implements the associative memories described in this document. They store tuples of elements (called messages of characters) and are able to retrieve them given only a subset of initial characters with high probability (as long as the number of stored messages is not too large). This implementation allows to consider associative memories of any type. On the other hand, performance is limited: simulations show that it can be up to 10 times longer than using an ad hoc construction. A typical use is:

# let sam = Sam.create 4;;
val sam : '_a Sam.t = Sam.Sam [|<abstr>; <abstr>; <abstr>; <abstr>|]
# Sam.add sam [|"Hel";"lo";" Wo";"rld!"|];;
- : unit = ()
# Sam.retrieve_unique sam [|None; Some "lo"; None; Some "rld!"|];;
- : string array = [|"Hel"; "lo"; " Wo"; "rld!"|]
# Sam.add sam [|"H";"i";" Wo";"rld!"|];;
- : unit = ()
# Sam.retrieve sam [|None; None; Some " Wo"; Some "rld!"|];;
- : string list array = [|["H"; "Hel"]; ["i"; "lo"]; [" Wo"]; ["rld!"]|]

type 'a t = {

	`mutable max_iterations :int;`
	`mutable total_iterations :int;`
	`mutable nb_retrievals :int;`
	`size :int;`
	`length :int;`
	`table :('a, ('a, bool) Hashtbl.t array) Hashtbl.t array;`
	`lists :('a, 'a list array) Hashtbl.t array;`

}

Type for internal representation of sparse associative memories.

val create : ?length:int -> int -> 'a t

Sam.create n creates an associative memory working on n characters. Sam.create ~length:l n creates an associative memory working on n characters with the information that the number of different characters will be about l.

val size : 'a t -> int

Sam.size sam returns the number of characters in messages in sam.

val add : 'a t -> 'a array -> unit

Sam.add sam motive adds message motive to the sam described by sam. Learning a second time the same message will leave the sam unchanged.

val retrieve_from_lists : 'a t -> ?iterations:int -> 'a list array -> 'a list array

Sam.retrieve_from_lists ?iterations sam listed_motives takes an array of lists of characters as argument, which contains the possibilities at each position. The list [] is interpreted as being all possibilities for associated character. It iterates until reaching a fixed point unless a maximum number of iterations is given.

val retrieve : 'a t -> ?iterations:int -> 'a option array -> 'a list array

Sam.retrieve sam some_motive considers None values as characters to be retrieved. It is equivalent to Sam.retrieve_from_lists sam listed_motives when listed_motives is the same array as some_motive where Some x has been replaced by [x] and None by [].

exception Not_unique

Exception raised when finding several solutions in the decoding of retrieve_unique.

val retrieve_unique : 'a t -> ?iterations:int -> 'a option array -> 'a array

Sam.retrieve_unique sam some_motive is the same as Sam.retrieve but it gives as a result the unique retrieved pattern. If several are decoded, it raises exception Not_unique.

val alphabet : 'a t -> int -> 'a list

Sam.alphabet sam i returns the list of all used characters at position i in sam.

val density : ?length:int -> 'a t -> float

Sam.density sam returns the density of sam considering only used characters. Sam.density ~length=l sam returns the density of sam considering that characters can take l different values.

val average_iterations : 'a t -> float

Sam.average_iterations sam returns the average number of iterations during the previously retrievals realized on sam.

val max_iterations : 'a t -> int

Sam.max_iterations sam returns the maximum number of iteration observed for a single retrieval previously realized on sam.