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