Topling 中文纠错算法

void append_adfa_topological(size_t len, state_id_t root2) {
		assert(stack.empty());
		//
		// append reverse topological order on path
		stack.push_back(root2);
		R.resize_indegree(au->total_states());
	// now indegree serve as 'color' flag for DFS
		while (!stack.empty()) {
			state_id_t parent = stack.back();
			switch (R.indegree(parent)) {
			case 0:
				R.indegree_set(parent, 1);
				au->for_each_dest_rev(parent,
				[&](state_id_t child) {
					switch (R.indegree(child)) {
					case 0:
						stack.push_back(child);
						break;
					case 1: // back edge
						if (child == parent)
							throw std::logic_error("add_suffix_adfa: found a self-loop");
						else
							throw std::logic_error("add_suffix_adfa: found a back-loop");
						break;
					case 2:
						break;
					default:
						assert(0);
						break;
					}
				});
				break;
			case 1:
				R.indegree_set(parent, 2);
				path.push_back(parent); // on_finish
				// fall through:
			case 2:
				stack.pop_back();
				break;
			default:
				assert(0);
				break;
			}
		}
		assert(path.back() == root2);
		//
		// compute_reverse_adfa_and_indegree:
		//
		// now path[len+1...end) is in reverse topological order
		inv_nfa.index.reserve(path.size()-(len+1)+1);
		inv_nfa.index.erase_all();
		for (size_t j = len+1, n = path.size(); j < n; ++j)
			inv_nfa.index.unchecked_push_back({path[j], 0});
		inv_nfa.index.unchecked_push_back({nil_state+0, 0});
		std::sort(inv_nfa.index.begin(), inv_nfa.index.end()
				, CompareIndexEntry());
		size_t trans_num = 0;
		R.indegree_set(root2, 1);
		for (size_t j = len+1, n = path.size(); j < n; ++j)
			R.indegree_set(path[j], 0);
		for (size_t j = len+1, n = path.size(); j < n; ++j) {
			au->for_each_dest(path[j], [&](state_id_t child) {
				R.indegree_inc(child);
				auto p = inv_nfa.lower_bound(child);
				assert(p < inv_nfa.index.end()-1 && p->state == child);
				p[1].offset++;
				trans_num++;
			});
		}
		tmp_idx.resize_no_init(inv_nfa.index.size());
		tmp_idx[0] = 0;
		for (size_t j = 1; j < inv_nfa.index.size(); ++j)
			tmp_idx[j] = inv_nfa.index[j].offset += inv_nfa.index[j-1].offset;
		inv_nfa.data.resize_no_init(trans_num);
		for (size_t j = len+1, n = path.size(); j < n; ++j) {
			state_id_t parent = path[j];
			au->for_each_move(parent,
			[&,parent](state_id_t child, auchar_t ch) {
				auto p = inv_nfa.lower_bound(child);
				assert(p < inv_nfa.index.end()-1 && p->state == child);
				auto& idx = tmp_idx[p - inv_nfa.index.begin()];
				inv_nfa.data[idx++] = CharTarget<state_id_t>(ch, parent);
			});
		}
		for (size_t j = len+1, n = path.size(); j < n; ++j) {
			state_id_t& child = path[j];
			std::pair<size_t, bool> ib = R.find_or_add(child);
			if (!ib.second) { // existed an equivalent state
				state_id_t EqState = ib.first;
				if (EqState == child)
					break;
				auto p = inv_nfa.lower_bound(child);
				assert(p < inv_nfa.index.end()-1 && p->state == child);
				for (size_t k = p[0].offset; k < p[1].offset; ++k) {
					auto ct = inv_nfa.data[k]; // inverse transition to parent
					au->set_move(ct.target, EqState, ct.ch); // modify parent
				}
				au->del_state(child);
				R.indegree_set(child, 0); // reset indegree of deleted state
				R.indegree_inc(child = EqState);
			}
		}
	}

dfa_intersection_search(KeyDFA, DataBaseDFA) {
	// a queue which add new elements at tail
	// and can search by key = pair<StateID, StateID>
	// the first  StateID of key identify states of KeyDFA
	// the second StateID of key identify states of DataBaseDFA
	// qset[nth] access the nth added element
	// the qset never delete elements
	qset = new bfs_queue_set<pair<StateID, StateID> >();

	// new qset is empty, the first add will always success
	qset.add_element(pair(KeyDFA.root, DataBaseDFA.root));

	matched_states = {};

	// This is an implicit BFS (Breath First Search)
	// bfshead is the pointer(element index) for qset
	// qset.size() will increase when new elements are added
	for (bfshead = 0; bfshead < qset.size(); ++bfshead) {
		pair(state1, state2) = qset[bfshead];
		if (KeyDFA.is_final(state1)) {
			// Delim is a special char, such as '\t'
			// Delim will not in any where except between PinYin and HanZi
			target = DataBaseDFA.target_of(state2, Delem);
			if (target != nil) {
				matched_states.add_element();
			}
		}
		// children_of return children in label_char order
		children1 =      KeyDFA.children_of(state1);
		children2 = DataBaseDFA.children_of(state2);
		children = {};
		// compute intersection on label_char
		for (i = 0, j = 0; i < children1.size() && j < children2.size; ) {
			if (children1[i].label_char < children2[j].label_char) {
				++i;
			}
			else if (children1[i].label_char > children2[j].label_char) {
				++j;
			}
			else { // label_char matched
				target1 = children1[i].target;
				target2 = children2[j].target;
				// qset.size() will increased if add_element success
				// add_element fails if pair(target1, target2) already
				// exists in qset
				qset.add_element(pair(target1, target2));
				++i; ++j;
			}
		}
	}
	for_each(state in matched_states) {
		for_each(string in DataBaseDFA.right_lange(state)) {
			output(string);
		}
	}
}