`

编程之美-最短摘要的生成

阅读更多

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

public class ShortestAbstract {

	/**
	 * 编程之美 最短摘要的生成
	 * 扫描过程始终保持一个[pBegin,pEnd]的range,初始化确保[pBegin,pEnd]的range里包含所有关键字
	 * 然后每次迭代,尝试调整pBegin和pEnd:
	 * 1.pBegin递增,直到range无法包含所有关键字
	 * 2.pEnd递增,直到range重新包含所有关键字
	 * 计算新的range,与旧的range相比,看是否缩短了,如果是,则更新
	 * 不考虑关键字的先后顺序
	 */
	public static void main(String[] args) {
//		String description = "w0,w1,w2,w3,q0,w4,w5,q1,w6,w7,w8,q0,w9,q1";
		String description = "w0,w1,w2,q1,w3,q0,w4,w5,q1,q0,w6,w7,w8,,q0,w9,q1";
		String[] keywords = {"q1","q0"};
		String summery = shortestAbstract(description, keywords);
		System.out.println(summery);
	}
	
	public static String shortestAbstract(String description, String[] keywords) {
		if (description == null || description.length() == 0
				|| keywords == null || keywords.length == 0) {
			return null;
		}
		String[] desc = description.split(",");
		return extract(desc, keywords);
	}

	public static String extract(String[] desc, String[] keywords) {
		Map<String, Integer> map = new HashMap<String, Integer>();		//key=关键字 value=关键字出现的次数
		for (String keyword : keywords) {
			if (keyword != null && keyword.length() != 0) {		//忽略null和空字符
				map.put(keyword, 0);
			}
		}
		if (map.isEmpty()) {
			return null;
		}
		
		String summery = null;
		int descLen = desc.length;
		int shortestLen = descLen + 1;
		int pBegin = 0;
		int pEnd = 0;
		int abstractBegin = -1;
		int abstractEnd = -1;
		
		while (true) {
			
			//相当于初始化,从desc[0]开始,找到第一个包含所有关键字的摘要:desc[0]~desc[pEnd],此时pBegin=0
			while (!isAllVisited(map) && pEnd < descLen) {
				if (map.containsKey(desc[pEnd])) {
					setVisited(map, desc[pEnd], 1);		//出现次数加1
				}
				pEnd++;
			}
			
			//pBegin右移,停止条件为:已经无法包含所有关键字;
			//然后回到上面,右移pEnd,重新初始化,使得pBegin~pEnd重新包含所有关键字
			while (isAllVisited(map)) {
				if (pEnd - pBegin < shortestLen) {
					shortestLen = pEnd - pBegin;
					abstractBegin = pBegin;
					abstractEnd = pEnd -1;
				}
				if (map.get(desc[pBegin]) != null) {
					setVisited(map, desc[pBegin], -1);		//出现次数减1
				}
				pBegin++;
			}
			
			if (pEnd >= descLen) {
				break;
			}
			
		}
		
		//返回找到的最短摘要,没找到则返回null
		if (abstractBegin == -1 || abstractEnd == -1) {
			System.out.println("one or more keywords not found.");
		} else {
			StringBuilder sb = new StringBuilder();
			for (int i = abstractBegin; i <= abstractEnd; i++) {
				sb.append("," + desc[i]);
			}
			if (sb.length() > 1) {
				summery = sb.substring(1);
			}
		}
		return summery;
	}
	
	//所有关键字出现次数大于0,则找到了一个摘要
	private static boolean isAllVisited(Map<String, Integer> map) {
		for (Entry<String, Integer> entry : map.entrySet()) {
			int count = entry.getValue();
			if (count == 0) {
				return false;
			}
		}
		return true;
	}
	
	private static void setVisited(Map<String, Integer> map, String key, int add) {
		int count = map.get(key);
		map.put(key, count + add);
	}
	
}
0
3
分享到:
评论

相关推荐

    Algorithm:CS455-算法和结构化编程-图

    介绍: 最短路径是以下问题:在图中找到两个顶点(或节点)之间的路径,以使其组成边的权重之和最小。 MST是连接的加权无向图的边的子集,该边以最小可能的总边权重连接所有顶点。解决方案: 解决问题1(最短路径)...

    CMP302-Summary

    CMP302:算法设计和分析摘要 该存储库是本课程的摘要,...动态编程最短路径 Floyd-Warshall算法 全对最短路径上的应用 传递闭包 约翰逊算法 最大流量问题 对流图建模不同的图 流网络定义 残留网络 增强路径 流网削减 最

    java生成海报实例源码-code-transformer:论文“Language-agnosticrepresentationlearnin

    java生成海报实例源码代码转换器 这是CodeTransformer模型的官方 PyTorch 实现: D. Zügner、T. Kirschstein、M. Catasta、J. Leskovec 和 S. Günnemann, “从结构和上下文中学习源代码的语言不可知表示” 出现在...

    《算法》中文版,Robert Sedgewick,塞奇威克

     7、与网络相结合:配套网站algs4.cs.princeton.edu提供了本书内容的摘要及相关的代码、测试数据、编程练习、教学课件等资源 作者简介  Robert Sedgewick,斯坦福大学博士,导师为Donald E.Knuth,从1985年开始...

    算法 第4版 高清中文版

    算法(第4版)》是Sedgewick之巨著,与高德纳TAOCP一脉相承,是算法领域经典的参考书,涵盖所有程序员必须掌握的50种算法,全面介绍了关于算法和数据结构的必备知识,并特别针对排序、搜索、图处理和字符串处理进行了...

    JAVA上百实例源码以及开源项目

     Java生成密钥、保存密钥的实例源码,通过本源码可以了解到Java如何产生单钥加密的密钥(myKey)、产生双钥的密钥对(keyPair)、如何保存公钥的字节数组、保存私钥到文件privateKey.dat、如何用Java对象序列化保存私钥...

    JAVA上百实例源码以及开源项目源代码

    Java生成密钥的实例 1个目标文件 摘要:Java源码,算法相关,密钥 Java生成密钥、保存密钥的实例源码,通过本源码可以了解到Java如何产生单钥加密的密钥(myKey)、产生双钥的密钥对(keyPair)、如何保存公钥的字节数组、...

    CLRS:算法入门第3版中的一些练习和问题

    笔记本摘要我基础1算法在计算中的作用2入门3功能成长4分而治之5概率分析和随机算法II排序和订单统计6堆排序7快速排序8线性时间排序9中位数和订单统计III数据结构10种基本数据结构11哈希表12个二叉搜索树13棵红黑树14...

    算法,4th,塞奇威克 (Robert Sedgewick)韦恩 (Kevin Wayne), 谢路云 译.azw3

    与网络相结合:配套网站algs4.cs.princeton.edu提供了本书内容的摘要及相关的代码、测试数据、编程练习、教学课件等资源。 作者简介 作者:(美国)塞奇威克(Robert Sedgewick)^韦恩(Kevin Wayne) 译者:谢路云...

Global site tag (gtag.js) - Google Analytics