论文部分内容阅读
字符串匹配问题是计算机科学中十分重要且应用广泛。在我的国家巴基斯坦,使用的母语是Urdu语言。Urdu语言文本与英语语言文本完全不一样。Urdu语言文本具有自己的(己已_qI)特征。Urdu语言文本字符之间是关联的。Urdu语言文本字符采用utf-8编码,utf-8编码是变长编码方法。如果采用ASCII编码方法设计实现Urdu语言文本字符串匹配算法,那么将得不到正确的匹配位置。据我们所知,以前没有针对Urdu文本的字符串匹配算法研究的文献报道。为此,面向Urdu语言文本,研究实现有效的Urdu字符串匹配串行和并行处理具有现实意义。 本文首先分析研究Urdu语言文本的特性及其字符编码表示方法,融合采用wchar t类型和unicode编码方式以有效表示Urdu语言文本字符编码,进而研究实现针对Urdu语言文本字符串匹配的BM,KMP,BF和Sunday串行算法,并通过大量Urdu语言文本正文串和模式串的实验评估测试串行匹配算法的运行性能。实验结果比较表明,对于不同规模(长度)的Urdu语言文本正文串和模式串,总体上,针对Urdu语言文本开发实现的串行BM串匹配处理算法在4个算法中是最快速的,第二快速的是串行Sunday串匹配处理算法;此外,随着Urdu语言文本正文串的增大,KMP和BF串行匹配算法所需的运行时间增加很快,而BM和Sunday串行匹配算法所需的运行时间增加缓慢并且运行性能稳定。与KMP、Sunday和BF串匹配算法相比,采用自右至左扫描模式和正文字符的BM串匹配算法更适用于Urdu语言文本结构的大规模字符串匹配处理。 基于分组原理、多核并行计算、Pthread多线程程序设计方法,采取重叠部分正文字符策略,通过将长度n的Urdu语言正文串txt[0..n-1]划分为numthreads个正文子串txt[(i*n/num_threads..(i+1)n/num_threads+m-1]的方法,其中m为Urdu语言模式串长度,i=0~num threads-1,num threads为并行线程数,本文进一步研究实现多核计算平台上的面向Urdu语言文本的BM、KMP、BF和Sunday字符串匹配并行化算法。对于不同规模的Urdu语言文本字符串,在多核计算机上运行不同数目的并行线程的实验结果比较表明:运行的并行线程数量对于并行化串匹配算法所需的匹配时间具有明显的影响;并行BM和Sunday串匹配算法所需的运行时间远远少于并行KMP和BF串匹配算法所需的运行时间;总体来说,并行BM串匹配算法在4个并行串匹配算法中是最快速的,第二快速的是并行Sunday串匹配算法,并行BM和Sunday串匹配算法运行10个线程或者8个并行线程时,其完成Urdu语言文本字符串匹配所需时间最少;并行多线程BM和Sunday算法分别获得最高和次最高加速比。与其他3个并行化串匹配算法相比,BM多线程并行化算法更适用于Urdu语言文本结构的大规模字符串匹配并行处理。