The rapid development of mobile network brings opportunities for researchers to analyze user behaviors based on largescale network traffic data. It is important for Internet Service Providers(ISP) to optimize resource...The rapid development of mobile network brings opportunities for researchers to analyze user behaviors based on largescale network traffic data. It is important for Internet Service Providers(ISP) to optimize resource allocation and provide customized services to users. The first step of analyzing user behaviors is to extract information of user actions from HTTP traffic data by multi-pattern URL matching. However, the efficiency is a huge problem when performing this work on massive network traffic data. To solve this problem, we propose a novel and accurate algorithm named Multi-Pattern Parallel Matching(MPPM) that takes advantage of HashMap in data searching for extracting user behaviors from big network data more effectively. Extensive experiments based on real-world traffic data prove the ability of MPPM algorithm to deal with massive HTTP traffic with better performance on accuracy, concurrency and efficiency. We expect the proposed algorithm and it parallelized implementation would be a solid base to build a high-performance analysis engine of user behavior based on massive HTTP traffic data processing.展开更多
Most existing multi-pattern matching algorithms are designed for single English texts leading to issues such as missed matches and space expansion when applied to Chinese-English mixed-text environments.The Hash Trie-...Most existing multi-pattern matching algorithms are designed for single English texts leading to issues such as missed matches and space expansion when applied to Chinese-English mixed-text environments.The Hash Trie-based matching machine demonstrates strong compatibility with both Chinese and English,ensuring high accuracy in text processing and subtree positioning.In this study,a novel functional framework based on the HashTrie structure is proposed and mechanically verified using Isabelle/HOL.This framework is applied to design Functional Multi-Pattern Matching(FMPM),the first functional multi-pattern matching algorithm for Chinese-English mixed texts.FMPM constructs the HashTrie matching machine using character codes and threads the machine according to the associations between pattern strings.The experimental results show that as the stored string information increases,the proposed algorithm demonstrates more significant optimization in retrieval efficiency.FMPM simplifies the implementation of the Threaded Hash Trie(THT)for Chinese-English mixed texts,effectively reducing the uncertainties in the transition from the algorithm description to code implementation.FMPM addresses the problem of space explosion Chinese-English mixed texts and avoids issues such as bound variable iteration errors.The functional framework of the HashTrie structure serves as a reference for the formal verification of future HashTrie-based algorithms.展开更多
Multi-pattern matching with wildcards is a problem of finding the occurrence of all patterns in a pattern set {p^1,… ,p^k} in a given text t. If the percentage of wildcards in pattern set is not high, this problem ca...Multi-pattern matching with wildcards is a problem of finding the occurrence of all patterns in a pattern set {p^1,… ,p^k} in a given text t. If the percentage of wildcards in pattern set is not high, this problem can be solved using finite automata. We introduce a multi-pattern matching algorithm with a fixed number of wildcards to overcome the high percentage of the occurrence of wildcards in patterns. In our proposed method, patterns are matched as bit patterns using a sliding window approach. The window is a bit window that slides along the given text, matching against stored bit patterns. Matching process is executed using bit wise operations. The experimental results demonstrate that the percentage of wildcard occurrence does not affect the proposed algorithm＇s performance and the proposed algorithm is more efficient than the algorithms based on the fast Fourier transform. The proposed algorithm is simple to implement and runs efficiently in O（n ＋ d（n/σ ）（m/w）） time, where n is text length, d is symbol distribution over k patterns, m is pattern length, and σ is alphabet size.展开更多
AAC算法(Advanced AC)是使用最为广泛的多模式串匹配算法,匹配性能高,匹配时间稳定。针对AAC算法为判定转移目标状态是否为终结状态,在匹配时每读入一个字符都要访问output表,代价较高的问题,通过两种方法改进了AAC算法。第一种方法为...AAC算法(Advanced AC)是使用最为广泛的多模式串匹配算法,匹配性能高,匹配时间稳定。针对AAC算法为判定转移目标状态是否为终结状态,在匹配时每读入一个字符都要访问output表,代价较高的问题,通过两种方法改进了AAC算法。第一种方法为拷贝自动机中的终结状态,将其附加在AAC自动机后,并将原自动机中指向终结状态的转移目标修改为附加状态,直接根据转移目标位置判断当前状态是否是终结状态,从而提出Advanced AC with Additive state(AACA)算法。第二种改进方法为将自动机中指向终结状态的状态转移值置为负数,根据转移目标的值直接判断目标状态是否为终结状态,从而提出Advanced AC with Negative state(AACN)算法。以上两种改进算法只有在发现模式匹配时才需进行output表的访问。实验数据表明:AACA和AACN算法性能均高于AAC算法,特别在中小规模匹配上,性能提升更为明显。展开更多
基金supported in part by National Natural Science Foundation of China(61671078)the Director Funds of Beijing Key Laboratory of Network System Architecture and Convergence(2017BKL-NSACZJ-06)
文摘The rapid development of mobile network brings opportunities for researchers to analyze user behaviors based on largescale network traffic data. It is important for Internet Service Providers(ISP) to optimize resource allocation and provide customized services to users. The first step of analyzing user behaviors is to extract information of user actions from HTTP traffic data by multi-pattern URL matching. However, the efficiency is a huge problem when performing this work on massive network traffic data. To solve this problem, we propose a novel and accurate algorithm named Multi-Pattern Parallel Matching(MPPM) that takes advantage of HashMap in data searching for extracting user behaviors from big network data more effectively. Extensive experiments based on real-world traffic data prove the ability of MPPM algorithm to deal with massive HTTP traffic with better performance on accuracy, concurrency and efficiency. We expect the proposed algorithm and it parallelized implementation would be a solid base to build a high-performance analysis engine of user behavior based on massive HTTP traffic data processing.
基金Supported by the National Natural Science Foundation of China(62462036,62462037)Jiangxi Provincial Natural Science Foundation(20242BAB26017,20232BAB202010)+1 种基金Cultivation Project for Academic and Technical Leader in Major Disciplines in Jiangxi Province(20232BCJ22013)the Jiangxi Province Graduate Innovation Found Project(YC2024-S214)。
文摘Most existing multi-pattern matching algorithms are designed for single English texts leading to issues such as missed matches and space expansion when applied to Chinese-English mixed-text environments.The Hash Trie-based matching machine demonstrates strong compatibility with both Chinese and English,ensuring high accuracy in text processing and subtree positioning.In this study,a novel functional framework based on the HashTrie structure is proposed and mechanically verified using Isabelle/HOL.This framework is applied to design Functional Multi-Pattern Matching(FMPM),the first functional multi-pattern matching algorithm for Chinese-English mixed texts.FMPM constructs the HashTrie matching machine using character codes and threads the machine according to the associations between pattern strings.The experimental results show that as the stored string information increases,the proposed algorithm demonstrates more significant optimization in retrieval efficiency.FMPM simplifies the implementation of the Threaded Hash Trie(THT)for Chinese-English mixed texts,effectively reducing the uncertainties in the transition from the algorithm description to code implementation.FMPM addresses the problem of space explosion Chinese-English mixed texts and avoids issues such as bound variable iteration errors.The functional framework of the HashTrie structure serves as a reference for the formal verification of future HashTrie-based algorithms.
基金Supported by the European Framework Program(FP7)(FP7-PEOPLE-2011-IRSES)the National Sci-Tech Support Plan of China(2014BAH02F03)
文摘Multi-pattern matching with wildcards is a problem of finding the occurrence of all patterns in a pattern set {p^1,… ,p^k} in a given text t. If the percentage of wildcards in pattern set is not high, this problem can be solved using finite automata. We introduce a multi-pattern matching algorithm with a fixed number of wildcards to overcome the high percentage of the occurrence of wildcards in patterns. In our proposed method, patterns are matched as bit patterns using a sliding window approach. The window is a bit window that slides along the given text, matching against stored bit patterns. Matching process is executed using bit wise operations. The experimental results demonstrate that the percentage of wildcard occurrence does not affect the proposed algorithm＇s performance and the proposed algorithm is more efficient than the algorithms based on the fast Fourier transform. The proposed algorithm is simple to implement and runs efficiently in O（n ＋ d（n/σ ）（m/w）） time, where n is text length, d is symbol distribution over k patterns, m is pattern length, and σ is alphabet size.
文摘AAC算法(Advanced AC)是使用最为广泛的多模式串匹配算法,匹配性能高,匹配时间稳定。针对AAC算法为判定转移目标状态是否为终结状态,在匹配时每读入一个字符都要访问output表,代价较高的问题,通过两种方法改进了AAC算法。第一种方法为拷贝自动机中的终结状态,将其附加在AAC自动机后,并将原自动机中指向终结状态的转移目标修改为附加状态,直接根据转移目标位置判断当前状态是否是终结状态,从而提出Advanced AC with Additive state(AACA)算法。第二种改进方法为将自动机中指向终结状态的状态转移值置为负数,根据转移目标的值直接判断目标状态是否为终结状态,从而提出Advanced AC with Negative state(AACN)算法。以上两种改进算法只有在发现模式匹配时才需进行output表的访问。实验数据表明:AACA和AACN算法性能均高于AAC算法,特别在中小规模匹配上,性能提升更为明显。
