论文研究-位图映射法在长话流量流向分析中的应用.pdf

所需积分/C币:6 2019-07-22 18:17:30 145KB .PDF
收藏 收藏
举报

通过对传统长话流量流向分析方法进行剖析,深入研究了用户呼叫清单和流向分析的特性,进而提出了进行流量流向分析的一种优化算法——位图映射法及一系列改进算法,包括哈希位图映射算法、最优位图映射算法等。算法分析与测试结果均证明该系列算法能够有效提高处理效率。
172 计算机应用研究 2005年 2)。对每个区号(除去前面的O,剩余的数宁设为kk的位数 最大运算次数S1=2×10×int(log(1000)+1)=2 为1/≤m-2),所有以k开头的元素都赋值为1例如m2=8,103,最多需要做20亿次比较。 中国的区号为0086,则mdt-> inter[860000]=2,mdt-> inter 平均运算次数S2=2×10×nt(og2(1000+2)/2= [86999]=2具体拆分一个长途区号算法如下:取前面m11×10,平均需要做11亿次比较 位,去掉最前面的两个0剩下m2-2位,查找区号阵列mt,74优化拆分算法 得到相应元紊值/1如果/1为0,则拆分失败;否则,区号为前 最大运算次数=N平均运算次数S2=N。显然,该算 l1+2位 法在时间复杂度上比前面的算法都要好。 7算法分析 8实验结果 7.1位图映射算法 通过实验对比这几种方法在记录数为10万、20万、40万 下面分析位图映射算法拆分长途区号操作的运算规模。80万、160万、320万条情况拆分被叫号码的时间(注:测试 构建多维区号位图映射表所花费的时间很知,与区号拆分的时采用的原始数据只包含被叫号码),也可以看出位图映射法的 间相比,几乎可以忽略不计。由于比较操作的运算量比较大,优越性。实验结果如表3所示。 侒照比较次数来估算运算量。对于每一个被叫号码,做一次区 表3实验测试结果 号拆分的运算量为 记录数(厅条) 10 160 0 (1)国内区号拆分最多需要(m-n1+2)次比较,最少需 传统拆分出 117 459 分查找法 0.471.011.944.10 2|15.43 要1次比较。 位图映射淞 0.270521.042.174.12820 (2)国际区号拆分最多需要(m-n2+2)次比较,最少需 优化位图畎射法0.230480.901.833.557.09 要1次比较。 图表对比如图1(a)所示。由于传统拆分法和其他方法相 山于m-m<m2-m2最大运算次数S1=N×(m-差非常人,图1(b)为剔除传统拆分法其他方法的比较 n2+2)。此时所有话单都是打往国际方向。 假设国内通话记录占总通话记P%国际通话记录占 分查搜法优化位映射法 图珙射法传统拆分法 配映汰他北你图映 l00 总通话记录的(1-P)%则平均运算次数 16 800 s=N×((1+m-m1+2)2×P%+(1+m2-n2+2)12×(1 60 P)%) 10 例如,当N=200000000,R=1000,m2=8,n2=4m=5 n=3P=95吋, 最人运算次数S=2×103×(8-4+2)=12×10最多需要 10204080160320 记录数(万条 记录数万条) 做12亿次比较操作。 (a)凹和拆分法对比 b)去除传统拆分法的对比 平均运算次数S=2×10×((1+5-3+2)2×95%+ 图1拆分方法对比图 (1+8-4+2)2×5%)=51×10平均需要做51亿次比较 操作。 9结论 7.2传统区号拆分方法 通过算法分析和实验结果均表明,位图映射法的运算规模 面看看传统区号拆分方法的运算规模。对于每一个被比传统方法减少了上百倍的比较操作,效率是传统拆分方法的 叫号码,做一次区号拆分运算最多需要R次字符串比较,最少近百倍,比改进过后的二分查找法高一倍的效率。另外位图映 需要1次字符串比较。 射法的运算规模只与区号位数的长度有关,与区号的个数无 最大运算次数S1=n×R。 关,这也使得该算法的稳定性很好。通过该方法可以有效地进 平均运算次数S=n×(1+R)/2 行长途区号的拆分处理,快速作出长途电话的流量流间分析。 例如,当N=200000000R=1000时, 参考文献 最大运算次数S=2×10×10=2×10最多需要做2[1唐世渭.电信企业信息化中数据仓库技术的应用[]电信科 千亿次比较 学,2003,19(1):51-54 平均运算次数S2=2×10×(1+103)2=1001×10°,即[2]庄义大·离散数学与最优决策[M]·上海:复旦大学出版社, 平均需要做1001亿次比较。 2002 [3 William Ford, William Topp. Data Structures with C ++[M. Prenti ce 7.3改进的二分查找区号拆分方法 Hdl,1996.79-805 卜面分析一下改进的分查找拆分方法的运算规模。对作者简介 」每一个被叫号码,做一次区号拆分运算最多需要lrt(log杨一鸣(1964-),男,广东信宜人,博士研究生,主要研究方向为数据挖 (R)+1)次字符串比较,最少需要1次字符串比较。 掘、机器学习;潘嵘(1976-),男,广东蕾禺人,博士研究生,主要硏究方 向为数据挖掘、机器学习;黄平(1973-),男,广东开平人,高级工程师, 最大运算次数S1=N×mt((R)+1) 硕士硏究生,主要研究方向为数据仓库、数据挖掘;李磊(1951-),男 平均运算次数S=NⅪimt(lag(R)+2)/2 湖南益阳人;教授,博土生导师,主要专业为计算机软件与理论、应用数 例如,当N=200000000R=1000时 学,主要研究方向为数据库与知识库。

...展开详情
试读 3P 论文研究-位图映射法在长话流量流向分析中的应用.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-位图映射法在长话流量流向分析中的应用.pdf 6积分/C币 立即下载
    1/3
    论文研究-位图映射法在长话流量流向分析中的应用.pdf第1页

    试读已结束,剩余2页未读...

    6积分/C币 立即下载 >