grew_fs.ml 9.63 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

  let of_conll line =
    let morph_fs =
      List.map (fun (feat_name, feat_value) -> Feature.Equal (feat_name, [feat_value])) line.Conll.morph in
57
58
59
60
61
62
63
64
    let unsorted = 
      Feature.Equal ("phon", [line.Conll.phon]) ::
      Feature.Equal ("lemma", [line.Conll.lemma]) ::
      Feature.Equal ("cat", [line.Conll.pos2]) :: 
      morph_fs in
    List.sort Feature.compare unsorted 


pj2m's avatar
pj2m committed
65
66
67
  let empty = []

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

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

pj2m's avatar
pj2m committed
79
80
  let string_of_feature = function
    | Feature.Equal (feat_name, atoms) -> 
bguillaum's avatar
bguillaum committed
81
	sprintf "%s=%s" feat_name
pj2m's avatar
pj2m committed
82
83
84
85
86
	  (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
87
	sprintf "%s<>%s" feat_name
pj2m's avatar
pj2m committed
88
89
90
91
92
93
94
95
	  (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

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
124
125
126

  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
127
128
129
130
131
132
  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

133
134
135
136
137
138
139
  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
140
141
142
143
144
145
146
147
148
149

  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
150
151
152
    | ((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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
    | _ -> 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) 
174
175
	  (* when fn_pat = fn *) ->
            (match fv_pat, fv with 
pj2m's avatar
pj2m committed
176
177
178
179
180
181
182
183
184
185
186
187
	    | [],_ | _, [] -> 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)
188
      
pj2m's avatar
pj2m committed
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
277
278
279

  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