基于乌肯算法优化后缀树，实现线性效率的文本搜索
Optimizing Text Search: A Novel Pattern Matching Algorithm Based on Ukkonen's Approach
- 结合乌肯算法与新搜索技术构建优化后缀树
- 在基因组数据中达100%识别准确率，时间空间线性
- 适合需要高效模式匹配的自然语言与生物信息场景
在计算机科学领域，文本搜索算法的效率对处理大规模数据至关重要，尤其在自然语言处理和生物信息学中。传统方法如朴素搜索、KMP和Boyer-Moore虽具基础意义，但在应对现代数据集（如Reuters语料库和人类基因组序列）的复杂性与规模时表现不足。本研究深入分析文本搜索算法，聚焦通过分裂法和乌肯算法优化后缀树，并在Reuters语料库及人类基因组等数据集上进行验证。提出一种融合乌肯算法与新型搜索技术的优化方案，实现线性时间与空间复杂度，显著优于传统方法。实证测试验证了其理论优势，表明优化后缀树在基因组序列模式识别任务中可达到100%准确率。该研究不仅推动文本搜索算法的学术进展，也展现出在自然语言处理和生物信息学中的显著实用价值，得益于其优越的资源效率与可靠性。
原文摘要 · Abstract (English)
In the realm of computer science, the efficiency of text-search algorithms is crucial for processing vast amounts of data in areas such as natural language processing and bioinformatics. Traditional methods like Naive Search, KMP, and Boyer-Moore, while foundational, often fall short in handling the complexities and scale of modern datasets, such as the Reuters corpus and human genomic sequences. This study rigorously investigates text-search algorithms, focusing on optimizing Suffix Trees through methods like Splitting and Ukkonen's Algorithm, analyzed on datasets including the Reuters corpus and human genomes. A novel optimization combining Ukkonen's Algorithm with a new search technique is introduced, showing linear time and space efficiencies, outperforming traditional methods like Naive Search, KMP, and Boyer-Moore. Empirical tests confirm the theoretical advantages, highlighting the optimized Suffix Tree's effectiveness in tasks like pattern recognition in genomic sequences, achieving 100% accuracy. This research not only advances academic knowledge in text-search algorithms but also demonstrates significant practical utility in fields like natural language processing and bioinformatics, due to its superior resource efficiency and reliability.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。