markov.h

矩阵编码和马尔可夫链的实现例程。实现类似黑客帝国数字屏保

/*
 Copyright (c) 2001 
 Author: Konstantin Boukreev 
 E-mail: [e-mail] 

 Created: 19.12.2001 14:50:43
 Version: 1.0.0

 fun with Markov chains 
 well-known algorithm for generating of a nonsense text

 see definition of Markov chains on : 
 http://pespmc1.vub.ac.be/ASC/Markov_chain.html
 
*/

#ifndef _Markov_358a5dee_3eaa_4e9f_be46_15b54b33b45f
#define _Markov_358a5dee_3eaa_4e9f_be46_15b54b33b45f

#if _MSC_VER > 1000 
#pragma once
#endif // _MSC_VER > 1000

#include <map>
#include <list>
#include <vector>
#include <string>
#include <fstream>

class markov_chains
{
public:

	enum 
	{
		HEURISTICS_AVE_WORD_LENGTH	= 5,
		HEURISTICS_HASH_MAX_DEEP	= 5,
		HEURISTICS_HASH_MAGIC_VALUE	= 31,
	};

	struct suffix
	{
		suffix(char * s_) : s(s_), n(1)
			{}
		char *		s;
		unsigned	n;
	};
	
	typedef std::list<suffix> suffixs;
	struct prefix
	{		
		char *	first;		
		char *	second;
		suffixs suffxs;
	};

 private:
	typedef std::list<prefix>		prefixs;	
	typedef std::vector<prefixs>	hash;

 public:
	class iterator : 
		public std::iterator<std::forward_iterator_tag, prefix>
	{
		friend class markov_chains;

	public:
		typedef value_type& reference;

	private:
		iterator (markov_chains & m, 
			hash::iterator h, 
			prefixs::iterator p)
			: markov(m), hash_it(h), prfx_it(p)
		{}

	public:	

		iterator (const iterator& i) 
			: markov(i.markov) 
		{ *this == i; }

		iterator& operator = (const iterator& i);
		
		bool operator == (const iterator& i) const;
		bool operator != (const iterator& i) const;	
		iterator& operator ++ ();
		iterator operator ++ (int);
		reference operator * ();
		
	private:
		markov_chains &		markov;
		hash::iterator		hash_it;
		prefixs::iterator	prfx_it;
	};
	
	friend class iterator;
	typedef prefix value_type;
	typedef prefix& reference;

private:
	struct less_word {
		bool operator () (const char * x1, const char * x2) const {
			return markov_chains::compare(x1, x2) < 0;
		}
	};	
			
	typedef std::map<char *, char *, less_word> words;
			
	words		m_words;
	hash		m_hash;	
	unsigned	m_size;
		
public:
	markov_chains(unsigned hash_size);
	~markov_chains();
	
	void insert(const char * first, const char * second, const char * suffix);
	const char * find(const char * first, const char * second);	// returns a suffix

	iterator begin();
	iterator end();
	reference front()	{return m_hash.front().front();}
	reference back()	{return m_hash.back().back();}
	size_t size() const {return m_size;}	
	void clear();

	#ifdef _DEBUG
	void debug_report1(std::ostream&);
	void debug_report2(std::ostream&);
	#endif //_DEBUG

	static markov_chains* create_from_file(const char * filename, 
			unsigned ave_word_size = HEURISTICS_AVE_WORD_LENGTH , 
			unsigned hash_max_deep = HEURISTICS_HASH_MAX_DEEP);

private:
		
	unsigned markov_chains::hash_func(const char * p1, const char * p2)
	{			
		unsigned h = 0;
		while (*p1 || *p2)
		{
		//	h = HEURISTICS_HASH_MAGIC_VALUE * h + tolower(*p1) + tolower(*p2);
			h = HEURISTICS_HASH_MAGIC_VALUE * h + *p1 + *p2;
			if (*p1) ++p1;
			if (*p2) ++p2;
		}
		return h % m_hash.size();	
	}

	char * find_word(const char * s)
	{
		words::iterator w = m_words.find((char *)s);
		if (w == m_words.end())
		{
			char * t = strdup(s);
			w = m_words.insert(words::value_type(t, t)).first;
		}
		return (*w).second;
	}

public:
	static int compare(const char* s1, const char* s2)
	{
	//	return _stricmp(s1, s2);
		return strcmp(s1, s2);
	}
};


#endif //_Markov_358a5dee_3eaa_4e9f_be46_15b54b33b45f