XML关键字查询：最紧致片段问题与Dewey编码新算法

"XML关键字查询中最紧致片段问题的研究" 这篇硕士学位论文主要探讨了XML（可扩展标记语言）关键字查询中的一个关键问题——最紧致片段（Smallest Lowest Common Ancestor, SLCA）问题。XML作为网络相关应用领域，如Web服务、电子商务、数字图书馆等，事实上的数据描述标准，其数据查询机制受到了广泛关注。论文作者张雷在导师洪晓光的指导下，对XML数据查询算法进行了分类，主要分为结构查询和XML关键字查询。 结构查询依赖于正则表达式，能清晰表达用户查询意图，但对用户的技术要求较高。相比之下，XML关键字查询允许用户仅输入关键字进行查询，更适合普通用户使用。然而，XML关键字查询的核心挑战在于找到包含所有查询关键字的最紧致片段SLCA，这是一个涉及到XML文档结构的问题。 论文中提到了几种已有的SLCA求解算法，如Stack、ILE、SE、USA和LISA II。ILE和SE在处理大量XML数据时表现出高效率，仅需一次顺序读取。LISA和LISA II在轻量级查询中表现更优，但LISA需要频繁扫描节点和集合交操作，消耗大量CPU周期；而LISA II虽减少了不必要的扫描，但引入了特有的编码方式，降低了通用性和效率。 针对这些缺点，论文提出了一个名为NDT（New Dewey编码的Tree算法）。NDT是一种轻量级且适用于XML关键字查询的通用算法，它利用Dewey编码来改进SLCA查找过程，旨在减少节点扫描和提高查询速度。Dewey编码是一种用于XML文档节点标识的方法，通过这种编码，NDT算法可能能够降低计算复杂性并提高查询效率，从而为XML关键字查询提供更快捷的解决方案。 这篇论文深入研究了XML关键字查询中的SLCA问题，分析了现有算法的优缺点，并提出了NDT算法这一创新性尝试，以解决XML查询效率和通用性的问题。