src/recognize_kanji.c

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