允许错误的（汉字）字符串快速检索技术

在计算机应用的诸多领域中都会遇到字符串似检索问题。本提出了一种技术。它通过应用搜索状态向量及字符－模式匹配向量，将字符串匹配比较转化简单的整数字位运算，有效地解决了字符／汉字串的相似匹配问题，中也给出了实现算法并分析了算法的复杂性。     

改进的中文近似字符串匹配算法

BPM-BM算法在针对汉字等大字符集的近似字符串匹配时取得了很好的实际效果,但该算法在最差情况下的总体时间复杂度为O(!+nm)。而提出的IBPM-BM算法由于具有记忆的能力,保证了过滤阶段的无回溯,可以在理论上保证最差情况下的总体时间复杂度为O(!+n),而在最佳情况下的时间复杂度与BPM-BM算法一致。     

一种优化的并行汉字／字符串匹配算法

字符串检索指在一个文本Text=t1…tn中找出一个字符串Pat=p1…pm的所有出现。本文给出了在CREW/CRCW PRAM机器模型上并行检索汉字/字符串的算法, 它使用n/m。个处理机, 预处理时间为O(m+|∑|, 并行执行时间为O(m)。     

一种快速的字符串匹配算法

字符串匹配技术在许多领域里广泛应用，本文在分析了BF、BM算法以及一些重要的改进算法的基础上，提出了一种新的改进算法——BMH2C，该算法利用两个字符计算右移量并保存在二维数组里，使右移量增大，比较次数减少，有效地提高了匹配速度．最后本文还给出了几种匹配算法的测试结果。     

字符串近似匹配查询技术综述

字符串匹配是计算机科学中最经典、研究最广泛的问题之一,并且已经被应用到了众多领域当中。然而随着计算机和网络技术的飞速发展以及新问题的不断提出,人们逐渐发现在实际应用中有时更需要进行近似字符串匹配。因此,研究高效的近似字符串匹配算法具有重要的理论价值和实际意义。     

几种字符串匹配算法的分析和比较

字符串匹配技术在许多领域里被广泛应用。分析了BF、KMP、BM算法以及一些重要的改进算法,并对其性能进行了测试,为不同的应用领域采用适当的算法提供了思路。     

基于过滤的中文多模式近似字符串匹配算法

当前近似字符串匹配算法主要针对英文等中小字符集,该文针对汉字等大字符集的有效算法很少,尤其缺少适合汉字等大字符集的多模式近似匹配算法的情况,提出了一种适合汉字等大字符集的多模式近似匹配算法——MBPM-BM,通过实验证明了该算法的有效性。 近似字符串匹配;中文字符串匹配;多模式匹配;位并行运算;过滤     

基于分层存储理论模型的近似字符串匹配 并行算法研究

CUDA (Compute Unified Device Architecture)是一种重要的并行处理架构,但其具有相对复杂的线程管理机制和多重存储模块,从而使得基于CUDA的算法时间复杂度很难量化.针对这一问题,提出了一种分层存储理论模型—HMM (Hierarchical Memory Machine)模型,该模型所具有的分层存储结构可以有效地描述图形处理单元设备不同存储模块的物理特性,因此非常适用于对CUDA算法时间复杂度的量化评估.作为HMM模型的应用实例,文章提出了一种基于HMM模型的并行近似字符串匹配算法,并给出了相应算法时间复杂度的计算过程.与串行算法相比,该算法可以获得60倍以上的加速比.     

字符串匹配的自动机方法

本文讨论了字符串的连续匹配、离散匹配及求解最长公共子串的自动机算法，给出了上述各算法的形式化。     

快速中文字符串模糊匹配算法

本文解决了中文字符串模糊匹配的两个主要问题:空间问题和时间问题。目前字符串模糊匹配的两个主要方法是位向量方法和过滤方法。由于汉字众多,应用位向量方法时,需要大量空间。对于某些内存很少的小型计算机,比如嵌入式系统,这将会是一个问题。本文改进了位向量方法,使其在应用于中文字符串时,空间需求降低到约5%。本文还利用汉字非常多的特点,提出一种新的基于过滤方法的中文字符串模糊匹配算法,BPM-BM,其速度比世界上最快的算法至少提高14%;在大部分情况下,是其速度的1.5～2倍。     

一种有效的并行汉字／字符串相似检索技术

本文提出了一种有效的并行汉字／字符串相似检索技术．通过引入搜索状态向量及字符一模式匹配向量，该技术将字符串匹配比较转化为简单的整数字位运算，通过对字符串方向相反的搜索有效地实现了多处理机对汉字／字符串的并行相似检索．文中也给出了并行实现算法，同时分析了算法的复杂性．     

Faster Approximate String Matching

We present a new algorithm for on-line approximate string matching. The algorithm is based on the simulation of a nondeterministic finite automaton built from the pattern and using the text as input. This simulation uses bit operations on a RAM machine with word length w = Ω (log n) bits, where n is the text size. This is essentially similar to the model used in Wu and Manber's work, although we improve the search time by packing the automaton states differently. The running time achieved is O(n) for small patterns (i.e., whenever mk = O(log n)) , where m is the pattern length and k<m is the number of allowed errors. This is in contrast with the result of Wu and Manber, which is O(kn) for m=O(log n) . Longer patterns can be processed by partitioning the automaton into many machine words, at O(mk/w n) search cost. We allow generalizations in the pattern, such as classes of characters, gaps, and others, at essentially the same search cost. We then explore other novel techniques to cope with longer patterns. We show how to partition the pattern into short subpatterns which can be searched with less errors using the simple automaton, to obtain an average cost close to . Moreover, we allow the superimposition of many subpatterns in a single automaton, obtaining near average complexity (σ is the alphabet size). We perform a complete analysis of all the techniques and show how to combine them in an optimal form, also obtaining new tighter bounds for the probability of an approximate occurrence in random text. Finally, we show experimental results comparing our algorithms against previous work. These experiments show that our algorithms are among the fastest for typical text searching, being the fastest in some cases. Although we aim mainly at text searching, we believe that our ideas can be successfully applied to other areas such as computational biology. Received November 22, 1996; revised October 13 and December 5, 1997.     

一种基于模式最长前缀正文分割的串匹配新算法

字符串的模式匹配问题是计算机科学的基本问题之一，本文提出了基于模式最长前缀正文分割的匹配新算法(Text Divided Algorithm，以下简称TD算法)．首先在模式P中寻找最长的前缀子串subp，使其末字符在subp中只出现一次；然后根据subp末字符的特点，将正文T进行分段，按段对模式P进行匹配．新算法有以下重要的特点：1．最坏情况下，本算法有效地减少了字符重复比较的次数，从而提高了算法的匹配效率；2．匹配算法在二维匹配和不精确匹配中较易推广；3．匹配过程近似于直接算法，便于接受和理解。     

网络信息审计系统中的多模式相似匹配算法

针对网络信息审计系统的需要,提出一种新颖的基于Episode距离的快速多模式相似串匹配算法.该算法把模式串集合转换为多个有限自动机,然后利用模式串集合建立一个状态驱动器.依次用待匹配串的字符驱动状态驱动器,由状态驱动器驱动各个有限自动机,实现了中英文混合的允许插入错误的相似多模式匹配.该算法不需要匹配每个字符,能充分利用匹配过程中本次匹配不成功的信息并结合改进的文本窗机制,跳过尽可能多的字符;能够控制每个模式串的允许错误上限;匹配速度与允许插入的错误字符教k无关.该算法在信息审计、数据库、信息检索等领域有     

String Matching Over Compressed Text on Handheld Devices Using Tagged Sub-Optimal Code (TSC)

This paper presents Tagged Sub-optimal code (TSC), a new coding technique to speed up string matching over compressed databases on personal digital assistants (PDA). TSC is a variable-length sub-optimal code that supports minimal prefix property. It always determines its codeword boundary without traversing a tree or lookup table. TSC technique may be beneficial in many types of applications: speeding up string matching over compressed text, and speeding decoding process. This paper also presents two algorithms for string matching over compressed text using TSC (SCTT) and the Byte Pair Encoding (BPE) technique (SCTB). indent Several experiments were conducted to compare the performance of TSC, Byte Pair Encoding (BPE), and Huffman code. Several PDA databases with different record sizes were used: the well-known Calgary dataset and a set of small-sized PDA databases. Experimental results show that SCTT is almost twice as fast as the Huffman-based algorithm. SCTT has also the same performance in search time as the search in uncompressed databases and is faster than the SCTB algorithm. For frequently updated PDA databases such as phone books, to-do list, and memos, SCTT is the recommended method regardless of the size of the average record length, since the time required to compress the updated records using BPE poses significant delays compared to TSC.Abdeghani Bellaachia is an associate professor at the Computer Science Department, George Washington University. He received his Diploma of Engineering from Mohammadia School of Engineering in Rabat, Morocco, in 1983, the MS and Doctoral of Science degrees from the George Washington University in 1992. He was the chief architect of the Arabization of the Palm-OS platform. His research interests include data mining, multi-lingual information retrieval systems, cross-language retrieval systems, database management systems, bio-informatics, design and analysis of algorithms, handheld computing, and parallel processing.Iehab AL Rassan works for Ministry of higher education in Saudi Arabia, director of information technology department. He received his B.A. in Computer Information Systems from King Faisal University. He then received his M.S. in Computer Science from Fairleigh Dickinson University and his Doctor of Science in Computer Science from the George Washington University. His research interests include coding theories, information retrieval, string-matching algorithms, data compression, and handheld computing.     

一种用于内容过滤和检测的快速多关键词识别算法

基于字符串匹配的检测方法是内容过滤和检测系统中一类很重要的分析方法,首先分析了现有的几种快速字符串匹配算法,然后提出了一种新的多模式字符串匹配算法,并简单分析了算法的复杂性,算法在设计的过程中吸取了BM算法中跳跃的特性,采用了后缀树算法得到了最大跳跃值,采用AC算法的匹配自动机原理从而避免对搜索树内每一个字符的匹配,最后,通过具体的实验数据验证了这些算法的性能,通过实验可以看出,新算法使得检测速度有很大提高,并有效屏蔽了关键词数量的增加对检测速度的影响。     

一种改进的字符串匹配算法

基于字符串匹配的检测方法是入侵检测系统中的一种重要方法。在分析了几种常见的字符串匹配算法（BF、KMP、BM、Sunday等）的基础上,提出了一种改进的字符串匹配算法——sundayNcw。该算法使每一次匹配不成功后都能跳过尽可能多的字符以进行下一轮匹配,并且匹配次数大大减少,从而提高了匹配效率。最后,分析了该算法的性能,并用具体的实验数据给出了几种匹配算法的测试结果。     

入侵检测中一种新的快速字符串匹配算法

基于字符串匹配的检测方法是入侵检测系统中一类很重要的分析方法。文章首先分析了现有的几种准确字符串匹配算法,然后提出了一种新的多模式字符串匹配算法,并且分析了这些算法的复杂性。最后,文章用具体的实验数据来验证这些算法的性能。通过实验可以看出,新算法使得检测速度大大提高,签名容量大大增加。