src/recognize_kanji.c

   1
   2 #include "defs.h"
   3
   4 #include "recognize_stroke.h"
   5 #include "recognize_kanji.h"
   6 #include "recognize_extra.h"
   7
   8 #if 0
   9 void print_stroke(GList *s)
  10 {
  11     g_print("stroke len = %d\n", g_list_length(s));
  12     for(;s; s = g_list_next(s))
  13     {
  14         gint16 x = ((GdkPoint *)s->data)->x;
  15         gint16 y = ((GdkPoint *)s->data)->y;
  16         g_printf("%d %d\n", x, y);
  17     }
  18 }
  19
  20 static void print_gunichar2(gunichar2 *entry, gint len)
  21 {
  22     gint i;
  23     for(i = 0; i < len; i++)
  24     {
  25         gchar *tmp = (gchar*)entry;
  26         if(tmp[0] == 0xD)
  27             break;
  28         gchar *utfstr = g_convert((gchar*)(entry++), 2, "UTF-8", "UTF-16LE", NULL, NULL, NULL);
  29         g_printf("%s", utfstr);
  30         g_free(utfstr);
  31     }
  32     g_printf("\n");
  33 }
  34 #endif
  35
  36 typedef struct _kanji_result
  37 {
  38     gunichar2 uc;
  39     gint dist;
  40 } kanji_result;
  41
  42 gint LevenshteinDistance(gint l1, gchar *s1, gint l2, gchar *s2)
  43 {
  44     gchar *d = calloc((l1+1)*(l2+1)+1, sizeof(gchar));
  45
  46     int i, j;
  47     for(i = 0; i <= l1; i++)
  48         d[i*(l2 + 1)] = i;
  49     for(j = 0; j <= l2; j++)
  50         d[j] = j;
  51
  52     for(j = 1; j <= l2; j++)
  53     {
  54         for(i = 1; i <= l1; i++)
  55         {
  56             if(s1[i-1] == s2[j-1])
  57                 d[i*(l2 + 1) + j] = d[(i-1)*(l2 + 1) + j - 1];
  58             else
  59             {
  60                 gint a = d[(i-1)*(l2 + 1) + j] + 1;
  61                 gint b = d[i*(l2 + 1) + j - 1] + 1;
  62                 gint c = d[(i-1)*(l2 + 1) + j - 1] + 1;
  63                 d[i*(l2 + 1) + j] = (a > b) ? ((b > c) ? c : b) : ((a > c) ? c : a);
  64             }
  65         }
  66     }
  67     gint ret = d[(l1+1)*(l2+1) - 1];
  68     g_free(d);
  69     return ret;
  70 }
  71
  72 static kanji_result* rate_next_kanji(GList *strokes, gchar **sdata, gunichar2 *entry)
  73 {
  74     kanji_result *res = calloc(1, sizeof(kanji_result));
  75     res->uc = *++entry;
  76     gunichar2 *bakptr = entry;
  77     gint i, j, l, l1 = 0, l2 = 0;
  78     for(i = 0; i < g_strv_length(sdata); i++)
  79         l1 += strlen(sdata[i]);
  80     gchar *s1 = calloc(l1, sizeof(gchar));
  81     for(i = 0, j = 0; i < g_strv_length(sdata); i++)
  82     {
  83         l = strlen(sdata[i]);
  84         g_memmove(&(s1[j]), sdata[i], l);
  85         j += l;
  86     }
  87     for(l2 = 0; g_ascii_isalpha((gchar)*++entry); l2++);
  88     gchar *s2 = calloc(l2, sizeof(gchar));
  89     entry = bakptr;
  90     for(i = 0; i < l2; s2[i++] = (gchar)(*++entry));
  91     res->dist += LevenshteinDistance(l1, s1, l2, s2);
  92     g_free(s1);
  93     g_free(s2);
  94     entry++;
  95     if(*entry == '|')
  96     {
  97         res->dist += pass_extra_filters(strokes, entry);
  98     }
  99     return res;
 100 }
 101
 102 static gint kanji_results_compare(gpointer *ptr1, gpointer *ptr2)
 103 {
 104     kanji_result *kr1 = (kanji_result*)*ptr1, *kr2 = (kanji_result*)*ptr2;
 105     if(kr1->dist > kr2->dist)
 106         return 1;
 107     if(kr1->dist < kr2->dist)
 108         return -1;
 109     return 0;
 110 }
 111
 112 static gunichar2* find_next_entry(gchar *allkanji, gunichar2 *entry, gint allkanjilen, gunichar2 key)
 113 {
 114     if(allkanji == (gchar*)entry)
 115     {
 116         ++entry;
 117         if(*entry != key)
 118             return find_next_entry(allkanji, entry, allkanjilen, key);
 119     }
 120     else
 121     {
 122         if((gchar*)entry - allkanji >= allkanjilen)
 123             return 0;
 124         while((gchar*)entry - allkanji < allkanjilen)
 125         {
 126             if(*++entry == '\n')
 127             {
 128                 entry++;
 129                 if(*entry == key)
 130                     break;
 131                 if(*entry > key)
 132                     return 0;
 133                 ++entry;
 134             }
 135         }
 136     }
 137     return entry;
 138 }
 139
 140 static gunichar2* pick_kanji(GList *strokes, gchar **sdata, gchar *allkanji, gint allkanjilen)
 141 {
 142     const gint MAX_DISTANCE = g_list_length(strokes) - 1;
 143     gint datalen = g_strv_length(sdata), i;
 144     gunichar2 key = 'A' + datalen - 1;
 145     gunichar2 *entry = (gunichar2*)allkanji;
 146     if(key > 'Z')
 147         return 0;
 148
 149     entry = find_next_entry(allkanji, entry, allkanjilen, key);
 150     if(!entry)
 151         return 0;
 152     GPtrArray *arr = g_ptr_array_new();
 153     g_ptr_array_set_free_func(arr, g_free);
 154     for(;;)
 155     {
 156         kanji_result *res = rate_next_kanji(strokes, sdata, entry);
 157         g_ptr_array_add(arr, res);
 158         g_ptr_array_sort(arr, (GCompareFunc)kanji_results_compare);
 159         for(i = arr->len - 1; i >= 0; i--)
 160         {
 161             kanji_result *res = g_ptr_array_index(arr, i);
 162             if(res->dist > MAX_DISTANCE)
 163                 g_ptr_array_remove_index(arr, i);
 164             else
 165                 break;
 166         }
 167         entry = find_next_entry(allkanji, entry, allkanjilen, key);
 168         if(!entry)
 169             break;
 170     }
 171     gunichar2 *ret = calloc(arr->len + 1, sizeof(gunichar2));
 172     for(i = 0; i < arr->len; i++)
 173     {
 174         kanji_result *res = (kanji_result*)g_ptr_array_index(arr, i);
 175         ret[i] = res->uc;
 176     }
 177     g_ptr_array_free(arr, TRUE);
 178     return ret;
 179 }
 180
 181 static GMappedFile* load_strokes_txt(gchar *dir)
 182 {
 183     gchar *fname = g_build_filename(dir, "strokes.txt", NULL);
 184     GMappedFile *file = g_mapped_file_new(fname, FALSE, NULL);
 185     g_free(fname);
 186     return file;
 187 }
 188
 189 gunichar2* recognize_kanji(GList *strokes)
 190 {
 191     static gchar **sdata = NULL;
 192     static gint sdata_len = 0;
 193     static GList *tmp = NULL;
 194     gint strokes_len = g_list_length(strokes);
 195     if(!strokes_len)
 196     {
 197         int i;
 198         for(i = 0; i < sdata_len; g_free(sdata[i++]));
 199         g_free(sdata);
 200         sdata = NULL;
 201         sdata_len = 0;
 202         g_list_free(tmp);
 203         tmp = NULL;
 204         return 0;
 205     }
 206     if(strokes_len == sdata_len - 1)
 207     {
 208         g_free(sdata[sdata_len - 1]);
 209         tmp = g_list_remove(tmp, g_list_last(tmp)->data);
 210     }
 211     sdata = g_realloc(sdata, (strokes_len + 1)*sizeof(gchar*));
 212     if(strokes_len == sdata_len + 1)
 213     {
 214         GList *s = NULL;
 215         sdata[strokes_len - 1] = recognize_stroke(g_list_first(g_list_last(strokes)->data), &s);
 216         tmp = g_list_append(tmp, s);
 217     }
 218     sdata[strokes_len] = 0;
 219     sdata_len = strokes_len;
 220     GMappedFile *file = load_strokes_txt("");
 221     if(!file)
 222     {
 223 #ifdef KP123_DATADIR
 224         file = load_strokes_txt(KP123_DATADIR);
 225 #endif
 226     }
 227     if(!file)
 228     {
 229         g_printf("failed to load strokes.txt\n");
 230         return 0;
 231     }
 232     gint allkanjilen = g_mapped_file_get_length(file);
 233     gchar *allkanji = g_mapped_file_get_contents(file);
 234     gunichar2 *result = pick_kanji(tmp, sdata, allkanji, allkanjilen);
 235     g_mapped_file_unref(file);
 236     return result;
 237 }
 238