一、最小编辑距离
编辑距离（Minimum Edit Distance，MED），又称Levenshtein距离，是指两个字符串之间，由一个转成另一个所需要的最少编辑操作次数。允许的编辑操作包括：将一个字符替换成另一个字符（substitution，s），插入一个字符（insert，i）或者删除一个字符（delete，d），最终求得D(n,m)即为字符串X[0...n]与Y[0...m]之间的最小编辑距离。
应用
最小编辑距离通常作为一种相似度计算函数被用于多种实际应用中，详细如下： （特别的，对于中文自然语言处理，一般以词为基本处理单元）
拼写纠错（Spell Correction）：又拼写检查（Spell Checker），将每个词与词典中的词条比较，英文单词往往需要做词干提取等规范化处理，如果一个词在词典中不存在，就被认为是一个错误，然后试图提示N个最可能要输入的词——拼写建议。常用的提示单词的算法就是列出词典中与原词具有最小编辑距离的词条。
这里肯定有人有疑问：对每个不在词典中的词（假如长度为len）都与词典中的词条计算最小编辑距离，时间复杂度是不是太高了？的确，所以一般需要加一些剪枝策略。
DNA分析：基因学的一个主要主题就是比较 DNA 序列并尝试找出两个序列的公共部分。如果两个 DNA 序列有类似的公共子序列，那么这些两个序列很可能是同源的。在比对两个序列时，不仅要考虑完全匹配的字符，还要考虑一个序列中的空格或间隙（或者，相反地，要考虑另一个序列中的插入部分）和不匹配，这两个方面都可能意味着突变（mutation）。在序列比对中，需要找到最优的比对（最优比对大致是指要将匹配的数量最大化，将空格和不匹配的数量最小化）。如果要更正式些，可以确定一个分数，为匹配的字符添加分数、为空格和不匹配的字符减去分数。
命名实体抽取（Named Entity Extraction）：由于实体的命名往往没有规律，如品牌名，且可能存在多种变形、拼写形式，如“IBM”和“IBM Inc.”，这样导致基于词典完全匹配的命名实体识别方法召回率较低，为此，我们可以使用编辑距离由完全匹配泛化到模糊匹配，先抽取实体名候选词。
实体共指（Entity Coreference）：通过计算任意两个实体名之间的最小编辑距离判定是否存在共指关系？如“IBM”和“IBM Inc.”, "Stanford President John Hennessy "和"Stanford University President John Hennessy"。
机器翻译（Machine Translation）：1）识别平行网页对：由于平行网页通常有相同或类似的界面结构，因此平行网页在HTML结构上应该有很大近似度。首先将网页的HTML标签抽取出来，连接成一个字符串，然后用最小编辑距离考察两个字符串的近似度。实际中，此策略一般与文档长度比例、句对齐翻译模型等方法结合使用，以识别最终的平行网页对。 2）自动评测：首先存储机器翻译原文和不同质量级别的多个参考译文，评测时把自动翻译的译文对应到与其编辑距离最小的参考译文上，间接估算自动译文的质量。
二、语言模型
1）N-gram介绍
在实际应用中，我们经常需要解决这样一类问题：如何计算一个句子的概率？如：
机器翻译：P(high winds tonite) > P(**large **winds tonite)
拼写纠错：P(about fifteen **minutes **from) > P(about fifteen minuets from)
语音识别：P(I saw a van) >> P(eyes awe of an)
音字转换：P(你现在干什么|nixianzaiganshenme) > P(你西安在干什么|nixianzaiganshenme)
自动文摘****、问答系统、... ...
以上问题的形式化表示如下：
p(S)=p(w1,w2,w3,w4,w5,…,wn)
=p(w1)p(w2|w1)p(w3|w1,w2)...p(wn|w1,w2,...,wn-1)//链规则
p(S)被称为语言模型，即用来计算一个句子概率的模型。
那么，如何计算p(wi|w1,w2,...,wi-1)呢？最简单、直接的方法是直接计数做除法，如下：
p(wi|w1,w2,...,wi-1) = p(w1,w2,...,wi-1,wi) / p(w1,w2,...,wi-1)
但是，这里面临两个重要的问题：数据稀疏严重；参数空间过大，无法实用。
基于马尔科夫假设（Markov Assumption）：下一个词的出现仅依赖于它前面的一个或几个词。
假设下一个词的出现依赖它前面的一个词，则有：
p(S)=p(w1)p(w2|w1)p(w3|w1,w2)...p(wn|w1,w2,...,wn-1)
=p(w1)p(w2|w1)p(w3|w2)...p(wn|wn-1) // bigram
假设下一个词的出现依赖它前面的两个词，则有：
p(S)=p(w1)p(w2|w1)p(w3|w1,w2)...p(wn|w1,w2,...,wn-1)
=p(w1)p(w2|w1)p(w3|w1,w2)...p(wn|wn-1,wn-2) // trigram
那么，我们在面临实际问题时，如何选择依赖词的个数，即n。
更大的n：对下一个词出现的约束信息更多，具有更大的辨别力；
更小的n：在训练语料库中出现的次数更多，具有更可靠的统计信息，具有更高的可靠性。
理论上，n越大越好，经验上，trigram用的最多，尽管如此，原则上，能用bigram解决，绝不使用trigram。
2）构造语言模型
通常，通过计算最大似然估计（Maximum Likelihood Estimate）构造语言模型，这是对训练数据的最佳估计，公式如下：
p(w1|wi-1) = count(wi1-, wi) / count(wi-1)
如给定句子集
<s> I am Sam </s>
<s> Sam I am </s>
<s> I do not like green eggs and ham </s>
部分bigram语言模型如下所示：
c(wi)如下:
c(wi-1,wi)如下:
则bigram为：
那么，句子“<s> I want english food </s>”的概率为：
p(<s> I want english food </s>)=p(I|<s>)
× P(want|I)
× P(english|want)
× P(food|english)
× P(</s>|food)
= .000031
为了避免数据溢出、提高性能，通常会使用取log后使用加法运算替代乘法运算。
log(p1p2p3*p4) = log(p1) + log(p2) + log(p3) + log(p4)
推荐开源语言模型工具：
SRILM（http://www.speech.sri.com/projects/srilm/）
IRSTLM（http://hlt.fbk.eu/en/irstlm）
MITLM（http://code.google.com/p/mitlm/）
BerkeleyLM（http://code.google.com/p/berkeleylm/）
推荐开源n-gram数据集：
Google Web1T5-gram（http://googleresearch.blogspot.com/2006/08/all-our-n-gram-are-belong-to-you.html）
Total number of tokens: 1,306,807,412,486
Total number of sentences: 150,727,365,731
Total number of unigrams: 95,998,281
Total number of bigrams: 646,439,858
Total number of trigrams: 1,312,972,925
Total number of fourgrams: 1,396,154,236
Total number of fivegrams: 1,149,361,413
Total number of n-grams: 4,600,926,713
Google Book N-grams（http://books.google.com/ngrams/）
Chinese Web 5-gram（http://www.ldc.upenn.edu/Catalog/catalogEntry.jsp?catalogId=LDC2010T06）
三、拼写纠错
1）任务定义
拼写纠错（Spelling Correction），又称拼写检查（Spelling Checker），往往被用于字处理软件、输入法和搜索引擎中
拼写纠错一般可以拆分成两个子任务：
Spelling Error Detection：按照错误类型不同，分为Non-word Errors和Real-word Errors。前者指那些拼写错误后的词本身就不合法，如错误的将“giraffe”写成“graffe”；后者指那些拼写错误后的词仍然是合法的情况，如将“there”错误拼写为“three”（形近），将“peace”错误拼写为“piece”（同音），将“two”错误拼写为“too”（同音）。
Spelling Error Correction：自动纠错，如把“hte”自动校正为“the”，或者给出一个最可能的拼写建议，甚至一个拼写建议列表。
2）Non-word拼写错误
Spelling error detection：任何不被词典所包含的word均被当作spelling error，识别准确率依赖词典的规模和质量。
Spelling error correction：查找词典中与error最近似的word，常见的方法有Shortest weighted edit distance和Highest noisy channel probability。
3）Real-word拼写错误
Spelling error detection：每个word都作为spelling error candidate。
Spelling error correction：从发音和拼写等角度，查找与word最近似的words集合作为拼写建议，常见的方法有Highest noisy channel probability和Classifier。
4）基于Noisy Channel Model的拼写纠错
Noisy Channel Model即噪声信道模型，或称信源信道模型，这是一个普适性的模型，被用于语音识别、拼写纠错、机器翻译、中文分词、词性标注、音字转换等众多应用领域。
5）Real-word拼写纠错
Kukich（1992）指出有25%~40%的拼写错误都属于Real-word类型，与Non-word类型相比，纠错难度更大，因为句子中的每个word都被当作待纠错对象。
