本文主要是介绍Opening Window Time Ratio (OPW-TR) 的多线程实现 C/C++,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1.题目要求
Opening Window Time Ratio (OPW-TR) 的多线程实现C/C++
2.需求分析
近年来,GPS设备被广泛应用。根据Canalys(一个信息公司)报告, 在2006到2007一年间,GPS设备销售增加了116%。 2009年,据估计有2700万安装了GPS设备的手机被销售。截止2009年,有6.8亿的GPS用户。这是设备都能够产生、存储和传输轨迹数据。
随着基于位置的服务应用(Location basedservice, LBS)广泛使用轨迹数据,有如下3个主要问题:
(1)存储开销问题:假设轨迹数据在没有压缩的情况下,以每10s采集一次,一天仅仅4000个移动对象就会产生1Gb的数据。这样,对海量轨迹数据的存储和查询将是一个巨大的问题;
(2)传输开销问题:移动手机或是传输网络传送轨迹数据的代价是昂贵的,一般 5-7美元/M。假设跟踪4000车辆,一天的费用就是5000-7000美元,一年就是1,800,000 – 2,500,000美元。
(3)计算开销问题:随着轨迹数据规模的增加,很难快速地从轨迹数据中发现有用的模式。而减少轨迹数据的规模可以加速轨迹数据模式挖掘的速度。
这三个问题的出现使得数据压缩算法快速的发展,这里我们采用常规开放窗口算法对数据进行在线压缩
3.问题分析
l 采用开放式窗口算法标识一个潜在压缩数据段的开始点。
l 如果压缩效果好,然后尝试去压缩更长的数据段。
l 在线压缩过程从定义一段数据开始:起始点(第一个数据)到浮动点(第三个数据)。
l 如果这段数据中的每个点的误差都低于一个距离阈值,尝试移动浮动点一个点。
(1)当即将超出阈值时,两个策略中的一个被实施:
a.常规开放窗口(NormalOpening Window, NOPW): 导致阈值变化的数据点成为当前段的尾端点,成为下一个段的标签点。
b.前置开放窗口(BeforeOpening Window, BOPW):导致阈值变化的数据点的前一数据点当前段的尾端点,成为下一个段的标签点。
如果没有超越阈值,浮动一位(即窗口近一步开放),整个过程如此循环,只到所有数据被转换。
(2)常规开放窗口(NOPW)策略:阈值超过数据点是断开点,如图1所示, 在这条移动数据轨迹中总共有16个移动数据轨迹点,而我们通过NOPW算法对移动数据轨迹点进行压缩,存取其中的五个点(0,4,8,12,16)来近似的模拟出移动数据轨迹。如果压缩效果好,然后尝试去压缩更长的数据段。在线压缩过程从定义一段数据开始:起始点(第一个数据)到浮动点(第三个数据)。导致阈值变化的数据点成为当前段的尾端点,成为下一个段的标签点。如果没有超越阈值,浮动一位(即窗口近一步开放),整个过程如此循环,直到所有数据被转换。
图1
(3)前置开放窗口(BOPW)策略:在阈值超过数据点前一个数据点是断开点。OPW算法能够在有噪音的较短数据序列中进行压缩,其时间复杂度为O(n2),如图2所示。
图2
Opening Window Time Ratio (OPW-TR) 是一个对OPW的扩展。OPW-TR利用SED(synchronized euclidean distance) 代替spatial error。相对OPW, OPW-TR把时间维度考虑进去。类似OPW, OPW-TR的时间复杂度也是O(n2)
(4)集中压缩方法比较如下表所示:
4.模块设计
首先定义移动数据轨迹点的结构体
struct point
{
float x; //轨迹点的横坐标
float y; //轨迹点的纵坐标
int t; //轨迹点所处的时刻t
};
然后分为两个模块(输入模块和压缩模块)来实现移动数据轨迹压缩
(1) 输入模块
通过设置一个循来依次输入压缩轨迹经过的轨迹点
point p[16];
printf("请输入压缩轨迹经过几个点\n");
int n; //压缩轨迹经过的点
scanf_s("%d",&n);
for(i=0;i<n;i++)
{
printf("请输入第%d个轨迹点横坐标\n",i);
scanf_s("%f",&p[i].x);
printf("请输入第%d个轨迹点纵坐标\n",i);
scanf_s("%f",&p[i].y);
printf("请输入第%d个轨迹点时刻\n",i);
scanf_s("%d",&p[i].t);
}
(2) 压缩模块
分为两层循环,大循环保证这条数据轨迹上的压缩数据轨迹段的移动,判断压缩的数据轨迹段是否压缩完成,是否要开始压缩新的数据轨迹段。小循环保证其中的一段数据轨迹上数据轨迹点的移动,当数据轨迹段上所有的点都不超过阈值,则移动尾端点到下一个点,重新开始压缩新的数据轨迹段,当其中有点超过阈值,则将它压缩存储进来并作为下个数据压缩轨迹段的起始点,当所有的数据轨迹点经过这两层循环后,就能把压缩的数据点存储起来。如图3所示。
图3
for(;qishi<=13;) //大循环直到检测到最后一个数据段终止
{
if((p[zhongzhi+1].x)-p[qishi].x!=0)
{
k=(p[zhongzhi+1].y-p[qishi].y)/(p[zhongzhi+1].x-p[qishi].x);
}
else
{
k=10000; //起始点和终止点横坐标相同,设斜率为无穷大
}
b=p[qishi].y-k*p[qishi].x;
float d; //d为点到直线的距离
for(;qishi<=zhongzhi;qishi++) //循环检测起始点到终止点这段数据中每个点和阈值的关系
{
int t=qishi; //保留一个原始的起始值
d=(k*p[qishi].x-p[qishi].y+b)/(sqrt(k*k+1)); //点到直线距离公式
if(d>m) //如果点到直线的距离超过阈值,则将它设为断开点,并存储在q数组里
{
q[count].x=p[qishi].x;
q[count].y=p[qishi].y;
q[count].t=p[qishi].t;
count++;
zhongzhi=qishi+2; //新的数据段
break; //跳出循环,开始检测下一个数据段
}
else if(qishi==zhongzhi) //检测到整个数据段的点到直线距离都小于阈值
{
zhongzhi=zhongzhi+1; //将终止点往后移动一位
qishi=t; //将起始点回复成原来位置
}
}
}
5.运行结果
压缩轨迹数据点
(0,0,0)
(1,1,1)
(2,1,2)
(3,2,3)
(4,1,4)
(5,6,5)
(6,7,6)
(7,8,7)
(8 ,6, 8)
(9,1,9)
(10,2,10)
(11,6,11)
(12,10,12)
(13,7,13)
(14,6,14)
(15,1,15)
源代码及测试数据下载网址:http://download.csdn.net/detail/bryank/9532411
这篇关于Opening Window Time Ratio (OPW-TR) 的多线程实现 C/C++的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!