Модуль Stable_matching

module Stable_matching: sig .. end

module Item: sig .. end

type left_index = int

type right_index = int

type rank = int

type ('a, 'v) matches = {

	`left : 'a list;`
	`pairs : ('v * 'v) list;`
	`right : 'a list;`

}

type ('v, 'k) item_matches = (('v, 'k) Item.t, 'v) matches

type unstable_matching = {

	`first : left_index * right_index;`
	`second : left_index * right_index;`
	`current_rank : rank * rank;`
	`optimal : rank * rank;`

}

val stable_matches : distance:(int -> int -> int) ->       ('a, int) matches ->       (unit, unstable_matching) Result.t

val strong_stable_matches : distance:(int -> int -> int) ->       ('a, int) matches ->       (unit, unstable_matching) Result.t

val matches : compatible:(left_index -> right_index -> bool) ->       preferences:(right_index ->                    (left_index * rank) array) ->       size:int * int -> (int, int) matches

matches ~compatible ~preferences ~size:(ls,rs) вычисляет паросочетание между набором из ls элементов слева и rs элементов справа, отдавая предпочтение правой стороне. Паросочетание является совместимым и слабо устойчивым согласно матрице preferences. Размер паросочетания составляет не менее 2/3 размера оптимального паросочетания (вычисление оптимального паросочетания с частичными предпочтениями и безразличием является NP-полной задачей).

val fuzzy_match_names : compatibility:('k -> 'k -> bool) ->       max_right_items:int ->       cutoff:(string -> int) ->       ('v, 'k) Item.t list ->       ('v, 'k) Item.t list -> ('v, 'k) item_matches

fuzzy_match_names ~compatibility ~max_right_item ~cutoff left right вызывает функцию Stable_matching.matches, используя расстояние редактирования OSA для вычисления предпочтений с функцией отсечения. Чтобы избежать квадратичной сложности при большом размере модуля, мы ограничиваем правую сторону первыми max_right_item элементами