基于文法分支覆盖的短句子生成算法

提出一种上下文无关文法的句子生成算法.对于给定文法,算法生成一个满足该文法分支覆盖准则的句子集.结合长度控制、冗余消除和句子集规模控制等策略,使得生成的句子较短、无冗余、句子集规模较小.考察了算法在基于文法的软件系统的测试数据生成方面的应用情况.实验结果表明,该算法生成的测试数据具有较强的程序揭错能力,并且能够帮助测试人员提高测试速度.     

上下文感知系统中的规则生成与匹配算法

针对现有上下文感知系统中的规则主要依靠开发者或用户手工定义的问题,提出了一种基于粗糙集理论的自动规则生成方法.该方法将上下文感知系统视为一种决策信息系统,并利用可辨识矩阵对上下文信息加以约简,进而自动生成规则.由于可供使用的数据有限,所生成的规则无法完全覆盖上下文的取值范围,因此可能出现找不到与上下文状态相匹配规则的问题.为了解决这一问题,提出了一种基于语义距离的规则匹配算法.最后验证了所提出方法的有效性和效率.     

一种有效的结点标号上下文无关图文法分析算法

本文讨论了上下文无关图文法的性质，并证明了图文法推导具有独立性．本文还给出了一种有效的上下文无关图文法分析算法，它具有多项式时间复杂性，并给出了算法的正确性证明．该算法已经用Ｃ语言实现．     

采用预测策略的Earley算法

在自然语言处理中,句法分析主要有基于统计的方法和基于规则的方法。Earley算法是一种基于规则的方法,可以分析任意上下文无关文法(CFG),而不需要对文法进行修改。详细分析了Earley算法的特点。在通常的Earley算法中增加了多种预测机制,这些预测机制借鉴了LL,LR以及SLR等确定性分析算法的一些思想,并对这几种不同的预测机制及其组合在相同条件下进行了中文句法分析实验。结果显示,引入这些预测机制通常可以减少产生项目的数量,从而节省存储空间,减少运行时间。     

获取上下文无关文法的一种交互式算法

本文提出一种交互式的上下文无关语言的学习算法，该算法是专门为ＳＡＱ系统设计的，所得到的文法能够自然地反映句子的内部结构，从而很容易刻划句子的含义（语义）。     

上下文相关图文法分析及其应用初探

图文法是一种对可视化语言进行形式化定义的元语言，具有表达自然、能力强大的特点.随着使用可视化语言的最终用户编程技术的广泛应用，图文法分析尤其是上下文相关图文法分析在工程应用中的重要性日益突出.国内外相关文献或着重于纯理论探讨，或局限于特定语法类的特定应用，不利于工程应用人员参考.本文选取简洁明了的符号体系，介绍上下文相关图文法分析的一般性过程，并将其中规则选取关键步骤描述为CSP问题，利用已有的针对CSP问题的优化方法来优化算法，介绍了现有的优化方法并给出实现算法;同时，结合自身实践，讨论其在一个面向体系结构的Web服务集成系统中的应用.     

新的普适计算环境下上下文缓存置换算法

由于普适计算环境高度动态的特点以及无线环境连接易中断、传输速度低等方面的约束,使得普适计算应用对于上下文的访问开销非常大。为此,首先给出一个上下文感知系统框架,然后提出了一种基于规则的上下文缓存置换算法--RCRA,算法根据上下文的被访问概率、上下文时效性及历史访问次数决定是否将其置换出缓存。当有新的上下文需要进入缓存时执行该算法,以保证缓存中的上下文最新且最有价值。实验表明,RCRA不仅在命中率方面有较大提高,而且能够有效降低上下文访问的开销。算法应用于基于推理规则的上下文感知系统中,具有良好的可实用性。     

一种层次化的LSD规则体系及其分析算法

本文提出了一种基于词汇属性结构描述和规则继承的层次化LSD规则体系,讨论了该规则体系下的规则搜索策略和词汇化规则索引的实现方法,并在此基础上首次给出了LSD文法的非确定性分析算法。该规则系统具有从传统属性文法到现代词汇文法的可伸缩性,同时较好地解决了线性规则库中复杂的规则交互问题。     

量化上下文无关语言的代数性质

通过引入量化下推自动机与量化上下文无关文法的定义,研究了以两种不同方式接受语言的量化下推自动机等价性问题,证明了在可交换的双幺赋值幺半群上,量化下推自动机接受的语言与量化上下文无关文法生成的语言相同。     

上下文相关图文法的表达能力分析

上下文相关图文法是描述可视化语言的形式化工具.为了直观地刻画并高效地分析可视化语言,已有图文法形式框架均着重于文法形式和分析算法的研究,而忽略了对它们之间表达能力的分析.在对已有上下文相关图文法形式框架的关键特征进行分析和归纳的基础上,通过构造不同形式框架之间的转换算法,揭示并形式化证明了它们表达能力之间的关系.而且,转换算法在不同形式框架之间建立了关联,使图文法的应用不必再局限于一个框架,而是可以选择不同框架分别进行图的描述和分析,从而提高了上下文相关图文法的易用性.     

A Toolkit for Generating Sentences from Context-Free Grammars

Producing sentences from a grammar, according to various criteria, is required in many applications. It is also a basic building block for grammar engineering. This paper presents a toolkit for context-free grammars, which mainly consists of several algorithms for sentence generation or enumeration and for coverage analysis for context-free grammars. The toolkit deals with general context-free grammars. Besides providing implementations of algorithms, the toolkit also provides a simple graphical user interface, through which the user can use the toolkit directly. The toolkit is implemented in Java and is available at http://lcs.ios.ac.cn/~zhiwu/toolkit.php. In the paper, the overview of the toolkit and the major algorithms implemented in the toolkit are presented, and experimental results and preliminary applications of the toolkit are also contained.     

神经网络规则抽取评估方法

神经网络规则抽取是神经网络领域的一个重要方向,但是对抽取的规则评估算法却很少.针对这一问题,提出了神经网络抽取规则评估方法.首先证明所有的规则形式都可以统一为区间的形式,然后在区间算法的基础上提出规则评估方法.评估的标准有四个:覆盖性、准确性、矛盾性,以及冗余性.由于规则的矛盾性和冗余性是规则之间的问题,所以该文仅仅研究规则的覆盖性和准确性,提出了覆盖性判断定理,并提出了覆盖性、准确性判断算法.实例证实了该算法的有效性.     

A Methodology for Creating a Segment Inventory for Greek Time Domain Speech Synthesis

This article focuses on the systematic design of a segment database which has been used to support a time-domain speech synthesis system for the Greek language. Thus, a methodology is presented for the generation of a corpus containing all possible instances of the segments for the specific language. Issues such as the phonetic coverage, the sentence selection and iterative evaluation techniques employing custom-built tools, are examined. Emphasis is placed on the comparison of the process-derived corpus to naturally-occurring corpora with respect to their suitability for use in time-domain speech synthesis. The proposed methodology generates a corpus characterised by a near-minimal size and which provides a complete coverage of the Greek language. Furthermore, within this corpus, the distribution of segmental units is similar to that of natural corpora, allowing for the extraction of multiple units in the case of the most frequently-occurring segments. The corpus creation algorithm incorporates mechanisms that enable the fine-tuning of the segment database's language-dependent characteristics and thus assists in the generation of high-quality text-to-speech synthesis.     

基于碰撞域检测优化的测试用例自动生成方法

摘 要: 随着软件行业的快速发展,软件测试的作用也越来越大,自动化测试用例生成方法也越来越多。所以如何提出一种高效的测试用例生成算法,一直是测试领域关注的热点。本文提出了一种基于碰撞域检测优化的测试用例生成方法检测优化的测试用例生成方法能规避大量的冗余测试用例产生,因此该算法在短时间内能将代码的语句覆盖度收敛到一个较为满意的值。同时通过半径的动态调整,保证算法的覆盖度逐级上升,结合遗传算法对高覆盖率的测试用例进行交叉变异,快速找到有效的测试用例数据。实验证明,该算法的性能相比于传统随机法有较大的提升,而且参数的范围越大,效果越好。     

Unrestricted gapping grammars1

Since Colmerauer's introduction of metamorphosis grammars (MGs), with their associated type-O-like grammar rules, there has been a desire to allow more general rule formats in logic grammars. Gap symbols were added to the MG rule by Pereira, resulting in extraposition grammars (XGs). Gaps, which are referenced by gap symbols, are sequences of zero or more unspecified symbols which may be present anywhere in a sentence or in a sentential form. However, XGs imposed restrictions on the position of gap symbols and on the contents of gaps. With the introduction of gapping grammars (GGs) by Dahl, these restrictions were removed but the rule was still required to possess a nonterminal symbol as the first symbol on the left-hand side. This restriction is removed with the introduction of unrestricted gapping grammars. FIGG, a flexible implementation of gapping grammars, possesses a bottom-up parser which can process a large subset of unrestricted gapping grammars. It can be used to examine the usefulness of unrestricted GGs for describing phenomena of natural languages such as free word order and partially free word/constituent order. Unrestricted gapping grammars, as implemented in FIGG, can also be used to describe grammars (or metagrammars) that utilize the gap concept, such as Gazdar's generalized phrase structure grammars.     

频率相似度算法在审计规则库中的应用

在语句语义相似度计算的算法中,没有考虑语句中的不同词语对语句之间相似度值的不同贡献程度,以致计算结果不理想。为此提出了基于频率函数的改进词语相似度算法,该算法将词语在语料库中的频率函数作为权重值,引入至语句的词语相似度计算中,以降低高频率词语在语句相似度值中的比重,提高算法精确率。由于当前审计方法存在散、乱、重复等现象,为了更好地复用已有的审计方法,将根据审计方法建立审计规则库,在此基础上,利用上述改进的语义相似度算法,计算用户输入与审计规则之间的相似度值,返回满足相似度阈值条件的审计规则所对应的审计方法,用户根据所返回的审计方法,选择合适的审计方法进行审计工作。实际应用表明,该算法的应用减少了人工搜索审计方法的时间,提高了审计效率。     

Generation of text from logical formulae

The paper addresses the problem of generating sentences from logical formulae. It describes a simple and efficient algorithm for generating text which has been developed for use in machine translation, but will have wider application in natural language processing. An important property of the algorithm is that the logical form used to generate a sentence need not be one which could have been produced by parsing the sentence: formal equivalence between logical forms is allowed for. This is necessary for a machine translation system, such as the one envisaged in this paper, which uses single declarative grammars of individual languages, and declarative statements of translation equivalences for transfer. In such a system, it cannot be guaranteed that transfer will produce a logical form in the same order as would have been produced by parsing some target-language sentence, and it is not practicable to define a normal form for the logical forms. The algorithm is demonstrated using a categorial grammar and a simple indexed logic, as this allows a particularly clear and elegant formulation. It is shown that the algorithm can be adapted to phrase-structure grammars, and to more complex semantic representations than that used here.     

DeepRanger:覆盖制导的深度森林测试方法

深度学习软件的结构特征与传统软件存在明显差异,因此即使展开了大量测试,依然无法有效衡量测试数据对深度学习软件的覆盖情况和测试充分性,并造成后续使用过程中依然可能存在大量未知错误.深度森林是一种新型深度学习模型,其克服了深度神经网络存在的一些缺点,例如:需要大量训练数据、需要高算力平台、需要大量超参数.但目前还没有相关工作对深度森林的测试方法进行研究.针对深度森林的结构特点,制定了一组由随机森林结点覆盖率RFNC、随机森林叶子覆盖率RFLC、级联森林类型覆盖率CFCC和级联森林输出覆盖率CFOC组成的测试覆盖率评价指标.在此基础上,基于遗传算法设计了覆盖制导的测试数据自动生成方法DeepRanger,可自动生成能有效提高模型覆盖率的测试数据集.为对所提出覆盖指标的有效性进行验证,在深度森林开源项目gcForest和MNIST数据集上设计并进行了一组实验.实验结果表明,所提出的4种覆盖指标均能有效评价测试数据集对深度森林模型的测试充分性.此外,与基于随机选择的遗传算法相比,使用覆盖信息制导的测试数据生成方法 DeepRanger能达到更高的模型覆盖率.     

Generating semantically valid test inputs using constrained input grammars

ContextGenerating test cases based on software input interface is a black-box testing technique that can be made more effective by using structured input models such as input grammars. Automatically generating grammar-based test inputs may lead to structurally valid but semantically invalid inputs that may be rejected in early semantic error checking phases of a system under test.ObjectiveThis paper aims to introduce a method for specifying a grammar-based input model with the model’s semantic constraints to be used in the generation of positive test inputs. It is also important that the method can generate effective test suites based on appropriate grammar-based coverage criteria.MethodFormal specification of both input structure and input semantics provides the opportunity to use model instantiation techniques to create model instances that satisfy all specified constraints. The input interface of a subject system can be specified using a high-level specification scheme such as attribute grammars, and a transformation function from this scheme to an instantiable formal modeling language can generate the desired model instances.ResultsWe propose a declarative grammar-based input specification method that is based on a variation of attribute grammars and allows the user to specify input constraints in addition to input structure. The model can be instantiated automatically to generate structurally and semantically valid test inputs. The proposed method has the capability to specify test requirements and coverage criteria and use them to generate valid test suites that satisfy test coverage criteria requirements.ConclusionThe work presented in this paper provides a black-box test generation method for grammar-based software inputs that can automatically generate criteria-covering test suites.