/**
     * @param document 目标文档
     * @param size     需要的关键句的个数
     * @param sentence_separator 句子分隔符，正则格式， 如：[。？?！!；;]
     * @return 关键句列表
     */
    public static List<String> getTopSentenceList(String document, int size, String sentence_separator)
    {
        List<String> sentenceList = splitSentence(document, sentence_separator);//句子划分
        List<List<String>> docs = convertSentenceListToDocument(sentenceList);//句子分词，转成doc对象
        TextRankSentence textRank = new TextRankSentence(docs);//TextRank自动摘要
        int[] topSentence = textRank.getTopSentence(size);//获取前几个句子
        List<String> resultList = new LinkedList<String>();
        for (int i : topSentence)
        {
            resultList.add(sentenceList.get(i));
        }
        return resultList;
    }

/**
     * 将文章分割为句子
     *	 
     * @param document 待分割的文档
     * @param sentence_separator 句子分隔符，正则表达式，如：   [。:？?！!；;]
     * @return
     */
    static List<String> splitSentence(String document, String sentence_separator)
    {
        List<String> sentences = new ArrayList<String>();
        for (String line : document.split("[\r\n]"))
        {
            line = line.trim();
            if (line.length() == 0) continue;
            for (String sent : line.split(sentence_separator))//分割句子 [，,。:：“”？?！!；;]
            {
                sent = sent.trim();
                if (sent.length() == 0) continue;
                sentences.add(sent);
            }
        }

        return sentences;
    }

    /**
     * 将句子列表转化为文档
     *
     * @param sentenceList
     * @return
     */
    private static List<List<String>> convertSentenceListToDocument(List<String> sentenceList)
    {
        List<List<String>> docs = new ArrayList<List<String>>(sentenceList.size());
        for (String sentence : sentenceList)
        {
            List<Term> termList = StandardTokenizer.segment(sentence.toCharArray());//句子分词，源码中用的维特比分词
            List<String> wordList = new LinkedList<String>();
            for (Term term : termList)
            {
                if (CoreStopWordDictionary.shouldInclude(term))//去掉停用词（常见的停用词直接写在字典里面了）
                {
                    wordList.add(term.word);
                }
            }
            docs.add(wordList);
        }
        return docs;
    }

/*
 * <summary></summary>
 * <author>He Han</author>
 * <email>hankcs.cn@gmail.com</email>
 * <create-date>2014/8/22 14:17</create-date>
 *
 * <copyright file="BM25.java" company="上海林原信息科技有限公司">
 * Copyright (c) 2003-2014, 上海林原信息科技有限公司. All Right Reserved, http://www.linrunsoft.com/
 * This source is subject to the LinrunSpace License. Please contact 上海林原信息科技有限公司 to get more information.
 * </copyright>
 */
package com.hankcs.hanlp.summary;

import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/**
 * 搜索相关性评分算法
 * @author hankcs
 */
public class BM25
{
    /**
     * 文档句子的个数
     */
    int D;

    /**
     * 文档句子的平均长度
     */
    double avgdl;

    /**
     * 拆分为[句子[单词]]形式的文档
     */
    List<List<String>> docs;

    /**
     * 文档中每个句子中的每个词与词频
     */
    Map<String, Integer>[] f;

    /**
     * 文档中全部词语与出现在几个句子中
     */
    Map<String, Integer> df;

    /**
     * IDF
     */
    Map<String, Double> idf;

    /**
     * 调节因子
     */
    final static float k1 = 1.5f;

    /**
     * 调节因子
     */
    final static float b = 0.75f;

    public BM25(List<List<String>> docs)
    {
        this.docs = docs;
        D = docs.size();//文档句子的个数
        for (List<String> sentence : docs)
        {
            avgdl += sentence.size();
        }
        avgdl /= D; // 句子平均长度
        f = new Map[D]; // 保存每一个句子中的 词与词频
        df = new TreeMap<String, Integer>(); //保存所有的 词与词频
        idf = new TreeMap<String, Double>();//保存所有词的逆文档频率
        init();
    }

    /**
     * 在构造时初始化自己的所有参数
     */
    private void init()
    {
        int index = 0;
        for (List<String> sentence : docs)//依次处理每一个句子
        {
            Map<String, Integer> tf = new TreeMap<String, Integer>();//保存词与词频
            for (String word : sentence)
            {
                Integer freq = tf.get(word);
                freq = (freq == null ? 0 : freq) + 1;
                tf.put(word, freq);//保存词与词频
            }
            f[index] = tf; //保存每一个句子中的 词与词频
            for (Map.Entry<String, Integer> entry : tf.entrySet())//计算所有的 词与词频
            {
                String word = entry.getKey();
                Integer freq = df.get(word);
                freq = (freq == null ? 0 : freq) + 1;
                df.put(word, freq);//保存所有的 词与词频
            }
            ++index;
        }
        for (Map.Entry<String, Integer> entry : df.entrySet())//计算所有词的逆文档频率
        {
            String word = entry.getKey();
            Integer freq = entry.getValue();
            idf.put(word, Math.log(D - freq + 0.5) - Math.log(freq + 0.5));//保存所有词的逆文档频率
        }
    }

    //相似度计算：计算当前句子与某一个句子的相似度
    public double sim(List<String> sentence, int index)
    {
        double score = 0;
        for (String word : sentence)
        {
            if (!f[index].containsKey(word)) continue;//如果当前句子中不包含该词，则跳过
            int d = docs.get(index).size();//当前句子的大小（包含多少个词）
            Integer wf = f[index].get(word);//当前句子中的词的词频
            score += (idf.get(word) * wf * (k1 + 1)
                    / (wf + k1 * (1 - b + b * d
                                                / avgdl)));//BM25计算公式
        }

        return score;
    }

    //相似度计算：依次计算当前句子与文档中所有句子的相似度
    public double[] simAll(List<String> sentence)
    {
        double[] scores = new double[D];//相似度评分
        for (int i = 0; i < D; ++i)//依次计算当前句子与文档中所有句子的相似度
        {
            scores[i] = sim(sentence, i);
        }
        return scores;
    }
}

    //TextRank的具体实现
    private void solve()
    {
        int cnt = 0;
        for (List<String> sentence : docs)
        {
            double[] scores = bm25.simAll(sentence);//计算一个句子和其他句子的相似度
            weight[cnt] = scores;  // 第cnt个句子与其他句子的相似度
            weight_sum[cnt] = sum(scores) - scores[cnt]; // 减掉自己，自己跟自己肯定最相似
            vertex[cnt] = 1.0;//初始TextRank值
            ++cnt;
        }
        //不断迭代，慢慢收敛
        for (int _ = 0; _ < max_iter; ++_)
        {
            double[] m = new double[D];
            double max_diff = 0;
            for (int i = 0; i < D; ++i)
            {
                m[i] = 1 - d;
                for (int j = 0; j < D; ++j)
                {
                    if (j == i || weight_sum[j] == 0) continue;
                    m[i] += (d * weight[j][i] / weight_sum[j] * vertex[j]);//TextRank计算公式
                }
                double diff = Math.abs(m[i] - vertex[i]);
                if (diff > max_diff)//记录每次变化最大的值
                {
                    max_diff = diff;
                }
            }
            vertex = m;//保存当前值，作为公式中上一次的值
            if (max_diff <= min_diff) break;
        }
        // 我们来排个序吧（从大到小），方便后面的句子获取
        for (int i = 0; i < D; ++i)
        {
            top.put(vertex[i], i);
        }
    }

    /**
     * 使用已经分好的词来计算rank
     *
     * @param termList
     * @return
     */
    public Map<String, Float> getRank(List<Term> termList)
    {
        List<String> wordList = new ArrayList<String>(termList.size());
        for (Term t : termList)
        {
            if (shouldInclude(t))//只保留 名词、动词、副词、形容词
            {
                wordList.add(t.word);
            }
        }

        Map<String, Set<String>> words = new TreeMap<String, Set<String>>();//保存每个词的相邻词（邻接表）
        Queue<String> que = new LinkedList<String>();//使用队列作为滑动窗口
        for (String w : wordList)//获取各个词的窗口词，可以理解为图的邻接表
        {
            if (!words.containsKey(w))
            {
                words.put(w, new TreeSet<String>());
            }
            // 复杂度O(n-1)
            if (que.size() >= 5)//使用队列作为滑动窗口
            {
                que.poll();
            }
            for (String qWord : que)
            {
                if (w.equals(qWord))//碰到一样的词，就不需要再放了
                {
                    continue;
                }
                //既然是邻居,那么关系是相互的,遍历一遍即可
                words.get(w).add(qWord);
                words.get(qWord).add(w);
            }
            que.offer(w);
        }
//        System.out.println(words);
        Map<String, Float> score = new HashMap<String, Float>();
        //依据TF来设置初值
        for (Map.Entry<String, Set<String>> entry : words.entrySet()){ 
        	score.put(entry.getKey(),sigMoid(entry.getValue().size()));
        }
        //开始迭代，不断收敛
        for (int i = 0; i < max_iter; ++i)
        {
            Map<String, Float> m = new HashMap<String, Float>();//保存每次结果值
            float max_diff = 0;
            for (Map.Entry<String, Set<String>> entry : words.entrySet())
            {
                String key = entry.getKey();
                Set<String> value = entry.getValue();
                m.put(key, 1 - d);
                for (String element : value)//根据公式进行计算（这里是抽取关键字，TextRank退化为PageRake）
                {
                    int size = words.get(element).size();
                    if (key.equals(element) || size == 0) continue;
                    m.put(key, m.get(key) + d / size * (score.get(element) == null ? 0 : score.get(element)));
                }
                max_diff = Math.max(max_diff, Math.abs(m.get(key) - (score.get(key) == null ? 0 : score.get(key))));//出现迭代前后差值最大的值 都小于阈值就停止迭代
            }
            score = m;//作为下一次的初始值
            if (max_diff <= min_diff) break; // 出现迭代前后差值最大的值 都小于阈值就停止迭代
        }

        return score;//最终的分数值
    }