博客

首先，拿到这样的图，表示空间临近关系的空间实例。从而生成二阶候选模式

之后通过以下步骤生成二阶及其多阶：

1. 首先，将图中的每个具有空间临近关系的空间实例以表实例的形式绘成表格，就像step1一样。同时检查每个表实例的参与度，如果小于阈值就删除该表实例。以AD为例子，A的PR参与率为0.25，D的PR参与率为0.5，因此，该表实例的参与度为0.25，小于阈值0.3，删去。
2. 如果是k阶的模式，那么寻找前k-1个特征相同的模式进行连接，例如在这个图中，第一个表实例中的A.2和第二个表实例中的A.2相同，那么他们可以进行连接成为{A.2,B.4,C.2}的行实例，同时，还要检查B.4和C.2是否符合临近关系（在图中的表现就是用黑线连接了）。只有同时满足以上的两个条件时，才可以连接成为新的k+1阶候选模式。
3. 继续检查新的候选模式的参与度，如果小于就淘汰。以上重复过程，直到不再生成新的候选模式。

c++代码实现：

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
using namespace std;
map< char, int> characNum;              //每个空间特征的实例个数
double min_prev = 0.3;
struct table{
	string name;                        // 候选模式的空间特征
	vector<vector<string> > row_instance;     //表实例
	int jie;                    //候选模式的阶
	set<string> instance_set;      //  每个候选模式中某个空间特征的实例的集合
	map<char, int> charac_count;   // 候选模式中空间特征的计数
};
set<string> allSet;             // 每个空间特征的总计数
map<string, table> table_instance;     //连接空间特征与候选模式的重要结构
map<string ,vector<string> > graph;
map<vector<string> , bool> isHave;
bool isNiber(string n1, string n2) {                   //判断两个实例直接是否相邻
	for (int i = 0; i < graph[n1].size(); i++) {
		if (graph[n1][i] == n2) {
			return true;
		}
	}
	return false;
}

void createNewTable(vector<string> row, int k){   // 通过连接后的行实例来建立新的候选模式
	string newName = "";
	for (int i = 0; i < row.size(); i++) {
		newName += string(1,row[i][0]);
	}
	if (table_instance.count(newName) == 0) {
		table t;
		t.name = newName;
		t.jie = k+1;
		t.row_instance.push_back(row);
		for (auto it = row.begin(); it != row.end(); it ++) {
			t.instance_set.insert(*it);
		}
		table_instance[newName] = t;
	}else {
		table_instance[newName].row_instance.push_back(row);
		for (auto it = row.begin(); it != row.end(); it ++) {
			table_instance[newName].instance_set.insert(*it);
		}
	}
}

void check(int k) {
	for (auto it = table_instance.begin(); it != table_instance.end();) {
		bool flag = false;
		table t = it->second;
		if (k == t.jie) {
			set<string> s = it->second.instance_set;
			for (auto i = s.begin(); i != s.end(); i++) {
				string str = *i;
				it->second.charac_count[str[0]] ++; //计算不同空间特征在候选模式中的次数
			}
			t = it->second;
			for (int i = 0; i < t.jie; i++) {
				double prev = double(t.charac_count[t.name[i]]) / double(characNum[t.name[i]]);
				if (prev < min_prev ) {
					table_instance.erase(it++);      // 小于阈值的过滤掉
					flag = true;
					break;  
				}
			}
		}
		if (flag == false) {
			it++;
		}
	}
}

void outPut(table t) {
	cout << " 阶数: " << t.jie << endl;
	for (int i = 0; i < t.name.size(); i++) {
		cout << t.name[i] << " ";
	}
	cout << endl;
	for (auto it1 = t.row_instance.begin(); it1 != t.row_instance.end(); it1 ++) {
		vector<string> temp = *it1;
		for (auto it2 = temp.begin(); it2 != temp.end(); it2 ++) {
			string str = *it2;
			cout << str[1] << " ";
		}
		cout << endl;
	}
}

int main(int argc, char *argv[]) {
	int n;
	cin >> n;     
	for (int i = 0; i < n; i++) {
		string a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
		string table_name = string(1,a[0]) + string(1,b[0]);   // 生成对应的模式名字
		if (table_name[0] != table_name[1]) {          //防止相同空间特征连接的情况
			table_instance[table_name].name = table_name;
			table_instance[table_name].jie = 2;
			table_instance[table_name].instance_set.insert(a);
			table_instance[table_name].instance_set.insert(b);
			vector<string> temp;       //行实例
			temp.push_back(a);
			temp.push_back(b);
			table_instance[table_name].row_instance.push_back(temp);
		}
		allSet.insert(a);
		allSet.insert(b); // 分母
	}
	for (auto it = allSet.begin(); it != allSet.end(); it ++) {
		string str = *it;
		characNum[str[0]] ++;    // 不同空间特征在总体中出现的次数
	}

	int k = 2;
	bool flag = true;
	while (flag) {
		flag = false;
		check(k);            //根据参与度阈值来筛选
		map<string, table> New_table_instance;  //每一轮都有不同的处理对象
		for (auto it = table_instance.begin(); it != table_instance.end(); it ++) {
			if (it->second.jie == k) {
				New_table_instance[it->first] = it->second;
			}
		}
		map<string, bool> deReapt; //避免重复
		for (auto it = New_table_instance.begin(); it != New_table_instance.end(); it ++) {
			deReapt[it->first] = false;
		}
		for (auto it1 = New_table_instance.begin(); it1 != New_table_instance.end(); it1 ++) {
			string coName = it1->first.substr(0,k-1);
			for (auto it2 = New_table_instance.begin(); it2 != New_table_instance.end(); it2 ++) {
				if (it1 != it2 ) {
					string compareName = it2->first.substr(0,k-1);
					if (coName == compareName && deReapt[it2->first] == false) {  //检查k-1个空间特征是否一致
						deReapt[it1->first] = true;
						vector<vector<string> > t1 = it1->second.row_instance;
						vector<vector<string> > t2 = it2->second.row_instance;
						for (int i = 0; i < t1.size(); i++) {
							for (int j = 0; j < t2.size(); j++) {
								vector<string> compare1 = t1[i];
								vector<string> compare2 = t2[j];
								compare1.erase(compare1.begin()+k-1, compare1.end());
								compare2.erase(compare2.begin()+k-1, compare2.end());
								if (compare1 == compare2) {    //检查前k-1个实例是否一致
									string n1 = t1[i][t1[i].size()-1];
									string n2 = t2[j][t2[j].size()-1];
									if (isNiber(n1, n2)) { //检查第K个实例是否满足临近关系
										flag = true;
										vector<string> temp = t1[i];
										temp.push_back(n2);   //形成新的行实例
										if (isHave[temp] == false) {
											isHave[temp] = true;
											createNewTable(temp,k);
										}
									}
								}
							}
						}
					}
				}
			}
		}
		New_table_instance.clear();
		k++;
	}
	for (auto it = table_instance.begin(); it != table_instance.end(); it ++) {
		outPut(it->second);
	}
}