我们知道，在这个ugc的年代里，网络上各种各样支持文本输出的地方（比如：无意义的微博及评论、利用随机生成器注册id等等），经常出现一些无意义的乱语（英文叫：gibberish），比如“asdfqwer”。如何去识别它，是一个有意思的主题。

直觉跳出最简单的一种方式是，收集一本较全的英文字典，然后过滤一次，看看目标是否落在字典中。这是一种方式。准确率会有大幅提升，但是肯定还是会有一些case是难以解决的，比如：两个有意义的词刚好连在一起，却不在字典中。

另外我们再进一步思考一下，是否有什么算法进行训练，进而识别直接识别是否是乱语呢？可以考虑使用markov链模型。

对于一句话或短语来说：“hello buddy”，每个字母都与上下两个字母有关，这种关系可以通过2-gram来表示。比如：he, el, ll, lo, o[space], [space]b, …。

我们可以建立这样一个状态转移矩阵：

在一个语料库， 我们会统计这些2-gram的频数，并将它们进行归一化。这样每个字母后的下一个字母出现都有一个概率分布（26个字母加空格）。

对于字母a，它的下一个输入为b的组成的2-gram的状态转换概率为：

为什么不是直接概率，而要使用log呢？

• 由于字典很大，但一些词的出现概率会过小，计算机下溢(undeflow problem)将它们当成0来处理。
• 我们最后要求的是整个“hello buddy”的概率，即：p = prob(he) * prob(el) * prob(ll) * … prob(dy)的概率，这在英文2gram的语言模型，而使用log可以利用log的性质：log(ab)=log(a)+log(b)
• 最后，再通过e转换回正常概率即可.

如何判断是否是乱语？

我们可以收集一些乱语（bad），还有一些比较好的短语或语汇(good)。然后分别统计出对应bad以及good的平均转移概率。

平均转移概率=概率/转移次数

阀值的选取？

一般来说，good的平均转移概率，要比bad的大。可以选择平均：

thresh = (min(good_probs)+max(bad_probs))/2

• 大于thresh，认为是good。
• 小于等于thresh，认为是bad。

ok，利用这个模型，就可以识别字典之外的乱语了。如果你的训练语料很标准的话，那么相应的效果就会好很多。

参考：

• why log
• 相应的算法

word2vec的源码中，自带着另一个工具word2phrase，之前一直没有关注，可以用来发现短语. 代码写的很精练，不到300行，那么我们可以看一下，这不到300行的代码是如何实现短语发现的。

一、参数

• train: 训练文件（已经分好词的文件）
• debug: 是否开启调试模式 (debug=2，在训练时会有更多的输出信息)
• output: 输出文件
• min-count: 最小支持度，小于该值的词将不会被采用，缺省为5
• threshold: 超过该得分，才形成短语，该值越高，形成的短语也会越少。(default:100)

二、词汇表

struct vocab_word {
    long long cn;    //
    char *word;    //
};

每个词汇由vacab_word构成，由这些词汇形成一个大的词汇表：vacab_hash。（最大条目：500M个）

三、模型训练 TrainModel（）

内部原理很简单：是一个分词后2-gram的模型，统计出现频次. 本质是利用互信息(mi)计算内聚程度。（内部做了一些内存优化＝>牺牲了一点点准确性，如果想更准，不如自己写map-reduce或spark）

公式为：

score = (pab - min_count) / (real)pa / (real)pb * (real)train_words;

可以简化为：

互信息只是简单的多个log2而已.

如果你有做过新词发现等经验，就知道这并不是一个比较优的方法，目前流行的做法是：互信息＋min(左右邻字信息熵). 这里的字换成词即是短语发现.

Wang/Jenkins Hash算法在网上提到的也甚多，但是很少有人或有文章能系统地能将该算法的来龙去脉说明白。于是，我就充当了该苦工，幸好还是找到了一些东西，尝试着将该算法简单道来。

最早，Bob Jenkins提出了多个基于字符串通用Hash算法（搜Jenkins Hash就知道了），而Thomas Wang在Jenkins的基础上，针对固定整数输入做了相应的Hash算法。因而，其名字也就成了Wang/Jenkins Hash，其64位版本的 Hash算法如下：

uint64_t hash(uint64_t key) {
    key = (~key) + (key << 21); // key = (key << 21) - key - 1;
    key = key ^ (key >> 24);
    key = (key + (key << 3)) + (key << 8); // key * 265
    key = key ^ (key >> 14);
    key = (key + (key << 2)) + (key << 4); // key * 21
    key = key ^ (key >> 28);
    key = key + (key << 31);
    return key;
}

其关键特性是：

• 1.雪崩性（更改输入参数的任何一位，就将引起输出有一半以上的位发生变化）
• 2.可逆性（input ==> hash ==> inverse_hash ==> input）

其逆Hash函数为：

uint64_t inverse_hash(uint64_t key) {
    uint64_t tmp;

    // Invert key = key + (key << 31)
    tmp = key-(key<<31);
    key = key-(tmp<<31);

    // Invert key = key ^ (key >> 28)
    tmp = key^key>>28;
    key = key^tmp>>28;

    // Invert key *= 21
    key *= 14933078535860113213u;

    // Invert key = key ^ (key >> 14)
    tmp = key^key>>14;
    tmp = key^tmp>>14;
    tmp = key^tmp>>14;
    key = key^tmp>>14;

    // Invert key *= 265
    key *= 15244667743933553977u;

    // Invert key = key ^ (key >> 24)
    tmp = key^key>>24;
    key = key^tmp>>24;

    // Invert key = (~key) + (key << 21)
    tmp = ~key;
    tmp = ~(key-(tmp<<21));
    tmp = ~(key-(tmp<<21));
    key = ~(key-(tmp<<21));

    return key;
}

由上述的算法实现可知，原始的hash算法过程是非常快的，而其逆Hash算法则比较慢一些。

参考：

• 1.jenkins 32位Hash算法
• 2.Geoffrey Irving’s blog