• JamesLee121
    了解作者
  • Java
    开发工具
  • 10.1MB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 0
    下载次数
  • 2019-12-08 20:11
    上传日期
一种基于四叉树的空间文本索引结构,可以提高关键词的查询效率
keywordTree.zip
内容介绍
package util; import java.awt.*; import java.util.ArrayList; import java.util.BitSet; import java.util.HashMap; import java.util.Stack; import static util.GlobalDefine.global_area_id; import static util.GlobalDefine.max_contain; public class TreeNode { private Point left_bottom_point; private Point right_top_point; private int num;//记录区域对象个数 private TreeNode right_bottom_child; private TreeNode right_top_child; private TreeNode left_bottom_child; private TreeNode left_top_child; private boolean is_leaf; private ArrayList<ObjectYelp> object_list; private HashMap<String,BitSet> keyword_map; private int area_id; public TreeNode(Point left_bottom_point,Point right_top_point){ this.left_bottom_point = left_bottom_point; this.right_top_point = right_top_point; this.num = 0; this.area_id = 0; this.right_bottom_child = null; this.right_top_child = null; this.left_bottom_child = null; this.left_top_child = null; this.is_leaf = true; this.object_list = new ArrayList<>(); this.keyword_map = new HashMap<>(); } public void setAreaId(int area_id){this.area_id=area_id;} public int getArea_id(){return area_id;} public TreeNode getRight_bottom_child(){return right_bottom_child;} public TreeNode getRight_top_child(){return right_top_child;} public TreeNode getLeft_bottom_child(){return left_bottom_child;} public TreeNode getLeft_top_child(){return left_top_child;} public void setIs_leaf(boolean is_leaf){ this.is_leaf = is_leaf; } public boolean getIs_leaf(){ return is_leaf; } public ArrayList<ObjectYelp> getObject_list(){ return this.object_list; } //判断对象是否在该四叉树中 public boolean IsInNode(ObjectYelp obj){ if(obj.getLongitude()>=this.left_bottom_point.getLongitude() && obj.getLongitude()<this.right_top_point.getLongitude() && obj.getLatitude() >= this.left_bottom_point.getLatitude() && obj.getLatitude() < this.right_top_point.getLatitude()) return true; else return false; } //树节点分裂 public void split(){ //分裂之后节点由叶子节点变为中间节点 this.is_leaf = false; //this.num = -1; //按照四叉树的方法分裂出4个子节点 Point point1 = new Point(this.left_bottom_point.getLongitude(), (this.left_bottom_point.getLatitude() + this.right_top_point.getLatitude()) / 2); Point point2 = new Point((this.left_bottom_point.getLongitude() + this.right_top_point.getLongitude()) / 2 , this.right_top_point.getLatitude()); Point point3 = new Point((this.left_bottom_point.getLongitude() + this.right_top_point.getLongitude()) / 2 , (this.left_bottom_point.getLatitude() + this.right_top_point.getLatitude()) / 2); Point point4 = new Point(this.right_top_point.getLongitude(), this.right_top_point.getLatitude()); Point point5 = new Point(this.left_bottom_point.getLongitude(), this.left_bottom_point.getLatitude()); Point point6 = new Point((this.left_bottom_point.getLongitude() + this.right_top_point.getLongitude()) / 2 , this.left_bottom_point.getLatitude()); Point point7 = new Point(this.right_top_point.getLongitude(), (this.left_bottom_point.getLatitude() + this.right_top_point.getLatitude()) / 2); this.left_top_child = new TreeNode(point1, point2); this.right_top_child = new TreeNode(point3, point4); this.left_bottom_child = new TreeNode(point5, point3); this.right_bottom_child = new TreeNode(point6, point7); //重新分配对象 for(ObjectYelp obj : this.getObject_list()){ if(this.left_top_child.IsInNode(obj)){ this.left_top_child.object_list.add(obj); //this.left_top_child.num++; global_area_id++; this.left_top_child.setAreaId(global_area_id); } else if(this.left_bottom_child.IsInNode(obj)){ this.left_bottom_child.object_list.add(obj); //this.left_bottom_child.num++; global_area_id++; this.left_bottom_child.setAreaId(global_area_id); } else if(this.right_top_child.IsInNode(obj)){ this.right_top_child.object_list.add(obj); //this.right_top_child.num++; global_area_id++; this.right_top_child.setAreaId(global_area_id); } else{ this.right_bottom_child.object_list.add(obj); //this.right_bottom_child.num++; global_area_id++; this.right_bottom_child.setAreaId(global_area_id); } } this.object_list.clear(); } //空间文本对象插入 public void insert(ObjectYelp obj,TreeNode root_node){ TreeNode temp; Stack<TreeNode> node_stack = new Stack(); node_stack.push(root_node); while(!node_stack.empty()){ temp = node_stack.pop(); if(!temp.IsInNode(obj)) continue; if(temp.getIs_leaf()){ //temp.setNum(temp.getNum()+1); if(temp.object_list.size() < max_contain ) temp.object_list.add(obj); else { temp.split(); } } else{ node_stack.push(temp.left_top_child); node_stack.push(temp.left_bottom_child); node_stack.push(temp.right_top_child); node_stack.push(temp.right_bottom_child); } } } //对每个树节点生成相应的keyword倒排表 public void setArrayKey(){ int i = 0; while(i < this.object_list.size()){ int j = 0; String[] temp = this.object_list.get(i).getCategories(); while(j < temp.length){ BitSet bit = new BitSet(max_contain); bit.set(i); if(this.keyword_map.containsKey(temp[j])) bit.or(this.keyword_map.get(temp[j])); this.keyword_map.put(temp[j],bit); j++; } i++; } } //构建全局的倒排索引 public void setBITable(TreeNode root_node){ Stack<TreeNode> node_stack = new Stack<>(); TreeNode temp; node_stack.push(root_node); while(!node_stack.empty()){ temp = node_stack.pop(); if(temp.getIs_leaf()){ if(temp.object_list.size()!=0) temp.setArrayKey(); } else{ node_stack.push(temp.left_top_child); node_stack.push(temp.left_bottom_child); node_stack.push(temp.right_top_child); node_stack.push(temp.right_bottom_child); } } } //判断查询点与当前区域是否相交 public boolean intersect(Point query_point,double query_radius){ if(query_point.getLongitude()<= this.left_bottom_point.getLongitude() && query_point.getLatitude() >= this.right_top_point.getLatitude()){ if((Math.pow(query_point.getLongitude()-this.left_bottom_point.getLongitude(),2)+Math.pow(query_point.getLatitude()-this.right_top_point.getLatitude(),2))<= Math.pow(query_radius,2)){ return true; } } else if(query_point.getLongitude() >= this.left_bottom_point.getLongitude() && query_point.getLongitude()<=this.right_top_point.getLongitude() && query_point.getLatitude() >= this.right_top_point.getLatitude()){ if(Math.pow(quer
评论
    相关推荐
    • 数据结构算法与应用-C++语言描述[中文版]
      11.4.2 m 搜索 345 11.4.3 m 序B- 346 11.4.4 B-的高度 347 11.4.5 B-的搜索 348 11.4.6 B-的插入 348 11.4.7 B-的删除 350 11.4.8 节点结构 353 11.5 应用 354 11.5.1 直方图 354 11.5.2 用最优...
    • 数据结构、算法与应用--C++语言描述
      11.4.2 m 搜索 345 11.4.3 m 序B- 346 11.4.4 B-的高度 347 11.4.5 B-的搜索 348 11.4.6 B-的插入 348 11.4.7 B-的删除 350 11.4.8 节点结构 353 11.5 应用 354 11.5.1 直方图 354 11.5.2 用最优...
    • 数据结构算法与应用-C++语言描述(Recommondate)
      11.4.2 m 搜索 345 11.4.3 m 序B- 346 11.4.4 B-的高度 347 11.4.5 B-的搜索 348 11.4.6 B-的插入 348 11.4.7 B-的删除 350 11.4.8 节点结构 353 11.5 应用 354 11.5.1 直方图 354 11.5.2 用最优...
    • 数据结构(C语言描述)
      11.4.2 m 搜索 345 11.4.3 m 序B- 346 11.4.4 B-的高度 347 11.4.5 B-的搜索 348 11.4.6 B-的插入 348 11.4.7 B-的删除 350 11.4.8 节点结构 353 11.5 应用 354 11.5.1 直方图 354 11.5.2 用最优...
    • 数据结构算法与应用-C__语言描述
      11.4.2 m 搜索 345 11.4.3 m 序B- 346 11.4.4 B-的高度 347 11.4.5 B-的搜索 348 11.4.6 B-的插入 348 11.4.7 B-的删除 350 11.4.8 节点结构 353 11.5 应用 354 11.5.1 直方图 354 11.5.2 用最优...
    • 数据结构算法与应用-C++语言描述
      11.4.2 m 搜索 345 11.4.3 m 序B- 346 11.4.4 B-的高度 347 11.4.5 B-的搜索 348 11.4.6 B-的插入 348 11.4.7 B-的删除 350 11.4.8 节点结构 353 11.5 应用 354 11.5.1 直方图 354 11.5.2 用最优...
    • (朱明)数据挖掘教材
      本书的主要内容包括:数据挖掘基本知识、数据挖掘处理流程、数据预处理方法、定性概念归纳、决策分类方法、回归统计预测方法、关联规则发现方法、各种聚类算法,以及复杂数据,尤其是多媒体数据挖掘方法的最新...
    • 数据结构算法与应用(C++语言描述).rar
      11.4.2 m 搜索 345 11.4.3 m 序B- 346 11.4.4 B-的高度 347 11.4.5 B-的搜索 348 11.4.6 B-的插入 348 11.4.7 B-的删除 350 11.4.8 节点结构 353 11.5 应用 354 11.5.1 直方图 354 11.5.2 用最优...
    • postgreSQL空间SQL操作
      需要安装Postgis插件都懂的吧,资源是postgreSQL的关于空间数据字段the_geom的一些SQL示例,写的比较模糊,主要是想网上留一份以防丢失。有需要或不明白的找我吧,我研究的也不多,基本的会一点,有需要的可以一起...
    • supermarket-database.rar
      小型超市管理系统 目录 1、项目计划 1.1系统开发目的 1.2背景说明 1.3项目确立 1.4应用范围 1.5定义 1.6参考资料 2、逻辑分析与详细分析 2.1系统功能 2.2数据流图 2.3用户类型与职能 2.4系统开发步骤 2.5系统环境需求 2.6系统安全问题 3、基于UML的建模 3.1语义规则 3.2 UML模型 3.3系统实现图 4、概要设计文档 5、逻辑设计文档 6、物理设计文档 7、小结