cnshortpath.java

基于中科院的ICTCLAS实现中文分词系统 开发工具是JAVA.经测试,效果很好

package com.gftech.ictclas4j.segment;

import com.gftech.ictclas4j.utility.Final;

public class CNShortPath {
	private CDynamicArray[] m_apCost;

	private int m_nValueKind;// The number of value kinds

	private int m_nVertex;// The number of vertex in the graph

	private CQueue[][] m_pParent;// The 2-dimension array for the nodes

	private double[][] m_pWeight;// The weight of node

	public int m_nResultCount;

	public int Output(int[][] nResult, boolean bBest, int npCount) {
		return 0;
	}

	public int ShortPath() {
		int nCurNode = 1, nPreNode, nIndex;
		double eWeight;
		TagArrayChain[] pEdgeList = null;

		for (int i = 0; nCurNode < m_nVertex && i < m_apCost.length; nCurNode++, i++) {
			CQueue queWork;

			eWeight = m_apCost[nCurNode].GetElement(-1, nCurNode, 0, pEdgeList,
					null);// Get all the edges
			for (TagArrayChain tac : pEdgeList) {
				if (tac.col == nCurNode) {
					nPreNode = tac.row;
					eWeight = tac.value;// Get the value of edges
					for (i = 0; i < m_nValueKind; i++) {
						if (nPreNode > 0)// Push the weight and the pre node
											// infomation
						{
							if (m_pWeight[nPreNode - 1][i] == Final.INFINITE_VALUE)
								break;
							queWork.Push(nPreNode, i, eWeight
									+ m_pWeight[nPreNode - 1][i]);
						} else {
							queWork.Push(nPreNode, i, eWeight);
							break;
						}
					}// end for
				}
			}// end while

			// Now get the result queue which sort as weight.
			// Set the current node information
			for (i = 0; i < m_nValueKind; i++) {
				m_pWeight[nCurNode - 1][i] = Final.INFINITE_VALUE;
			}
			// memset((void *),(int),sizeof(ELEMENT_TYPE)*);
			// init the weight
			i = 0;

			while (i < m_nValueKind) {// Set the current node weight and
										// parent
				TagQueueElem queue = queWork.Pop();
				if (queue != null) {
					if (m_pWeight[nCurNode - 1][i] == Final.INFINITE_VALUE)
						m_pWeight[nCurNode - 1][i] = eWeight;
					else if (m_pWeight[nCurNode - 1][i] < eWeight)// Next
																	// queue
					{
						i++;// Go next queue and record next weight
						if (i == m_nValueKind)// Get the last position
							break;
						m_pWeight[nCurNode - 1][i] = eWeight;
					}
					m_pParent[nCurNode - 1][i].Push(nPreNode, nIndex);
				} else
					break;
			}
		}// end for

		return 1;
	}

	public CNShortPath(CDynamicArray[] aCost) {
		new CNShortPath(aCost, 1);
	}

	public CNShortPath(CDynamicArray[] apCost, int nValueKind) {
		m_apCost = apCost;// Set the cost
		m_nValueKind = nValueKind;// Set the value kind
		m_nVertex = apCost[0].m_nCol + 1;
		if (m_nVertex < apCost[0].m_nRow + 1)
			m_nVertex = apCost[0].m_nRow + 1;// Get the vertex numbers

		m_pParent = new CQueue[m_nVertex - 1][];// not including the first node
		m_pWeight = new double[m_nVertex - 1][];
		// m_pParent=(CQueue **)malloc((m_nVertex-1)*sizeof(CQueue *));//not
		// including the first node
		// m_pWeight=(ELEMENT_TYPE **)malloc(sizeof(ELEMENT_TYPE
		// *)*(m_nVertex-1));

		for (int i = 0; i < m_nVertex - 1; i++)// The queue array for every
												// node
		{
			m_pParent[i] = new CQueue[nValueKind];
			m_pWeight[i] = new double[nValueKind];
			// m_pParent[i]=(CQueue *)malloc(sizeof(CQueue)*nValueKind);
			// m_pWeight[i]=(ELEMENT_TYPE
			// *)malloc(sizeof(ELEMENT_TYPE)*nValueKind);
		}
	}

	private void GetPaths(int nNode, int nIndex, int[][] nResult, boolean bBest) {

		int nCurNode, nCurIndex, nResultIndex = 0;

		if (m_nResultCount >= Final.MAX_SEGMENT_NUM)// Only need 10 result
			return;
		nResult[m_nResultCount][nResultIndex] = -1;// Init the result
		CQueue queResult = new CQueue();
		queResult.Push(nNode, nIndex);
		nCurNode = nNode;
		nCurIndex = nIndex;
		boolean bFirstGet;

		TagQueueElem elem = null;

		while (!queResult.IsEmpty()) {
			while (nCurNode > 0)//
			{// Get its parent and store them in nParentNode,nParentIndex
				elem = m_pParent[nCurNode - 1][nCurIndex].Pop(false, true);
				if (elem != null) {
					nCurNode = elem.nParent;
					nCurIndex = elem.nIndex;
				}
				if (nCurNode > 0)
					queResult.Push(nCurNode, nCurIndex);
			}
			if (nCurNode == 0) { // Get a path and output
				nResult[m_nResultCount][nResultIndex++] = nCurNode;// Get the
																	// first
																	// node
				bFirstGet = true; 

				while ((elem = queResult.Pop(false, bFirstGet)) != null) {
					nResult[m_nResultCount][nResultIndex++] = elem.nParent;
					bFirstGet = false; 
				}
				nResult[m_nResultCount][nResultIndex] = -1;// Set the end
				m_nResultCount += 1;// The number of result add by 1
				if (m_nResultCount >= Final.MAX_SEGMENT_NUM)// Only need 10
															// result
					return;
				nResultIndex = 0;
				nResult[m_nResultCount][nResultIndex] = -1;// Init the result

				if (bBest)// Return the best result, ignore others
					return;
			}
			elem = queResult.Pop(false, true);// Read the top node
			while (queResult.IsEmpty() == false
					&& (m_pParent[elem.nParent - 1][elem.nIndex].IsSingle() || m_pParent[elem.nParent - 1][elem.nIndex]
							.IsEmpty(true))) {
				elem = queResult.Pop();// Get rid of it
				elem = queResult.Pop(false, true);// Read the top node
			}
			if (queResult.IsEmpty() == false
					&& m_pParent[elem.nParent - 1][elem.nIndex].IsEmpty(true) == false) {
				elem = m_pParent[elem.nParent - 1][elem.nIndex].Pop(false,
						false);
				nCurNode = elem.nParent;
				nCurIndex = elem.nIndex;
				if (nCurNode > 0)
					queResult.Push(nCurNode, nCurIndex);
			}
		}
	}
}