基于Web语料的维吾尔文重复模式识别算法及应用研究

Algorithms for sequence repeat pattern recognition are related to many computer science domain knowledge, and have a wide range of applications in the fields of data mining, data compression, bioinformatics, and Web information extraction. This project takes the Uyghur Web corpus as the research object, and is based on the pre-research, to design the algorithms for Uyghur repeat pattern recognition and its applications,by using the combination methods of algorithm design and prototype system testing. To improve the algorithm pre-processing time efficiency, we will design a new algorithm so that it can calculate the suffix array and longest common prefix array at the same time. We analyze the repeat pattern extraction algorithm in the applications of Web text clustering, and design a repeat pattern based Uyghur Web text clustering algorithm. On this basis, we will construct a method to calculate the key term weight with multi-features, and study the meaningful string-based network hot topic extraction method, thereby analyze the Uyghur Web information semantic representation. We hope to achieve the goal of providing a theoretical basis and strong technical support for the fields of Uyghur network text mining, intelligent information retrieval, and network monitoring public opinion.

序列中重复模式识别算法研究涉及到很多相关的计算机学科领域知识，并在数据挖掘、数据压缩、生物信息学、Web信息抽取等领域都有着重要的应用。本课题以维吾尔语Web语料库为研究对象，在前期预研的基础上，采用算法设计与原型系统检验相结合的方法，进行基于Web语料的维吾尔文重复模式识别算法及应用研究。为提高算法预处理阶段时间效率，设计新算法使之能同时计算后缀数组与最长公共前缀数组；研究与设计基于Web语料维文重复模式快速识别与统计算法；研究重复模式特征提取算法在维语Web文本聚类中的应用，进而设计一种基于重复模式的维语Web文本快速聚类算法。在此基础上，构造用于网络热点话题检测的多特征融合的特征词权重的计算方法，进行基于有意义串的网络热点话题发现方法研究并初步研究基于重复模式的Web信息语义表示方法。为维吾尔语Web文本挖掘、智能信息检索、网络舆情监测等领域研究提供理论基础及有力的技术支持。

重复模式识别算法研究涉及到很多相关的计算机学科领域知识，并在数据挖掘、数据压缩、Web信息抽取等领域都有着重要的应用。本项目在大量调研的基础上，采用算法设计与原型系统检验相结合的方法，进行了基于Web语料的维吾尔文重复模式识别算法及应用研究。重点研究了最大重复模式快速识别与提取算法、维吾尔语术语抽取、基于有意义串的维吾尔Web文本聚类及热点话题发现方法，取得了一定的研究成果。.在重复模式识别与提取算法研究方面，研制了一种基于QSA数组计算所有带有约束条件的NE重复模式（最大重复模式）的算法RPT，空间效率是目前的最好水平，最小周期和最大间距约束条件的引入，使得用户使用算法时可根据具体应用筛选符合条件的重复模式。实验结果表明对维吾尔语Web文本中的最大重复模式的识别与提取很有效。为了进一步提高重复模式提取效率，设计了一种高效的基于特征提取的识别最大重复模式的算法MRepF，通过对序列的线性扫描，可快速得到所有完整重复模式的各项统计信息，算法达到了线性时间和空间复杂度。在研究匹配相似程度和模式间隔的基础上，利用MRepF的输出结果，设计了一种近似最大重复模式的识别算法，理论分析和对维吾尔Web文本的实验结果都表明算法比同类算法性能得到提高，可应用于后续的相关领域研究。研制了一种基于逐层剪枝算法的大规模语料重复模式提取算法，通过短串过滤长串及级联剪枝技术，及时滤出低频垃圾字符串，有效减少内存用量，进而高效处理容量大于内存容量的语料。.通过深入挖掘维吾尔语统计特征和语言知识特征，对领域术语识别方法与技术进行了较为全面的研究，提出了有效的识别方法。.针对目前维吾尔Web文本聚类存在的问题，在最大重复模式识别的基础上构造候选集合，并应用领域相关的特定统计量，包括逆文档频率、互信息并结合术语识别等进行有意义串的提取，设计了一种基于有意义串的聚类分析算法，可实现维吾尔语Web文本的有效聚类，并对基于文本语义挖掘的热点话题发现方法提供了基础。.针对在算法与软件的研究过程中需要进行大量的需求分析与建模，因而对使用UML进行系统分析方面进行了研究。同时对研究过程中发现的新问题如维吾尔文字符标准编码的存储空间效率偏低等，也提出了新的解决方案。