采用预测策略的Earley算法

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

基于Earley算法的多功能雷达文法概率快速学习算法

针对基于随机上下文无关文法（SCFG）建模的多功能雷达（MFR）概率学习问题,在传统Inside-Outside（IO）算法和Viterbi-Score（VS）算法的基础上,提出一种基于Earley算法的多功能雷达文法概率快速学习算法。该算法通过对截获的雷达数据进行预处理,构造可以反映派生过程的Earley剖析表,并且基于最大子树概率原则从剖析表中提取出最优剖析树,利用改进的IO算法和改进的VS算法对文法概率进行学习,实现MFR参数估计,得到文法参数后,再利用Viterbi算法对MFR状态进行估计。理论分析和实验仿真表明,与IO算法和VS算法相比,改进算法在保持估计精度的同时,可以有效降低计算复杂度和减少运行时间,验证了Earley算法能够提高文法概率的学习速度。     

一种改进Viterbi算法的应用研究

为降低现代汉语句法分析的难度,以北大和哈工大语料为基础,利用改进的Viterbi算法对汉语真实文本进行了短语识别研究.提出了在隐马尔可夫模型(HMM)框架下,训练阶段依据统计概率信息,以极大似然法获取HMM参数,识别阶段用一种改进的Viterbi算法进行动态规划,识别同层短语;在此基础上,运用逐层扫描算法和改进Viterbi算法相结合的方法来识别汉语嵌套短语.实验结果表明,识别正确率在封闭测试中可达93.52%,在开放测试中达到77.529%,证明该算法对短语识别问题具有良好的适应性和实用性.     

一种有效的汉语概率句法分析算法

一种有效的汉语概率句法分析算法通过制定语法功能词表和包含语法功能词的概率上下文无关规则集进行句法分析。它以语法功能词为切入点,首先识别出所有包含语法功能词的短语,然后分析短语之间的组合关系,最终得到句法树。实验表明该算法能获得较高的准确率。     

基于Viterbi算法LFSR的恢复与设计

通过优化传统Viterbi算法的存储结构，使其能够对约束长度较大、码率很低卷积码进行译码。离线构造Hamming距离对照表，给出了一种可查表的Viterbi硬判决快速译码算法。实验表明，当误码率为37%以下时，生成多项式的次数在60以内的LFSR(线性反馈移位寄存器)序列的初始状态，可进行快速恢复。与传统的Viterbi译码算法相比，算法的译码效率提高了几乎10倍左右。     

基于容错Earley解析算法的领域语义文法自动学习方法

精细化的领域文本分析是高质量领域知识获取的重要前提,它通常依赖于大量某种形式的语义文法产生式,但总结这些文法通常耗时耗力.对此,文中提出了 一种基于容错Earley解析算法的语义文法自动学习方法,根据种子文法自动生成新的语义文法(包括词类和文法产生式),以减少人工成本.该方法利用优化后的容错Earley解析器,对输入的语句进行容错解析,然后根据容错解析生成的解析树产生候选语义文法,最后对候选语义文法进行过滤或纠正得到最终的语义文法.在5种不同疾病的中医医案的实验中,该方法的词类学习的正确率达到63.88％,文法产生式学习的正确率达到81.78％.     

基于序列检验和Viterbi的检测前跟踪算法

针对弱小目标的检测跟踪问题,提出了一种基于序列检验和Viterbi的检测前跟踪算法;将雷达扫描区域进行划分后,在方位-距离-多普勒平面内联合处理回波信号,为了搜集目标驻留时间内的散射能量,可以通过Viterbi算法搜索连续扫描时允许的目标转移状态,最后通过序列检测做出判决;序列检验可以解决目标检测过程中时延较大的问题,Viterbi算法用来获取检测统计量及目标的轨迹;仿真结果表明,该算法对高速运动的目标具有良好的检测与跟踪性能.     

基于Earley剖析的多功能雷达文法参数估计算法

针对基于随机上下文无关文法(Stochastic Context-Free Grammar,SCFG)建模的多功能雷达(Multi-Function Radars,MFR)参数估计问题的研究,在原有Inside-Outside(IO)算法和Viterbi-Score(VS)算法的基础上,提出一种基于Earley剖析的多功能雷达文法参数估计算法——EIO算法。该算法将IO算法与Earley剖析相结合,通过对截获的雷达数据进行预处理,可以处理任意形式的文法产生式,对文法产生式概率进行学习,从而实现MFR文法参数估计。通过理论分析和实验仿真,EIO算法可以在减少计算复杂度、记忆复杂度和运行时间的同时,有效保持文法参数估计精度,论证了方法的正确性和有效性。     

基于Viterbi改进算法的高棉语分词研究

采用最大匹配算法对高棉语进行分词准确率较低,且难以正确识别词库中没有的新词。针对该问题,采用改进的Viterbi算法,利用自动机实现音节切分,通过最优选择及剪枝操作提高分词效率,以统计语言模型对未知新词进行数据平滑,提高识别正确率。实验结果表明,改进的Viterbi算法具有较高的分词效率和准确率。     

基于Dubins路径的无人艇运动规划算法

针对无人艇运动规划问题,通过Dubins路径的理论分析,提出一种利用纯粹几何方法的Dubins路径计算方法。该方法中没有出现解方程组的运算,而是首先根据无人艇运动状态计算转向圆,然后利用几何方法计算转向圆间的公切线,最后通过公切线连接得到Dubins路径。通过5组仿真实验验证了所提方法的有效性。前4组仿真实验分别设计了计算Dubins路径过程中可能出现的各种情形,以验证算法适用于多种情况的Dubins路径计算。最后一组仿真实验用于无人艇的路径规划及运动状态调整,仿真结果表明,基于Dubins路径的无人艇运动规划算法是可行的。     

Viterbi改进算法研究

Viterbi译码算法是最大似然译码。论文所研究的改进Viterbi算法,不但保持了原有Viterbi算法的特性,而且在减少译码路径的情况下,能较好地解决突发错误信道中,原Viterbi译码算法则性能急剧下降的问题。通过在编码信道模型上的仿真表明,已知正确的约束位越多,分布的越密,则提高的性能越明显。     

多目标路的扩展Dijstra算法

在一个运输网络中,一条时间最短、费用最少并且最安全的路,是一个多目标路的实例。使用传统的Dijstra算法或多目标规划方法求一条多目标路是困难的。首先将多目标路问题转换为单目标路问题,或一个"综合"目标问题,然后分别给出"基于顶点标号"的扩展Dijstra算法。     

一种卷积码维特比译码算法的软件实现

提出了数字通信系统中一种卷积码译码的软件实现方案,该方案应用软件技术实现了卷积码维特比译码器功能,在程序实现中充分利用了卷积码的特性,运用蝶形运算,周期性的回溯以得到译码输出。在程序设计上采用了一些宏定义等处理方法,可以提升运算速度,是一种软件方法的前向纠错编码技术。     

基于音频内容与维特比解码的音频数字水印算法

利用音频自身特征作为水印的同步信号有利于提高音频水印的鲁棒性。提出了一种基于音频内容分析的算法,算法先经过音频内容分析得到一组特征点,在特征点后面的音频中嵌入水印。水印检测时,同样先分析待测音频得到特征点,利用特征点后面的音频提取出有意义的水印。为了提高水印的检测速度,提出采用维特比（Vitebi）解码技术判决水印。实验结果表明,算法对加噪、低通滤波等具有一定的鲁棒性。     

约束维特比译码的算法与在其二进制均衡信道中的性能研究

约束维特比算法是利用已知的正确信息，对维特比算法进行改进。本文针对约束维特比算法进行了探讨，并对其性能进行了仿真实验。仿真结果证明，在二进制均衡信道中当采用约束维特比算法时，性能得到了较大的提高。     

超宽带系统中维特比译码器的设计与实现

提出一种超宽带系统中的维特比译码器,对混合幸存路径管理单元进行改进,使其最高工作频率提升25%,译码延时减少40个时钟周期。在Xilinx Virtex-5 XC5VLX330 FPGA上的实现结果表明,该维特比译码器能在240 MHz的时钟频率下正确工作。并行使用 2个该译码器,可对系统中所有8种速率的数据译码。     

一种基于遗传算法与概率转发的分簇协议

针对以LEACH协议为基础的分簇协议存在簇头选择不稳定以及簇间路由能耗高的问题,提出一种结合遗传算法与概率转发准则的新的分簇协议LEACH-GPF(Genetic and Probabilistic Forwarding algorithm for Energy Balance in LEACH),对分簇算法的簇头选择以及簇头与基站的通信方式进行了优化。将所提协议与LEACH协议和LEACH-C协议进行了性能对比分析。实验结果表明,这种新的分簇算法相对于LEACH和LEACH-C协议拥有更好的能耗均衡的能力,且性能稳定。