马尔可夫链算法(markov算法)的awk、C++、C语言实现代码_C 语言

1. 问题描述

马尔可夫链算法用于生成一段随机的英文,其思想非常简单。首先读入数据,然后将读入的数据分成前缀和后缀两部分,通过前缀来随机获取后缀,籍此产生一段可读的随机英文。

为了说明方便,假设我们有如下一段话:
 

复制代码 代码如下:

   Show your flowcharts and conceal your tables and I will be mystified. Show your tables and your flowcharts will be obvious.
 

假设前缀的长度为2,则我们处理输入以后得到如下数据,我们首先获取一个前缀,然后在前缀的后缀列表中随机选择一个单词,然后改变前缀,重复上述过程,这样,我们产生的句子将是可读的。

下面是处理过的数据:

复制代码 代码如下:

前缀  后缀
show your  flowcharts tables
your flowcharts  and will
flowcharts and  conceal
flowcharts will  be
your tables  and and
will be  mystified. obvious.
be mystified.  show
be obvious.  (end)

处理这个文本的马尔可夫链算法将首先带引show your,然后随机取出flowcharts 或者table 两个单词,假设选择的是flowcharts, 则新的前缀就是your flowcharts,同理,选择table 时,新的前缀就是your table,有了新的前缀your flowcharts 以后,再次随即选择它的后缀,这次是在and 和 will 中随机选择,重复上述过程,就能够产生一段可读的文本。具体描述如下:

复制代码 代码如下:

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

循环:
    随机地选出 w3,它是文本中 w1 w2 的后缀中的一个
    打印 w3
    把 w1 和 w2 分别换成 w2 和 w3
    重复循环

2.awk 程序

马尔可夫链算法并不难,我们会在后面看到,用c语言来解决这个问题会相当麻烦,而用awk则只需要5分钟就能搞定。这简直就是一个演示awk优点的问题。

awk 中有关联数组,正好可以用来表示前缀和后缀的关系。程序如下:

# markov.awk: markov chain algorithm for 2-word prefixes
BEGIN { MAXGEN = 10000; NONWORD = "\n"; w1 = w2 = NONWORD }

{  for (i = 1; i <= NF; i++) {   # read all words
    statetab[w1,w2,++nsuffix[w1,w2]] = $i
    w1 = w2
    w2 = $i
  }
}

END {
  statetab[w1,w2,++nsuffix[w1,w2]] = NONWORD # add tail
  w1 = w2 = NONWORD
  for (i = 0; i < MAXGEN; i++) { # generate
    r = int(rand()*nsuffix[w1,w2]) + 1 # nsuffix >= 1
    p = statetab[w1,w2,r]
    if (p == NONWORD)
      exit
    print p
    w1 = w2     # advance chain
    w2 = p
  }
}  

3. C++ 程序

该问题的主要难点就在于通过前缀随机的获取后缀,在C++ 中,我们可以借助map 来实现前缀和后缀的对应关系,以此得到较高的开发效率。

/* Copyright (C) 1999 Lucent Technologies */
/* Excerpted from 'The Practice of Programming' */
/* by Brian W. Kernighan and Rob Pike */

#include <time.h>
#include <iostream>
#include <string>
#include <deque>
#include <map>
#include <vector>

using namespace std;

const int NPREF = 2;
const char NONWORD[] = "\n";  // cannot appear as real line: we remove newlines
const int MAXGEN = 10000; // maximum words generated

typedef deque<string> Prefix;

map<Prefix, vector<string> > statetab; // prefix -> suffixes

void    build(Prefix&, istream&);
void    generate(int nwords);
void    add(Prefix&, const string&);

// markov main: markov-chain random text generation
int main(void)
{
  int nwords = MAXGEN;
  Prefix prefix; // current input prefix

  srand(time(NULL));
  for (int i = 0; i < NPREF; i++)
    add(prefix, NONWORD);
  build(prefix, cin);
  add(prefix, NONWORD);
  generate(nwords);
  return 0;
}

// build: read input words, build state table
void build(Prefix& prefix, istream& in)
{
  string buf;

  while (in >> buf)
    add(prefix, buf);
}

// add: add word to suffix deque, update prefix
void add(Prefix& prefix, const string& s)
{
  if (prefix.size() == NPREF) {
    statetab[prefix].push_back(s);
    prefix.pop_front();
  }
  prefix.push_back(s);
}

// generate: produce output, one word per line
void generate(int nwords)
{
  Prefix prefix;
  int i;

  for (i = 0; i < NPREF; i++)
    add(prefix, NONWORD);
  for (i = 0; i < nwords; i++) {
    vector<string>& suf = statetab[prefix];
    const string& w = suf[rand() % suf.size()];
    if (w == NONWORD)
      break;
    cout << w << "\n";
    prefix.pop_front(); // advance
    prefix.push_back(w);
  }
}

4. c 程序

如果需要程序运行得足够快,那就只能用较低级的语言来实现了。当我们用c 语言来实现时,就不得不考虑各种各样的问题了。首先,面临的第一个问题就是,如何表示前缀和后缀的关系?

这里采用前缀的key,后缀为value 的方式存储前缀与后缀的关系,我们知道,hash表的查找速度最快,所以,这里采用hash表也是情理之中的事,只是看你能不能想到,用前缀作key,基于上面的思路,再仔细一点,就没有什么大问题了。

/* Copyright (C) 1999 Lucent Technologies */
/* Excerpted from 'The Practice of Programming' */
/* by Brian W. Kernighan and Rob Pike */

/*
 * Markov chain random text generator.
 */

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "eprintf.h"

enum {
  NPREF  = 2,  /* number of prefix words */
  NHASH  = 4093, /* size of state hash table array */
  MAXGEN = 10000 /* maximum words generated */
};

typedef struct State State;
typedef struct Suffix Suffix;

struct State { /* prefix + suffix list */
  char  *pref[NPREF];  /* prefix words */
  Suffix *suf;      /* list of suffixes */
  State  *next;     /* next in hash table */
};

struct Suffix { /* list of suffixes */
  char  *word;     /* suffix */
  Suffix *next;     /* next in list of suffixes */
};

State  *lookup(char *prefix[], int create);
void  build(char *prefix[], FILE*);
void  generate(int nwords);
void  add(char *prefix[], char *word);

State  *statetab[NHASH];  /* hash table of states */

char NONWORD[] = "\n"; /* cannot appear as real word */

/* markov main: markov-chain random text generation */
int main(void)
{
  int i, nwords = MAXGEN;
  char *prefix[NPREF];    /* current input prefix */

  int c;
  long seed;

  setprogname("markov");
  seed = time(NULL);

  srand(seed);
  for (i = 0; i < NPREF; i++) /* set up initial prefix */
    prefix[i] = NONWORD;
  build(prefix, stdin);
  add(prefix, NONWORD);
  generate(nwords);
  return 0;
}  

const int MULTIPLIER = 31; /* for hash() */

/* hash: compute hash value for array of NPREF strings */
unsigned int hash(char *s[NPREF])
{
  unsigned int h;
  unsigned char *p;
  int i;

  h = 0;
  for (i = 0; i < NPREF; i++)
    for (p = (unsigned char *) s[i]; *p != '\0'; p++)
      h = MULTIPLIER * h + *p;
  return h % NHASH;
}

/* lookup: search for prefix; create if requested. */
/* returns pointer if present or created; NULL if not. */
/* creation doesn't strdup so strings mustn't change later. */
State* lookup(char *prefix[NPREF], int create)
{
  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]) != 0)
        break;
    if (i == NPREF)   /* found it */
      return sp;
  }
  if (create) {
    sp = (State *) emalloc(sizeof(State));
    for (i = 0; i < NPREF; i++)
      sp->pref[i] = prefix[i];
    sp->suf = NULL;
    sp->next = statetab[h];
    statetab[h] = sp;
  }
  return sp;
}

/* addsuffix: add to state. suffix must not change later */
void addsuffix(State *sp, char *suffix)
{
  Suffix *suf;

  suf = (Suffix *) emalloc(sizeof(Suffix));
  suf->word = suffix;
  suf->next = sp->suf;
  sp->suf = suf;
}

/* add: add word to suffix list, update prefix */
void add(char *prefix[NPREF], char *suffix)
{
  State *sp;

  sp = lookup(prefix, 1); /* create if not found */
  addsuffix(sp, suffix);
  /* move the words down the prefix */
  memmove(prefix, prefix+1, (NPREF-1)*sizeof(prefix[0]));
  prefix[NPREF-1] = suffix;
}

/* build: read input, build prefix table */
void build(char *prefix[NPREF], FILE *f)
{
  char buf[100], fmt[10];

  /* create a format string; %s could overflow buf */
  sprintf(fmt, "%%%ds", sizeof(buf)-1);
  while (fscanf(f, fmt, buf) != EOF)
    add(prefix, estrdup(buf));
}

/* generate: produce output, one word per line */
void generate(int nwords)
{
  State *sp;
  Suffix *suf;
  char *prefix[NPREF], *w;
  int i, nmatch;

  for (i = 0; i < NPREF; i++) /* reset initial prefix */
    prefix[i] = NONWORD;

  for (i = 0; i < nwords; i++) {
    sp = lookup(prefix, 0);
    if (sp == NULL)
      eprintf("internal error: lookup failed");
    nmatch = 0;
    for (suf = sp->suf; suf != NULL; suf = suf->next)
      if (rand() % ++nmatch == 0) /* prob = 1/nmatch */
        w = suf->word;
    if (nmatch == 0)
      eprintf("internal error: no suffix %d %s", i, prefix[0]);
    if (strcmp(w, NONWORD) == 0)
      break;
    printf("%s\n", w);
    memmove(prefix, prefix+1, (NPREF-1)*sizeof(prefix[0]));
    prefix[NPREF-1] = w;
  }
}

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索马尔可夫链算法
markov算法
马尔可夫链算法、awk算法、银行家算法c语言代码、算法精解 c语言描述、c语言算法,以便于您获取更多的相关知识。

时间: 2024-11-05 18:33:35

马尔可夫链算法(markov算法)的awk、C++、C语言实现代码_C 语言的相关文章

k均值算法c++语言实现代码_C 语言

复制代码 代码如下: //k-mean.h #ifndef KMEAN_HEAD #define KMEAN_HEAD  #include <vector> #include <map>  //空间点的定义 class Node {     public:        double pos_x;        double pos_y;        double pos_z;      Node()      {          pos_x = 0.0;          p

C语言 奇偶排序算法详解及实例代码_C 语言

C语言奇偶排序算法 奇偶排序,或奇偶换位排序,或砖排序,是一种相对简单的排序算法,最初发明用于有本地互连的并行计算.这是与冒泡排序特点类似的一种比较排序.该算法中,通过比较数组中相邻的(奇-偶)位置数字对,如果该奇偶对是错误的顺序(第一个大于第二个),则交换.下一步重复该操作,但针对所有的(偶-奇)位置数字对.如此交替进行下去. 使用奇偶排序法对一列随机数字进行排序的过程 处理器数组的排序 在并行计算排序中,每个处理器对应处理一个值,并仅有与左右邻居的本地互连.所有处理器可同时与邻居进行比较.交

希尔排序算法的C语言实现示例_C 语言

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本.希尔排序是非稳定排序算法. 希尔排序是基于插入排序的以下两点性质而提出改进方法的: 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位 希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能.这样可以让一个元素可以一次性地朝最终位置前进一大步.然后算法再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几

C语言二分查找算法及实现代码_C 语言

二分査找也称折半査找,其优点是查找速度快,缺点是要求所要査找的数据必须是有序序列.该算法的基本思想是将所要査找的序列的中间位置的数据与所要査找的元素进行比较,如果相等,则表示査找成功,否则将以该位置为基准将所要査找的序列分为左右两部分.接下来根据所要査找序列的升降序规律及中间元素与所查找元素的大小关系,来选择所要査找元素可能存在的那部分序列,对其采用同样的方法进行査找,直至能够确定所要查找的元素是否存在,具体的使用方法可通过下面的代码具体了解. #include <stdio.h> binar

Dijkstra最短路径算法实现代码_C 语言

Dijkstra的最短路径算法是基于前驱顶点的最短路径计算的,整体上来讲还是比较简单的,下面是代码: 复制代码 代码如下: #include <iostream>#include <vector>#include <limits> void shortestpath( const std::vector <std::vector< short> >& paths, int from, std::vector< short>&a

C语言对堆排序一个算法思路和实现代码_C 语言

算法思想简单描述: 堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(h1,h2,...,hn),当且仅当满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,...,n/2)时称之为堆.在这里只讨论满足前者条件的堆. 由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项.完全二叉树可以很直观地表示堆的结构.堆顶为根,其它为左子树.右子树. 初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的

C++实现顺序排序算法简单示例代码_C 语言

本文实例讲述了最直接的顺序排序法VC++示例代码,还记得以前上学时候这是计算机的必考题,而且在排序算法中,顺序排序似乎是最简单的了,也是最容易掌握的.现在列出来让大家重新回顾一下! 具体代码如下: //顺序排序 void InsertSort(int r[], int n){ for (int i=2; i<n; i++){ r[0]=r[i]; //设置哨兵 for (int j=i-1; r[0]<r[j]; j--) //寻找插入位置 r[j+1]=r[j]; //记录后移 r[j+1]

深入解析Radix Sort基数排序算法思想及C语言实现示例_C 语言

基本思想: 将待排数据中的每组关键字依次进行桶分配. 具体示例: 278.109.063.930.589.184.505.269.008.083 我们将每个数值的个位,十位,百位分成三个关键字: 278 -> k1(个位)=8,k2(十位)=7,k3=(百位)=2. 然后从最低位个位开始(从最次关键字开始),对所有数据的k1关键字进行桶分配(因为,每个数字都是 0-9的,因此桶大小为10),再依次输出桶中的数据得到下面的序列. 930.063.083.184.505.278.008.109.58

C 语言插入排序算法及实例代码_C 语言

插入排序是排序算法的一种,它不改变原有的序列(数组),而是创建一个新的序列,在新序列上进行操作. 这里以从小到大排序为例进行讲解. 基本思想及举例说明 插入排序的基本思想是,将元素逐个添加到已经排序好的数组中去,同时要求,插入的元素必须在正确的位置,这样原来排序好的数组是仍然有序的. 在实际使用中,通常是排序整个无序数组,所以把这个无序数组分为两部分排序好的子数组和待插入的元素.第一轮时,将第一个元素作为排序好的子数组,插入第二个元素:第二轮,将前两个元素作为排序好的数组,插入第三个元素.以此类