+++ /dev/null
-/**
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package org.apache.lucene.analysis.cn.smart.hhmm;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.HashMap;
-import java.util.List;
-import java.util.Map;
-
-import org.apache.lucene.analysis.cn.smart.Utility;
-
-/**
- * Graph representing possible token pairs (bigrams) at each start offset in the sentence.
- * <p>
- * For each start offset, a list of possible token pairs is stored.
- * </p>
- * @lucene.experimental
- */
-class BiSegGraph {
-
- private Map<Integer,ArrayList<SegTokenPair>> tokenPairListTable = new HashMap<Integer,ArrayList<SegTokenPair>>();
-
- private List<SegToken> segTokenList;
-
- private static BigramDictionary bigramDict = BigramDictionary.getInstance();
-
- public BiSegGraph(SegGraph segGraph) {
- segTokenList = segGraph.makeIndex();
- generateBiSegGraph(segGraph);
- }
-
- /*
- * Generate a BiSegGraph based upon a SegGraph
- */
- private void generateBiSegGraph(SegGraph segGraph) {
- double smooth = 0.1;
- int wordPairFreq = 0;
- int maxStart = segGraph.getMaxStart();
- double oneWordFreq, weight, tinyDouble = 1.0 / Utility.MAX_FREQUENCE;
-
- int next;
- char[] idBuffer;
- // get the list of tokens ordered and indexed
- segTokenList = segGraph.makeIndex();
- // Because the beginning position of startToken is -1, therefore startToken can be obtained when key = -1
- int key = -1;
- List<SegToken> nextTokens = null;
- while (key < maxStart) {
- if (segGraph.isStartExist(key)) {
-
- List<SegToken> tokenList = segGraph.getStartList(key);
-
- // Calculate all tokens for a given key.
- for (SegToken t1 : tokenList) {
- oneWordFreq = t1.weight;
- next = t1.endOffset;
- nextTokens = null;
- // Find the next corresponding Token.
- // For example: "Sunny seashore", the present Token is "sunny", next one should be "sea" or "seashore".
- // If we cannot find the next Token, then go to the end and repeat the same cycle.
- while (next <= maxStart) {
- // Because the beginning position of endToken is sentenceLen, so equal to sentenceLen can find endToken.
- if (segGraph.isStartExist(next)) {
- nextTokens = segGraph.getStartList(next);
- break;
- }
- next++;
- }
- if (nextTokens == null) {
- break;
- }
- for (SegToken t2 : nextTokens) {
- idBuffer = new char[t1.charArray.length + t2.charArray.length + 1];
- System.arraycopy(t1.charArray, 0, idBuffer, 0, t1.charArray.length);
- idBuffer[t1.charArray.length] = BigramDictionary.WORD_SEGMENT_CHAR;
- System.arraycopy(t2.charArray, 0, idBuffer,
- t1.charArray.length + 1, t2.charArray.length);
-
- // Two linked Words frequency
- wordPairFreq = bigramDict.getFrequency(idBuffer);
-
- // Smoothing
-
- // -log{a*P(Ci-1)+(1-a)P(Ci|Ci-1)} Note 0<a<1
- weight = -Math
- .log(smooth
- * (1.0 + oneWordFreq)
- / (Utility.MAX_FREQUENCE + 0.0)
- + (1.0 - smooth)
- * ((1.0 - tinyDouble) * wordPairFreq / (1.0 + oneWordFreq) + tinyDouble));
-
- SegTokenPair tokenPair = new SegTokenPair(idBuffer, t1.index,
- t2.index, weight);
- this.addSegTokenPair(tokenPair);
- }
- }
- }
- key++;
- }
-
- }
-
- /**
- * Returns true if their is a list of token pairs at this offset (index of the second token)
- *
- * @param to index of the second token in the token pair
- * @return true if a token pair exists
- */
- public boolean isToExist(int to) {
- return tokenPairListTable.get(Integer.valueOf(to)) != null;
- }
-
- /**
- * Return a {@link List} of all token pairs at this offset (index of the second token)
- *
- * @param to index of the second token in the token pair
- * @return {@link List} of token pairs.
- */
- public List<SegTokenPair> getToList(int to) {
- return tokenPairListTable.get(to);
- }
-
- /**
- * Add a {@link SegTokenPair}
- *
- * @param tokenPair {@link SegTokenPair}
- */
- public void addSegTokenPair(SegTokenPair tokenPair) {
- int to = tokenPair.to;
- if (!isToExist(to)) {
- ArrayList<SegTokenPair> newlist = new ArrayList<SegTokenPair>();
- newlist.add(tokenPair);
- tokenPairListTable.put(to, newlist);
- } else {
- List<SegTokenPair> tokenPairList = tokenPairListTable.get(to);
- tokenPairList.add(tokenPair);
- }
- }
-
- /**
- * Get the number of {@link SegTokenPair} entries in the table.
- * @return number of {@link SegTokenPair} entries
- */
- public int getToCount() {
- return tokenPairListTable.size();
- }
-
- /**
- * Find the shortest path with the Viterbi algorithm.
- * @return {@link List}
- */
- public List<SegToken> getShortPath() {
- int current;
- int nodeCount = getToCount();
- List<PathNode> path = new ArrayList<PathNode>();
- PathNode zeroPath = new PathNode();
- zeroPath.weight = 0;
- zeroPath.preNode = 0;
- path.add(zeroPath);
- for (current = 1; current <= nodeCount; current++) {
- double weight;
- List<SegTokenPair> edges = getToList(current);
-
- double minWeight = Double.MAX_VALUE;
- SegTokenPair minEdge = null;
- for (SegTokenPair edge : edges) {
- weight = edge.weight;
- PathNode preNode = path.get(edge.from);
- if (preNode.weight + weight < minWeight) {
- minWeight = preNode.weight + weight;
- minEdge = edge;
- }
- }
- PathNode newNode = new PathNode();
- newNode.weight = minWeight;
- newNode.preNode = minEdge.from;
- path.add(newNode);
- }
-
- // Calculate PathNodes
- int preNode, lastNode;
- lastNode = path.size() - 1;
- current = lastNode;
- List<Integer> rpath = new ArrayList<Integer>();
- List<SegToken> resultPath = new ArrayList<SegToken>();
-
- rpath.add(current);
- while (current != 0) {
- PathNode currentPathNode = path.get(current);
- preNode = currentPathNode.preNode;
- rpath.add(Integer.valueOf(preNode));
- current = preNode;
- }
- for (int j = rpath.size() - 1; j >= 0; j--) {
- Integer idInteger = rpath.get(j);
- int id = idInteger.intValue();
- SegToken t = segTokenList.get(id);
- resultPath.add(t);
- }
- return resultPath;
-
- }
-
- @Override
- public String toString() {
- StringBuilder sb = new StringBuilder();
- Collection<ArrayList<SegTokenPair>> values = tokenPairListTable.values();
- for (ArrayList<SegTokenPair> segList : values) {
- for (SegTokenPair pair : segList) {
- sb.append(pair + "\n");
- }
- }
- return sb.toString();
- }
-
-}
fnp / pylucene.git / blobdiff