使用快速分词匹配地区

标签: 分词 匹配 地区 | 发表时间:2014-04-25 16:49 | 作者:kernaling.wong
出处:http://www.iteye.com

  需求的提出

   现在的公司数据集群中,已经存在约8亿的数据,现在有一个业务的要求如下,

   1. 比如搜索"广东",则需要把包含广东以下市,区,镇,街道等的所有的关键字都给匹配出来.

   2. 同时,搜索"天河",则需要返回一个"广东 广州 天河" 这样子详细的路径出来.意思不能是简单的关键字匹配,因为它有地区的层次归属.

   3. 比如文章中含有"朝阳",则全国地区中只含有"朝阳"的,: 吉林 长春 朝阳,  辽宁 朝阳,  北京 朝阳,都要全部返回.

   4. 如果文章中,是 广州,天河区,则匹配出来的,只需要 "广东 广州 天河" 就可以了.

 

  如何做?

   其实从上面的需求来说,要实现起来其实并不困难,因为只要找一个这样子地区对应表回来,判断文章中是否包含了这些地区关键字,然后组织成分层次的地区就可以了.

   但现在的情况是数据量有8亿,在匹配这些关键字过程中,是否性能跟得上?

   另外一种,我通过类似分词的方式去匹配对比地区,类似于IK分词,但针对地区作了改进.

 

   方法中,getAllArea 是使用了分词的方式, getAllArea2 是使用了字符匹配的方式.

   大家可以直接执行 main 方法,可以对比出两者之间的性能差别,分词的结果是一样的.

 

   对比性能结果图如下:

   

 

   

   如果对源码感兴趣,可以查看下面:

 

	private static String[] areaList[] = new String[100*1000][];
	private static String[] areaNameList = new String[100*1000] ;

	private static HashMap<String, Object> hMap = new HashMap<String,Object>();
	private static HashMap<String, Set<String>> mappingSet = new HashMap<String, Set<String>>();
	
	static{
		// 会完善好这些地区列表
		InputStream in = null;
		BufferedReader reader = null;
		try {

			in = new FileInputStream("conf/all_area.txt");
			reader = new BufferedReader(new InputStreamReader(in, "utf-8"));
			String line = null;
			int index = 0;
			while ((line = reader.readLine()) != null) {
				line = line.trim();
				
				if (isEmptyString(line)){
					continue;
				}
				String areas[] = line.split("\\s+");
//				String lastArea = areas[areas.length-1];
				
				areaList[index] = areas;
				areaNameList[index] = line;
				index++;
			}

	
			for(String[] areas:areaList){		// 每个区域从大到小开始匹配
				if(areas == null){	// 数据原生数组,效率比 ArrayList 要快不少
					break;
				}
//				String areas[] = area.split("\\s+");
				String lastArea = areas[areas.length-1];
				
				loadMap(lastArea , hMap );	// 加载分词的结构 map
				
			}
			
			loadMapping(mappingSet);	// 加载分词后,对应的地区 mapping

		} catch (Exception e) {

			e.printStackTrace();

		} finally {
			if (reader != null) {
				try {
					reader.close();
				} catch (IOException e) {

					e.printStackTrace();
				}
			}
			if (in != null) {
				try {
					in.close();
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}
		
	}
	
	/**
	 * 
	 * @param input
	 * @return
	 * 			采用关键字包含形式,
	 * 			现在已经不再使用这种方式
	 * 
	 */
	
	public static String getAllArea2(String input){
//		input = input + "";
//		in
		LinkedList<String> allLinkedArea = new LinkedList<String>();	// 为了性能,使用了ArrayList, 初始化 100
		int areaIndexs = 0;
		
		for(String[] areas:areaList){		// 每个区域从大到小开始匹配
			if(areas == null){	// 数据原生数组,效率比 ArrayList 要快不少
				break;
			}
//			String areas[] = area.split("\\s+");
			String lastArea = areas[areas.length-1];
//			int lastArea = areas.length-1;
//			String lastArea = "";
//			;
			String area = null;
			area = areaNameList[areaIndexs++];
			if (   input.contains(lastArea)  ){
				
				int listIndex = -1;
				boolean notMatch = true;
				
				for(int s=0;s<allLinkedArea.size();s++){
//				for(String tmp:allLinkedArea){
					String tmp = allLinkedArea.get(s).trim();
					int t1 = tmp.split("\\s+").length;
					int t2 = area.split("\\s+").length;
					if((tmp.contains(area) || area.contains(tmp))){
						notMatch = false;
						if( t1 < t2){
							//比如三级包含了二级,则不需要加入
							listIndex = s;
							break;
						}
						// 如果是三级包含了二级,则忽略
					}
				}
				
				if(allLinkedArea.isEmpty() || notMatch){					
					allLinkedArea.add(area);
					continue;
				}
				
				if(listIndex > -1){
					allLinkedArea.remove(listIndex);
					allLinkedArea.add(area);
				}
			}
		}
		
		return allLinkedArea.toString().replaceAll("\\]|\\[", "").trim();
		
	
	}
	
	/**
	 * 
	 * @param input
	 * @return
	 * 
	 * 		基于自己实现的地区分词,
	 * 		性能:
	 * 			未去从前:
	 * 			  	普通PC 10W遍 515 个字的文本,用时 6.8 秒.
	 * 			   	折合:速度为 757352 字/s
	 *  		去从后:
	 *  			普通PC 10W遍 515 个字的文本,用时 8.7 秒.
	 *  			折合:速度为 591954  字/s
	 */
	public static String getAllArea(String input){
		
		if(input == null){
			return "";
		}
	
		char[] chars = input.toCharArray();

		int c = 0;
		HashSet<String> matchedArea = new HashSet<String>();
		HashMap<String, Object> firstMap = hMap;	// 初始化

		// 已经重新开始匹配了
		StringBuffer word = new StringBuffer();
		HashMap<String, Object> tMap = null;
		LinkedList<String> allLinkedArea = new LinkedList<String>();
		
		while ( c < chars.length ){
			String nowChar = String.valueOf(chars[c]);
			
			if ( (tMap=((HashMap<String, Object>)firstMap.get(nowChar ))) == null ){	// 中间断开了
				firstMap = hMap;	//把 Map 退回最原始的, 本层已经断开了
				word = new StringBuffer();
				
				if ((tMap=((HashMap<String, Object>)firstMap.get(nowChar ))) == null ){	// 中间断开了
					// 在最 top 层查找
					c++;
					word = new StringBuffer();
					continue;
				}
			}
			
			word.append(nowChar);
			
			if(word.length() > 1){	// 如果匹配了2个字以上
									// 找回对应的一个地区对应多个地方的情况
				Set<String> areaSet = (Set<String>)mappingSet.get(word.toString());
				
				if(areaSet != null){						
//					System.out.println(word.toString() + " ->  " + areaSet);	// debug 时用
					matchedArea.addAll(areaSet);
				}
			}
			
			c++;
			
			if(  c > chars.length  ){
				break;
			}
			
			if ( tMap.isEmpty() ){	// 最尽头了

				continue;
			}
			
			firstMap = tMap;
		
		}


		for(String area:matchedArea){
			
			int listIndex = -1;
			boolean notMatch = true;
			
			for(int s=0;s<allLinkedArea.size();s++){
//						for(String tmp:allLinkedArea){
				String tmp = allLinkedArea.get(s).trim();
				int t1 = tmp.split("\\s+").length;
				int t2 = area.split("\\s+").length;
				if((tmp.contains(area) || area.contains(tmp))){
					notMatch = false;
					if( t1 < t2){
						//比如三级包含了二级,则不需要加入
						listIndex = s;
						break;
					}
					// 如果是三级包含了二级,则忽略
				}
			}
			
			if(allLinkedArea.isEmpty() || notMatch){					
				allLinkedArea.add(area);
				continue;
			}
			
			if(listIndex > -1){
				allLinkedArea.remove(listIndex);
				allLinkedArea.add(area);
			}
		}
//		allLinkedArea.toString().replaceAll("\\]|\\[", "").trim()
		return allLinkedArea.toString().replaceAll("\\[|\\]", "").replace("\\s+", " ");
//		return "";
		
	}
	
	private static void loadMap(String values  ,HashMap<String, Object> tmpMap){
		
		if ( values.trim().isEmpty()){
			return ;
		}
		
		String nowChar = values.substring(0, 1);
		Object valObject = tmpMap.get( nowChar );
		
		String nextStr = values.substring(1, values.length());
		
		if(valObject == null){
			HashMap<String, Object> tMap = new HashMap<String, Object>();
			tmpMap.put(nowChar+"" , tMap );
			loadMap(nextStr , tMap);
		}
		
		if(valObject instanceof HashMap){
			
			HashMap<String, Object> exitsMap = (HashMap<String, Object>)valObject;	
			loadMap(nextStr , exitsMap);
		}
	}
	
	private static void loadMapping(HashMap<String, Set<String>> mappingSet){
		
		int aid = 0;
		for(String[] areas:areaList){		// 每个区域从大到小开始匹配
			if(areas == null){	// 数据原生数组,效率比 ArrayList 要快不少
				break;
			}
//			String areas[] = area.split("\\s+");
			String lastArea = areas[areas.length-1];
			
			Set<String> areaSet = (Set<String>)mappingSet.get(lastArea);
			String fullAreaName = areaNameList[aid++];
			
			if(areaSet == null){
				areaSet = new HashSet<String>();
				mappingSet.put(lastArea, areaSet);
			}
			
			areaSet.add(fullAreaName.trim());
						
		}
		
	}

	private static boolean isEmptyString(String input){
		return input == null || input.trim().isEmpty();
	}
	
	public static void main(String[] args) {
		
		
		String str = "【首款涡轮增压车型 静态评测雷克萨斯NX】在本届北京车展上,雷克萨斯带来了全新NX。雷克萨斯NX的设计灵感来源于雷克萨斯去年法兰克福车展发布的LF-NX概念车,基于RAV4平台打造的,定位低于雷克萨斯RX,以奔驰GLA、宝马X1、奥迪Q3为竞争对手。更多详情:";
		str = str + "广东新闻【雷克萨斯NX系列】4月20日,雷克萨斯全新SUV NX系列全球首发,其设计灵感来自LF-NX概念车。搭载2.0T发动机,最大功率达到243马力。雷克萨斯NX定位于紧凑型SUV,未来将与奥迪Q3、奔驰GLA等车型展开竞争";
		str = str + "【莲花SUV车型T5亮相 预计四季度上市】莲花在北京车展发布中型SUV莲花T5,莲花T5的设计同样来自于英国莲花独特的“边缘激流动力美学”设计理念,赋予了莲花T5纯正的莲花车动力美学。该车安全配置丰富,为行车安全增添了保障,预计将于今年第四季度正式上市";
		str = str + "本报记者从现场传来消息:火是从五六楼空调外挂机附近引发,目前现场已封锁,尚无人员伤亡消息。消防出动云梯车投入灭火,现在出顶层附近仍烟雾缭绕外,已看不到明火。一些附近居民纷纷拿出水盆、水桶,想参与救火,已被隔离在封锁线外。";
		str = str + "北京市车展, 明年会在广州琶洲开幕,然后向二级城市,如江门镇,佛山地区";

		System.out.println("匹配的内容字数:" + str.length());
//		str = "朝阳";

		long l = System.currentTimeMillis();
		for(int i = 0;i<100;i++){			
//			String s = getAllArea2(str);// 旧的字符包含方式
			String s = getAllArea(str);	// 现在的分词方式
//			System.out.println(s);
		}
		l = System.currentTimeMillis() - l;
		System.out.println(l + " ms");
		System.exit(0);
		
		
	}
	
	

 

 

                                                                          欢迎转载,请注明出处及原作者 kernaling.wong

                                                                                    http://kernaling-wong.iteye.com/blog/2054626





已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [分词 匹配 地区] 推荐:

使用快速分词匹配地区

- - 编程语言 - ITeye博客
   现在的公司数据集群中,已经存在约8亿的数据,现在有一个业务的要求如下,.    1. 比如搜索"广东",则需要把包含广东以下市,区,镇,街道等的所有的关键字都给匹配出来..    2. 同时,搜索"天河",则需要返回一个"广东 广州 天河" 这样子详细的路径出来.意思不能是简单的关键字匹配,因为它有地区的层次归属..

中文分词算法 之 基于词典的逆向最大匹配算法

- - ITeye博客
在之前的博文中介绍了 基于词典的正向最大匹配算法,用了不到50行代码就实现了,然后分析了词典查找算法的时空复杂性,最后使用前缀树来实现词典查找算法并做了3次优化. 下面我们看看基于词典的逆向最大匹配算法的实现,如下代码所示:. //取指定的最大长度的文本去词典里面匹配. //如果长度为一且在词典中未找到匹配,则按长度为一切分.

中文分词算法 之 基于词典的逆向最小匹配算法

- - 编程语言 - ITeye博客
在之前的博文中介绍了 基于词典的逆向最大匹配算法,比如我们切分句子: 中华人民共和国万岁万岁万万岁,使用逆向最大匹配算法的切分结果为:[中华人民共和国, 万岁, 万岁, 万万岁],可以看到,切分出来的词是很长的,粒度很粗,如果我们想要切分出很细粒度的词,该怎么办呢. 本文介绍 逆向最小匹配算法,该算法和 逆向最大匹配算法相得益彰,一个强调细粒度,一个强调粗粒度.

solr相似匹配

- - CSDN博客推荐文章
相似匹配   在我们使用网页搜索时,会注意到每一个结果都包含一个 “相似页面” 链接,单击该链接,就会发布另一个搜索请求,查找出与起初结果类似的文档. Solr 使用 MoreLikeThisComponent(MLT)和 MoreLikeThisHandler 实现了一样的功能. 如上所述,MLT 是与标准 SolrRequestHandler 集成在一起的;MoreLikeThisHandler 与 MLT 结合在一起,并添加了一些其他选项,但它要求发布一个单一的请求.

execution匹配符解析

- - CSDN博客推荐文章
Spring AOP 用户可能会经常使用 execution切入点指示符. 除了返回类型模式(上面代码片断中的ret-type-pattern),名字模式和参数模式以外, 所有的部分都是可选的. 返回类型模式决定了方法的返回类型必须依次匹配一个连接点. 你会使用的最频繁的返回类型模式是*,它代表了匹配任意的返回类型.

字符串匹配那些事(一)

- jiessie - 搜索技术博客-淘宝
本系列文章主要介绍几种常用的字符串比较算法,包括但不限于蛮力匹配算法,KMP算法,BM算法,Horspool算法,Sunday算法,fastsearch算法,KR算法等等. 本文主要介绍KMP算法和BM算法,它们分别是前缀匹配和后缀匹配的经典算法. 所谓前缀匹配是指:模式串和母串的比较从左到右,模式串的移动也是从左到右;所谓后缀匹配是指:模式串和母串的的比较从右到左,模式串的移动从左到右.

PHP正则之递归匹配

- KnightE - 风雪之隅
作者: Laruence(. 本文地址: http://www.laruence.com/2011/09/30/2179.html. 我记得早前有同事问, 正则是否能处理括号配对的正则匹配. 比如, 对于如下的待匹配的字符串:. 在以前, 这种情况, 正则无法处理, 最多只能处理固定层数的递归, 而无法处理无线递归的情况… 而在perl 5.6以后, 引入了一个新的特性: Recursive patterns, 使得这种需求可以被正确的处理..

多模匹配算法与dictmatch实现

- flychen50 - 搜索研发部官方博客
多模式匹配在这里指的是在一个字符串中寻找多个模式字符字串的问题. 一般来说,给出一个长字符串和很多短模式字符串,如何最快最省的求出哪些模式字符串出现在长字符串中是我们所要思考的. 该算法广泛应用于关键字过滤、入侵检测、病毒检测、分词等等问题中. 多模问题一般有Trie树,AC算法,WM算法等等. 可以单字、双字、全字、首尾字hash.

字符串匹配的Boyer-Moore算法

- - 阮一峰的网络日志
上一篇文章,我介绍了 KMP算法. 但是,它并不是效率最高的算法,实际采用并不多. 各种文本编辑器的"查找"功能(Ctrl+F),大多采用 Boyer-Moore算法. Boyer-Moore算法不仅效率高,而且构思巧妙,容易理解. 1977年,德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了这种算法.