使用快速分词匹配地区

需求的提出

现在的公司数据集群中,已经存在约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

Tagged: , ,

Comments are closed.