通用文本算法库的设计毕业论文.doc

通用文本算法库的设计通用文本算法库的设计 毕业论文毕业论文 目目 录录 第一章 工程结构说明 1 第二章 源程序头文件 2 Base h 2 Queue h 2 ExactMatchingS h 3 Automata h 4 ExactMatchingM h 5 RegularExpression h 5 SuffixArray h 7 ExtendKMP h 8 DES H 8 DoubleHash h 10 第三章 源程序代码文件 12 ExactMatchingS cpp 12 ExactMatchingM cpp 20 Automata cpp 23 RegularExpression cpp 26 SuffixArray cpp 33 DES cpp 39 DoubleHash cpp 45 ExtendKMP cpp 47 通用文本算法库的设计 代码清单第一章 工程结构说明 1 第一章 工程结构说明 整个工程由 10 个头文件以及 8 个源文件组成 可在 Visual C 或者 GCC 下编 译 头文件中含有所有的函数声明 而源文件中则是所有函数的具体实现 该工程的结构如下图所示 通用文本算法库 基础数据结构库 宏 基础函数库 精确模式匹配库 正则表达式库 索引结构库 其他文本算法库 通用文本算法库的设计 代码清单第二章 源程序头文件 2 第二章 源程序头文件 Base h Base h 头文件包含及基础数据结构 头文件 by 赵扶摇 include include include include include include include include include include include include using namespace std define MAX RANGE 256 define MAX PATTERN LENGTH 1024 define MAX TEXT LENGTH 100000 define MAX LOGN 20 define FAIL 1 define EPSILON 1 define MAX REP 50 define MACHINE WORD LENGTH 32 define LOG 2 0 693147 ln 2 的大小 define log 2 a int log double a LOG 2 define newArray type p size val p new type size memset p val sizeof type size Queue h Queue h 队列 头文件 by 赵扶摇 pragma once 通用文本算法库的设计 代码清单第二章 源程序头文件 3 typedef struct int curr int parent char label QueueNode 专用队列节点 define EnQueue Q rear front 0 ExactMatchingS h ExactMatchingS h 多串精确模式匹配 头文件 by 赵扶摇 pragma once include Base h Shift And 算法 void ShiftAnd char t char p int n int m int res int cnt ShiftOr 算法 void ShiftOr char T char P int n int m int res int cnt 暴力算法 void Naive char t char p int n int m int res int cnt RabinKarp 算法 void RabinKarp char t char p int n int m int res int cnt 更快的 RabinKarp 匹配版本 void RabinKarpFaster char t char p int n int m int res int cnt 自动机的建立 void Build DFA char P int m int trans MAX PATTERN LENGTH 使用前向自动机的匹配算法 void PrefixFiniteAutomata char T char P int n int m int res int cnt KMP 算法预处理函数 void preKmp char P int m int kmpNext KMP 算法 void KMP char P int m char T int n int res int cnt Horspool 算法 通用文本算法库的设计 代码清单第二章 源程序头文件 4 void Horspool char t char p int n int m int res int cnt BOM 算法 void BOM char T char P int n int m int res int cnt BNDM 算法 void BNDM char t char p int n int m int res int cnt algo3 算法 void Algo3 char T char P int n int m int res int cnt Automata h Automata h 用于多串匹配的自动机 头文件 by 赵扶摇 pragma once include Base h define TERMINAL 1 define NON TERMINAL 0 define INITIAL STATE 0 include base h 自动机的结构体 typedef struct Automata int matrix MAX RANGE int vexnum int F 50 F curr 1 m 表示终止状态所代表那些模式串 点存储着数 量 int S bool terminal char next MAX RANGE 快速获得一个节点的邻接节点 而不是做 range 次的扫 描 char first Automata 取得 trans curr c 的转移 define getTrans au curr c au matrix c curr 设置 trans curr c 的转移为 state define setTrans au curr c state au matrix c curr state 判断 curr 的特征是否为结束 define isTerminal au curr au terminal curr NON TERMINAL 设置 curr 的特征为结束 通用文本算法库的设计 代码清单第二章 源程序头文件 5 define setTerminal au curr au terminal curr TERMINAL 创建一个新的状态 返回其节点编号 define newState au s au terminal au vexnum NON TERMINAL au vexnum F 集合中的数量 define sizeFSet au curr au F 0 curr 增加集合集中的字符串 define addFSet au curr i au F sizeFSet au curr curr i define getFSet au curr i au F i curr 查找指定转移的标号 void InitAutomata Automata 初始 化自动机 void DestroyAutomata Automata int Trie char P int m int r Automata 构造 Trie rev 表示是否倒排 P 为模式串集合 m 是模式串大小集合 r 为模式串数量 F q 中包含 q 所对应的 P 中的字符串 返回 lmin void ClearAutomata Automata ExactMatchingM h ExactMatchingM h 多串精确模式匹配 头文件 by 赵扶摇 pragma once AhoCorasick 匹配算法 完全性自动机 void Aho Corasick Ad char T char P int n int m int r int res 2 int cnt SBOM 匹配算法 void SBOM char T char P int n int m int r int res 2 int cnt RegularExpression h RegularExpression h 正则表达式匹配 头文件 by 赵扶摇 pragma once include Base h 解析树的节点结构 struct PaserTreeNode 通用文本算法库的设计 代码清单第二章 源程序头文件 6 char val PaserTreeNode lchild rchild PaserTreeNode PaserTreeNode char letter PaserTreeNode left PaserTreeNode right 是否是正则表达式字符 bool isRegLetter char letter 解析正则表达式 PaserTreeNode Parse char p int 状态 struct State struct Pair State next char letter Pair char letter State next int id bool isAcc bool mark list transList State State bool isAcc void SetNFATrans char letter State next void SetDFATrans char letter State next State GetDFATrans char letter list GetNFATrans char letter 闭包集合 struct Closure list stateSet int hashValue bool containTerminal Closure void Add State s void Merge const Closure bool isEqual Closure class NFA private void Identify State s int 通用文本算法库的设计 代码清单第二章 源程序头文件 7 void setMark State s Tompson 自动机的构造的递归过程 void TompsonRecur PaserTreeNode v State public State start int stateNumber NFA NFA char reg Tompson 自动机的构造 void ConstructTompson char reg class DFA private void Identify State s int vector stateIndex tempely vector nStatesIndex public State start int stateNumber 构造函数 从 NFA 转成 DFA DFA State NFA 自动机的最小化 void Minimize DFA 匹配过程 void DFAMatcher char text int res int cnt SuffixArray h SuffixArray h 头文件 包括 Lempel ziv 压缩 by 赵扶摇 include Base h s 为原串 SA 为后缀数组 void SuffixArray char s int n int SA int Rank O n 时间内求 height 数组 void GetLcp char s int n int SA int Rank int RMQ 问题预处理 void BuildSparseTable int A int ST MAX LOGN int n 通用文本算法库的设计 代码清单第二章 源程序头文件 8 返回待查数组中最小值的编号 如果不能保证 i1 次 int LongestRepeatSubstringAtLeastK char s int n int k 在后缀数组上进行二分搜索 int BinarySearchSA int SA int lcp int rank int ST MAX LOGN char t int n char p int m 最近最小元素计算 void calNearestElement int a int n int leftElements int rightElements LEMPEL ZIV 分解算法 void LempelZiv char s int n int LZ int k ExtendKMP h ExtendKMP h 扩展 KMP 及其应用 头文件 by 赵扶摇 include Base h 下标位从开始 保证最后为 0 void PreExtKMP char p int m int lcp res 为 t i 和 p 的 lcp void ExtKMP char t int n char p int m int lcp int res 分治法 借助扩展 KMP 求平方子串数量 void MainLorentz char s int n int DES H DES h DES 加密 头文件 by 赵扶摇 include Base h class DES public int PermutedKey 8 通用文本算法库的设计 代码清单第二章 源程序头文件 9 int shiftList int keyCompress 8 int txttRightExpand 8 int initialPermutation 8 char sBox 4 16 int permutationFunc 8 int inversePermutation 8 保存个 key 每个 key 有 8 48 位 但是为了扩展与压缩的方便 我们这里用位字符进行 存储 数据靠前存储 char keys 16 8 存放明文 左半部分前四个字节 右半部分后四个字节 char txtt 8 char key 9 标记是加密还是解密 1 是加密 0 是解密 int decodeEncode 定义文件流 ifstream fileIn ofstream fileOut DES virtual DES 产生个 key void generateKey 对于一个分块数据的处理进行加密 并存储到文件中去 void txttCeil ofstream bool void solve private 所有进行表的替代的操作的集中函数 void substitution int int char int 8 char int int int 移位函数 用于实现对于某个多字节整体的移位 是函数 generateKey 的一个附属函数 void shiftKeyPar int int char 函数用于 s 盒压缩 void sBoxCompress char char 通用文本算法库的设计 代码清单第二章 源程序头文件 10 DoubleHash h DoubleHash h 双哈希应用 by 赵扶摇 include Base h struct HashString 倍增算法计算 LCP static const int d1 3 d2 4 static const int q1 990001 q2 999883 long long hvalue1 MAX TEXT LENGTH MAX LOGN long long hvalue2 MAX TEXT LENGTH MAX LOGN char s MAX TEXT LENGTH int n int logn HashString char str 建立哈希表 void BuildHashTable 两个子串的公共最长前缀 int LCP int i int j 不同串的两个子串的公共最长前缀 int LCP int i HashString 两个子串的字母序 int Compare int i int leni int j int lenj 不同串的两个子串的字母序 int Compare int i int leni HashString class LongestCommonSubstring public int n 字符串的总数量 char str 6 1000011 不同的字符串 int len 6 字符串的长度 define q1 990001 define q2 999883 define CON 2 define MAX 1000000 int hash MAX CON 这里理论上应该用链表的 不然就有水的嫌疑 通用文本算法库的设计 代码清单第二章 源程序头文件 11 char cnt MAX CON 这里存的是一组哈希值是在第几个字符串被发现的 bool ok void Add int v1 int v2 int l 把两个 hash 值分别为 v1 v2 的字符串加入哈 希表 bool Check int m 寻找 m 长的公共最长子串 通用文本算法库的设计 代码清单第三章 源程序代码文件 12 第三章 源程序代码文件 ExactMatchingS cpp ExactMatchingS cpp 单串精确模式匹配 by 赵扶摇 include Base h Shift And 算法 void ShiftAnd char t char p int n int m int res int cnt 在字符集小及 m 较小的情况为优 register unsigned int B MAX RANGE int i register unsigned int mask D cnt 0 if m 32 return Preprocessing memset B 0 sizeof B for i mask 1 i m i mask 1 Searching D 0 for i 1 i n i D D 1 1 if D ShiftOr 算法 void ShiftOr char T char P int n int m int res int cnt 在字符集小及 m 较小的情况为优 register unsigned int B MAX RANGE mask int i register unsigned int lim D cnt 0 Preprocessing memset B 0 sizeof B mask 1 lim 0 for i 1 i m i mask 1 Searching D 0 i 1 while i n D D 1 B T i if D lim res cnt i m 暴力算法 void Naive char t char p int n int m int res int cnt int i j k 0 cnt 0 for i 0 i n m i for j 1 j m j if p j t i j break if j m 1 res cnt i 1 RabinKarp 算法 void RabinKarp char t char p int n int m int res int cnt define HASH t i T t d t T i q define REHASH t i T t d t T i h T i m q int d 26 int q 65537 int offset q d int t 0 int p 0 int h int i j cnt 0 Preprocessing for i h 1 i m i h h d q for i 1 i m i HASH p i p HASH t i t Searching 通用文本算法库的设计 代码清单第三章 源程序代码文件 14 i 0 while i n m if p t for j 1 j m j if j m 1 res cnt i 1 i REHASH t i t t d t t i h t i m q 更快的 RabinKarp 匹配版本 void RabinKarpFaster char t char p int n int m int res int cnt int t 0 int p 0 int h int i j cnt 0 Preprocessing h 1 m 1 for i 1 i m i p p 1 p i t t 1 t i Searching i 0 while i n m if p t for j 1 j m j if j m 1 res cnt i 1 i t t t i h 1 t i m void Build DFA char P int m int trans MAX PATTERN LENGTH int S MAX PATTERN LENGTH 1 int curr down i int c for i 0 i MAX RANGE i trans i 0 0 S 0 FAIL for curr 1 curr m curr 通用文本算法库的设计 代码清单第三章 源程序代码文件 15 c P curr trans c curr 1 curr down S curr 1 while down FAIL if down FAIL S curr trans c down else S curr 0 for int i 0 i MAX RANGE i if trans i curr FAIL trans i curr trans i S curr 完全化 使用前向自动机的匹配算法 void PrefixFiniteAutomata char T char P int n int m int res int cnt int i curr cnt 0 int trans MAX RANGE MAX PATTERN LENGTH memset trans FAIL sizeof trans Preprocessing Build DFA P m trans Searching for i 1 curr 0 i n i curr trans T i curr if curr m res cnt i m 1 void preKmp char P int m int kmpNext int i j i 0 j kmpNext 0 1 while i 1 i j if P i P j kmpNext i kmpNext j else 通用文本算法库的设计 代码清单第三章 源程序代码文件 16 kmpNext i j KMP 算法 void KMP char P int m char T int n int res int cnt int i j kmpNext MAX PATTERN LENGTH 1 cnt 0 Preprocessing preKmp P m kmpNext Searching i j 0 while j 1 i j if i m res cnt j i i kmpNext i Horspool 算法 void Horspool char t char p int n int m int res int cnt 在字符集小及 m 较小的情况为优 int d MAX RANGE 1 int i pos cnt 0 Preprocessing for i 0 i MAX RANGE i d i m for i 1 i m 1 i d p i m i Searching pos 0 while pos 0 if i 0 res cnt pos 1 pos d t pos m 通用文本算法库的设计 代码清单第三章 源程序代码文件 17 void Oracle on line char p int m int trans MAX PATTERN LENGTH int S MAX PATTERN LENGTH 1 int k s j int c S 0 FAIL for j 0 j m j c p m j trans c j j 1 k S j while k FAIL k S k if k FAIL s 0 elses trans c k S j 1 s BOM 算法 void BOM char T char P int n int m int res int cnt int i pos current cnt 0 int trans MAX RANGE MAX PATTERN LENGTH memset trans FAIL sizeof trans Preprocessing Oracle on line P m trans Searching pos 0 while pos 0 i if current FAIL res cnt pos 1 pos i 1 BNDM 算法 通用文本算法库的设计 代码清单第三章 源程序代码文件 18 void BNDM char t char p int n int m int res int cnt 在字符集小及 m 较小的情况为优 register unsigned int B MAX RANGE 1 int last pos i temp register unsigned int D register int mask 1 32 return cnt 0 Preprocessing memset B 0 sizeof B temp 1 for i m i 0 i B p i temp temp 1 Searching pos 0 while pos 0 last i elseres cnt pos 1 D 1 pos last void algo1 char T int n char P int m int res int cnt int i j register unsigned int p 0 register unsigned int t 0 cnt 0 register int beta MACHINE WORD LENGTH m bool flag MAX RANGE 1 beta the mask to get the bit of a character register unsigned int get 1 beta 1 the mask to eliminate the bits shifted higher 通用文本算法库的设计 代码清单第三章 源程序代码文件 19 register unsigned int remove long long 1 m beta 1 for i 0 i m i p p beta P i t t beta T i i m while i n if p t if flag res cnt i else for j 0 j m j if j m res cnt i t t beta use the macro the define functions in algo2 keeps the beta and get to be implemented as constants define algo2 macro name beta get void name char T int n char P int m int mm int res int cnt int i j nn register unsigned int p 0 t 0 for i 0 i mm i p p beta P i t t beta T i nn n m mm i mm while i nn if p t for j 0 j m j if j m res cnt i mm t t beta T i define functions used in algo2 algo2 macro algo2 b1 1 1 algo2 macro algo2 b2 2 3 algo2 macro algo2 b4 4 15 algo2 macro algo2 b8 8 127 algo2 macro algo2 b16 16 127 void algo2 char T int n char P int m int res int cnt 通用文本算法库的设计 代码清单第三章 源程序代码文件 20 int mm 1 log 2 m int beta MACHINE WORD LENGTH mm if beta 1 algo2 b1 T n P m mm res cnt else if beta 2 algo2 b2 T n P m mm res cnt else if beta 4 algo2 b4 T n P m mm res cnt else if beta 8 algo2 b8 T n P m mm res cnt else if beta 16 algo2 b16 T n P m mm res cnt algo3 算法 void Algo3 char T char P int n int m int res int cnt T P cnt 0 if MAX RANGE 2 state parent 0 while EmptyQueue state DeQueue queue 获取当前状态 通用文本算法库的设计 代码清单第三章 源程序代码文件 21 curr state curr par state parent c state label down OR S par while down FAIL down OR S down if down FAIL 另一个区别是这没有奇怪的语句 OR S curr getTrans OR down c else if curr 0 OR S curr 0 重整队列 for i OR first curr i FAIL i OR next i curr state EnQueue queue state curr getTrans OR curr i state parent curr state label i delete queue return lmin void SBOM char T char P int n int m int r int res 2 int cnt int i j k index pos curr lmax 0 Automata OR for i 0 i r i lmax max lmax m i InitAutomata OR m i r int lmin Build Oracle Multiple P m r OR cnt 0 pos 0 while pos 1 curr getTrans OR curr T pos i i if curr FAIL for j 1 j sizeFSet OR curr j index getFSet OR curr j 获取匹配的模式串编号 for k 1 k m index res cnt 0 index res cnt 1 pos 1 pos i 1 void Build AC Ad char P int m int r Automata char c Trie P m r AC AC S 0 FAIL int front rear 队列最大长度不超过 PATTERN LENGTH QueueNode queue state front rear 0 InitQueue queue r m r 1 以下主要求 S 这个供给链函数 先把点入队列 state EnQueue queue state curr 0 state parent 0 while EmptyQueue state DeQueue queue 获取当前状态 curr state curr par state parent c state label down AC S par while down FAIL if down FAIL AC S curr getTrans AC down c 我认为古怪的事情终究还是发生 啦 哈哈哈 if isTerminal AC AC S curr setTerminal AC curr for int i 1 i 0 AC S curr 0 重整队列 for int i 0 i curr getTrans AC curr i state parent curr 通用文本算法库的设计 代码清单第三章 源程序代码文件 23 state label i else if curr 0 setTrans AC curr i getTrans AC AC S curr i 完全化 else setTrans AC 0 i 0 队列重整完毕 delete queue void Aho Corasick Ad char T char P int n int m int r int res 2 int cnt 完全的自动机 int curr pos i j Automata AC cnt 0 InitAutomata AC m r r Proprocessing Build AC Ad P m r AC Searching curr 0 for pos 1 pos n pos curr getTrans AC curr T pos if isTerminal AC curr for i 1 i sizeFSet AC curr i j getFSet AC curr i 获取匹配的模式串编号 res cnt 0 j res cnt 1 pos m j 1 Automata cpp include Automata h Automata au 不考虑内存分配时间构造 int matrix char next int F void InitAutomata Automata 通用文本算法库的设计 代码清单第三章 源程序代码文件 24 au terminal new bool r lmax 1 newArray char au first r lmax 1 FAIL newArray int matrix r lmax 1 MAX RANGE FAIL newArray char next r lmax 1 MAX RANGE FAIL newArray int F r lmax 1 MAX REP 0 void DestroyAutomata Automata delete next delete F delete au first delete au S delete au terminal int Trie SimpleRev char P int m int r Automata char last int lmin 65536 newArray char last r m r 1 FAIL newState au NON TERMINAL Create an initial non terminal state 0 for i 1 i 1 j 略过公共的部分 while j 1 state newState au NON TERMINAL state 为转移到的下一个状态 setTrans au curr P i j state 如果该状态还无任何转移 if au first curr FAIL au first curr P i j elseau next last curr curr P i j last curr P i j 为 curr 最新创建的转移 curr state 通用文本算法库的设计 代码清单第三章 源程序代码文件 25 j 添加新的转移 if isTerminal au curr setTerminal au curr addFSet au curr i delete last return lmin int Trie char P int m int r Automata P 为模式串集合 m 是模式串大小集合 r 为模式串数量 F q 中包含 q 所对应的 P 中的字符串 这里认为不可能用两个相同的串 int i j curr state trans char last newArray char last r m r 1 FAIL newState au NON TERMINAL Create an initial non terminal state 0 for i 1 i r i curr 0 j 1 while j m i j 略过公共的部分 while j letter letter this next next State State mark isAcc false id 1 State State bool isAcc mark false this isAcc isAcc id 1 void State SetNFATrans char letter State next transList push back Pair letter next void State SetDFATrans char letter State next for list iterator it transList begin it transList end it if it letter letter it next next return transList push back Pair letter next State State GetDFATrans char letter for list iterator it transList begin it transList end it if it letter letter return it next return NULL list State GetNFATrans char letter list res for list iterator it transList begin it transList end it if it letter letter res push back it next 通用文本算法库的设计 代码清单第三章 源程序代码文件 28 return res Closure Closure hashValue 0 containTerminal false void Closure Add State s stateSet push back s id containTerminal s isAcc hashValue s id void Closure Merge const Closure containTerminal b containTerminal hashValue b hashValue bool Closure isEqual Closure stateSet sort b stateSet sort for list iterator it stateSet begin itb b stateSet begin it stateSet end it itb if it itb return false return true void NFA Identify State s int s id last s mark true for list iterator it s transList begin it s transList end it Identify it next last void NFA setMark State s if s mark false return s mark false for list iterator it s transList begin it s transList end it setMark it next 通用文本算法库的设计 代码清单第三章 源程序代码文件 29 Tompson 自动机的构造的递归过程 void NFA TompsonRecur PaserTreeNode v State State rightStart rightTerminal if v val v val TompsonRecur v lchild leftStart leftTerminal TompsonRecur v rchild rightStart rightTerminal else if v val TompsonRecur v lchild leftStart leftTerminal if v val EPSILON isRegLetter v val start new State false terminal new State true start SetNFATrans v val terminal else if v val leftTerminal isAcc false leftTerminal transList rightStart transList delete rightStart start leftStart terminal rightTerminal else if v val start new State false terminal new State true leftTerminal isAcc false rightTerminal isAcc false start SetNFATrans EPSILON leftStart start SetNFATrans EPSILON rightStart leftTerminal SetNFATrans EPSILON terminal rightTerminal SetNFATrans EPSILON terminal else if v val start new State false terminal new State true leftTerminal isAcc false start SetNFATrans EPSILON leftStart start SetNFATrans EPSILON terminal leftTerminal SetNFATrans EPSILON leftStart leftTerminal SetNFATrans EPSILON terminal NFA NFA NFA NFA char reg 通用文本算法库的设计 代码清单第三章 源程序代码文件 30 ConstructTompson reg stateNumber 0 Identify sta