快速模式匹配在网络教育平台中的应用研究

网络教育平台建设的核心是教学资源库的建设,各种类型资源的快速匹配是需要频繁使用的基础功能。现有的解决方案往往使用的是BF等经典算法,匹配效率有一定的提高空间。用XML技术作为平台中各种资源描述的统一工具,通过对XML技术中DTD模式匹配方法的研究以及对模式匹配快速算法的改进,提高模式匹配的效率,从而设计出一种有效的信息模式匹配技术模型。通过仿真实验表明该模型可有效地提高网络教育平台中信息匹配的效率,进而为平台中资源的整合与模式的统一提供支持。     

最佳比较序字符串匹配算法研究和应用

为了使在数据量很大的环境下的字符匹配工作获得较高的效率，该算法利用概率加权的方法，计算出拥有最大平均跳步的目标串的比较序列，并利用该序列进行字符串的匹配工作。对该算法的效率进行了研究，并将其与利用逐字节比较技术的字符串匹配算法做了比较，找出了本算法的适用环境。     

Boyer-Moore算法的改进设计

模式匹配算法在理论计算机科学领域占有重要地位,Boyer-Moore算法被认为是日常应用中效率最高的模式 匹配算法,本文提出了富有挑战性的问题:给出了该算法的一个优化模型。     

Optimizing of large-number-patterns string matching algorithms based on definite-state automata

Because the small CACHE size of computers, the scanning speed of DFA based multi-pattern stringmatching 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 mem- ory 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.     

基于Trie树的哈希表

受到AC算法与链式哈希的启发,提出了一种基于Trie树的哈希表。该算法通过增加一个后继状态计数器,能够为后续的查找等运算提供更加简单和快速的信息。分析与实验表明该算法具有较高的效率、较强的稳定性,且降低了能耗。     

Space Curve Representation and Recognition Based on Wavelet Transform Zero-Crossings

A method to construct a representation of space curves based on the zero-crossings of the dyadic wavelet transform is introduced. The principal axes of inertia of these space curves, referred to as objects, are considered as the reference system. The representation is translation, rotation and size invariant. Instances of objects in images are recognised by matching their representations with those of the models. A string-matching technique is adapted and used for this purpose. Experimental results show that the representation is robust and efficient in extracting and matching object information.     

串的快速连续弱哈希及其应用

提出串的快速连续弱哈希(fast continuous weak Hash,简称FCWH),并研究它在理论和工程上的应用.首先提出FCWH的概念,从代数结构角度统一规划该类哈希的构造框架;然后对哈希冲突概率进行理论分析和实验数据分析,推广并加强了Rabin的相关工作;最后,通过推广串匹配的Karp-Rabin算法,应用FCWH解决顺序抽取公共子串问题(sequential extraction of common substrings,简称SECS),并据此设计快速同步协议X-Sync来解决当今宽带网络和云计算环境下文档多版本内容的实时备份检索.     

On obtaining the Boyer-Moore string-matching algorithm by partial evaluation

We present the first derivation of the search phase of the Boyer-Moore string-matching algorithm by partial evaluation of an inefficient string matcher. The derivation hinges on identifying the bad-character-shift heuristic as a binding-time improvement, bounded static variation. An inefficient string matcher incorporating this binding-time improvement specializes into the search phase of the Horspool algorithm, which is a simplified variant of the Boyer-Moore algorithm. Combining the bad-character-shift binding-time improvement with our previous results yields a new binding-time-improved string matcher that specializes into the search phase of the Boyer-Moore algorithm.     

Real-time recognition of substring repetition and reversal

Real-time multitape Turing machine algorithms are presented for recognizing the languages {wxyxz^*:|w|=r|x,|z| =t|x|} and {wxyx ^R _z ^*:|w|=r|x,|z| =t|x|} for fixedr, s, andt and for string-matching with forced mismatches.This research was supported in part by the National Science Foundation under Grant MCS77-06613 (first author) and the Bat-Sheva Fund (second author). Part of the work was conducted while the second author was at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York. A preliminary report was included in a paper the authors presented at the Seventeenth Annual IEEE Symposium on Foundations of Computer Science, Houston, Texas, October 1976.