Because the small CACHE size of computers, the scanning speed of DFA based multi-pattern string-matching algorithms slows down rapidly especially when the number of patterns is very large. For solving such problems, w...Because the small CACHE size of computers, the scanning speed of DFA based multi-pattern string-matching algorithms slows down rapidly especially when the number of patterns is very large. For solving such problems, we cut down the scanning time of those algorithms (i.e. DFA based) by rearranging the states table and shrinking the DFA alphabet size. Both the methods can decrease the probability of large-scale random memory accessing and increase the probability of continuously memory accessing. Then the hitting rate of the CACHE is increased and the searching time of on the DFA is reduced. Shrinking the alphabet size of the DFA also reduces the storage complication. The AC++algorithm, by optimizing the Aho-Corasick (i.e. AC) algorithm using such methods, proves the theoretical analysis. And the experimentation results show that the scanning time of AC++and the storage occupied is better than that of AC in most cases and the result is much attractive when the number of patterns is very large. Because DFA is a widely used base algorithm in may string matching algorithms, such as DAWG, SBOM etc., the optimizing method discussed is significant in practice.展开更多
This paper deals with the follower jamming(FJ)resistance for the frequency hopping(FH)communication system over additive white Gaussian noise(AWGN)channel.Conventional FH systems are susceptible to be jammed by FJ,and...This paper deals with the follower jamming(FJ)resistance for the frequency hopping(FH)communication system over additive white Gaussian noise(AWGN)channel.Conventional FH systems are susceptible to be jammed by FJ,and multi-pattern frequency hopping(MPFH)has good resistance to FJ.To further improve the FJ rejection capability of MPFH,we propose a wide gap multi-pattern frequency hopping(WGMPFH)scheme.WGMPFH uses channels to represent messages,and the data channel and complementary channel are hopping on orthogonal frequency slots according to wide gap FH patterns.The transmitted signal lures FJ to aim at the data channel and the complementary channel is away from FJ by adopting wide gap frequency patterns.FJ does not affect the complementary channel but increases the signal energy in the data channel,thus the effect of FJ is reduced.Its bit error rate(BER)is derived under FJ and the effects of three FJ parameters(tracking success probability,jamming duration ratio and jamming bandwidth ratio)on the BER performance of WGMPFH are investigated versus the co nventional FH/BFSK and MPFH system.Numerical and simulation results show that when under the worst-case FJ,the proposed WGMPFH outperforms the MPFH by about 1-3 dB and outperforms the conventional FH/BFSK by more than 4 dB.The proposed WGMPFH shows superior jamming rejection performance under FJ especially in severe signal-to-jamming ratio(SJR).展开更多
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.展开更多
The article presents multi-pattern formation exchange of mobile robots according to the image signals, programs motion paths using A＊ searching algorithm, and avoids the collision points of motion paths. The system c...The article presents multi-pattern formation exchange of mobile robots according to the image signals, programs motion paths using A＊ searching algorithm, and avoids the collision points of motion paths. The system contains an image system, a grid based motion platform, some wireless Radio Frequency （RF） modules and five mobile robots. We use image recognition algorithm to classify variety pattern formation according to variety Quick Response （QR） code symbols on the user interface of the supervised computer. The supervised computer controls five mobile robots to execute formation exchange and presents the movement scenario on the grid based motion platform. We have been developed some pattern formations according to game applications, such as long snake pattern formation, phalanx pattern formation, crane wing pattern formation, sword pattern formation, cone pattern formation, sward pattern tbrmation, T pattern formation, rectangle pattern formation and so on. We develop the user interface of the multi-robot system to program motion paths for variety pattern formation exchange according to the minimum displacement. In the experimental results, the supervised computer recognizes the various QR-code symbols using image system and decides which pattern formation to be selected on real-time. Mobile robots can receive the pattern formation command from the supervised computer, present the movement scenario from the original pattern formation to the assigned pattern formation on the motion platform, and avoid other mobile robots on real-time.展开更多
文摘Because the small CACHE size of computers, the scanning speed of DFA based multi-pattern string-matching algorithms slows down rapidly especially when the number of patterns is very large. For solving such problems, we cut down the scanning time of those algorithms (i.e. DFA based) by rearranging the states table and shrinking the DFA alphabet size. Both the methods can decrease the probability of large-scale random memory accessing and increase the probability of continuously memory accessing. Then the hitting rate of the CACHE is increased and the searching time of on the DFA is reduced. Shrinking the alphabet size of the DFA also reduces the storage complication. The AC++algorithm, by optimizing the Aho-Corasick (i.e. AC) algorithm using such methods, proves the theoretical analysis. And the experimentation results show that the scanning time of AC++and the storage occupied is better than that of AC in most cases and the result is much attractive when the number of patterns is very large. Because DFA is a widely used base algorithm in may string matching algorithms, such as DAWG, SBOM etc., the optimizing method discussed is significant in practice.
基金The National Natural Science Foundation of China(No.61531009,No.61471108)The National Major Projects of China(No.2016ZX03001009)。
文摘This paper deals with the follower jamming(FJ)resistance for the frequency hopping(FH)communication system over additive white Gaussian noise(AWGN)channel.Conventional FH systems are susceptible to be jammed by FJ,and multi-pattern frequency hopping(MPFH)has good resistance to FJ.To further improve the FJ rejection capability of MPFH,we propose a wide gap multi-pattern frequency hopping(WGMPFH)scheme.WGMPFH uses channels to represent messages,and the data channel and complementary channel are hopping on orthogonal frequency slots according to wide gap FH patterns.The transmitted signal lures FJ to aim at the data channel and the complementary channel is away from FJ by adopting wide gap frequency patterns.FJ does not affect the complementary channel but increases the signal energy in the data channel,thus the effect of FJ is reduced.Its bit error rate(BER)is derived under FJ and the effects of three FJ parameters(tracking success probability,jamming duration ratio and jamming bandwidth ratio)on the BER performance of WGMPFH are investigated versus the co nventional FH/BFSK and MPFH system.Numerical and simulation results show that when under the worst-case FJ,the proposed WGMPFH outperforms the MPFH by about 1-3 dB and outperforms the conventional FH/BFSK by more than 4 dB.The proposed WGMPFH shows superior jamming rejection performance under FJ especially in severe signal-to-jamming ratio(SJR).
基金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.
文摘The article presents multi-pattern formation exchange of mobile robots according to the image signals, programs motion paths using A＊ searching algorithm, and avoids the collision points of motion paths. The system contains an image system, a grid based motion platform, some wireless Radio Frequency （RF） modules and five mobile robots. We use image recognition algorithm to classify variety pattern formation according to variety Quick Response （QR） code symbols on the user interface of the supervised computer. The supervised computer controls five mobile robots to execute formation exchange and presents the movement scenario on the grid based motion platform. We have been developed some pattern formations according to game applications, such as long snake pattern formation, phalanx pattern formation, crane wing pattern formation, sword pattern formation, cone pattern formation, sward pattern tbrmation, T pattern formation, rectangle pattern formation and so on. We develop the user interface of the multi-robot system to program motion paths for variety pattern formation exchange according to the minimum displacement. In the experimental results, the supervised computer recognizes the various QR-code symbols using image system and decides which pattern formation to be selected on real-time. Mobile robots can receive the pattern formation command from the supervised computer, present the movement scenario from the original pattern formation to the assigned pattern formation on the motion platform, and avoid other mobile robots on real-time.
