/**
    * sentence:当前的句子
    * featureMap：一个TreeMap，用于保存所有特征
    * position：句子的index，即此时处理的哪一个字符
    */
    protected int[] extractFeature(String sentence, FeatureMap featureMap, int position)
    {
        List<Integer> featureVec = new LinkedList<Integer>();

        char pre2Char = position >= 2 ? sentence.charAt(position - 2) : CHAR_BEGIN;//前两个词
        char preChar = position >= 1 ? sentence.charAt(position - 1) : CHAR_BEGIN;//前一个词
        char curChar = sentence.charAt(position);//当前词
        char nextChar = position < sentence.length() - 1 ? sentence.charAt(position + 1) : CHAR_END;//后一个词
        char next2Char = position < sentence.length() - 2 ? sentence.charAt(position + 2) : CHAR_END;//后两个词

        StringBuilder sbFeature = new StringBuilder();
      
        sbFeature.delete(0, sbFeature.length());
        sbFeature.append(preChar).append('1');
        addFeature(sbFeature, featureVec, featureMap);//第一个特征，前一个词

        sbFeature.delete(0, sbFeature.length());
        sbFeature.append(curChar).append('2');
        addFeature(sbFeature, featureVec, featureMap);//第二个特征，当前词

        sbFeature.delete(0, sbFeature.length());
        sbFeature.append(nextChar).append('3');
        addFeature(sbFeature, featureVec, featureMap);//第三个特征，后一个词


        //char bigram feature
        sbFeature.delete(0, sbFeature.length());
        sbFeature.append(pre2Char).append("/").append(preChar).append('4');  
        addFeature(sbFeature, featureVec, featureMap);//第四个特征，前两个词与前一个词

        sbFeature.delete(0, sbFeature.length());
        sbFeature.append(preChar).append("/").append(curChar).append('5');
        addFeature(sbFeature, featureVec, featureMap);//第五个特征，前一个词与当前词

        sbFeature.delete(0, sbFeature.length());
        sbFeature.append(curChar).append("/").append(nextChar).append('6');
        addFeature(sbFeature, featureVec, featureMap);//第六个特征，当前词与后一个词

        sbFeature.delete(0, sbFeature.length());
        sbFeature.append(nextChar).append("/").append(next2Char).append('7');
        addFeature(sbFeature, featureVec, featureMap);//第七个特征，后一个词与后两个词

        return toFeatureArray(featureVec);//所有特征转为一个数组
    }

// 加载训练语料
        TagSet tagSet = createTagSet();
        MutableFeatureMap mutableFeatureMap = new MutableFeatureMap(tagSet);
        ConsoleLogger logger = new ConsoleLogger();
        logger.start("开始加载训练集...\n");
        Instance[] instances = loadTrainInstances(trainingFile, mutableFeatureMap);//所有句子实例
        tagSet.lock();
        logger.finish("\n加载完毕，实例一共%d句，特征总数%d\n", instances.length, mutableFeatureMap.size() * tagSet.size());

        // 开始训练
        ImmutableFeatureMap immutableFeatureMap = new ImmutableFeatureMap(mutableFeatureMap.featureIdMap, tagSet);
        mutableFeatureMap = null;
        double[] accuracy = null;

        AveragedPerceptron model;
        model = new AveragedPerceptron(immutableFeatureMap);
        final double[] total = new double[model.parameter.length];
        final int[] timestamp = new int[model.parameter.length];
        int current = 0;//每次迭代，每个句子就加一，记录时间戳
        for (int iter = 1; iter <= maxIteration; iter++)
        {
                Utility.shuffleArray(instances);//数据随机化
                for (Instance instance : instances)
                {
                    ++current;
                    int[] guessLabel = new int[instance.length()];
                    model.viterbiDecode(instance, guessLabel);//用不断更新的模型去做预测
                    for (int i = 0; i < instance.length(); i++)
                    {
                        int[] featureVector = instance.getFeatureAt(i);//一个字符的特征向量
                        int[] goldFeature = new int[featureVector.length];//正确的特征
                        int[] predFeature = new int[featureVector.length];//预测的特征
                        for (int j = 0; j < featureVector.length - 1; j++)//7个自定义特征
                        {
                            goldFeature[j] = featureVector[j] * tagSet.size() + instance.tagArray[i];//实际特征+实际标签作为特征，方便后面的权重特征更新
                            predFeature[j] = featureVector[j] * tagSet.size() + guessLabel[i];//实际特征+预测标签作为特征，方便后面的权重特征更新
                        }
                        goldFeature[featureVector.length - 1] = (i == 0 ? tagSet.bosId() : instance.tagArray[i - 1]) * tagSet.size() + instance.tagArray[i];//正确的转移特征
                        predFeature[featureVector.length - 1] = (i == 0 ? tagSet.bosId() : guessLabel[i - 1]) * tagSet.size() + guessLabel[i];//预测的转移特征
                        model.update(goldFeature, predFeature, total, timestamp, current);//更新权重值
                    }
                }
            
        }


/*******权重值更新update*******/
/**
     * 根据答案和预测更新参数
     *
     * @param goldIndex    预测正确的特征函数
     * @param predictIndex 命中的特征函数
     */
    public void update(int[] goldIndex, int[] predictIndex, double[] total, int[] timestamp, int current)
    {
        for (int i = 0; i < goldIndex.length; ++i)
        {
            if (goldIndex[i] == predictIndex[i])
                continue;
            else
            {
                update(goldIndex[i], 1, total, timestamp, current);//正确预测，权重加1
                if (predictIndex[i] >= 0 && predictIndex[i] < parameter.length)
                    update(predictIndex[i], -1, total, timestamp, current);//错误预测，权重减1
                else
                {
                    throw new IllegalArgumentException("更新参数时传入了非法的下标");
                }
            }
        }
    }
/*******实际权重值更新update*******/
  /**
     * 根据答案和预测更新参数
     *
     * @param index     特征向量的下标
     * @param value     更新量
     * @param total     权值向量总和
     * @param timestamp 每个权值上次更新的时间戳
     * @param current   当前时间戳
     */
    private void update(int index, float value, double[] total, int[] timestamp, int current)
    {
        int passed = current - timestamp[index];//距离index上次更新已经过去多少个时刻了
        total[index] += passed * parameter[index];
        parameter[index] += value;//特征权重更新
        timestamp[index] = current;
    }
    
 /*******模型预测，使用维特比算法预测一个字符是{B,M,E,S}哪一标签*******/   
  /**
     * 维特比解码
     *
     * @param instance   实例
     * @param guessLabel 输出标签
     * @return
     */
    public double viterbiDecode(Instance instance, int[] guessLabel)
    {
        final int[] allLabel = featureMap.allLabels();//所有标签
        final int bos = featureMap.bosTag();//标签集合大小
        final int sentenceLength = instance.tagArray.length;//句子长度
        final int labelSize = allLabel.length;//标签集合大小

        int[][] preMatrix = new int[sentenceLength][labelSize];//转态转移矩阵
        double[][] scoreMatrix = new double[2][labelSize];//滚动数组，记录上一次分数和这一次分数

        for (int i = 0; i < sentenceLength; i++)
        {
            int _i = i & 1;
            int _i_1 = 1 - _i;//用于滚动数组
            int[] allFeature = instance.getFeatureAt(i);//一个字符的所有特征
            final int transitionFeatureIndex = allFeature.length - 1;
            if (0 == i)
            {
                allFeature[transitionFeatureIndex] = bos;
                for (int j = 0; j < allLabel.length; j++)
                {
                    preMatrix[0][j] = j;

                    double score = score(allFeature, j);

                    scoreMatrix[0][j] = score;
                }
            }
            else
            {
                //每一个状态转移到哪一个更好
                for (int curLabel = 0; curLabel < allLabel.length; curLabel++)
                {

                    double maxScore = Integer.MIN_VALUE;

                    //上一次的状态0,1,2,3  哪一个转移curLabel状态更好
                    for (int preLabel = 0; preLabel < allLabel.length; preLabel++)
                    {

                        allFeature[transitionFeatureIndex] = preLabel;//转移特征
                        double score = score(allFeature, curLabel);//当前标签的词特征权值和作为分数，以此表示当前词特征作为某一种标签的概率

                        double curScore = scoreMatrix[_i_1][preLabel] + score;//分数累加

                        if (maxScore < curScore)//分数越大越好
                        {
                            maxScore = curScore;
                            preMatrix[i][curLabel] = preLabel;//上一次preLabel状态转移到curLabe状态更好
                            scoreMatrix[_i][curLabel] = maxScore;
                        }
                    }
                }

            }
        }

        int maxIndex = 0;
        double maxScore = scoreMatrix[(sentenceLength - 1) & 1][0];

        //找出最后一次的最大值和索引
        for (int index = 1; index < allLabel.length; index++)
        {
            if (maxScore < scoreMatrix[(sentenceLength - 1) & 1][index])
            {
                maxIndex = index;
                maxScore = scoreMatrix[(sentenceLength - 1) & 1][index];
            }
        }

        //反向回溯，预测标签
        for (int i = sentenceLength - 1; i >= 0; --i)
        {
            guessLabel[i] = allLabel[maxIndex];
            maxIndex = preMatrix[i][maxIndex];
        }

        return maxScore;
    }