改进的混合压缩算法在GPS数据压缩中的应用

1、改进的混合压缩算法在GPS数据压缩中的应用 第 3 0 卷 第 1 2 期 计 算 机 应 用 与 软 件 V o l ? 3 0 N o . 1 22 0 1 3 年 1 2 月 C o m p u t e r A p p l i c a t i o n s a n d S o f t w a r e D e c . 2 0 1 3改 进 的 混 合 压 缩 算 法 在 G P S 数 据 压 缩 中 的 应 用?周 桂 宇 马 宪 民 李 卫 斌( 西 安 科 技 大 学 电 气 与 控 制 工 程 学 院 陕 西 西 安 7 1 0 0 5 4 )摘 要 介 绍 一 种 H u f f

2、m a n 算 法 与 R L E ( R u n ? L e n g t h E n c o d i n g ) 算 法 相 结 合 的 混 合 压 缩 算 法 对 车 载 监 控 系 统 G P S 数 据 进 行 压 缩 处理 。 该 算 法 依 据 N M E A 0 1 8 3 协 议 获 取 G P S 数 据 的 统 计 特 性 , 混 合 对 重 复 的 单 字 节 数 据 的 压 缩 率 高 的 H u f f m a n 算 法 以 及 对 重 复 码 段压 缩 率 高 的 R L E 算 法 , 对 G P S 数 据 进 行 压 缩 , 提 高 数 据 的 编 码 效

3、率 , 抑 制 数 据 膨 胀 。 在 编 码 过 程 中 添 加 标 志 位 , 对 G P S 数 据 进 行 分类 处 理 , 便 于 解 码 时 有 效 识 别 两 种 算 法 的 输 出 , 保 证 对 压 缩 的 数 据 进 行 完 整 解 码 。 将 改 进 的 混 合 压 缩 算 法 应 用 于 车 载 终 端 G P S 数据 的 本 地 存 储 与 3 G 远 程 传 输 , 结 果 表 明 该 算 法 对 G P S 数 据 的 压 缩 性 能 具 有 明 显 提 高 。关 键 词 混 合 压 缩 算 法 H u f f m a n 算 法 R L E 算 法 车 载 监

4、 控 系 统 G P S 数 据中 图 分 类 号 T N 9 1 1 . 7 2 T P 3 文 献 标 识 码 A D O I : 1 0 . 3 9 6 9 / j . i s s n . 1 0 0 0 ? 3 8 6 x . 2 0 1 3 . 1 2 . 0 4 4A P P L I C A T I O N O F I M P R O V E D H Y B R I D C O M P R E S S I O NA L G O R I T H M I N G P S D A T A C O M P R E S S I O N?Z h o u G u i y u M a X i a

5、n m i n L i W e i b i n( C o l l e d g e o f E l e c t r i c a l a n d C o n t r o l E n g i n e e r i n g , X i a n U n i v e r s i t y o f S c i e n c e a n d T e c h n o l o g y , X i a n 7 1 0 0 5 4 , S h a a n x i , C h i n a )A b s t r a c t I n t h e p a p e r w e i n t r o d u c e a h y b r

6、i d c o m p r e s s i o n a l g o r i t h m , w h i c h i s t h e c o m b i n a t i o n o f H u f f m a n a l g o r i t h m a n d R L E a l g o r i t h m ,f o r c o m p r e s s i n g t h e G P S d a t a . T h i s a l g o r i t h m a c q u i r e s s t a t i s t i c a l c h a r a c t e r i s t i c s o

7、 f G P S d a t a a c c o r d i n g t o t h e N M E A 0 1 8 3 p r o t o c o l , m i x e sH u f f m a n a l g o r i t h m a n d R L E a l g o r i t h m t o c o m p r e s s G P S d a t a , t o i m p r o v e t h e c o d i n g e f f i c i e n c y a n d t o r e s t r a i n d a t a e x p a n s i o n . H u

8、f f m a na l g o r i t h m h a s h i g h c o m p r e s s i o n r a t e o n d u p l i c a t e d s i n g l e ? b y t e d a t a w h i l e R L E a l g o r i t h m h a s h i g h c o m p r e s s i o n r a t e o n d u p l i c a t e d c o d es e g m e n t . T h e f l a g b i t i s a d d e d i n t h e p r o

9、c e s s o f e n c o d i n g f o r t h e c l a s s i f i c a t i o n p r o c e s s i n g o n G P S d a t a i n o r d e r t o e f f e c t i v e l y i d e n t i f y t h eo u t p u t s o f t w o k i n d s o f a l g o r i t h m w h e n d e c o d i n g a n d t o e n s u r e t h e c o m p l e t e d e c o d

10、 i n g o f c o m p r e s s e d d a t a . T h i s i m p r o v e d h y b r i d c o m p r e s s i o na l g o r i t h m i s a p p l i e d t o l o c a l s t o r a g e a n d 3 G r e m o t e t r a n s m i s s i o n o f v e h i c l e t e r m i n a l G P S d a t a , r e s u l t s s h o w t h a t t h e a l g

11、o r i t h m h a s c l e a ri m p r o v e m e n t i n c o m p r e s s i o n p e r f o r m a n c e o f G P S d a t a .K e y w o r d s H y b r i d c o m p r e s s i o n a l g o r i t h m H u f f m a n c o m p r e s s i o n a l g o r i t h m R u n ? L e n g t h E n c o d i n g ( R L E ) a l g o r i t h

12、m V e h i c l e m o n i t o ?r i n g s y s t e m G P S d a t a续 码 段 用 其 值 和 串 长 ( 即 重 复 的 个 数 ) 来 表 示 , 连 续 相 同 的 字 符0 引 言 及 出 现 连 续 相 同 的 次 数 越 多 , 压 缩 比 越 大 , 压 缩 效 果 越 好 , 但 是由 于 R L E 算 法 只 针 对 定 长 字 符 所 设 计 的 , 因 此 在 应 用 过 程 中 具 3 车 载 监 控 系 统 中 , 车 载 终 端 需 要 获 取 G P S 信 号 ( 经 度 、 纬有 局 限 性 。 针 对

13、 G P S 数 据 格 式 特 性 , 比 如 码 头 重 复 性 、 经 度度 、 速 度 、 方 向 角 等 ) 实 时 上 传 至 监 控 中 心 , 监 控 中 心 按 通 信 协值 前 7 位 重 复 、 纬 度 前 6 位 重 复 等 , 将 这 两 种 算 法 混 合 使 用 , 对议 将 收 到 的 定 位 信 息 进 行 本 地 存 储 , 便 于 实 时 监 控 以 及 历 史 轨车 载 终 端 的 G P S 数 据 具 有 更 高 的 压 缩 率 。 改 进 的 H u f f m a n 与迹 回 放 。 在 对 车 队 进 行 监 控 管 理 过 程 中 , 多

14、辆 车 同 时 向 监 控 中R L E 混 合 压 缩 算 法 在 编 码 过 程 中 , 首 先 对 G P S 数 据 进 行 扫 描 ,心 传 输 G P S 文 件 , 在 数 据 量 大 的 情 况 下 , 对 数 据 进 行 有 效 地 压提 取 出 重 复 的 超 长 码 段 , 将 具 有 重 复 码 段 特 性 的 数 据 添 加 标 志缩 , 降 低 信 息 冗 余 , 降 低 通 信 费 用 , 减 少 对 传 输 信 道 的 占 用 是 在位 F 1 , 采 用 R L E 算 法 进 行 压 缩 处 理 ; 对 单 字 节 重 复 的 数 据 提 取数 据 传 输

15、过 程 中 需 要 解 决 的 关 键 问 题 。 由 于 G P S 数 据 的 获 取出 来 , 添 加 标 志 位 F 0 , 采 用 H u f f m a n 压 缩 算 法 进 行 处 理 ; 其 他 数 1 是 根 据 N M E A 0 1 8 3 协 议 , 由 协 议 的 码 头 重 复 性 以 及 经 纬 度 值据 直 接 拷 贝 , 不 做 任 何 处 理 。 添 加 标 志 位 的 目 的 是 便 于 在 混 合的 前 几 位 具 有 相 同 码 段 的 特 性 可 知 , G P S 文 本 数 据 具 有 码 段 以算 法 的 解 码 过 程 中 , 识 别 H

16、u f f m a n 编 码 和 R L E 编 码 , 从 而 达 到及 单 字 符 的 高 度 重 复 性 。将 G P S 数 据 进 行 混 合 编 码 以 后 能 够 完 全 还 原 数 据 。在 几 种 无 损 压 缩 算 法 中 , H u f f m a n 算 法 的 优 点 是 基 于 对 信息 中 单 个 字 符 出 现 频 率 进 行 统 计 , 输 出 的 编 码 都 是 异 字 码 头 , 保收 稿 日 期 : 2 0 1 2 - 0 7 - 2 6 。 陕 西 省 重 大 科 技 创 新 工 程 项 目 ( 2 0 1 1 Z K证 了 码 的 唯 一 可 译

17、性 。 编 码 过 程 中 , 数 据 重 复 度 越 高 , 压 缩 率 越C 0 6 - 4 ) ; 科 技 部 创 新 基 金 项 目 ( 1 1 C 2 6 2 1 6 1 0 6 0 2 4 ) 。 周 桂 宇 , 硕 士 生 , 主高 , 但 是 只 能 对 字 符 逐 个 进 行 编 码 , 这 样 在 遇 到 重 复 码 段 时 , 反研 领 域 : 数 据 压 缩 , 3 G无 线 通 信 。 马 宪 民 ( 通 讯 作 者 ) , 教 授 。 李 卫 斌 , 2 而 会 降 低 压 缩 效 率 。 R L E 算 法 的 优 点 是 将 一 个 相 同 值 的 连教 授 。

18、 1 6 8 计 算 机 应 用 与 软 件 2 0 1 3 年1 G P S 数 据 格 式 3 R L E 算 法目 前 G P S 卫 星 信 号 接 收 机 采 用 美 国 国 家 海 洋 电 子 协 会 指 定 的 在 车 载 监 控 系 统 中 , 终 端 接 收 到 的 G P S 数 据 格 式 的 码 头N M E A 0 1 8 3 协 议 通 信 标 准 。 通信标准输出的 数 据 格 式 主 要 有 G G AG P R M C 以 及 经 纬 度 信 息 的 前 几 位 均 为 重 复 码 段 , 因 此 , 采 用( G l o b a l P o s i t i

19、o n i n g S y s t e m F i x D a t a ) 位 置 测 定 系 统 定 位 信 息 、 G L LR L E 算 法 对 这 部 分 重 复 码 段 进 行 压 缩 处 理 。 R L E 算 法 的 原 理( G e o g r a p h i c P o s i t i o n ) 基 本 地 理 位 置 、 G S A ( G N S S D O Pa n d A c t i v e扫 描 出 由 字 符 构 成 的 数 据 流 中 重 复 出 现 的 码 段 , 将 重 复 的 码 段S a t e l l i t e s ) D O P 误 差 信 息

20、 与 有 效 卫 星 、 G S V ( G N S S s a t e l l i t e s i n v i e w ) 7 用 其 值 和 串 长 ( 重 复 的 个 数 ) 以 及 标 志 位 进 行 替 代 。天空 范 围 内 的 卫 星 、 R M C ( R e c o m m e n d e d M i n i m u m S p e c i f i c G N S S D a ?在 压 缩 过 程 中 , 非 重 复 字 节 可 以 有 任 意 长 度 而 不 被 控 制 字t a ) 基 本 定 位 信 息 和 V T G ( C o u r s e O v e r G r

21、 o u n d a n d G r o u n d S p e e d ) 相节 打 断 , 除 非 指 定 的 标 记 字 节 出 现 在 非 重 复 节 ( 顶 多 以 两 个 字 4 对 位 移 方 向 和 相 对 位 移 速度 。 由于车载终端需要采集基本定位节 来 编 码 ) 的 稀 有 情 况 下 , 根 据 这 个 原 理 可 以 统 计 出 重 复 出 现信 息 , 因 此 终 端 G P S 系 统 使 用 G P R M C 语 句 。 例 如 , 接 收 到 的 一 条 8 的 码 段 。 我 们 在 M i c r o s o f t V i s u a l S t

22、u d i o 2 0 0 8 环 境 下 按 照 R L E完 整 的 $ G P R M C 语 句 为 : $ G P R M C , 1 2 1 5 3 0 , A , 3 4 1 3 . 5 7 3 0 , N , 1 0 8 5 4 .压 缩 算 法 的 原 理 , 采 用 C + + 编 写 R L E 编 码 程 序 , 将 G P S 数 据 格1 6 1 3 , E , 0 . 2 8 2 , 2 6 9 . 0 2 6 , 0 3 0 5 1 2 , , 3 9 。G P R M C 语 句 一 共 占 用 7 0?个 字 节 ( 其 中 包 括 用 于 分 隔 字 符

23、的 1 1 个 逗 号 ) , 每 秒 接 收 一 次 式 中 的 “ 0 5 1 2 ” ( 月 年 ) 、 “ $ G P R M C ” ( 码 头 ) 、 “ 1 0 8 5 4 . 1 ” ( 经 度数 据 , 由 此 可 算 出 平 均 每 天 一 辆 车 的 本 地 存 储 量 约 为 5 . 8 M 。 根 值 ) 、 “ 3 4 1 3 . 5 ” ( 纬 度 值 ) 等 重 复 字 段 分 别 放 在 不 同 的 文 本 文 件据 G P S 数 据 格 式 的 特 点 , 码 头 $ G P R M C 是 重 复 的 字 段 , 在 市 区中 , 检 验 在 不 同 重

24、 复 码 段 ( 重 复 码 段 的 长 度 不 同 ) 的 情 况 下 对内 对 车 辆 进 行 监 控 , 经 度 值 的 前 7 位 字 符 , 纬 度 值 的 前 6 位 几 乎R L E 的 压 缩 率 的 影 响 , 结 果 如 表 2 所 示 。不 变 , 因 此 采 用 对 重 复 字 段 压 缩 率 高 的 R L E 算 法 与 对 单 个 字 符表 2 压 缩 算 法 对 G P S 数 据 进 行 压 缩 的 数 据的 重 复 度 高 、 压 缩 率 好 的 H u f f m a n 算 法 进 行 混 合 , 从 而 对 G P S 数重 复 码 段 的 次 数 出

25、 现 重 复 码 段 的 长 度 / b y t e 压 缩 比 / %据 进 行 压 缩 处 理 。6 4 ( 0 5 1 2 ) 4 52 H u f f m a n 算 法 6 6 ( $ G P R M C ) 6 76 7 ( 1 0 8 5 4 . 1 ) 7 8通 常 数 据 压 缩 的 性 能 指 标 是 : 编 码 失 真 度 、 压 缩 比 、 算 法 复6 6 ( 3 4 1 3 . 5 ) 6 7杂 度 、 抗 信 道 误 码 率 。 这 几 个 因 素 在 不 同 的 应 用 中 , 侧 重 要 求 也 5 由 表 2 可 以 看 出 , G P S 数 据 中 ,

26、在 重 复 码 段 出 现 的 次 数 相 等不 同 。 在 对 车 载 G P S 数 据 进 行 压 缩 的 过 程 中 , 主 要 考 虑 压 缩比 , 因 为 终 端 G P S 数 据 是 每 秒 接 收 一 次 卫 星 信 号 , 按 通 信 协 议 的 情 况 下 , 出 现 的 重 复 码 段 的 长 度 越 长 , 采 用 R L E 算 法 的 压 缩是 每 秒 上 传 一 次 定 位 信 息 , 数 据 量 大 , 编 码 失 真 度 要 求 不 是 很效 果 越 好 。高 , 在 传 输 过 程 中 采 用 3 G 无 线 通 信 , 信 道 较 G P R S 宽 ,

27、 因 此 对 抗信 号 误 码 率 的 要 求 也 不 高 。4 改 进 的 混 合 压 缩 算 法 的 实 现H u f f m a n 压 缩 算 法 的 主 导 思 想 是 扫 描 文 件 , 根 据 扫 描 出 的数 据 符 号 发 生 的 概 率 进 行 编 码 , 对 于 小 概 率 的 输 入 符 号 采 用 较混 合 压 缩 算 法 充 分 利 用 对 单 字 符 重 复 性 越 高 压 缩 率 越 好 的长 码 字 表 示 , 对 于 大 概 率 的 输 入 符 号 采 用 较 短 码 字 表 示 。 在 无H u f f m a n 压 缩 算 法 与 对 重 复 码 段

28、的 压 缩 率 高 的 R L E 算 法 进 行 有损 压 缩 的 编 码 中 , H u f f m a n 压 缩 编 码 的 平 均 码 率 可 以 接 近 信 息效 的 结 合 , 先 用 H u f f m a n 算 法 对 G P S 数 据 进 行 扫 描 , 逐 个 提 取 字源 熵 值 。 根 据 H u f f m a n 编 码 的 原 理 , 数 据 压 缩 以 后 的 最 短 长 度符 , 当 提 取 出 的 数 据 具 有 单 字 符 重 复 时 , 则 在 单 字 符 数 据 前 先 添np 6 i可 以 通 过 H = - p l o g 进 行 计 算 , 其 中 P 表 示 第 i 种 操 作加 标 志 位 F 0 , 对 其 采 用 H u f f m a n 压 缩 算 法 ; 当 提 取 出 的 数 据 具 i 2 ii = 1有 重 复 码 段 时 , 比 如 ( $ G P R M C ) 则 先 在 重 复 码 段 前 添 加 标 志 位码 在 程 序 中 出 现 的 概 率 。 通 过 H u f f m a n 压 缩 算 法 对 只 具 有 以F 1 , 对 其 采 用 R L E 算 法