使用快速分词匹配地区

　　需求的提出

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

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

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

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

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

　　如何做？

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

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

　　　另外一种，我通过类似分词的方式去匹配对比地区，类似于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