1 /*
2  * 確率を評価しビタビアルゴリズム(viterbi algorithm)によって
3  * 文節の区切りを決定してマークする。
4  *
5  *
6  * 外部から呼び出される関数
7  *  anthy_mark_borders()
8  *
9  * Copyright (C) 2006-2007 TABATA Yusuke
10  * Copyright (C) 2004-2006 YOSHIDA Yuichi
11  * Copyright (C) 2006 HANAOKA Toshiyuki
12  *
13  */
14 /*
15   This library is free software; you can redistribute it and/or
16   modify it under the terms of the GNU Lesser General Public
17   License as published by the Free Software Foundation; either
18   version 2 of the License, or (at your option) any later version.
19 
20   This library is distributed in the hope that it will be useful,
21   but WITHOUT ANY WARRANTY; without even the implied warranty of
22   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
23   Lesser General Public License for more details.
24 
25   You should have received a copy of the GNU Lesser General Public
26   License along with this library; if not, write to the Free Software
27   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
28  */
29 /*
30  * コンテキスト中に存在するmeta_wordをつないでグラフを構成します。
31  * (このグラフのことをラティス(lattice/束)もしくはトレリス(trellis)と呼びます)
32  * meta_wordどうしの接続がグラフのノードとなり、構造体lattice_nodeの
33  * リンクとして構成されます。
34  *
35  * ここでの処理は次の二つの要素で構成されます
36  * (1) グラフを構成しつつ、各ノードへの到達確率を求める
37  * (2) グラフを後ろ(右)からたどって最適なパスを求める
38  *
39  */
40 #include <stdio.h>
41 #include <stdlib.h>
42 #include <string.h>
43 #include <math.h>
44 
45 #include <anthy/alloc.h>
46 #include <anthy/xstr.h>
47 #include <anthy/segclass.h>
48 #include <anthy/splitter.h>
49 #include <anthy/feature_set.h>
50 #include <anthy/diclib.h>
51 #include "wordborder.h"
52 
53 static float anthy_normal_length = 20.0; /* 文節の期待される長さ */
54 static void *trans_info_array;
55 
56 #define NODE_MAX_SIZE 50
57 
58 /* グラフのノード(遷移状態) */
59 struct lattice_node {
60   int border; /* 文字列中のどこから始まる状態か */
61   enum seg_class seg_class; /* この状態の品詞 */
62 
63 
64   double real_probability;  /* ここに至るまでの確率(文節数補正無し) */
65   double adjusted_probability;  /* ここに至るまでの確率(文節数補正有り) */
66 
67 
68   struct lattice_node* before_node; /* 一つ前の遷移状態 */
69   struct meta_word* mw; /* この遷移状態に対応するmeta_word */
70 
71   struct lattice_node* next; /* リスト構造のためのポインタ */
72 };
73 
74 struct node_list_head {
75   struct lattice_node *head;
76   int nr_nodes;
77 };
78 
79 struct lattice_info {
80   /* 遷移状態のリストの配列 */
81   struct node_list_head *lattice_node_list;
82   struct splitter_context *sc;
83   /* ノードのアロケータ */
84   allocator node_allocator;
85 };
86 
87 /*
88  */
89 static void
print_lattice_node(struct lattice_info * info,struct lattice_node * node)90 print_lattice_node(struct lattice_info *info, struct lattice_node *node)
91 {
92   if (!node) {
93     printf("**lattice_node (null)*\n");
94     return ;
95   }
96   printf("**lattice_node probability=%.128f\n", node->real_probability);
97   if (node->mw) {
98     anthy_print_metaword(info->sc, node->mw);
99   }
100 }
101 
102 static double
get_poisson(double lambda,int r)103 get_poisson(double lambda, int r)
104 {
105   int i;
106   double result;
107 
108   /* 要するにポワソン分布 */
109   result = pow(lambda, r) * exp(-lambda);
110   for (i = 2; i <= r; ++i) {
111     result /= i;
112   }
113 
114   return result;
115 }
116 
117 /* 文節の形式からスコアを調整する */
118 static double
get_form_bias(struct meta_word * mw)119 get_form_bias(struct meta_word *mw)
120 {
121   double bias;
122   int r;
123   /* wrapされている場合は内部のを使う */
124   while (mw->type == MW_WRAP) {
125     mw = mw->mw1;
126   }
127   /* 文節長による調整 */
128   r = mw->len;
129   if (r > 6) {
130     r = 6;
131   }
132   if (r < 2) {
133     r = 2;
134   }
135   if (mw->seg_class == SEG_RENTAI_SHUSHOKU &&
136       r < 3) {
137     /* 指示語 */
138     r = 3;
139   }
140   bias = get_poisson(anthy_normal_length, r);
141   return bias;
142 }
143 
144 static void
build_feature_list(struct lattice_node * node,struct feature_list * features)145 build_feature_list(struct lattice_node *node,
146 		   struct feature_list *features)
147 {
148   int pc, cc;
149   if (node) {
150     cc = node->seg_class;
151   } else {
152     cc = SEG_TAIL;
153   }
154   anthy_feature_list_set_cur_class(features, cc);
155   if (node && node->before_node) {
156     pc = node->before_node->seg_class;
157   } else {
158     pc = SEG_HEAD;
159   }
160   anthy_feature_list_set_class_trans(features, pc, cc);
161 
162   if (node && node->mw) {
163     struct meta_word *mw = node->mw;
164     anthy_feature_list_set_dep_class(features, mw->dep_class);
165     anthy_feature_list_set_dep_word(features,
166 				    mw->dep_word_hash);
167     anthy_feature_list_set_mw_features(features, mw->mw_features);
168     anthy_feature_list_set_noun_cos(features, mw->core_wt);
169 
170   }
171   anthy_feature_list_sort(features);
172 }
173 
174 static double
calc_probability(int cc,struct feature_list * fl)175 calc_probability(int cc, struct feature_list *fl)
176 {
177   struct feature_freq *res, arg;
178   double prob;
179 
180   /* 確率を計算する */
181   res = anthy_find_feature_freq(trans_info_array,
182 				fl, &arg);
183   prob = 0;
184   if (res) {
185     double pos = res->f[15];
186     double neg = res->f[14];
187     prob = 1 - (neg) / (double) (pos + neg);
188   }
189   if (prob <= 0) {
190     /* 例文中に存在しないパターンなので0に近いスコア */
191     prob = 1.0f / (double)(10000 * 100);
192   }
193 
194   if (anthy_splitter_debug_flags() & SPLITTER_DEBUG_LN) {
195     anthy_feature_list_print(fl);
196     printf(" cc=%d(%s), P=%f\n", cc, anthy_seg_class_sym(cc), prob);
197   }
198   return prob;
199 }
200 
201 static double
get_transition_probability(struct lattice_node * node)202 get_transition_probability(struct lattice_node *node)
203 {
204   struct feature_list features;
205   double probability;
206 
207   /**/
208   anthy_feature_list_init(&features);
209   build_feature_list(node, &features);
210   probability = calc_probability(node->seg_class, &features);
211   anthy_feature_list_free(&features);
212 
213   /* 文節の形に対する評価 */
214   probability *= get_form_bias(node->mw);
215   return probability;
216 }
217 
218 static struct lattice_info*
alloc_lattice_info(struct splitter_context * sc,int size)219 alloc_lattice_info(struct splitter_context *sc, int size)
220 {
221   int i;
222   struct lattice_info* info = (struct lattice_info*)malloc(sizeof(struct lattice_info));
223   info->sc = sc;
224   info->lattice_node_list = (struct node_list_head*)
225     malloc((size + 1) * sizeof(struct node_list_head));
226   for (i = 0; i < size + 1; i++) {
227     info->lattice_node_list[i].head = NULL;
228     info->lattice_node_list[i].nr_nodes = 0;
229   }
230   info->node_allocator = anthy_create_allocator(sizeof(struct lattice_node),
231 						NULL);
232   return info;
233 }
234 
235 static void
calc_node_parameters(struct lattice_node * node)236 calc_node_parameters(struct lattice_node *node)
237 {
238   /* 対応するmetawordが無い場合は文頭と判断する */
239   node->seg_class = node->mw ? node->mw->seg_class : SEG_HEAD;
240 
241   if (node->before_node) {
242     /* 左に隣接するノードがある場合 */
243     node->real_probability = node->before_node->real_probability *
244       get_transition_probability(node);
245     node->adjusted_probability = node->real_probability *
246       (node->mw ? node->mw->score : 1000);
247   } else {
248     /* 左に隣接するノードが無い場合 */
249     node->real_probability = 1.0;
250     node->adjusted_probability = node->real_probability;
251   }
252 }
253 
254 static struct lattice_node*
alloc_lattice_node(struct lattice_info * info,struct lattice_node * before_node,struct meta_word * mw,int border)255 alloc_lattice_node(struct lattice_info *info,
256 		   struct lattice_node* before_node,
257 		   struct meta_word* mw, int border)
258 {
259   struct lattice_node* node;
260   node = anthy_smalloc(info->node_allocator);
261   node->before_node = before_node;
262   node->border = border;
263   node->next = NULL;
264   node->mw = mw;
265 
266   calc_node_parameters(node);
267 
268   return node;
269 }
270 
271 static void
release_lattice_node(struct lattice_info * info,struct lattice_node * node)272 release_lattice_node(struct lattice_info *info, struct lattice_node* node)
273 {
274   anthy_sfree(info->node_allocator, node);
275 }
276 
277 static void
release_lattice_info(struct lattice_info * info)278 release_lattice_info(struct lattice_info* info)
279 {
280   anthy_free_allocator(info->node_allocator);
281   free(info->lattice_node_list);
282   free(info);
283 }
284 
285 /*
286  * ノードを比較する
287  *
288  ** 返り値
289  * 1: lhsの方が確率が高い
290  * 0: 同じ
291  * -1: rhsの方が確率が高い
292  */
293 static int
cmp_node(struct lattice_node * lhs,struct lattice_node * rhs)294 cmp_node(struct lattice_node *lhs, struct lattice_node *rhs)
295 {
296   struct lattice_node *lhs_before = lhs;
297   struct lattice_node *rhs_before = rhs;
298 
299   if (lhs && !rhs) return 1;
300   if (!lhs && rhs) return -1;
301   if (!lhs && !rhs) return 0;
302 
303   while (lhs_before && rhs_before) {
304     if (lhs_before->mw && rhs_before->mw &&
305 	lhs_before->mw->from + lhs_before->mw->len == rhs_before->mw->from + rhs_before->mw->len) {
306       /* Give preference to OCHAIRE */
307       if (lhs->mw->type == MW_OCHAIRE && rhs->mw->type != MW_OCHAIRE)
308 	return 1;
309       else if (lhs->mw->type != MW_OCHAIRE && rhs->mw->type == MW_OCHAIRE)
310 	return -1;
311 
312       /* Give negative preference to COMPOUND_PART */
313       if (lhs->mw->type != MW_COMPOUND_PART && rhs->mw->type == MW_COMPOUND_PART)
314 	return 1;
315       else if (lhs->mw->type == MW_COMPOUND_PART && rhs->mw->type != MW_COMPOUND_PART)
316 	return -1;
317     } else {
318       break;
319     }
320     lhs_before = lhs_before->before_node;
321     rhs_before = rhs_before->before_node;
322   }
323 
324   /* 最後に遷移確率を見る */
325   if (lhs->adjusted_probability > rhs->adjusted_probability) {
326     return 1;
327   } else if (lhs->adjusted_probability < rhs->adjusted_probability) {
328     return -1;
329   } else {
330     return 0;
331   }
332 }
333 
334 /*
335  * 構成中のラティスにノードを追加する
336  */
337 static void
push_node(struct lattice_info * info,struct lattice_node * new_node,int position)338 push_node(struct lattice_info* info, struct lattice_node* new_node,
339 	  int position)
340 {
341   struct lattice_node* node;
342   struct lattice_node* previous_node = NULL;
343 
344   if (anthy_splitter_debug_flags() & SPLITTER_DEBUG_LN) {
345     print_lattice_node(info, new_node);
346   }
347 
348   /* 先頭のnodeが無ければ無条件に追加 */
349   node = info->lattice_node_list[position].head;
350   if (!node) {
351     info->lattice_node_list[position].head = new_node;
352     info->lattice_node_list[position].nr_nodes ++;
353     return;
354   }
355 
356   while (node->next) {
357     /* 余計なノードを追加しないための枝刈り */
358     if (new_node->seg_class == node->seg_class &&
359 	new_node->border == node->border) {
360       /* segclassが同じで、始まる位置が同じなら */
361       switch (cmp_node(new_node, node)) {
362       case 0:
363       case 1:
364 	/* 新しい方が確率が大きいか学習によるものなら、古いのと置き換え*/
365 	if (previous_node) {
366 	  previous_node->next = new_node;
367 	} else {
368 	  info->lattice_node_list[position].head = new_node;
369 	}
370 	new_node->next = node->next;
371 	release_lattice_node(info, node);
372 	break;
373       case -1:
374 	/* そうでないなら削除 */
375 	release_lattice_node(info, new_node);
376 	break;
377       }
378       return;
379     }
380     previous_node = node;
381     node = node->next;
382   }
383 
384   /* 最後のノードの後ろに追加 */
385   node->next = new_node;
386   info->lattice_node_list[position].nr_nodes ++;
387 }
388 
389 /* 一番確率の低いノードを消去する*/
390 static void
remove_min_node(struct lattice_info * info,struct node_list_head * node_list)391 remove_min_node(struct lattice_info *info, struct node_list_head *node_list)
392 {
393   struct lattice_node* node = node_list->head;
394   struct lattice_node* previous_node = NULL;
395   struct lattice_node* min_node = node;
396   struct lattice_node* previous_min_node = NULL;
397 
398   /* 一番確率の低いノードを探す */
399   while (node) {
400     if (cmp_node(node, min_node) < 0) {
401       previous_min_node = previous_node;
402       min_node = node;
403     }
404     previous_node = node;
405     node = node->next;
406   }
407 
408   /* 一番確率の低いノードを削除する */
409   if (previous_min_node) {
410     previous_min_node->next = min_node->next;
411   } else {
412     node_list->head = min_node->next;
413   }
414   release_lattice_node(info, min_node);
415   node_list->nr_nodes --;
416 }
417 
418 /* いわゆるビタビアルゴリズムを使用して経路を選ぶ */
419 static void
choose_path(struct lattice_info * info,int to)420 choose_path(struct lattice_info* info, int to)
421 {
422   /* 最後まで到達した遷移のなかで一番確率の大きいものを選ぶ */
423   struct lattice_node* node;
424   struct lattice_node* best_node = NULL;
425   int last = to;
426   while (!info->lattice_node_list[last].head) {
427     /* 最後の文字まで遷移していなかったら後戻り */
428     --last;
429   }
430   for (node = info->lattice_node_list[last].head; node; node = node->next) {
431     if (cmp_node(node, best_node) > 0) {
432       best_node = node;
433     }
434   }
435   if (!best_node) {
436     return;
437   }
438 
439   /* 遷移を逆にたどりつつ文節の切れ目を記録 */
440   node = best_node;
441   if (anthy_splitter_debug_flags() & SPLITTER_DEBUG_LN) {
442     printf("choose_path()\n");
443   }
444   while (node->before_node) {
445     info->sc->word_split_info->best_seg_class[node->border] =
446       node->seg_class;
447     anthy_mark_border_by_metaword(info->sc, node->mw);
448     /**/
449     if (anthy_splitter_debug_flags() & SPLITTER_DEBUG_LN) {
450       print_lattice_node(info, node);
451     }
452     /**/
453     node = node->before_node;
454   }
455 }
456 
457 static void
build_graph(struct lattice_info * info,int from,int to)458 build_graph(struct lattice_info* info, int from, int to)
459 {
460   int i;
461   struct lattice_node* node;
462   struct lattice_node* left_node;
463 
464   /* 始点となるノードを追加 */
465   node = alloc_lattice_node(info, NULL, NULL, from);
466   push_node(info, node, from);
467 
468   /* info->lattice_node_list[index]にはindexまでの遷移が入っているのであって、
469    * indexからの遷移が入っているのではない
470    */
471 
472   /* 全ての遷移を左から試す */
473   for (i = from; i < to; ++i) {
474     for (left_node = info->lattice_node_list[i].head; left_node;
475 	 left_node = left_node->next) {
476       struct meta_word *mw;
477       /* i文字目に到達するlattice_nodeのループ */
478 
479       for (mw = info->sc->word_split_info->cnode[i].mw; mw; mw = mw->next) {
480 	int position;
481 	struct lattice_node* new_node;
482 	/* i文字目からのmeta_wordのループ */
483 
484 	if (mw->can_use != ok) {
485 	  continue; /* 決められた文節の区切りをまたぐmetawordは使わない */
486 	}
487 	position = i + mw->len;
488 	new_node = alloc_lattice_node(info, left_node, mw, i);
489 	push_node(info, new_node, position);
490 
491 	/* 解の候補が多すぎたら、確率の低い方から削る */
492 	if (info->lattice_node_list[position].nr_nodes >= NODE_MAX_SIZE) {
493 	  remove_min_node(info, &info->lattice_node_list[position]);
494 	}
495       }
496     }
497   }
498 
499   /* 文末補正 */
500   for (node = info->lattice_node_list[to].head; node; node = node->next) {
501     struct feature_list features;
502     anthy_feature_list_init(&features);
503     build_feature_list(NULL, &features);
504     node->adjusted_probability = node->adjusted_probability *
505       calc_probability(SEG_TAIL, &features);
506     anthy_feature_list_free(&features);
507   }
508 }
509 
510 void
anthy_mark_borders(struct splitter_context * sc,int from,int to)511 anthy_mark_borders(struct splitter_context *sc, int from, int to)
512 {
513   struct lattice_info* info = alloc_lattice_info(sc, to);
514   trans_info_array = anthy_file_dic_get_section("trans_info");
515   build_graph(info, from, to);
516   choose_path(info, to);
517   release_lattice_info(info);
518 }
519