0

假设有许多已知是由单个模板生成的文本（例如，许多 HTML 页面，由某种数据库中的数据支持的模板呈现）。一个非常简单的例子：

id:937 name=alice;
id:28 name=bob;
id:925931 name=charlie;

仅给定这 3 个文本，我想获得如下所示的原始模板：

"id:" + $1 + " name=" + $2 + ";"

以及与此模板一起使用的 3 组字符串：

  • $1 = 937, $2 =alice
  • $1 = 28, $2 =bob
  • $1 = 925931, $3 =charlie

换句话说，“模板”是所有给定文本中遇到的公共子序列的列表，总是以一定的顺序出现，除了这些子序列之外的所有其他内容都应该被视为“数据”。

我猜一般算法将与任何 LCS（最长公共子序列）算法非常相似，尽管使用不同的回溯代码，它会以某种方式将“模板”（所有给定文本的通用字符）和“数据字符串”（不同字符）分开。

额外的问题：有现成的解决方案吗？

4

2 回答 2

2

我同意关于这个问题定义不明确的评论。格式似乎比您的一般问题所表明的要具体得多。

话虽如此，像RecordBreaker这样的东西可能会有所帮助。你也可以谷歌“包装归纳”来看看你是否找到了一些有用的线索。

于 2013-10-11T17:26:26.263 回答
1

执行全局多序列比对，然后调用模板中具有常量值部分的每个结果列：

                   id:   937 name=alice  ;
                   id: 28    name=bob    ;
                   id:925931 name=charlie;
Inferred template: XXX      XXXXXX       X

我所知道的用于多序列比对的大多数工具都需要较小的字母表——DNA 或蛋白质——但希望你能找到一种适用于你正在使用的字母表的工具（大概至少是所有可打印的 ASCII 字符）。在最坏的情况下，您当然可以自己实现 DP：要全局对齐 2 个序列（字符串），您使用Needleman-Wunsch 算法，而对于两个以上的序列，有几种方法，最常见的是 sum-of-pairs得分。不幸的是，k > 2 序列的精确算法在 k 中需要时间指数，但是在MUSCLE等生物信息学工具中采用的启发式算法速度更快，并且产生几乎一样好的对齐方式。如果可以说服他们使用您正在使用的字母表，那么他们将是自然的选择。

于 2013-10-11T17:45:51.340 回答