N-Gram 模型的假设

N-Gram 模型基于这样一种假设,第n个词的出现只与前面n-1个词相关,而与其它任何词都不相关,整句的概率就是各个词出现概率的乘积。在拼写检查里即是一个字母的出现概率只和前n-1个字母的出现概率相关,并且是前n-1个字母出现概率的乘积。

20世纪70年代之前,科学家们试图推断这个文字序列是否合乎文法、含义是否正确等。但这条路走不动。贾里尼克从另外一个角度来看待这个问题。用一个简单的统计语言模型非常美丽的搞定了它。贾里尼克的出发点非常easy:一个句子是否合理。就看看它的可能性大小怎样。至于可能性就用概率来衡量。第一个句子出现的概率最大,因此。第一个句子最有可能句子结构合理。这种方法更普通而严格的描写叙述是: 假定S表示某一个有意义的句子,由一连串特定顺序排列的词w1,w2,w3,…,wn组成。这里n是句子的长度。如今,我想知道S在文本中(语料库)出现的可能性,也就是数学上所说的S的概率P(S)。我们须要一个模型来估算概率。既然S=w1,w2,w3,…,wn。那么最好还是把P(S)展开表示: P(S)=P(w1,w2,w3,…,wn)

利用条件概率的公式。S这个序列出现的概率等于每个词出现的条件概率相乘,于是P(w1,…,wn)展开为:、
P(S)=P(W1,W2,W3,…,Wn)=P(W1)P(W2|W1)P(W3|W1,W2)…P(Wn|W1,W2,…,Wn-1)
当中P(w1)表示第一个词w1出现的概率;P(w2|w1)是已知第一个词的前提下。第二个词出现的概率;以此类推,词wn出现的概率取决于它前面全部的词。
可是这样的方法存在两个致命的缺陷:一个缺陷是參数空间过大(条件概率P(wn|w1,w2,…,wn-1)的可能性太多,无法估算),不可能有用处。另外一个缺陷是数据稀疏严重。
数据稀疏的解释:如果词表中有20000个词,如果是bigram model(二元模型)那么可能的2-gram就有400000000个,如果是trigram(3元模型),那么可能的3-gram就有8000000000000个!那么对于当中的非常多词对的组合,在语料库中都没有出现,依据最大似然估计得到的概率将会是0。这会造成非常大的麻烦,在算句子的概率时一旦当中的某项为0。那么整个句子的概率就会为0,最后的结果是,我们的模型仅仅能算可怜兮兮的几个句子,而大部分的句子算得的概率是0. 因此,我们要进行数据平滑(data Smoothing),数据平滑的目的有两个:一个是使全部的N-gram概率之和为1,使全部的N-gram概率都不为0,有关数据平滑处理的方法能够參考《数学之美》第33页的内容。

动态规划算法解决查找最长回文问题

class Solution {
public:
string longestPalindrome(string s) {
//BOTTOM-TOP 动态规划实现查找最长回文串
//初始化备忘矩阵
const int sz = s.size();
bool**q = new bool*[sz];
for (int i = 0; i < sz; ++i){
q[i] = new bool[sz];
for (int j = 0; j < sz; ++j){
q[i][j] = false;
}
}
//开始自底部向顶部动态规划
//首先初始化回文串起始终止位置
int pstart = -1, pend = pstart;
for (int i = sz – 1; i >= 0; –i){
for (int j = i; j < sz; ++j){
//如果子串的首尾字符相同,并且其距离不大于2或者首尾之间的子子串在备忘中是true的,
//该字串肯定是一个回文
//cout << i << “->” << j<<“|”;
if (s[i] == s[j] && (j – i <= 2 || q[i+1][j-1])==true){
q[i][j] = true;
if ((j – i+1)>(pend – pstart)) {
pstart = i;
pend = j;
//cout << i << “->” << j << endl;
}
}
}//end for

}//enf for
delete[] q;
return s.substr(pstart, pend – pstart + 1);
}

};

八皇后问题的递归解决(低效)

#include <iostream>
/**
*@author c0rpse
*@date 2015/9/22 23:14
*@usage A way to resolve the EightQueen Problem.
*/

using namespace std;
unsigned int cnt = 0;
int isSafe(int row, int col, int(*chess)[8]){
int i = 0, j;
//判断列方向有没有危险点
for (i = 0; i<8; ++i){
if (*(*(chess + i) + col) != 0){
//flag+col=1;
//break;
return 0;
}
}
//判断该坐标左上方有没有危险
for (i = row, j = col; i >= 0 && j >= 0; –i, –j){
if (*(*(chess + i) + j) != 0) return 0;
}
//判断该坐标右下方有没有危险
for (i = row, j = col; i<8 && j<8; ++i, ++j){
if (*(*(chess + i) + j) != 0) return 0;
}
//判断该坐标右上方有没有危险
for (i = row, j = col; i >= 0 && j<8; –i, ++j){
if (*(*(chess + i) + j) != 0) return 0;
}
//判断该坐标左下方有没有危险
for (i = row, j = col; i<8 && j >= 0; ++i, –j){
if (*(*(chess + i) + j) != 0) return 0;
}
return 1;
}
void eightQueen(int row, int col, int(*chess)[8]){

int i, j, chess2[8][8];//chess2为新棋盘,其复制了传入的chess棋盘
for (i = 0; i<8; ++i){
for (j = 0; j<8; ++j){
chess2[i][j] = chess[i][j];
}
}
if (row == 8){
//如果已经到达棋盘最后,那么输出棋盘
cout << “第” << cnt + 1 << “种摆法步骤” << endl;
for (i = 0; i<8; ++i){
for (j = 0; j<8; ++j){
cout << *(*(chess2 + i) + j) << ” “;
}
cout << endl;
}
cout << endl;
++cnt;
}
else {
for (j = 0; j<col; ++j){//对该行的每一列进行尝试
if (isSafe(row, j, chess)){
//在尝试前首先重置该行所有坐标为0,因为上次循环可能会改变该行坐标的值
for (i = 0; i<8; ++i){
*(*(chess2 + row) + i) = 0;
}
*(*(chess2 + row) + j) = 1;
eightQueen(row + 1, col, chess2);//递归测试下一行
}
}
}
}
int main()
{
int i, j, chess[8][8];
for (i = 0; i<8; ++i){
for (j = 0; j<8; ++j){
chess[i][j] = 0;
}
}
eightQueen(0, 8, chess);
return 0;
}

汉诺塔的递归解决

一位法国数学家曾编写过一个印度的古老传说:在世界中心贝拿勒斯的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。

不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。

僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。

继续阅读“汉诺塔的递归解决”

编辑距离算法 的Java实现

编辑距离是指通过添加删除或更改字符这三种操作,由一个字符串转到另一个字符串所需的最少次数。

俄国科学家Liechtenstein在1956年首次提出了这个概念.

对于编辑距离的实现,可以通过下述方式进行计算:

假设有字符串a,b,计算由a至b的编辑距离ed(a,b),此处设定La,Lb分别表示a,b字符串的长度

<1>La==0||Lb==0  –> ed(a,b)=La+Lb

<2>如果La,Lb都不等于0,那么 ed(a,b)=min{ed(a-1,b)+1, ed(a,b-1)+1,ed(a-1,b-1)+b(a,b)}     b(a,b)=1 if a的最后一个字符等于b的最后一个字符,否则b(a,b)=0

————————Code——————————-

package Levenshtein;

/**

* @author c0rpse * 编辑距离算法的实现 *

*/

 public class Levenshtein {

public static void main(String[] args){

 String a = "abc",b = "def";

System.out.println(levenshtein(a,b));

}

public static int levenshtein(String x,String y){

 int xl = x.length(),yl=y.length();

if(xl==0||yl==0) return yl+xl;

String x_1=xl-1&gt;0?x.substring(0, xl-1):"";

 String y_1=yl-1&gt;0?y.substring(0, yl-1):"";

int x__1=levenshtein(x_1,y)+1;

int y__1=levenshtein(y_1,x)+1;

 int x_y=levenshtein(x_1,y_1)+(x.substring(xl-1).equals(y.substring(yl-1))?0:1);

 return min(min(x__1,y__1),x_y);

}

public static int min(int x,int y)
{

return x&lt;y?x:y;

}

}

Python实现快速排序算法

#-*-encoding:utf-8-*-
import sys,random,time
reload(sys)
sys.setdefaultencoding('utf8')
def singleSort(list,start,end):
    if start>=end:
        return -1
    pivotPos = start
    pivot = list[pivotPos]
    low = start
    high = end
    while low<high:
        while list[high]>=pivot and low<high:
            high = high-1
        if low>=high: 
            return pivotPos
        exchange(list,pivotPos,high)
        pivotPos=high
        while list[low]<=pivot and low<high:
            low = low+1
        if low>=high: 
            return pivotPos
        exchange(list,pivotPos,low)
        pivotPos=low
def exchange(list,pos1,pos2):
    temp = list[pos1]
    list[pos1] = list[pos2]
    list[pos2] = temp
def qsort(list,low,high):
    pivotpos = singleSort(list,low,high)
    if pivotpos<0:
        return
    qsort(list,low,pivotpos-1)
    qsort(list,pivotpos+1,high)
def generateRandList(num):
    list=[]
    random.seed()
    for x in range(num):
        list.append(random.randint(0,65535))
    return list
if __name__ == '__main__':
     list = generateRandList(10000)
     #list=[4,8,2,3,7,9]
    qsort(list,0,len(list)-1)
    print list