grew_fs.ml 9.55 KB
Newer Older
bguillaum's avatar
bguillaum committed
1
open Printf
pj2m's avatar
pj2m committed
2
open Log
bguillaum's avatar
bguillaum committed
3 4 5

open Grew_utils
open Grew_ast
pj2m's avatar
pj2m committed
6 7 8 9 10 11 12 13 14

module Feature = struct
  (* feature= (feature_name, disjunction of atomic values). empty list to encode "any value" *) 
  type t = 
    | Equal of string * string list
    | Different of string * string list

  let get_name = function | Equal (n,_) -> n | Different (n,_) -> n

15 16
  let get_atom = function | Equal (n,[one]) -> Some one | _ -> None

pj2m's avatar
pj2m committed
17 18 19 20 21 22
  let compare feat1 feat2 = Pervasives.compare (get_name feat1) (get_name feat2)
  (* suppose all feat_names to be different and ordered *)

  let rec check ?domain loc name values = match domain with
  | None -> ()
  | Some [] -> Log.fmessage "[GRS] Unknown feature name '%s' %s" name (Loc.to_string loc)
bguillaum's avatar
bguillaum committed
23 24
  | Some ((Ast.Open n)::_) when n = name -> ()
  | Some ((Ast.Closed (n,vs))::_) when n = name -> 
pj2m's avatar
pj2m committed
25 26 27 28 29 30 31 32 33
      (match List_.sort_diff values vs with 
      | [] -> ()
      | l -> Error.build ~loc "Unknown feature values '%s' for feature name '%s'" 
	    (List_.to_string (fun x->x) ", " l)
	    name
      )
  | Some (_::t) -> check ~domain:t loc name values

  let build ?domain = function
bguillaum's avatar
bguillaum committed
34
    | ({Ast.kind=Ast.Equality;name=name;values=unsorted_values},loc) ->
pj2m's avatar
pj2m committed
35 36 37
	let values = List.sort Pervasives.compare unsorted_values in
	check ?domain loc name values;
	Equal (name, values)
bguillaum's avatar
bguillaum committed
38
    | ({Ast.kind=Ast.Disequality;name=name;values=unsorted_values},loc) ->
pj2m's avatar
pj2m committed
39 40 41 42 43 44 45 46 47 48
	let values = List.sort Pervasives.compare unsorted_values in
	check ?domain loc name values;
	Different (name, values)
end



module Feature_structure = struct
  (* list are supposed to be striclty ordered wrt compare*)
  type t = Feature.t list
bguillaum's avatar
bguillaum committed
49

pj2m's avatar
pj2m committed
50 51 52
  let build ?domain ast_fs =
    let unsorted = List.map (Feature.build ?domain) ast_fs in
    List.sort Feature.compare unsorted 
bguillaum's avatar
bguillaum committed
53 54 55 56 57 58 59 60 61

  let of_conll line =

    let morph_fs =
      List.map (fun (feat_name, feat_value) -> Feature.Equal (feat_name, [feat_value])) line.Conll.morph in
    Feature.Equal ("phon", [line.Conll.phon]) ::
    Feature.Equal ("lemma", [line.Conll.lemma]) ::
    Feature.Equal ("cat", [line.Conll.pos2]) :: 
    morph_fs
pj2m's avatar
pj2m committed
62 63 64
  let empty = []

  let rec get name = function
bguillaum's avatar
bguillaum committed
65 66
    | [] -> None
    | Feature.Equal (n,l) :: _ when n=name -> Some l
pj2m's avatar
pj2m committed
67
    | Feature.Equal (n,l) :: t when n<name -> get name t
bguillaum's avatar
bguillaum committed
68 69
    | Feature.Equal _ :: _ -> None
    | Feature.Different _ :: _ -> Log.critical "[Feature_structure.get] this fs contains 'Different' constructor"
pj2m's avatar
pj2m committed
70

bguillaum's avatar
bguillaum committed
71 72
  let get_atom name t =
    match get name t with
bguillaum's avatar
bguillaum committed
73
    | Some [one] -> Some one
bguillaum's avatar
bguillaum committed
74 75
    | _ -> None

pj2m's avatar
pj2m committed
76 77
  let string_of_feature = function
    | Feature.Equal (feat_name, atoms) -> 
bguillaum's avatar
bguillaum committed
78
	sprintf "%s=%s" feat_name
pj2m's avatar
pj2m committed
79 80 81 82 83
	  (match atoms with
	  | [] -> "*"
	  | h::t -> List.fold_right (fun atom acc -> atom^"|"^acc) t h
	  )
    | Feature.Different (feat_name, atoms) -> 
bguillaum's avatar
bguillaum committed
84
	sprintf "%s<>%s" feat_name
pj2m's avatar
pj2m committed
85 86 87 88 89 90 91 92
	  (match atoms with
	  | [] -> "EMPTY"
	  | h::t -> List.fold_right (fun atom acc -> atom^"|"^acc) t h
	  )


  let to_string t = List_.to_string string_of_feature "\\n" t

93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

  let get_main ?main_feat t =
    let main_list = match main_feat with
    | None -> []
    | Some string -> Str.split (Str.regexp " *; *") string in
    
    let rec loop = function
      | [] -> (None, t)
      | feat_name :: tail ->
          (match List.partition (fun f -> Feature.get_name f = feat_name) t with
          | ([], _) -> loop tail
          | ([one], sub) -> (Some one, sub)
          | _ -> Log.critical "[Feature_structure.to_dep] several feature with the same name") in
    loop main_list
    
  let escape  string =
    Str.global_replace (Str.regexp_string  "//PV//") ";"
      (Str.global_replace (Str.regexp_string  "//AND//") "&amp;" string)
  
  let to_dot ?main_feat t =
    let (main_opt, sub) = get_main ?main_feat t in
    sprintf "%s%s"
      (match main_opt with 
      | Some feat -> escape (match Feature.get_atom feat with Some atom -> atom^"|" | None -> "")
      | None -> "" )
      (List_.to_string string_of_feature "\\n" sub)

    
   


bguillaum's avatar
bguillaum committed
124 125 126 127 128 129
  let gr_of_feature = function
    | Feature.Equal (feat_name, [one]) -> sprintf "%s=\"%s\"" feat_name one
    | _ -> Log.critical "[Feature_structure.gr_of_feature] all feature in gr must be atomic value"

  let to_gr t = List_.to_string gr_of_feature ", " t

130 131 132 133 134 135 136
  let to_dep ?main_feat t =
    let (main_opt, sub) = get_main ?main_feat t in
    sprintf " word=\"%s\"; subword=\"%s\"; " 
      (match main_opt with 
      | Some feat -> escape (match Feature.get_atom feat with Some atom -> atom | None -> "")
      | None -> "")
      (escape (List_.to_string string_of_feature "#" sub))
pj2m's avatar
pj2m committed
137 138 139 140 141 142 143 144 145 146

  let rec set_feat feature_name atoms = function
    | [] -> [Feature.Equal (feature_name, atoms)]
    | ((Feature.Equal (fn,_))::_) as t when feature_name < fn -> (Feature.Equal (feature_name, atoms))::t
    | (Feature.Equal (fn,_))::t when feature_name = fn -> (Feature.Equal (feature_name, atoms))::t
    | Feature.Equal (fn,ats)::t -> Feature.Equal (fn,ats):: (set_feat feature_name atoms t) 
    | _ -> Log.bug "[Feature_structure.set_feat]: Disequality not allowed in graph features"; exit 2

  let rec del_feat feature_name = function
    | [] -> []
bguillaum's avatar
bguillaum committed
147 148 149
    | ((Feature.Equal (fn,_))::_) as t when feature_name < fn -> t
    | (Feature.Equal (fn,_))::t when feature_name = fn -> t
    | Feature.Equal (fn,ats)::t -> Feature.Equal (fn,ats):: (del_feat feature_name t) 
pj2m's avatar
pj2m committed
150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276
    | _ -> Log.bug "[Feature_structure.set_feat]: Disequality not allowed in graph features"; exit 2

  (* WARNING: different from prev implem: does not fail when pattern contains a feature_name or in instance *)
  let compatible pattern fs =
    let rec loop = function
      | [], _ -> true

      (* Three next cases: each feature_name present in pattern must be in instance *)
      | _, [] -> false
      | ((Feature.Equal (fn_pat, fv_pat))::t_pat, (Feature.Equal (fn, fv))::t) when fn_pat < fn -> false
      | ((Feature.Different (fn_pat, fv_pat))::t_pat, (Feature.Equal (fn, fv))::t) when fn_pat < fn -> false

      | ((Feature.Equal (fn_pat, fv_pat))::t_pat, (Feature.Equal (fn, fv))::t) 
	when fn_pat > fn ->
	  loop ((Feature.Equal (fn_pat, fv_pat))::t_pat, t)

      | ((Feature.Different (fn_pat, fv_pat))::t_pat, (Feature.Equal (fn, fv))::t) 
	when fn_pat > fn ->
	  loop ((Feature.Different (fn_pat, fv_pat))::t_pat, t)

      | ((Feature.Equal (fn_pat, fv_pat))::t_pat, (Feature.Equal (fn, fv))::t) 
	  (* when fn_pat = fn *) -> 
 	    (match fv_pat, fv with 
	    | [],_ | _, [] -> loop (t_pat,t)
	    | l_pat,l -> not (List_.sort_disjoint l_pat l) && loop (t_pat,t)
	    )

      | ((Feature.Different (fn_pat, fv_pat))::t_pat, (Feature.Equal (fn, fv))::t) 
	  (* when fn_pat = fn*) ->
 	  (match fv_pat, fv with 
	  | [],_ | _, [] -> loop (t_pat,t)
	  | l_pat,l -> (List_.sort_disjoint l_pat l) && loop (t_pat,t)
	  )
    | _ -> Log.bug "[Feature_structure.set_feat]: Disequality not allowed in graph features"; exit 2

    in loop (pattern,fs)

  exception Fail_unif 
  exception Bug_unif of string 
  let unif fs1 fs2 = 
    let rec loop = function
      | [], fs 
      | fs, [] -> fs

      | (f1::t1, f2::t2) when Feature.compare f1 f2 < 0 -> f1 :: loop (t1, f2::t2)
      | (f1::t1, f2::t2) when Feature.compare f1 f2 > 0 -> f2 :: loop (f1::t1, t2)

      (* all remaining case are fn1 = fn2 *)
      | ((Feature.Equal (fn, fv1))::t1, (Feature.Equal (_, fv2))::t2) -> 
 	  (match List_.sort_inter fv1 fv2 with
	  | [] -> raise Fail_unif
	  | fv -> (Feature.Equal (fn, fv)) :: (loop (t1, t2)))

      | ((Feature.Different (fn, fv1))::t1, (Feature.Equal (_, fv2))::t2) -> 
 	  (match List_.sort_diff fv2 fv1 with
	  | [] -> raise Fail_unif
	  | fv -> (Feature.Equal (fn, fv)) :: (loop (t1, t2)))

      | ((Feature.Equal (fn, fv1))::t1, (Feature.Different (_, fv2))::t2) -> 
 	  (match List_.sort_diff fv1 fv2 with
	  | [] -> raise Fail_unif
	  | fv -> (Feature.Equal (fn, fv)) :: (loop (t1, t2)))

       | _ -> raise (Bug_unif "two value declared \"Feature.Different\", cannot reply without the domain !")
    in try Some (loop (fs1, fs2)) with Fail_unif -> None




  let unifiable fs1 fs2 = 
    let rec loop = function
      | [], fs 
      | fs, [] -> true

      | (f1::t1, f2::t2) when Feature.compare f1 f2 < 0 -> loop (t1, f2::t2)
      | (f1::t1, f2::t2) when Feature.compare f1 f2 > 0 -> loop (f1::t1, t2)

      (* all remaining case are fn1 = fn2 *)
      | ((Feature.Equal (fn, fv1))::t1, (Feature.Equal (_, fv2))::t2) -> 
 	  (match List_.sort_inter fv1 fv2 with
	  | [] -> false
	  | _ -> loop (t1, t2))

      | ((Feature.Different (fn, fv1))::t1, (Feature.Equal (_, fv2))::t2) -> 
 	  (match List_.sort_diff fv2 fv1 with
	  | [] -> false
	  | _ -> loop (t1, t2))

      | ((Feature.Equal (fn, fv1))::t1, (Feature.Different (_, fv2))::t2) -> 
 	  (match List_.sort_diff fv1 fv2 with
	  | [] -> false
	  | _ -> loop (t1, t2))
	    
      | _ -> raise (Bug_unif "two value declared \"Different\", cannot reply without the domain !")
    in loop (fs1, fs2)



  let filter fs_p fs_g = 
    let rec loop = function
      | [], fs -> true
      | fs, [] -> false

      | (f1::t1, f2::t2) when Feature.compare f1 f2 < 0 -> false
      | (f1::t1, f2::t2) when Feature.compare f1 f2 > 0 -> loop (f1::t1, t2)

      (* all remaining case are fn1 = fn2 *)
      | ((Feature.Equal (fn, fv1))::t1, (Feature.Equal (_, fv2))::t2) -> 
 	  (match List_.sort_inter fv1 fv2 with
	  | [] -> false
	  | _ -> loop (t1, t2))

      | ((Feature.Different (fn, fv1))::t1, (Feature.Equal (_, fv2))::t2) -> 
 	  (match List_.sort_diff fv2 fv1 with
	  | [] -> false
	  | _ -> loop (t1, t2))

      | ((Feature.Equal (fn, fv1))::t1, (Feature.Different (_, fv2))::t2) -> 
 	  (match List_.sort_diff fv1 fv2 with
	  | [] -> false
	  | _ -> loop (t1, t2))
	    
      | _ -> raise (Bug_unif "two value declared \"Different\", cannot reply without the domain !")
    in loop (fs_p, fs_g)


end