面向中英文混合环境的多模式匹配算法

分析了中英文混合环境下多模式匹配的特点,以及已有多模式匹配算法应用于中英文混合环境时的不足,给出并证明了中英文混合环境下多模式匹配算法的性能定理,提出了一种适合于中英文混合环境的基于线索完全哈希Trie结构的多模式匹配算法.该算法扩展了标准Trie结构,以中英文字符内码为键值构造完全哈希Trie匹配机,并利用模式串之间的关系对Trie匹配机进行线索化.理论分析与实验结果表明,所提出的算法在匹配中无需复杂的哈希运算,不需要回溯匹配指针,在中英文混合环境下能够进行正确、高效的匹配,而且不存在空间膨胀问题,具有较低的空间与时间复杂度,有较大理论与应用价值.     

一种适合于GPU计算的并行后缀数组构造算法

后缀数组广泛应用于序列分析、字符串匹配和文本压缩,近年来,有关后缀数组构造和应用算法的不断探索构成了计算机科学中一个非常活跃的研究领域.在对现有串行算法进行了分析和对比之后,提出了一种新的、简洁的适合于GPU计算的并行后缀数组倍增构造算法,以排序方法替代传统的分组策略,不但能独立完成后缀数组的并行构造,还可与现存的串行倍增算法结合使用,以达到最高的执行效率.实验结果表明该算法在解决实际应用问题时,具有易于实现、执行速度快和可扩展性强等优点,尤其在处理小字符集的数据时效率更高.     

AprioriTid算法的MapReduce并行化实现

为解决AprioriTid算法对大数据执行效率不高的问题,根据Hadoop平台的MapReduce模型,分析了AprioriTid算法的并行化方法,给出了并行化的主要步骤和Map、Reduce函数的描述。与串行的AprioriTid算法相比,并行算法利用了多个节点的计算能力,缩短了从大数据集中挖掘关联规则的时间。对并行算法的性能进行了测试,实验结果表明,并行AprioriTid算法具有较高的执行效率和较好的可扩展性。     

基于Hadoop平台的TFIDF算法并行化研究

针对大数据集下文本分类算法在单机上训练和测试过程效率低下的问题,提出了基于Hadoop分布式平台的TFIDF文本分类算法,并给出了算法实现的具体流程。通过MapReduce编程模型实现了考虑到词在文档中位置的并行化TFIDF文本分类算法,并与传统串行算法进行了对比,同时在单机和集群模式下进行了实验。实验表明,使用并行化的TFIDF文本分类算法可实现对海量数据的高速有效分类,并使算法性能得到优化。     

基于并行计算的快速Dijkstra算法研究

通过分析经典Dijkstra算法的思想和执行流程,对多标号的Dijkstra算法给出新证明,以此作为理论依据对Dijkstra算法进行了多标号的串行与并行优化。对于正则树,给出了经典Dijkstra算法、串行多标号Dijkstra算法和并行多标号Dijkstra算法的时间复杂度排序。针对优化算法的特点,设计出四种实验,采用运行时间和并行加速比作为优化指标,考核三种算法的效率。仿真实验表明：对顶点数大于6 000的稠密图和稀疏图（正则树）,多标号并行算法优于串行算法,且优化效果明显;对于正则树,优化效果分别与深度、出度成正相关。     

WCCS环境下连续r位串匹配算法及其并行化研究

通过将免疫系统中连续r位匹配规则引入到串匹配算法中,在传统KMP串匹配算法的基础上提出了r-KMP算法,该算法使用匹配闽值r来控制文本串与模式串的匹配程度.然后在WCCS(Windows compute cluster server)平台下部署了并行化的r-KMP算法,通过实验分析了算法的性能和时间复杂度.实验结果表明,该算法能有效的控制串匹配程度,它的并行化减少了执行时的运算时间,提高了串匹配效率.     

一种实时并行图象匹配结构的设计

针对在传统串行结构上执行图象匹配算法时影响执行速度提高的原因，通过分析图象匹配算法的内部流水性，并行性，提出了一种加速执行图象匹配算法的硬件并行结构，通过引入流水线数据延迟及多个并行处理单元。该结构使得重复读取存贮器的操作次数大大减少，从而加速图象匹配操作。文中给出了该模型的实现框图，并计算了采用该结构执行图象匹配算法所需计算表明，对大小为６４×６４的搜索象，３２×３２的模板象。该结构可在不到９ｍ     

多核并行编程技术在中文分词程序优化中的应用

为了充分利用多核处理器的硬件资源和计算能力,提出了多核并行编程技术在中文分词程序中的优化方案.根据中文分词最大正向匹配算法的特点,由传统的串行程序,改为并行程序.利用多核并行编程模式的思想,设计了一个混合并行编程模式,通过Intel的性能分析工具,找出了该算法的热点和瓶颈,对其进行优化.实验结果表明,优化过后的执行时间较原来串行程序的执行时间缩短了50%～60%,同时提高了程序的加速性能,取得了良好的效果.     

Shape Context算法的CUDA并行化实现

研究了Shape Context形状识别串行算法,在此基础上针对CUDA平台多处理器流水线特性,将Shape Context算法进行适应CUDA特性的并行化改造,使得算法并行化后具有更高的执行精度,并达到了130倍以上的加速比,较大程度满足人脸识别海量数据的实时处理需求.     

基于Spark Streaming的流式并行文本校对

互联网的高速发展催生了海量网络文本,这对传统的串行文本校对算法提出了新的性能挑战。尽管近年来文本自动校对任务受到了较多关注,但相关研究工作多集中于串行算法,鲜有涉及校对的并行化。文中首先对串行校对算法进行泛化,给出一种串行校对的通用框架,然后针对串行校对算法处理大规模文本存在的耗时长的不足,提出3种通用的文本校对并行化方法:1)基于多线程的线程并行校对,它基于线程池的方式实现段落和校对功能的同时并行;2)基于Spark MapReduce的批处理并行校对,它通过RDD并行计算的方式实现段落的并行校对;3)基于Spark Streaming流式计算框架的流式并行校对,它通过将文本流的实时计算转为一系列小规模的基于时间分片的批处理作业,有效避免了固定开销,显著缩短了校对时延。由于流式计算兼有低时延和高吞吐的优势,文中最后选用流式校对来构建并行校对系统。性能对比实验表明,线程并行适合校对小规模文本,批处理并行适合大规模文本的离线校对,流式并行校对有效减少了约110s的固定时延,相比批处理校对,采用Streaming计算框架的流式校对取得了极大的性能提升。     

多重CCA算法的柬汉双语词向量构建方法

针对现有双语词向量研究方法获取双语词向量需要用到大量双语平行文本,对于柬汉双语而言存在着平行文本不足的关键问题,而英语作为通用语言,英语-汉语以及英语-柬埔寨语双语平行文本较多且容易获得,因此在典型相关分析跨语言词向量模型上作出进一步改进,提出以英语为中间语言的基于多重CCA算法的汉柬双语词向量构建方法。通过将英语、汉语词向量投影至汉-英向量空间,将英语、柬语词向量投影至柬-英向量空间,根据CCA算法分别得到英-汉、英-柬双语词向量;以英语作为中间词并结合部分实验室构建的柬汉双语电子词典将上一步得到的英-柬、英-汉双语词向量投影至第三方同一向量空间中,再次根据CCA算法得到柬语和汉语在新向量空间中的投影转换矩阵;得到柬英汉多语词向量,多语词向量中包含有柬汉双语词向量。与传统方法相比,该方法解决了当前其他模型所面临的初始柬汉平行文本稀缺的问题,且获得较高的柬汉双语词向量。     

基于多角度信息交互的文本语义匹配模型

现有的文本语义匹配方法大多基于简单的注意力机制进行交互,较少考虑文本自身结构信息和文本之间原始信息的的交互。针对2个中文文本的语义匹配问题,构建一个多角度信息交互的文本匹配模型MAII。分别从颗粒、局部、全局3个角度计算2个文本深层次的语义交互矩阵,同时考虑语序信息之间和结构信息之间的交互以及文本内部的依赖关系,从而得到含有丰富信息的语义向量,并通过语义推理计算出两文本之间的语义匹配度。实验结果表明,相比在英文数据集上表现良好的DSSM、ESIM和DIIN模型,MAII模型在CCKS 2018问句匹配大赛的中文数据集上达到77.77%的准确率,表现出更好的匹配性能。     

中文短文本聚合模型研究

中文短文本聚合的目的是将两个数据集中属于同一对象的短文本信息进行匹配关联,同时要避免匹配不属于同一对象的短文本信息,这项研究对于多源异构的短文本数据资源整合具有重要的理论和现实意义.提出了一种有效的中文短文本聚合模型,通过快速匹配和精细匹配两个关键步骤可以大幅度降低匹配的候选对数量,并保证匹配的精度.针对传统短文本相似度算法的不足,提出了一种新颖的广义Jaro-Winkler相似度算法,并从理论上分析了该算法的参数特性.通过对不同数据集上的商户信息数据进行聚合实验,结果表明,新算法与传统算法相比,在匹配准确率和稳定性上具有最优的性能.     

基于词或词组长度和频数的短中文文本关键词提取算法

中文文本的关键词提取是自然语言处理研究中的难点。国内外大部分关键词提取的研究都是基于英文文本的, 但其并不适用于中文文本的关键词提取。已有的针对中文文本的关键词提取算法大多适用于长文本,如何从一段短中文文本中准确地提取出具有实际意义且与此段中文文本的主题密切相关的词或词组是研究的重点。 提出了面向中文文本的基于词或词组长度和频数的关键词提取算法,此算法首先提取文本中出现频数较高的词或词组,再根据这些词或词组的长度以及在文本中出现的频数计算权重,从而筛选出关键词或词组。该算法可以准确地从中文文本中提取出相对重要的词或词组,从而快速、准确地提取此段中文文本的主题。实验结果表明,基于词或词组长度和频数的中文文本关键词提取算法与已有的其他算法相比,可用于处理中文文本,且具有更高的准确性。     

基于情感时序距离和转折同化的文本情感分类

考虑到中文评价文本的整体情感倾向性与其表达的情感顺序有很大关系,且在具有情感倾向的中文文本中,越是靠近文本最后所表达的情感倾向,对于整个文本的情感分类影响越大。因此对于情感倾向表达不明显或者表达不单一的短文本,通过考虑文本中情感节点出现的顺序以及情感转折同化来对文本进行情感分类。在来自某购物网站爬取的中评评价文本数据集上的实验结果显示,提出的分类方法明显高于单纯基于词特征的支持向量机（SVM）分类器。     

基于GLSTM和Attention的中文事件要素提取

事件信息抽取是信息抽取任务中的一种,旨在识别并提出一个事件的触发词和元素.由于容易受到数据稀疏的影响,事件要素的抽取是中文事件抽取任务中的一个难点,研究的重点在于特征工程的构建.中文语法相较英文要复杂许多,所以捕获英文文本特征的方法在中文任务中效果并不明显,而目前常用的神经网络模型仅考虑了上下文信息,不能兼顾词法和句法...     

Chicon—a Chinese text manipulation language

Text processing is an important computer application. Due to its importance, a number of text manipulation programming languages have been devised (e.g. Icon). These programming languages are very useful for applications such as natural language processing, text analysis, text editing, document formatting, text generation, etc. However, they were mainly designed to handle English texts, and are ineffective for Chinese. This is because English and Chinese texts are represented very differently in a computer. An English character is mainly represented in 7-bit ASCII, and its Chinese counterpart commonly in 16-bit GB or BIG-5. This difference makes direct application of English-based text manipulation programming languages to Chinese erroneous, e.g. application of Icon to reverse a string of Chinese characters. In this paper, a new dialect of Icon, referred to as Chicon (i.e. Chinese Icon), is proposed. In the design of Chicon, new data types were introduced to differentiate pure English and English/Chinese mixed texts. In addition, existing Icon text manipulation functions were modified to account for Chinese texts. Experiments have shown that Chicon not only could overcome the problems of Chinese processing in Icon, but its execution speed was actually superior to Icon in handling Chinese. Furthermore, application of Chicon to a real sized problem, namely word segmentation, has proved that the language is practical. © 1998 John Wiley & Sons, Ltd.     

一种用于中文文本查重的双因子相似度算法

为了提高搜索引擎的检索效率以及加强知识产权保护,结合汉语语言学以及自然语言处理的研究成果,提出了一种用于中文文本查重的算法.通过引入"动词中心词"的概念,扩展停用词的范围,将文本中的部分动词组成动词序列作为文本特征串,结合串匹配算法,计算出中文文本间语法相似性.同时根据IFIDF方法提取文本特征并进行权重计算,计算出中文文本间的语义相似性.结合文本间语法相似性和语义相似性得到文章的相似度,可以判断两篇中文内容的相似性,有效地进行重稿检测.     

融合多粒度信息与外部知识的短文本匹配模型

中文短文本通常使用单词序列而非字符序列进行语义匹配,以获得更好的语义匹配性能。然而,中文分词可能是错误或模糊的,容易引入噪声或者错误传播,从而损害模型的匹配性能。此外,多数中文词汇具有一词多义的特点,短文本由于缺少上下文环境,相比一词多义的长文本更难理解,这对于模型正确捕获语义信息是一个更大的挑战。提出一种短文本匹配模型,使用词格长短期记忆网络（Lattice LSTM）融合字符和字符序列的多粒度信息。引入外部知识HowNet解决多义词的问题,使用软注意力机制获取2个句子间的交互信息,并利用均值池化和最大池化算法进一步提取句子的特征信息,获取句子级语义编码表示。在数据集LCQMC和BQ上的实验结果表明,与ESIM、BIMPM和Lattice-CNN模型相比,该模型能有效提升中文短文本语义匹配的准确率。