fasttext源码学习(1)--dictionary

本文主要是介绍fasttext源码学习(1)--dictionary，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

fasttext源码学习(1)–dictionary

前言

fasttext在文本分类方面很厉害，精度高，速度快，模型小(压缩后)，总之非常值得学习。花了点时间学习了下源码，本篇主要是与dictionary相关。

dictionary主要存储词语和切分词及对应的id，因为fasttext能处理超大数据集，如果不使用一些方法，只是加载这些内容，内存就很容易爆掉，我们来看看有哪些关键方法。

一词语数量控制

该方法在Dictionary::readFromFile中调用，截取关键部分如下：

// 简化版
void Dictionary::readFromFile(std::istream& in) {int64_t minThreshold = 1; // [1]while (readWord(in, word)) {add(word);if (size_ > 0.75 * MAX_VOCAB_SIZE) { // [2]minThreshold++;threshold(minThreshold, minThreshold);}}threshold(args_->minCount, args_->minCountLabel); // [3]initTableDiscard();initNgrams();
}

其中threshold函数为一个过滤方法，即按出现频次过滤，小于阈值的被删除，逻辑并不复杂。

// t: 词语频次阈值
// t1: label频次阈值
void Dictionary::threshold(int64_t t, int64_t tl)

这里用到几个控制方法：

只存储词语和标签

while循环里的readWord(in, word)函数并没有做单词的切分，只读取了空格等分割的词语；而add函数内部做了去重，相同的词语只增加了计数。

2.自动过滤

从[1], [2]中可以看出，超出阈值就会自动进行一次过滤, 触发自动过滤的条件是大于 MAX_VOCAB_SIZE的3/4，MAX_VOCAB_SIZE值为3000万，一般情况下，只存储去重后的词语，还是很难触发自动过滤的。

3. 参数控制过滤

从[3]可以看出文件读取完成后，会再次调用threshold，控制参数是minCount,minCountLabel, 可以从控制台输入进行控制，这样即使未触发自动过滤，也会根据用户需要进行词语频次过滤。

使用以上方法可以根据实际需要，将用于存储(包括存储至模型中)的词语数量控制在一定范围内；其中最主要的是只存储词语，因为如果加上切词，可能会使词表迅速膨胀，那切词的信息是如何处理的？

二 ngrams处理

从前面可以看出readFromFile函数是在词语加载完毕之后，才调用了initNgrams函数来初始化ngrams信息，从这个调用逻辑也可以看出dictionary的处理思路，ngrams和words分开处理。

// 简化版
void Dictionary::initNgrams() {for (size_t i = 0; i < size_; i++) {std::string word = BOW + words_[i].word + EOW;if (words_[i].word != EOS) {computeSubwords(word, words_[i].subwords);// [1]}}
}
void Dictionary::computeSubwords(std::string& word,std::vector<int32_t>& ngrams) const {for (size_t i = 0; i < word.size(); i++) {std::string ngram;for (size_t j = i, n = 1; j < word.size() && n <= args_->maxn; n++) {ngram.push_back(word[j++]);if (n >= args_->minn && !(n == 1 && (i == 0 || j == word.size()))) {int32_t h = hash(ngram) % args_->bucket;pushHash(ngrams, h); // [2]}}}
}

从[1]、[2]可以看出，ngram的id是存储在每个word的结构体中的(words_[i].subwords)，加载文件时，会计算出该id，供后续的训练时候使用，但是该id并不会存储到模型中，那如何保证每次计算都得出正确的id呢？因为训练中的矩阵计算可不会区分words和ngrams，它们都在一个矩阵中。

三 hash与id

1 words的hash与id

从第一部分可以知道words的初始化是在add函数中，下面列出相关函数：

std::vector<int32_t> word2int_;
std::vector<entry> words_;
void Dictionary::add(const std::string& w) {int32_t h = find(w);ntokens_++;if (word2int_[h] == -1) {entry e;e.word = w;e.count = 1;e.type = getType(w);words_.push_back(e); // [1]word2int_[h] = size_++; // [2]} else {words_[word2int_[h]].count++;}
}

从[1] [2]以及定义可以看出，words_直接push进新的词，words2int_存储hash值与id的对应关系，而新词的id为在数组中的下标，而hash值通过find得出：

// 简化版
int32_t Dictionary::find(const std::string& w) const {return find(w, hash(w));
}
int32_t Dictionary::find(const std::string& w, uint32_t h) const {int32_t word2intsize = word2int_.size();int32_t id = h % word2intsize; // [1]while (word2int_[id] != -1 && words_[word2int_[id]].word != w) {id = (id + 1) % word2intsize; // [2]}return id;
}

其中[1]保证hash值不超过words2int_的大小(不越界), 而[2]是防碰撞策略，线性增加。

2 ngrams的hash与id

与ngrams有关的函数在computeSubwords中：

int32_t h = hash(ngram) % args_->bucket; // [1]
pushHash(ngrams, h); void Dictionary::pushHash(std::vector<int32_t>& hashes, int32_t id) const {hashes.push_back(nwords_ + id); // [2]
}

从[1]处得到id值，[2]中存储前将id加上了nwords_, 而nwords_是词语总数，这时候整个逻辑就很清晰了，words的id在nwords_内,而ngrams的id则会始终大于nwords_, 从而保证id不冲突。但是[1]处的args_->bucket又是怎么回事呢？

四 id与矩阵

训练时，会调用createRandomMatrix函数创建输入矩阵：

Matrix FastText::createRandomMatrix() const {DenseMatrix input = DenseMatrix(dict_->nwords() + args_->bucket, args_->dim); // [1]input->uniform(1.0 / args_->dim, args_->thread, args_->seed);return input;
}

从[1]处可以看出，输入矩阵的行数为nwords_ + args_->bucket, 结合上面的id的计算，可以看出整个全貌，words的id在前nwords_中；而ngrams的id散列在args_bucket中，加上nwords_的偏移.

而原始的哈希函数反而存在感是最低的：

uint32_t Dictionary::hash(const std::string& str) const {uint32_t h = 2166136261;for (size_t i = 0; i < str.size(); i++) {h = h ^ uint32_t(int8_t(str[i]));h = h * 16777619;}return h;
}

整个过程，hash是辅助手段，保证同样的内容得到同样的hash值，而words和ngrams的id分割则是后续矩阵运算的关键。