程序员经验分享-hwhale

如何正确区分树（即嵌套的字符串列表）？

2024-04-24

我正在使用由嵌套字符串列表组成的数据类型的在线编辑器。请注意，如果每次更改单个值时我都要传输整个结构，那么流量可能会变得难以忍受。所以，为了减少流量，我想到了应用 diff 工具。问题是：如何找到并报告两棵树的差异？例如：

["ah","bh",["ha","he",["li","no","pz"],"ka",["kat","xe"]],"po","xi"] ->
["ah","bh",["ha","he",["li","no","pz"],"ka",["rag","xe"]],"po","xi"]

在那里，唯一的变化是"kat" -> "rag"在树的深处。大多数 diff 工具适用于平面列表、文件等，但不适用于树。我找不到任何关于该特定问题的文献。报告此类变化的最小方式是什么？找出它的有效算法是什么？


XML 是一种常用的树状数据结构，通常用于描述结构化文档或其他需要监视其随时间变化的分层对象。因此，最近树比较方面的大部分工作都是在 XML 环境中进行的，这应该不足为奇。

这是 2006 年的一项调查，其中包含许多可能有用的链接：XML 树中的更改检测 http://www-poleia.lip6.fr/~gancarsk/grbd09/2005_03_B_Peters,L.J.-Change_detection_in_XML_trees_a_survey.pdf

上面的更有趣的链接之一，伴随着一个名为 TreePatch 的开源实现，但现在似乎已不复存在：Kyriakos Komvoteas 的论文 http://treepatch.sourceforge.net/report.pdf

另一篇调查文章，作者：丹尼尔·埃伦伯格 http://www.scribd.com/doc/14482474/XML-diff-survey，还有更多参考文献。 （那个来自question https://cstheory.stackexchange.com/questions/10205/efficient-diff-algorithm-for-trees-and-levenshtein-distance on http://cstheory.stackexchange.com http://cstheory.stackexchange.com)

祝你好运。

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

Algorithm

datastructures

languageagnostic

diff

如何正确区分树（即嵌套的字符串列表）？ 的相关文章

  • 树中的节点是否被视为其自己的祖先？

    我想知道计算机科学背景下对 祖先 定义的共识是什么 我问只是因为在算法简介 http en wikipedia org wiki Introduction to Algorithms 第二版 第 14 页 第259章 有算法的描述Tree

  • 以与版本页面上相同的方式区分两个字符串的算法是什么？

    我正在尝试按短语区分两个字符串 类似于 StackOverflow 在版本编辑页面上区分两个字符串的方式 执行此操作的算法是什么 是否有 gems 或其他标准库可以实现此目的 编辑 我见过其他比较算法 Differ http github

  • 如何使用 diff 排除多行模式？

    我想对两个 xml 文件进行比较 但忽略 2 3 行模式 例如 假设我想在比较下面的 xml 格式时忽略可用性和价格 这是我到目前为止所拥有的 diff I

  • PHP 中的 MPTT（修改的先序树遍历）问题

    我的第一篇文章在这里 看来这是一个变得明智的地方 我目前正在进行一些测试 第一次尝试使用 MPTT 修改的预序树遍历 方法在 PHP 的帮助下将数据存储在 Mysql 数据库中 但是 我试图找到最注重性能的方法来获取特定级别上的所有列表元素

  • 是否可以更改 Mercurial 中的默认 diff 工具？

    每次我做一个hg diff file ext我最终使用了控制台差异应用程序 我想使用 Kdiff3 或 WinMerge 我使用的是 Windows 有办法改变吗 我在 Mercurial 文档中找不到参考 我不是在谈论合并 我已经使用 M

  • 使用 NSMutableDictionary 与 NSMutableArray 造成的性能损失>

    我正在考虑使用 NSMutableDictionary 代替我当前的 NSMutableArray 这主要是出于 KVC KVO 的原因 该集合将在我的绘图方法的内循环中经历严重的变化 如果我继续进行此替换 性能是否会受到重大影响 干杯 道

  • 如何最小化两个子多边形的最大纵横比？

    我想使用直线将凸多边形切成给定面积比的两部分 以使两个子多边形的较大纵横比最小化 目前我的方法包括选择一个随机起点 计算将多边形分割成目标区域的适当终点 然后计算两个纵横比中较大的一个 然后重复这个很多次 直到我足够接近最小值 多边形 A

  • 替代位置基础系统（十六进制、八进制、二进制）如何工作？如何将它们转换为十进制？

    我以前在编程课上没有学过这一点 但现在我需要知道它 有哪些学习这些数字以及如何转换它们的好资源 我几乎会像记住乘法表一样记住这些 在我们日常的十进制系统中 基数或radix http en wikipedia org wiki Radix

  • 如何找到最长的回文子序列（不是它的长度）

    我想找出字符串中最长的回文子序列 我到处都找到了找出子序列长度的算法 并声明该算法也可以扩展以返回子序列 但我没有找到如何实现的 有人能解释一下我怎样才能得到序列吗 既然你提到了链接最长回文子序列 http www geeksforgeek

  • Java：使用indexOf方法根据另一个数组对数组进行排序

    我想根据另一个数组 索引 的排序顺序迭代两个数组 A B 在本例中为 10 34 32 21 String A a b c d String B e f g h int indexes 10 34 32 21 为这里的坏例子道歉 我已经更新

  • 添加到数组连续数字

    这是我向SO提出的第一个问题 我希望能答对 在 PHP 中 如果你不会 Python 或伪语言也可以 给定一个包含 n 个元素的数组 old array 1 2 3 5 7 8 9 20 21 23 29 我需要向新数组添加连续数字 如果不

  • 检查数独字段的很酷的算法？

    有谁知道一个简单的算法来检查数独配置是否有效 我想出的最简单的算法是 对于大小为 n 的板 伪代码 for each row for each number k in 1 n if k is not in the row using ano

  • 稀疏矩阵中的最大和子矩形

    求一个子矩形中的最大和NxN矩阵可以完成O n 3 正如其他帖子中指出的 使用 2 d kadane 算法的时间 然而 如果矩阵是稀疏的 具体来说O n 非零条目 可以O n 3 时间被打败了吗 如果有帮助的话 对于我感兴趣的当前应用程序

  • 交换两个向量之间的值，使两个向量的 max_element 之和最小

    这是 Codechef 的问题 但请耐心等待 https www codechef com ZCOPRAC problems ZCO16001 https www codechef com ZCOPRAC problems ZCO16001

  • Lockfree 标准集合和教程或文章

    有人知道用于无锁常用数据类型的实现 即源代码 的好资源吗 我正在考虑列表 队列等 锁定实现非常容易找到 但我找不到无锁算法的示例以及 CAS 的工作原理以及如何使用它来实现这些结构 查看 Julian M Bucknall 的博客 他 详细

  • 在无向图中查找强连通分量

    我想在无向图中找到强连接的组件 即如果我从节点开始A然后我会回到节点A并且每条边都被恰好访问一次 对于有向图可以使用Tarjan算法来寻找强连通分量 但是对于无向图怎么办 我认为您错过了强连通分量的含义 强连接组件 如果所有顶点对之间都存在

  • 如何在Scala中实现尾递归快速排序

    我写了一个递归版本 def quickSort T xs List T p T T gt Boolean List T xs match case Nil gt Nil case gt val x xs head val left righ

  • 加密成本高，解密成本低

    我希望该用户 攻击者加密数据并发送给服务器 现在我想要一种与标准算法完全相反的算法 使用快 难以解密 即很难使用服务器发送的密钥来加密密码等数据 以防止随机攻击 但很容易解密这样服务器在验证用户时消耗的时间非常少 但是对于攻击者来说 每次使

  • 哪种数据聚类算法适合检测时间序列事件中未知数量的聚类？

    这是我的场景 考虑在不同地点和时间发生的一组事件 例如 考虑有人在高空记录暴风雨期间城市中的雷击 就我的目的而言 闪电是瞬时的 只能击中某些位置 例如高层建筑 还可以想象每次雷击都有一个唯一的 ID 以便以后可以参考该雷击 这个城市大约有1

  • 在关键服务器上对字符串进行内存受限的外部排序，并合并和计算重复项（数十亿个文件名）

    我们的服务器生成如下文件 c521c143 2a23 42ef 89d1 557915e2323a sign xml在其日志文件夹中 第一部分是GUID 第二部分是名称模板 我想计算具有同名模板的文件的数量 例如 我们有 c521c143

随机推荐

  • 在模拟的 HttpContextBase 上设置属性

    我正在开发一个 ASP NET MVC 应用程序 并尝试针对控制器操作编写一些单元测试 其中一些操作 HttpContext 上的属性 例如 Session Request Cookies Response Cookies 等 在弄清楚如何

  • OpenTok - 如何手动发布/取消发布？

    我查看了这些链接 http www tokbox com opentok api tools js documentation overview publish html http www tokbox com opentok api to

  • 无法获取未知属性“组装”

    所以 昨天一切都很好 但现在 Android Studio 和我的项目抛出了这个错误 ERROR Could not get unknown property assemble for task patternjkh assembleDeb

  • android AlertDialog 具有透明背景

    我有一个自定义的 AlertDialog 我想使其背景完全透明 通常为了使活动完全透明 我会执行以下操作 将背景设置为 00000000在 xml 布局中 在清单集中android theme android style Theme Hol

  • 如何避免在php中刷新时重新发送数据

    我有一个页面 index php 其中有一个名为 add users php 的链接 在 add users php 中 我接受用户信息并返回到同一页面 index php 其中信息通过后操作传入并插入到数据库中 当我刷新页面或点击后退按钮

  • 如何在 Swift 中打开 URL？

    openURL已在 Swift 3 中弃用 任何人都可以提供一些如何替换的示例openURL options completionHandler 尝试打开网址时有效吗 所有你需要的是 guard let url URL string htt

  • C++ 中有标准的日期/时间类吗？

    C stl 有标准时间类吗 或者我是否必须在写入流之前转换为 c 字符串 例如 我想将当前日期 时间输出到字符串流 time t tm ostringstream sout sout lt lt tm lt lt ends 在本例中 我将当

  • 有没有好的方法来检查 Datastax Session.executeAsync() 是否引发异常？

    我试图通过调用来加速我们的代码session executeAsync 代替session execute 用于数据库写入 我们有数据库连接可能会关闭的用例 目前是之前的execute 当连接丢失 集群中没有可访问的主机 时抛出异常 我们可

  • 如何检查字符串是否是数字？ [复制]

    这个问题在这里已经有答案了 我有一个 GPA 计划 它适用于equalsIgnoreCase 方法比较两个字符串 即字母 a 与用户输入 检查他们是否输入 a 但现在我想添加一个异常 其中包含当输入数字时执行的错误消息 我希望程序意识到整数

  • 与 C++ 中的对象数组混淆

    所以我首先学习了Java 现在我正在尝试转向C 我在让数组正常工作方面遇到了一些困难 现在我只是想创建一个对象 Player 的数组并用一个对象填充它 但我收到错误 Player players new Player 1 players 0

  • Pydub 按样本切片音频片段

    假设我有两个采样率相同的音频片段 它们是从 Pydub 中的 wav 文件导入的 并且假设我知道哪个更短 现在假设我想将较长的音频文件分成两个片段 以便第一个片段与较短的音频文件具有完全相同的长度 精确到相同的样本数量 并将这两个片段中的每

  • 在离散 ggplot x 轴两侧添加不同数量的额外空间

    我有一个带有离散 x 轴的图 我想调整刻度两侧的额外空间 使其左侧较小 右侧较大 以便长标签适合 scale x discrete expand c 0 1 不是我的朋友 因为它总是同时在双方工作 这个问题 https stackoverf

  • 提取 HTML 表单的字段名称 - Python

    假设有一个链接 http www someHTMLPageWithTwoForms com 它基本上是一个具有两种表单 例如表单 1 和表单 2 的 HTML 页面 我有这样的代码 import httplib2 from Beautifu

  • 解析回调未定义 - 简单的 Webscraper (Scrapy) 仍未运行

    我google了半天还是没能搞定 也许你有一些见解 我尝试不是从终端而是从脚本启动我的抓取工具 这在没有规则的情况下运行良好 只需产生正常的解析函数即可 一旦我使用规则并将 callback parse 更改为 callback parse

  • 无法使 PHP PDT xDebug 在 Eclipse 中的断点处停止

    通过选择 在第一行中断 调试器会在输入每个文件时激活 从而允许我单步进入和退出代码 但是 必须通过 50 万步才能到达开始变得有趣的地步 这有点麻烦 我的设置是 WIMP Window 7 PHP 5 3 xDebug config zen

  • VotingClassifier：不同的功能集

    在我的例子中 我有两个不同的功能集 因此 行数相同且标签相同 DataFrames df1 A B C 1 4 2 1 4 8 2 1 1 2 3 0 3 2 5 df2 E F 6 1 1 3 8 1 2 8 5 2 labels lab

  • Azure DevOps 构建变量 Build.Reason 是否可以在 YAML 模板编译时条件中使用？

    我想要这样的东西 if or eq parameters RunTestsOnPRBuildOnly false eq variables Build Reason PullRequest template ps module run te

  • F# 中的组总计 - 使用序列很容易，可以使用列表吗？

    给定一组 id value 元组序列 很容易计算组总数 与使用 C 和 LINQ 执行此操作的方式几乎相同 let items g1 5 g2 10 g1 20 let groupsums items gt Seq groupBy fun

  • Android 中的 GZIP

    我只是想问一下在Android 中使用HttpClient 发送gzip 进行post 请求 在哪里获取要在 GZIPOutputstream 中传递的 OutputStream 有片段吗 您好 UseHttpUriRequest 如下所示

  • 如何正确区分树（即嵌套的字符串列表）？

    我正在使用由嵌套字符串列表组成的数据类型的在线编辑器 请注意 如果每次更改单个值时我都要传输整个结构 那么流量可能会变得难以忍受 所以 为了减少流量 我想到了应用 diff 工具 问题是 如何找到并报告两棵树的差异 例如 ah bh ha

热门标签