无法理解CYK算法伪代码

2024-04-04

我正在读关于CYK算法 https://en.wikipedia.org/wiki/CYK_algorithm,并且有一部分伪代码我无法理解。整个伪代码是:

let the input be a string S consisting of n characters: a1 ... an.
let the grammar contain r nonterminal symbols R1 ... Rr.
This grammar contains the subset Rs which is the set of start symbols.
let P[n,n,r] be an array of booleans. Initialize all elements of P to false.
for each i = 1 to n
  for each unit production Rj -> ai
    set P[i,1,j] = true
for each i = 2 to n -- Length of span
  for each j = 1 to n-i+1 -- Start of span
    for each k = 1 to i-1 -- Partition of span
      for each production RA -> RB RC
        if P[j,k,B] and P[j+k,i-k,C] then set P[j,i,A] = true
if any of P[1,n,x] is true (x is iterated over the set s, where s are all the indices for Rs) then
  S is member of language
else
  S is not member of language

这些部分是我感到困惑的:

    for each production RA -> RB RC
      if P[j,k,B] and P[j+k,i-k,C] then set P[j,i,A] = true

有人会对这些伪代码给出一些提示吗?


伪代码

For each production RA → RB RC:

如果 P[j,k,B] 和 P[j+k,i-k,C] 则设置 P[j,i,A] = true

Should be interpreted in the following way. Suppose that it's the case that P[j, k, B] is true. That means that the string formed from k characters starting at position j can derived from the nonterminal RB. If it's also the case that P[j + k, i - k, C] is true, then the string formed from the i - k characters starting at position j + k can be derived from nonterminal RC. Therefore, since RA → RB RC is a production, it's the case that the string formed from the i characters starting at position j can be derived from RA.

我认为这可能有助于将该伪代码解释为

For each production RA → RB RC:

如果 P[j,k,B] == true 且 P[j+k,i-k,C] == true,则设置 P[j,i,A] = true

希望这可以帮助!

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

无法理解CYK算法伪代码 的相关文章

  • 在Java中清空数组/处理

    除了循环遍历数组中的每个元素并将每个元素设置为 null 之外 Java 处理中是否有一个本机函数可以简单地清空数组 或销毁它 以便能够将其重新声明为新数组 There s Arrays fill myArray null 并不是说它执行的
  • 将 spring-security 与 spring-webflux 结合使用时禁用 WebSession 创建

    我正在使用 Rest api 运行无状态 spring boot 应用程序 并希望按照所述禁用 WebSessions 的创建https www baeldung com spring security session https www
  • Javadoc 1.5 和 1.6 中缺少 enum.valueOf(String name)

    这可能是一个愚蠢的问题 但我正在使用该方法enum valueOf String name 那里没问题 只是当我检查 javadoc 以了解有关此方法的更多信息时 我找不到它 有javadoc用于valueOf Class
  • 对 Java 中 *any* 类的所有实例进行全排序

    我不确定以下代码是否能确保 Comparator 的 Javadoc 中给出的所有条件 class TotalOrder
  • @OneToMany 与 @JoinTable 错误

    我试图理解 OneToMany with JoinTable 对于这样的场景 我正在使用 JPA 2 1 Hibernate 5 0 4 和 Oracle 11 XE 当我打电话时userDao save user 下面的代码 我有 jav
  • 从二叉堆中查找第 k 个最小元素的 O(klogk) 时间算法

    我们有一个 n 节点二叉堆 其中包含n不同的项目 根部的最小项目 为一个k lt n 发现O klogk 时间算法选择kth堆中的最小元素 O klogn 很明显 但无法找出O klogk 一 也许我们可以使用第二个堆 但不确定 好吧 你的
  • 哈希码是否用于加速集合中的对象查找?

    IIUC 相同类型的两个不同对象可以存储在 HashSet 中 即使两个对象在以下情况下返回相同的值 hashCode 叫做 例如根据本文 https eclipsesource com blogs 2012 09 04 the 3 thi
  • 以编程方式设置 Logback Appender 路径

    我正在尝试以编程方式设置 Logback 附加程序路径 滚动文件附加器 http logback qos ch apidocs ch qos logback core rolling RollingFileAppender html准确地说
  • C# 中的协变和逆变

    首先我要说的是 我是一名正在学习 C 编程的 Java 开发人员 因此 我会将我所知道的与我正在学习的进行比较 我已经使用 C 泛型几个小时了 我已经能够在 C 中重现我在 Java 中知道的相同内容 除了几个使用协变和逆变的示例 我正在读
  • 添加边后更新最大流量

    考虑我们有一个网络流量 并使用 Edmond Karp 算法 我们已经拥有网络上的最大流量 现在 如果我们向网络添加任意边 具有一定容量 更新最大流量的最佳方法是什么 我正在考虑更新关于新边缘的残差网络 并再次寻找增强路径 直到找到新的最大
  • 使用 ElementTree 在 python 中解析 xml

    我对 python 很陌生 我需要解析一些脏的 xml 文件 这些文件需要先清理 我有以下 python 代码 import arff import xml etree ElementTree import re totstring wit
  • 为什么现在()? (客观化)

    为什么我想要异步加载 Objectify 实体 异步加载到底意味着什么 根据客观化有关加载的文档 https code google com p objectify appengine wiki BasicOperations Loadin
  • 我们可以使用 for-each 循环来迭代 Iterator 类型的对象吗? [复制]

    这个问题在这里已经有答案了 如果我们执行以下操作 我们会收到错误 class FGH public static Iterator reverse List list Collections reverse list return list
  • 从给定的项目列表创建子列表

    我首先要说的是以下问题不是为了家庭作业目的即使因为我几个月前就完成了软件工程师的工作 无论如何 今天我正在工作 一位朋友向我询问了这个奇怪的排序问题 我有一个包含 1000 行的列表 每行代表一个数字 我想创建 10 个子列表 每个子列表都
  • 实时战略战争游戏人工智能算法

    我正在设计一款实时策略战争游戏 其中 AI 将负责控制大型六边形地图上的大量单位 可能超过 1000 个 一个单位有许多行动点 可以用于移动 攻击敌方单位或各种特殊行动 例如建造新单位 例如 一辆拥有 5 个行动点的坦克可以花费 3 个行动
  • 找不到符号assertEquals

    我正在尝试为计算器编写第一个单元测试 但 NetBeans 说它找不到该符号assertEquals和注释 Test 我应该包括一些东西吗 我正在使用 NetBeans 7 3 1 和 W7 package calculator impor
  • scala中的协变类型参数需要在java接口中保持不变

    我有一个看起来像这样的特征 一些进一步的信息可以在我自己提出了这个相关问题 https stackoverflow com questions 3695990 inheritance and automatic type conversio
  • 如果抛出RuntimeException,是否可以将其作为异常捕获?

    如果我有一个try抛出一个块RuntimException子类 可以是后续的catch块将其捕获为Exception 具体来说 public class MyAppException extends RuntimeException In
  • 将带有 webapp 的 WAR 部署到 Maven 中央存储库是否有意义?

    这样做有意义吗 如果是 我在哪里可以找到使用简单的 Web Hello World 执行此操作的示例 当人们从 Maven 执行 Web 应用程序时 他们会使用 Jetty 来运行它吗 我想 tomcat 太重了 任何帮助将不胜感激 谢谢
  • 如何从spark中的hbase表中获取所有数据

    我在 hbase 中有一个大表 名称为 UserAction 它具有三个列族 歌曲 专辑 歌手 我需要从 歌曲 列族中获取所有数据作为 JavaRDD 对象 我尝试了这段代码 但效率不高 有更好的解决方案来做到这一点吗 static Spa

随机推荐