编辑距离：是指两个字串之间，由一个转成另一个所需的最少编辑操作次数；俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念；编辑距离越小的两个字符串越相似，当编辑距离为0时，两字符串相等。
距离：两个子串之间的“差异”叫做距离。
海明距离：相同位相同值的个数。
Hash函数：就是把任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。
这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。
简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
Simhash算法：分为5个步骤：分词（带权重w）、hash（得hash值）、加权（hash值*w）、合并（多关键词）、降维（海明距离）。
算法伪代码：
1，将一个f维的向量V初始化为0；f位的二进制数S初始化为0；
2，对每一个特征：用传统的hash算法对该特征产生一个f位的签名b。
对i=1到f：
如果b的第i位为1，则V的第i个元素加上该特征的权重；
否则，V的第i个元素减去该特征的权重。
3，如果V的第i个元素大于0，则S的第i位为1，否则为0；
4，输出S作为签名。
通配符：一种特殊语句，主要有星号(*)和问号(?)，用来模糊搜索文件。
当查找文件夹时，可以使用它来代替一个或多个真正字符；当不知道真正字符或者懒得输入完整名字时，常常使用通配符代替一个或多个真正的字符。
TF词频（Term Frequency）：是指某一个给定的词语在该文件中出现的次数。
一种统计方法，
用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。
字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。
这个数字通常会被正规化，以防止它偏向长的文件。
（同一个词语在长文件里可能会比短文件有更高的词频，而不管该词语重要与否。
）对于在某一特定文件里的词语 i t 来说，它的重要性可表示为：∑=k j k j
i j i n n tf ,,,。
以上式子中 j i n ,是该词在文件j d 中的出现次数，而分母则是在文件j d 中所有字词的出现次数之和。
逆文档频率（IDF ）：文档频率的倒数。
主要用在TF-IDF 中。
是一个词语普遍重要性的度量。
某一特定词语的IDF ，可以由总文件数目除以包含该词语之文件的数目，再将得到的商
TF-IDF ：（TF*IDF ）即i j i j i i idf tf df tf ⋅=,,。
某一特定文件内的高词语频率，以及该词语在整个文件集合中的低文件频率，可以产生出高权重的TF-IDF 。
因此，TF-IDF 倾向于过滤掉常见的词语，保留重要的词语。
Bloom Filter ：是由 Howard Bloom 在 1970 年提出的二进制向量数据结构，它具有很好的空间和时间效率，被用来检测一个元素是不是集合中的一个成员。
采用哈希函数的方法，将一个元素映射到一个 m 长度的阵列上的一个点，当这个点是 1 时，那么这个元素在集合内，反之则不在集合内。
这个方法的缺点就是当检测的元素很多的时候可能有冲突，解决方法就是使用 k 个哈希 函数对应 k 个点，如果所有点都是 1 的话，那么元素在集合内，如果有 0 的话，元素则不在集合内。
欧几里得距离：n 维空间中两点的实际距离。
局部敏感散列（Local-Sensitive Hash ， LSH ）:
K 最近邻(k-Nearest Neighbor ，KNN)分类算法：是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。
该方法的思路是：如果一个样本在特征空间中的k 个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。
K 通常是不大于20的整数。
算法的描述为：
1）计算测试数据与各个训练数据之间的距离；
2）按照距离的递增关系进行排序；
3）选取距离最小的K 个点；
4）确定前K个点所在类别的出现频率；
5）返回前K个点中出现频率最高的类别作为测试数据的预测分类。
N-Gram（也称为N元模型）：区别于编辑距离的一种表达关键词间“差异”的方法。
是自然语言处理中一个非常重要的概念。
假设有一个字符串，那么该字符串的N-Gram就表示按长度N切分原词得到的词段，也就是所有长度为N的子字符串。
引用lucene的JAR包调用函数相关函数可以实现非重复N-Gram：
import org.apache.lucene.search.spell.*;
public class NGram_distance {
public static void main(String[] args) {
NGramDistance ng = new NGramDistance();
float score1 = ng.getDistance("Gorbachev", "Gorbechyov");
System.out.println(score1);
float score2 = ng.getDistance("girl", "girlfriend"); System.out.println(score2);
}
}
和我们预期的一样，字符串Gorbachev和Gorbechyov所得之距离评分较高（=0.7），说明二者很接近；而girl和girlfriend所得之距离评分并不高（=0.3999），说明二者并不很接近。
