垃圾邮件关键字过滤算法

垃圾邮件关键字过滤算法 垃圾邮件关键字过滤算法 张 溪 深 圳 市 地 铁 集 团 运 营 分 公 司 【摘 要】 本 课 题 在 对 电 子 邮 件 原 理 和 垃 圾 邮 件 的 过 滤 方 法 进 行 分 析 研 究 的 基 础 上 , 设 计 了 一 种 垃 圾 邮 件 过 滤 算 法 , 并 实 现 了 垃 圾 邮 件 过 滤 系 统 。 本 文 主 要 介 绍 了 关 键 字 过 滤 算 法 的 实 现 。 关 键 字 过 滤 是 根 据 中 文 分 词 算 法 和 关 键 字 过 滤 的 词 典 的 实 际 情 况 改 进 而 来 。 【关 键词 】 垃 圾 邮 件 过 滤 ; 关 键 字 过 滤 ; 中 图 分 类 号 : F 6 1 81 文 献 标 识 码 : A 文 章 编 号 : 引言 随 着 I n t e r n e t 的 普 及 , 电 子 邮 件 由 于 方 便 、 快 捷 、 低 成 本 的 特 点 逐 渐 取 代 了 传 统 的 通 信 方 式 , 成 为 现 代 社 会 主 要 的 通 讯 方 式 之 一 。 但 是 随 之 而 来 的 垃 圾 邮 件 也 给 人 们 带 来 了 许 多 的 不 便 与 烦 恼 , 而 且 这 个 问 题 也 日 益 的 严 重 。 邮 件 过 滤 技 术 就 是 根 据 邮 件 的 信 头 、 发 送 方 、 接 收 方 、 内 容 等 信 息 , 选 择 对 自 己 有 用 或 者 排 除 对 自 己 没 用 的 信 件 的 一 种 手 段 。 对 自 己 没 用 , 甚 至 是 有 害 的 邮 件 就 是 垃 圾 邮 件 。 垃 圾 邮 件 过 滤 技 术 就 是 最 大 程 度 上 的 把 这 类 邮 件 拒 绝 在 自 己 的 邮 箱 之 外 。 然 而 , 垃 圾 邮 件 过 滤 技 术 也 随 着 时 间 的 推 移 不 断 的 发 展 进 步 着 。 解决 垃圾 邮件 关键 字过 滤 的方 法 关 键 字 过 滤 是 基 于 规 则 过 滤 的 一 种 , 人 工 的 设 定 关 键 字 集 合 , 通 过 对 信 件 主 题 、 内 容 等 的 匹 配 来 过 滤 垃 圾 邮 件 的 一 种 机 械 的 过 滤 算 法 。 1 中文 分词 算法 说 到 关 键 字 过 滤 , 很 容 易 就 想 到 要 对 信 件 的 内 容 的 全 文 搜 索 。 传 统 的 做 法 是 将 一 篇 文 章 看 作 是 字 符 串 , 然 后 利 用 s t r i n g 类 所 提 供 的 i n d e x O f 方 法 进 行 通 配 , 看 文 章 中 是 否 有 自 己 设 定 的 关 键 字 。 如 果 有 , 则 过 滤 。 假 设 待 过 滤 的 内 容 的 字 数 是 L , 关 键 字 个 数 为 N , 那 么 过 滤 的 全 部 耗 时 为 O L N 。 在 对 传 统 算 法 研 究 和 改 进 的 基 础 上 , 有 人 提 出 了 中 文 分 词 算 法 。 这 样 就 解 决 了 传 统 算 法 在 对 全 文 通 配 时 的 浪 费 大 量 时 间 的 问 题 。 随 着 人 们 对 中 文 分 词 的 研 究 , 特 别 是 2 0 0 3 年 7 月 首 届 国 际 中 文 分 词 评 测 活 动 B a k e o 开 展 以 来 , 中 文 自 动 分 词 技 术 有 了 一 定 的 进 步 。 目 前 。 中 文 分 词 的 方 法 主 要 分 为 三 大 类 : 基 于 字 符 串 匹 配 的 分 词 方 法 、 基 于 统 计 的 分 词 方 法 和 基 于 理 解 的 分 词 方 法 。 国 内 学 者 在 上 述 三 类 分 词 方 法 基 础 上 , 展 开 了 中 文 分 词 算 法 较 深 入 的 研 究 。 刍 海 山 等 提 出 了 一 种 基 于 词 典 的 正 向 最 大 匹 配 和 逆 向 最 大 匹 配 相 结 合 的 中 文 分 词 方 案 。 可 以 高 效 、 准 确 [ 1 4 ] 地 实 现 中 文 文 档 的 主 题 词 条 的 抽 取 和 词 频 统 计 ; 应 志 伟 等 采 用 一 种 改 进 的 最 大 匹 配 法 , 提 出 了 一 种 基 于 统 计 模 型 的 算 法 来 处 理 其 中 的 多 交 集 歧 义 字 段 , 可 以 切 分 出 所 有 的 交 集 歧 义 ,[ 1 5 ] 解 决 多 音 字 的 异 读 问 题 以 及 中 文 姓 名 的 自 动 识 别 问 题 , 以 达 到 文 语 转 换 的 目 的 . 这 些 中 文 分 词 算 法 的 应 用 领 域 较 广 、 范 围 较 大 。 2 关键 字过 滤算 法原 理 本 系 统 使 用 的 关 键 字 过 滤 算 法 采 用 的 就 是 中 文 分 词 算 法 中 字 符 串 匹 配 的 分 词 方 法 的 思 路 。 不 同 的 是 , 通 常 基 于 字 符 串 匹 配 的 分 词 方 法 是 从 文 本 中 切 出 一 定 长 度 的 字 符 串 与 词 典 中 的 词 相 匹 配 , 若 匹 配 成 功 则 明 是 一 个 词 , 若 匹 配 不 成 功 则 改 变 切 出 的 字 符 串 长 度 再 匹 配 。 直 到 匹 配 成 功 , 中 文 分 词 算 法 旨 在 分 词 。 而 本 系 统 相 对 而 言 词 库 较 小 , 而 且 不 需 要 分 出 文 本 中 的 词 , 旨 在 匹 配 , 所 以 本 系 统 中 的 分 词 方 法 也 有 所 改 变 。 本 系 统 中 , 遍 历 待 查 字 符 串 , 查 询 关 键 字 首 字 串 , 当 匹 配 时 就 遍 历 关 键 字 表 , 每 个 关 键 字 都 与 待 查 字 符 串 匹 配 。 如 果 匹 配 成 功 , 则 从 成 功 词 组 的 下 一 个 字 继 续 , 如 果 不 成 功 则 , 在 原 来 字 的 下 一 个 字 继 续 。 流 程 在 下 一 节 中 将 有 详 细 的 介 绍 。 3 关键 字过 滤算 法的 数据 结构 首 先 , 我 们 定 义 两 个 字 符 串 s t r 和 p r e _ s t r , 定 义 s t r “ 一 个 广 告 的 代 理 厂 家 ” 是 待 查 询 的 字 符 串 , p r e _ s t r “ 好 人 广 他 免 ” 是 关 键 字 首 字 的 序 列 。 其 中 , 以 “ 广 ” 开 头 的 关 键 字 为 “ 广 告 好 代 理 ” 、 “ 广 场 的 ” 、 “ 广 告 ” 。 其 它 的 关 键 字 我 们 先 不 与 考 虑 。 本 系 统 中 采 用 的 是 最 大 [ 1 9 ] 长 度 匹 配 , 长 度 长 的 词 排 在 前 边 。 接 下 来 我 们 定 义 一 个 结 构 T a b l e N o d e , 这 个 结 构 存 储 对 应 的 关 键 字 首 字 以 及 指 向 以 该 字 为 首 字 的 所 有 关 键 字 数 组 的 指 针 。 定 义 如 下 : t y p e d e f s t r u c t t n o d e i n t n u m ; / / 以 该 字 为 首 字 的 词 条 数 目 K e y W o r d N o d e * f i r s t ; / / 指 向 以 该 字 为 首 字 的 关 键 字 数 组 的 指 针 T a b l e N o d e ; 我 们 还 要 定 义 一 个 结 构 K e y W o r d N o d e 来 存 储 关 键 字 和 关 键 字 的 长 度 : t y p e d e f s t r u c t n o d e i n t l e n ; / / 汉 字 的 个 数 s t r i n g k e y w o r d ; / / 关 键 字 K e y W o r d N o d e ; 定 义 : T a b l e N o d e a r r _ p r e w o r d [ 5 ] ; / / 假 设 有 最 多 5 个 不 同 的 首 字 K e y W o r d N o d e a r r _ k e y w o r d [ 1 0 ] ; / / 假 设 每 个 首 字 有 最 多 1 0 个 关 键 字 手 动 的 给 数 组 赋 值 : s t r i n g p r e _ s t r " 好 人 广 他 免 " ; / / 所 有 的 首 字 连 成 一 个 字 符 串 a r r _ p r e w o r d [ 2 ]n u m 3 ;a r r _ p r e w o r d [ 2 ]f i r s t a r r _ k e y w o r d ; a r r _ k e y w o r d [ 0 ]l e n 5 ; a r r _ k e y w o r d [ 0 ]k e y w o r d " 广 告 好 代 理 " ; a r r _ k e y w o r d [ 1 ]l e n 3 ; a r r _ k e y w o r d [ 1 ]k e y w o r d " 广 场 的 " ; a r r _ k e y w o r d [ 2 ]l e n 2 ; a r r _ k e y w o r d [ 2 ]k e y w o r d " 广 告 " ; 图 1 、本系统关键字过滤关键字结构示意图 4 关键 字过 滤算 法的 实现 关 键 匹 配 的 过 程 , 首 先 遍 历 待 查 询 字 符 串 , 在 遍 历 过 程 中 , 每 一 个 字 都 与 关 键 字 首 字 序 列 匹 配 , 如 果 匹 配 失 败 则 继 续 下 一 个 字 ; 如 果 匹 配 成 功 , 也 就 说 存 在 着 以 当 前 字 为 首 字 的 关 键 字 , 这 时 就 要 找 到 这 些 关 键 字 , 并 把 所 有 的 关 键 字 依 次 的 与 待 查 询 字 符 串 进 行 匹 配 , 如 果 成 功 则 继 续 查 找 待 查 字 符 串 中 改 关 键 字 的 下 一 个 字 , 如 果 匹 配 失 败 则 继 续 查 找 当 前 字 的 下 一 个 字 。 如 此 循 环 到 待 查 询 字 符 串 结 束 。 关键 字过 滤算 法实 验分 析 关 键 字 过 滤 算 法 的 实 现 过 程 在 上 文 中 已 经 有 了 详 细 的 介 绍 , 这 里 就 不 重 复 了 。 强 调 一 点 就 是 中 文 分 词 算 法 目 的 是 分 词 , 因 此 根 据 内 容 语 义 的 不 同 可 以 分 出 不 用 的 词 , 也 就 可 能 出 现 分 词 错 误 的 情 况 , 但 是 对 于 我 们 的 关 键 字 过 滤 算 法 来 说 就 不 存 在 “ 歧 义 ” 的 问 题 , 因 为 我 们的 目 的 是 对 字 符 串 匹 配 , 并 不 在 意 其 是 否 有 具 体 的 意 义 。 所 以 我 们 就 不 用 讨 论 其 错 误 率 , 只 要 考 察 其 匹 配 的 速 度 就 可 以 了 。 这 里 我 们 设 待 查 询 字 符 串 的 长 度 为 L , 关 键 字 首 字 序 列 的 长 度 为 N , 关 键 字 的 个 数 为 M , 最 后 设 我 们 调 用 的 系 统 函 数 f i n d 的 执 行 时 间 为 T 。 那 么 我 们 匹 配 过 程 最 最 糟 糕 的 情 况 就 是 O L N M 。对 于 查 询 函 数 f i n d 的 执 行 时 间 为 T , 在 匹 配 一 个 关 键 字 的 时 候 , 传 入 关 键 字 的 长 度 , 这 样 在 待 查 询 字 符 串 中 , 只 匹 配 到 关 键 字 的 长 度 处 即 可 , 这 样 节 省 了 很 大 一 部 分 时 间 。 对 于 关 键 字 的 个 数 M , 我 们 采 用 了 最 大 长 度 匹 配 的 原 则 , 先 匹 配 关 键 字 长 度 长 的 , 在 依 次 比 较 长 度 短 的 , 这 样 也 可 以 节 省 匹 配 时 间 。 结 束 语 本 文 对 垃 圾 邮 件 和 反 垃 圾 邮 件 技 术 做 了 简 单 的 介 绍 , 并 在 此 基 础 上 讲 述 了 我 们 实 现 的 这 个 系 统 的 整 个 思 路 和 系 统 工 作 流 程 。 着 重 介 绍 了 关 键 字 过 滤 算 法 。 通 过 实 验 的 数 据 证 明 , 我 们 的 这 个 系 统 基 本 上 达 到 了 预 期 的 目 标 , 实 现 了 较 高 效 率 的 垃 圾 邮 件 过 滤 , 相 比 其 他 的 反 垃 圾 邮 件 技 术 也 有 自 己 的 优 点 。