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

标签: 编程 摘要 | 发表时间:2012-08-10 18:37 | 作者:
出处:http://www.iteye.com

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 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [编程 摘要] 推荐:

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

- - ITeye博客
* 编程之美 最短摘要的生成. * 扫描过程始终保持一个[pBegin,pEnd]的range,初始化确保[pBegin,pEnd]的range里包含所有关键字. * 然后每次迭代,尝试调整pBegin和pEnd:. * 1.pBegin递增,直到range无法包含所有关键字. * 2.pEnd递增,直到range重新包含所有关键字.

自动摘要算法

- - isnowfy
当时yahoo以3000万美元的价格收购了summly的消息传出来之后,貌似大家都比变的对自动摘要产生了极大的兴趣,关于自导摘要 wiki这里有很详细的介绍,一般自动摘要比较常用的一个是摘取文章中的关键词,另一个则是摘取文章中的关键的句子,在这里我主要是介绍用textrank算法来搞句子的摘取. 相对于textrank,摘取关键句子还有一些比较简单的算法,比如 这篇,我们可以把句子分别和整篇文章做比较,相似性最大的就是关键的句子.

Web API 设计摘要

- - CSDN博客架构设计推荐文章
最近读了一本微电子书 Brian Mulloy 所著《Web API Design》感觉颇多收获,特对其内容做了个整理摘要以便回顾其观点精华以指导日常工作中的设计思路. 本文主要讲述 Web API 设计,追求一种更务实的 REST 风格. 正如作者所说 REST 是一种架构风格,而非严格的标准,没必要在形式定义上去做过多真论,到底什么才是真正的 REST.

Functional Programming for Java Developers 讀書摘要

- - ihower { blogging }
這是我之前念 Functional Programming for Java Developers 一書的摘要記錄. 這本書很薄只有90頁,是一本蠻不錯的 Functional Programming 概念入門勸敗書. 近來 Functional Programming (函數式編程,以下簡稱FP) 的重要性提昇就是為了因應 Concurrency 的需求.

Google丰富网页摘要教程

- - 月光博客
  Google的丰富网页摘要可以帮助Google搜索用户更为迅速地确定某一网站是否包含他们感兴趣的信息. Google之前已为购物、食谱、评论、视频、音乐以及活动推出了丰富网页摘要. 今天我就介绍一下丰富网页摘要在普通网站SEO优化上的使用.   对于博客来说,有两个主要的丰富网页摘要功能,一个是目录分类摘要功能,一个是作者摘要功能.

丰富网页摘要指南

- - Google China Blog
发表者:Jeremy Lubin,用户体验专家;Pierre Far,网站管理员趋势分析师. 原文: Rich snippets guidelines. 转载自: 谷歌中文网站管理员博客. 发布时间:2012年10月17日 下午 05:12:00. 传统纯文本的搜索结果网页摘要的目的是总结我们的搜索结果中某个页面的内容.

Hadoop Streaming 编程

- - 学着站在巨人的肩膀上
Hadoop Streaming是Hadoop提供的一个编程工具,它允许用户使用任何可执行文件或者脚本文件作为Mapper和Reducer,例如:. 采用shell脚本语言中的一些命令作为mapper和reducer(cat作为mapper,wc作为reducer). 本文安排如下,第二节介绍Hadoop Streaming的原理,第三节介绍Hadoop Streaming的使用方法,第四节介绍Hadoop Streaming的程序编写方法,在这一节中,用C++、C、shell脚本 和python实现了WordCount作业,第五节总结了常见的问题.

Shell编程

- - 博客园_首页
本来打算寒假回家好好学习Linux的,为以后学习嵌入式打好基础的. 回家之后的学习效率非常低,之前为了搭建Linux环境,折腾了很长时间,学到现在也就勉强才把Shell编程学完了. 今天就把自己学习的相关知识点总结整理一下. 个人感觉shell程序跟windows下的批处理文件有点像,就是将一些系统命令写进一个可执行文件中,然后执行.

软件应用的丰富网页摘要

- rokey - Google 黑板报 - Google (谷歌)中国的博客网志,走近我们的产品、技术和文化
发表者:Alejandro Goyen,产品经理. 原文:Introducing: Application Rich Snippets. 发布时间:2011年9月27日 下午 03:01:00. 丰富网页摘要可以帮助用户更为迅速地确定某一网站是否包含他们感兴趣的信息. 我们先前已为购物、食谱、评论、视频以及活动推出了丰富网页摘要,不久前,又推出了音乐丰富网页摘要.

谷奥: Google Maps 现可直接分享摘要信息到 Google+

- Woooon - 谷奥聚合——谷奥主站+谷安 aggregator
Google最近升级了Google Maps里硬又黑的导航条功能,现在当你在Google Maps里找到自己想要的地图或导航信息的时候,直接点击右上角Google+的分享按钮,即可将当前页的全部信息都分享出来. 以前你只能分享这个页的标题和链接,现在Google+会自动把Google Maps里你查询的信息也作为摘要信息分享出来,比如你的导航(上图)和定位信息(下图):.