third_party/mecab-0.996/src/darts.h

   1 /*
   2   Darts -- Double-ARray Trie System
   3
   4
   5   Copyright(C) 2001-2007 Taku Kudo <taku@chasen.org>
   6 */
   7 #ifndef DARTS_H_
   8 #define DARTS_H_
   9
  10 #define DARTS_VERSION "0.31"
  11 #include <vector>
  12 #include <cstring>
  13 #include <cstdio>
  14
  15 #ifdef HAVE_ZLIB_H
  16 namespace zlib {
  17 #include <zlib.h>
  18 }
  19 #define SH(p)((unsigned short)(unsigned char)((p)[0]) | ((unsigned short)(unsigned char)((p)[1]) << 8))
  20 #define LG(p)((unsigned long)(SH(p)) |((unsigned long)(SH((p)+2)) << 16))
  21 #endif
  22
  23 namespace MeCab {
  24
  25 namespace Darts {
  26
  27 template <class T> inline T _max(T x, T y) { return(x > y) ? x : y; }
  28 template <class T> inline T* _resize(T* ptr, size_t n, size_t l, T v) {
  29   T *tmp = new T[l];
  30   for (size_t i = 0; i < n; ++i) tmp[i] = ptr[i];
  31   for (size_t i = n; i < l; ++i) tmp[i] = v;
  32   delete [] ptr;
  33   return tmp;
  34 }
  35
  36 template <class T>
  37 class Length {
  38  public: size_t operator()(const T *key) const
  39   { size_t i; for (i = 0; key[i] != (T)0; ++i) {} return i; }
  40 };
  41
  42 template <> class Length<char> {
  43  public: size_t operator()(const char *key) const
  44   { return std::strlen(key); }
  45 };
  46
  47 template  <class node_type_,  class node_u_type_,
  48            class array_type_, class array_u_type_,
  49            class length_func_ = Length<node_type_> >
  50 class DoubleArrayImpl {
  51  private:
  52
  53   struct node_t {
  54     array_u_type_ code;
  55     size_t     depth;
  56     size_t     left;
  57     size_t     right;
  58   };
  59
  60   struct unit_t {
  61     array_type_   base;
  62     array_u_type_ check;
  63   };
  64
  65   unit_t        *array_;
  66   unsigned char *used_;
  67   size_t        size_;
  68   size_t        alloc_size_;
  69   node_type_    **key_;
  70   size_t        key_size_;
  71   size_t        *length_;
  72   array_type_   *value_;
  73   size_t        progress_;
  74   size_t        next_check_pos_;
  75   bool          no_delete_;
  76   int           error_;
  77   int (*progress_func_)(size_t, size_t);
  78
  79   size_t resize(const size_t new_size) {
  80     unit_t tmp;
  81     tmp.base = 0;
  82     tmp.check = 0;
  83     array_ = _resize(array_, alloc_size_, new_size, tmp);
  84     used_  = _resize(used_, alloc_size_, new_size,
  85                      static_cast<unsigned char>(0));
  86     alloc_size_ = new_size;
  87     return new_size;
  88   }
  89
  90   size_t fetch(const node_t &parent, std::vector <node_t> &siblings) {
  91     if (error_ < 0) return 0;
  92
  93     array_u_type_ prev = 0;
  94
  95     for (size_t i = parent.left; i < parent.right; ++i) {
  96       if ((length_ ? length_[i] : length_func_()(key_[i])) < parent.depth)
  97         continue;
  98
  99       const node_u_type_ *tmp = reinterpret_cast<node_u_type_ *>(key_[i]);
 100
 101       array_u_type_ cur = 0;
 102       if ((length_ ? length_[i] : length_func_()(key_[i])) != parent.depth)
 103         cur = (array_u_type_)tmp[parent.depth] + 1;
 104
 105       if (prev > cur) {
 106         error_ = -3;
 107         return 0;
 108       }
 109
 110       if (cur != prev || siblings.empty()) {
 111         node_t tmp_node;
 112         tmp_node.depth = parent.depth + 1;
 113         tmp_node.code  = cur;
 114         tmp_node.left  = i;
 115         if (!siblings.empty()) siblings[siblings.size()-1].right = i;
 116
 117         siblings.push_back(tmp_node);
 118       }
 119
 120       prev = cur;
 121     }
 122
 123     if (!siblings.empty())
 124       siblings[siblings.size()-1].right = parent.right;
 125
 126     return siblings.size();
 127   }
 128
 129   size_t insert(const std::vector <node_t> &siblings) {
 130     if (error_ < 0) return 0;
 131
 132     size_t begin = 0;
 133     size_t pos   = _max((size_t)siblings[0].code + 1, next_check_pos_) - 1;
 134     size_t nonzero_num = 0;
 135     int    first = 0;
 136
 137     if (alloc_size_ <= pos) resize(pos + 1);
 138
 139     while (true) {
 140    next:
 141       ++pos;
 142
 143       if (alloc_size_ <= pos) resize(pos + 1);
 144
 145       if (array_[pos].check) {
 146         ++nonzero_num;
 147         continue;
 148       } else if (!first) {
 149         next_check_pos_ = pos;
 150         first = 1;
 151       }
 152
 153       begin = pos - siblings[0].code;
 154       if (alloc_size_ <= (begin + siblings[siblings.size()-1].code))
 155         resize(static_cast<size_t>(alloc_size_ *
 156                                    _max(1.05, 1.0 * key_size_ / progress_)));
 157
 158       if (used_[begin]) continue;
 159
 160       for (size_t i = 1; i < siblings.size(); ++i)
 161         if (array_[begin + siblings[i].code].check != 0) goto next;
 162
 163       break;
 164     }
 165
 166     // -- Simple heuristics --
 167     // if the percentage of non-empty contents in check between the index
 168     // 'next_check_pos' and 'check' is greater than some constant
 169     // value(e.g. 0.9),
 170     // new 'next_check_pos' index is written by 'check'.
 171     if (1.0 * nonzero_num/(pos - next_check_pos_ + 1) >= 0.95)
 172       next_check_pos_ = pos;
 173
 174     used_[begin] = 1;
 175     size_ = _max(size_,
 176                  begin +
 177                  static_cast<size_t>(siblings[siblings.size() - 1].code + 1));
 178
 179     for (size_t i = 0; i < siblings.size(); ++i)
 180       array_[begin + siblings[i].code].check = begin;
 181
 182     for (size_t i = 0; i < siblings.size(); ++i) {
 183       std::vector <node_t> new_siblings;
 184
 185       if (!fetch(siblings[i], new_siblings)) {
 186         array_[begin + siblings[i].code].base =
 187             value_ ?
 188             static_cast<array_type_>(-value_[siblings[i].left]-1) :
 189             static_cast<array_type_>(-siblings[i].left-1);
 190
 191         if (value_ && (array_type_)(-value_[siblings[i].left]-1) >= 0) {
 192           error_ = -2;
 193           return 0;
 194         }
 195
 196         ++progress_;
 197         if (progress_func_)(*progress_func_)(progress_, key_size_);
 198
 199       } else {
 200         size_t h = insert(new_siblings);
 201         array_[begin + siblings[i].code].base = h;
 202       }
 203     }
 204
 205     return begin;
 206   }
 207
 208  public:
 209
 210   typedef array_type_  value_type;
 211   typedef node_type_   key_type;
 212   typedef array_type_  result_type;  // for compatibility
 213
 214   struct result_pair_type {
 215     value_type value;
 216     size_t     length;
 217   };
 218
 219   explicit DoubleArrayImpl(): array_(0), used_(0),
 220                               size_(0), alloc_size_(0),
 221                               no_delete_(0), error_(0) {}
 222   ~DoubleArrayImpl() { clear(); }
 223
 224   void set_result(value_type& x, value_type r, size_t) const {
 225     x = r;
 226   }
 227
 228   void set_result(result_pair_type& x, value_type r, size_t l) const {
 229     x.value = r;
 230     x.length = l;
 231   }
 232
 233   void set_array(void *ptr, size_t size = 0) {
 234     clear();
 235     array_ = reinterpret_cast<unit_t *>(ptr);
 236     no_delete_ = true;
 237     size_ = size;
 238   }
 239
 240   const void *array() const {
 241     return const_cast<const void *>(reinterpret_cast<void *>(array_));
 242   }
 243
 244   void clear() {
 245     if (!no_delete_)
 246       delete [] array_;
 247     delete [] used_;
 248     array_ = 0;
 249     used_ = 0;
 250     alloc_size_ = 0;
 251     size_ = 0;
 252     no_delete_ = false;
 253   }
 254
 255   size_t unit_size()  const { return sizeof(unit_t); }
 256   size_t size()       const { return size_; }
 257   size_t total_size() const { return size_ * sizeof(unit_t); }
 258
 259   size_t nonzero_size() const {
 260     size_t result = 0;
 261     for (size_t i = 0; i < size_; ++i)
 262       if (array_[i].check) ++result;
 263     return result;
 264   }
 265
 266   int build(size_t     key_size,
 267             key_type   **key,
 268             size_t     *length = 0,
 269             value_type *value = 0,
 270             int (*progress_func)(size_t, size_t) = 0) {
 271     if (!key_size || !key) return 0;
 272
 273     progress_func_ = progress_func;
 274     key_           = key;
 275     length_        = length;
 276     key_size_      = key_size;
 277     value_         = value;
 278     progress_      = 0;
 279
 280     resize(8192);
 281
 282     array_[0].base = 1;
 283     next_check_pos_ = 0;
 284
 285     node_t root_node;
 286     root_node.left  = 0;
 287     root_node.right = key_size;
 288     root_node.depth = 0;
 289
 290     std::vector <node_t> siblings;
 291     fetch(root_node, siblings);
 292     insert(siblings);
 293
 294     size_ += (1 << 8 * sizeof(key_type)) + 1;
 295     if (size_ >= alloc_size_) resize(size_);
 296
 297     delete [] used_;
 298     used_ = 0;
 299
 300     return error_;
 301   }
 302
 303   int open(const char *file,
 304            const char *mode = "rb",
 305            size_t offset = 0,
 306            size_t size = 0) {
 307     std::FILE *fp = std::fopen(file, mode);
 308     if (!fp) return -1;
 309     if (std::fseek(fp, offset, SEEK_SET) != 0) return -1;
 310
 311     if (!size) {
 312       if (std::fseek(fp, 0L,     SEEK_END) != 0) return -1;
 313       size = std::ftell(fp);
 314       if (std::fseek(fp, offset, SEEK_SET) != 0) return -1;
 315     }
 316
 317     clear();
 318
 319     size_ = size;
 320     size_ /= sizeof(unit_t);
 321     array_ = new unit_t[size_];
 322     if (size_ != std::fread(reinterpret_cast<unit_t *>(array_),
 323                             sizeof(unit_t), size_, fp)) return -1;
 324     std::fclose(fp);
 325
 326     return 0;
 327   }
 328
 329   int save(const char *file,
 330            const char *mode = "wb",
 331            size_t offset = 0) {
 332     if (!size_) return -1;
 333     std::FILE *fp = std::fopen(file, mode);
 334     if (!fp) return -1;
 335     if (size_ != std::fwrite(reinterpret_cast<unit_t *>(array_),
 336                              sizeof(unit_t), size_, fp))
 337       return -1;
 338     std::fclose(fp);
 339     return 0;
 340   }
 341
 342 #ifdef HAVE_ZLIB_H
 343   int gzopen(const char *file,
 344              const char *mode = "rb",
 345              size_t offset = 0,
 346              size_t size = 0) {
 347     std::FILE *fp  = std::fopen(file, mode);
 348     if (!fp) return -1;
 349     clear();
 350
 351     size_ = size;
 352     if (!size_) {
 353       if (-1L != static_cast<long>(std::fseek(fp, -8, SEEK_END))) {
 354         char buf[8];
 355         if (std::fread(static_cast<char*>(buf),
 356                        1, 8, fp) != sizeof(buf)) {
 357           std::fclose(fp);
 358           return -1;
 359         }
 360         size_ = LG(buf+4);
 361         size_ /= sizeof(unit_t);
 362       }
 363     }
 364     std::fclose(fp);
 365
 366     if (!size_) return -1;
 367
 368     zlib::gzFile gzfp = zlib::gzopen(file, mode);
 369     if (!gzfp) return -1;
 370     array_ = new unit_t[size_];
 371     if (zlib::gzseek(gzfp, offset, SEEK_SET) != 0) return -1;
 372     zlib::gzread(gzfp, reinterpret_cast<unit_t *>(array_),
 373                  sizeof(unit_t) * size_);
 374     zlib::gzclose(gzfp);
 375     return 0;
 376   }
 377
 378   int gzsave(const char *file, const char *mode = "wb",
 379              size_t offset = 0) {
 380     zlib::gzFile gzfp = zlib::gzopen(file, mode);
 381     if (!gzfp) return -1;
 382     zlib::gzwrite(gzfp, reinterpret_cast<unit_t *>(array_),
 383                   sizeof(unit_t) * size_);
 384     zlib::gzclose(gzfp);
 385     return 0;
 386   }
 387 #endif
 388
 389   template <class T>
 390   inline void exactMatchSearch(const key_type *key,
 391                                T & result,
 392                                size_t len = 0,
 393                                size_t node_pos = 0) const {
 394     result = exactMatchSearch<T>(key, len, node_pos);
 395     return;
 396   }
 397
 398   template <class T>
 399   inline T exactMatchSearch(const key_type *key,
 400                             size_t len = 0,
 401                             size_t node_pos = 0) const {
 402     if (!len) len = length_func_()(key);
 403
 404     T result;
 405     set_result(result, -1, 0);
 406
 407     register array_type_  b = array_[node_pos].base;
 408     register array_u_type_ p;
 409
 410     for (register size_t i = 0; i < len; ++i) {
 411       p = b +(node_u_type_)(key[i]) + 1;
 412       if (static_cast<array_u_type_>(b) == array_[p].check)
 413         b = array_[p].base;
 414       else
 415         return result;
 416     }
 417
 418     p = b;
 419     array_type_ n = array_[p].base;
 420     if (static_cast<array_u_type_>(b) == array_[p].check && n < 0)
 421       set_result(result, -n-1, len);
 422
 423     return result;
 424   }
 425
 426   template <class T>
 427   size_t commonPrefixSearch(const key_type *key,
 428                             T* result,
 429                             size_t result_len,
 430                             size_t len = 0,
 431                             size_t node_pos = 0) const {
 432     if (!len) len = length_func_()(key);
 433
 434     register array_type_  b   = array_[node_pos].base;
 435     register size_t     num = 0;
 436     register array_type_  n;
 437     register array_u_type_ p;
 438
 439     for (register size_t i = 0; i < len; ++i) {
 440       p = b;  // + 0;
 441       n = array_[p].base;
 442       if ((array_u_type_) b == array_[p].check && n < 0) {
 443         // result[num] = -n-1;
 444         if (num < result_len) set_result(result[num], -n-1, i);
 445         ++num;
 446       }
 447
 448       p = b +(node_u_type_)(key[i]) + 1;
 449       if ((array_u_type_) b == array_[p].check)
 450         b = array_[p].base;
 451       else
 452         return num;
 453     }
 454
 455     p = b;
 456     n = array_[p].base;
 457
 458     if ((array_u_type_)b == array_[p].check && n < 0) {
 459       if (num < result_len) set_result(result[num], -n-1, len);
 460       ++num;
 461     }
 462
 463     return num;
 464   }
 465
 466   value_type traverse(const key_type *key,
 467                       size_t &node_pos,
 468                       size_t &key_pos,
 469                       size_t len = 0) const {
 470     if (!len) len = length_func_()(key);
 471
 472     register array_type_  b = array_[node_pos].base;
 473     register array_u_type_ p;
 474
 475     for (; key_pos < len; ++key_pos) {
 476       p = b +(node_u_type_)(key[key_pos]) + 1;
 477       if (static_cast<array_u_type_>(b) == array_[p].check) {
 478         node_pos = p;
 479         b = array_[p].base;
 480       } else {
 481         return -2;  // no node
 482       }
 483     }
 484
 485     p = b;
 486     array_type_ n = array_[p].base;
 487     if (static_cast<array_u_type_>(b) == array_[p].check && n < 0)
 488       return -n-1;
 489
 490     return -1;  // found, but no value
 491   }
 492 };
 493
 494 #if 4 == 2
 495 typedef Darts::DoubleArrayImpl<char, unsigned char, short,
 496                                unsigned short> DoubleArray;
 497 #define DARTS_ARRAY_SIZE_IS_DEFINED 1
 498 #endif
 499
 500 #if 4 == 4 && !defined(DARTS_ARRAY_SIZE_IS_DEFINED)
 501 typedef Darts::DoubleArrayImpl<char, unsigned char, int,
 502                                unsigned int> DoubleArray;
 503 #define DARTS_ARRAY_SIZE_IS_DEFINED 1
 504 #endif
 505
 506 #if 4 == 4 && !defined(DARTS_ARRAY_SIZE_IS_DEFINED)
 507 typedef Darts::DoubleArrayImpl<char, unsigned char, long,
 508                                unsigned long> DoubleArray;
 509 #define DARTS_ARRAY_SIZE_IS_DEFINED 1
 510 #endif
 511
 512 #if 4 == 8 && !defined(DARTS_ARRAY_SIZE_IS_DEFINED)
 513 typedef Darts::DoubleArrayImpl<char, unsigned char, long long,
 514                                unsigned long long> DoubleArray;
 515 #endif
 516 }
 517 }
 518 #endif