马尔可夫链算法

引言：

　　我们现在准备做的就是给定一个由不同的单词组成的句子，由这个句子产生一些随机的可以读的英语文本。

马尔可夫链可以比较好的完成这个任务！

描述：

　　该算法把每个短语分割为两个部分：一部分是由多个词构成的前缀，另一部分是只包含一个词的后缀。马尔可夫链算法能够

生成输出短语的序列，其方法是依据 原文本的统计性质，随机性地选择跟在前缀后面的特定后缀。采用三个词的短语就能够工作

得很好——利用连续两个词构成的前缀来选择作为后缀的一个词：

　　设置w1和w2为文本的前两个词

　　输出w1和w2

　　循环：

　　　　随机地选出w3，它是文本中w1w2的后缀中的一个

　　　　打印w3

　　　　把w1和w2分别换成w2和w3

　　重复循环

马尔可夫的数据结构简单一点说就是：以NPREF个单词做为前缀，前缀可以用一个大小为NPREF的一维数组表示（键），

后缀可以用一个链表或者一个动态数组表示（值），看起来就像是一个映射，

用C++的语法表示可以是：

map<vector<string> key[NPREF],vector<string> value>

图示：



如果用纯C来设计数据结构的话，看起来像是这样：



数据结构部分代码：

 
typedef struct State State; typedef struct Suffix Suffix; struct State { char
*pref[NPREF]; Suffix *suf; State *next; }; struct Suffix { char *word; Suffix
*next; }; State *statetab[NHASH];
那么生成前缀后缀的算法应该是这样:

循环

       在哈希表中查找到前缀的位置(指针)，这一步需要用到hash函数，并返回指针.

       用返回的State指针的suf指针指向后缀.

       前缀向前移动一位,并将suf指针填充末位,循环第1步.

重复循环

 
#include <string> #include <time.h> #include <iostream> using namespace std;
const int MULTIPLIER = 1 << 5; //自定义一个数值 enum { NPREF = 2, NHASH = 4093, MAXGEN
= 10000 }; enum { BUFSIZE = 0 }; typedef struct State State; typedef struct
Suffix Suffix; struct State { char *pref[NPREF]; Suffix *suf; State *next; };
struct Suffix { char *word; Suffix *next; }; State *statetab[NHASH]; unsigned
int hash(char *s[NPREF]) //哈希函数:将前缀散列到哈希表某一位置 { unsigned int h = 0; unsigned
char *p = NULL; for (int i=0; i < NPREF; ++i) for (p=(unsigned char*)s[i]; *p
!= '\0'; ++p) h = MULTIPLIER *h + *p; return h % NHASH; } State* lookup(char
*prefix[NPREF],int create)//查找前缀数组prefix[NPREF]是否在哈希表中出现，如果未出现，就插入 { int i,h;
State *sp; h = hash(prefix); for (sp = statetab[h]; sp != NULL; sp = sp->next)
{ for (i=0; i < NPREF; ++i) { if (strcmp(prefix[i],sp->pref[i])) break; } if (i
== NPREF) //找到就返回 return sp; } if (create) { sp = new State; for (i = 0; i <
NPREF; ++i) { sp->pref[i] = prefix[i]; } sp->suf = NULL; sp->next =
statetab[h]; //头插法 statetab[h] = sp; } return sp; } void addsuffix(State
*sp,char *suffix)//在后缀链表中插入一个结点 { Suffix *suf = new Suffix; suf->word = suffix;
suf->next = sp->suf; sp->suf = suf; } void add(char *prefix[NPREF], char
*suffix)//往数据结构中插入一个项 { State *sp = NULL; sp = lookup(prefix,1);
addsuffix(sp,suffix); memmove(prefix,prefix+1,(NPREF-1)*sizeof(prefix[0]));
prefix[NPREF-1] = suffix; } void build(char * prefix[NPREF], FILE *f) { char
buf[100], fmt[10]; sprintf(fmt,"%%%ds",sizeof(buf)-1); //这个调用很奇妙! while
(fscanf(f,fmt,buf)!=EOF) add(prefix,strdup(buf)); } void generate(int nwords) {
State *sp; Suffix * suf; char *prefix[NPREF], *w; int i,nmatch; for (i = 0; i <
NPREF; ++i) prefix[i] = "\0"; for (i = 0; i < nwords; ++i) { sp =
lookup(prefix,0); nmatch = 0; for (suf = sp->suf; suf != NULL; suf = suf->next)
if (rand() % ++nmatch == 0) w = suf->word; if (strcmp(w,"\0")==0) break;
printf("%s\n",w); memmove(prefix,prefix+1,(NPREF-1)*sizeof(Suffix));
prefix[NPREF-1] = w; } } int main() { #ifndef ONLINE_JUDGE
freopen("2.txt","r",stdin); #endif int i,nwords = MAXGEN; char *prefix[NPREF];
srand((unsigned int)time(0)); //随机种子 for (i=0; i < NPREF; ++i) prefix[i] =
"\0"; build(prefix,stdin); add(prefix,"\0"); generate(nwords); return 0; }
上面的代码可以增长不少见识：

1.函数原型：void *memmove(void *dest, const void *source, size_t count)

  返回值说明：返回指向dest的void *指针

  参数说明：dest,source分别为目标串和源串的首地址。count为要移动的字符的个数

  函数说明：memmove用于从source拷贝count个字符到dest，如果目标区域和源区域有重叠的话，memmove能够保证源串在被覆盖

  之前将重叠区域的字节拷贝到目标区域中。

2.

 
void build(char * prefix[NPREF], FILE *f) { char buf[100], fmt[10];
sprintf(fmt,"%%%ds",sizeof(buf)-1); //这个调用很奇妙! while (fscanf(f,fmt,buf)!=EOF)
add(prefix,strdup(buf)); }
这一段

 

定义函数：int sprintf(char *str, const char * format, ...);

函数说明：sprintf()会根据参数format 字符串来转换并格式化数据, 然后将结果复制到参数str 所指的字符串数组,

 直到出现字符串结束('\0')为止

sprintf函数和我们常见的printf函数十分类似，只不过printf打印到标准输出流，而sprintf打印到字符串中。


sprintf(fmt,"%%%ds",sizeof(buf)-1)等价于sprintf(fmt,"%%%ds",99)，则运行后,fmt的结果为"%99s",所以下一句实质上为：

while (fscanf(f,"%99s",buf)!=EOF)，就很好理解了，意思为从文件中至多读99个字符到buf中。

3.strdup()复制给定字符串的一个副本。

C++ STL版本的实现（结构紧凑，思路清晰，效率比C低不少）

 
#include <map> #include <queue> #include <time.h> #include <vector> #include
<string> #include <iostream> using namespace std;
map<deque<string>,vector<string> > statetab; void add(deque<string>&
prefix,const string& s) { if (prefix.size() == 2) {
statetab[prefix].push_back(s); //增加后缀 prefix.pop_front(); //删除队列头 }
prefix.push_back(s); //入队，构成新的prefix } void build(deque<string>&
prefix,istream& in) { string buf; while (in >> buf) add(prefix,buf); } void
generate(int nwords) { deque<string> prefix; int i; for (i=0; i < 2; ++i)
add(prefix,"\0"); for (i=0; i < nwords; ++i) { vector<string>& suf =
statetab[prefix]; const string& w = suf[rand() % suf.size()]; if (w=="\0")
break; cout << w << ' '; prefix.pop_front(); prefix.push_back(w); } } int
main() { #ifndef ONLINE_JUDGE freopen("2.txt","r",stdin); #endif
srand(time(0)); int nwords = 10000; deque<string> prefix; for (int i = 0; i <
2; ++i) add(prefix,"\0"); build(prefix,cin); add(prefix,"\0");
generate(nwords); return 0; }
 

• « 上一篇：HashMap的算法解析及高并发下死循环分析
• » 下一篇：从头学习爬虫（三十一）实战篇----动漫之家漫画（Java实现）