无法理解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算法伪代码 的相关文章

  • Hashmap并发问题

    我有一个哈希图 出于速度原因 我希望不需要锁定 假设我不介意过时的数据 同时更新它和访问它会导致任何问题吗 我的访问是获取 而不是迭代 删除是更新的一部分 是的 这会导致重大问题 一个例子是向散列映射添加值时可能发生的情况 这可能会导致表重
  • 使用 Java 在 WebDriver 中按 Ctrl+F5 刷新浏览器

    我已经使用 java 刷新了 WebDriver 中的浏览器 代码如下 driver navigate refresh 如何使用 Java 在 WebDriver 中按 Ctrl F5 来做到这一点 我认为您可以使用 WebDriver 和
  • 在哪里可以获得有关 Java FitNesse 和 Slim 的一些教程? [关闭]

    就目前情况而言 这个问题不太适合我们的问答形式 我们希望答案得到事实 参考资料或专业知识的支持 但这个问题可能会引发辩论 争论 民意调查或扩展讨论 如果您觉得这个问题可以改进并可能重新开放 访问帮助中心 help reopen questi
  • 无法使用 json 架构验证器根据预定义的 yaml 文件验证查询参数

    我需要根据预定义的 yaml 文件架构验证查询参数的架构 因此我使用 json 架构验证器 验证如何失败 我正在执行以下步骤 填充参数和相应的架构 final List
  • 尝试使用 JRI 将 R 与我的 Java 应用程序集成,但出现错误。谁能解释一下原因和解决办法吗?

    我需要将 Java 与 R 集成来运行一些数学命令并使用 R 的功能进行绘图 以下部分代码给出了错误 public static void main String args HelloRWorld r new HelloRWorld r h
  • 所有平台上的java

    如果您想用 java 为 Windows Mac 和 Linux 编写桌面应用程序 那么所有这些代码都相同吗 您只需更改 GUI 即可使 Windows 应用程序更像 Windows 等等 如果不深入细节 它是如何工作的 Java 的卖点之
  • 从 @JsonProperty 值获取枚举常量

    我有一个标有 JsonProperty 的枚举 用于使用 Jackson 进行 JSON 序列化 反序列化 并且希望获取给定字符串 JsonProperty 的枚举值 public enum TimeBucket JsonProperty
  • n 或 nlog(n) 比常数时间或对数时间更好吗?

    在 Coursera 上的普林斯顿教程中 讲师解释了遇到的常见增长顺序函数 他说 线性和线性算术运行时间是 我们努力的目标 他的推理是 随着输入大小的增加 运行时间也会增加 我认为这是他犯了错误的地方 因为我之前听过他提到线性增长顺序对于高
  • 发生错误。请参阅日志文件 - eclipse juno

    每当我启动 Eclipse Juno 时 都会出现错误 发生错误 请查看日志文件 C Program Files eclipse configuration 1362989254411 log 有的网站说卸载jdk重新安装 我这样做了 但没
  • 在 Java 中将弯音发送到 MIDI 音序器

    我了解启动和运行 MIDI 音序器的基础知识 并且希望能够在播放过程中增加 减小序列的音高 但弯音是发送到合成器而不是音序器的消息 我尝试将音序器的接收器设置为合成器的发射器 当我发送弯音短消息时 音序器保持相同的音调 但随后合成器以新的弯
  • 如何找到被点击的JLabel并从中显示ImageIcon?

    这是我的代码 我想知道哪个l单击 然后在新框架中显示该 ImageIcon e getSource 不起作用 final JFrame shirts new JFrame T shirts JPanel panel new JPanel n
  • 如何在Java媒体框架中学习.wav持续时间?

    我正在尝试使用 java 媒体框架将 mov 文件与 wav 文件合并 因此我需要知道它们的持续时间 我怎样才能做到这一点 任何想法 将不胜感激 您可以使用以下方式了解声音文件的持续时间 即 VitalyVal 的第二种方式 import
  • Android Gradle 同步失败:无法解析配置“:classpath”的所有工件

    错误如下 Caused by org gradle api internal artifacts ivyservice DefaultLenientConfiguration ArtifactResolveException Could n
  • 了解 Spark 中的 DAG

    问题是我有以下 DAG 我认为当需要洗牌时 火花将工作划分为不同的阶段 考虑阶段 0 和阶段 1 有些操作不需要洗牌 那么为什么 Spark 将它们分成不同的阶段呢 我认为跨分区的实际数据移动应该发生在第 2 阶段 因为这里我们需要cogr
  • 为什么我的代码会产生错误:该语句没有返回结果集[重复]

    这个问题在这里已经有答案了 我正在从 Microsoft SQL Server Studio 执行以下查询 该查询工作正常并显示结果 SELECT INTO temp table FROM md criteria join WHERE us
  • 如何初始化静态地图?

    你会如何初始化静态Map在Java中 方法一 静态初始化方法二 实例初始化 匿名子类 或者 还有其他方法吗 各自的优点和缺点是什么 这是说明这两种方法的示例 import java util HashMap import java util
  • Java中的回调接口是什么?

    SetObserver 接口的代码片段取自有效的Java 避免过度同步第67条 public interface SetObserver
  • 公共方法与公共 API

    在干净的代码书中 有一个观点是 公共 API 中的 Javadocs 同样 Effective java 一书也有这样的内容 项目 56 为所有公开的 API 元素编写文档注释 所以这就是我的问题 所有公共方法都被视为公共 API 吗 它们
  • 对于当前月份和日期但年份不同的日期,经过的月份计算未给出正确的结果

    我正在尝试计算自特定日期以来经过的月份 该函数工作正常 尽管如果我将今天的日期与过去的不同年份放在一起 它会给我一个月的差异 不到一个月 假设对于所有日期 该函数都运行良好 除了 如果今天是 2014 03 06 YYYY MM DD 并且
  • Java:使用 Graph API 在线更新 Sharepoint 上的 docx 文件

    我在使用 Java 在线更新 Sharepoint 上的 docx 文件时遇到问题 首先 我检查了构建 PUT 请求的 URL 此处 并使用此请求 PUT drives drive id items item id content 我首先使

随机推荐