6

我必须通过分析格式化结果来启发式地确定格式模式字符串。

例如我有这些字符串:

您有3条未读消息。

您有10条未读消息。

对不起,戴夫。恐怕我做不到。

对不起,弗兰克。恐怕我做不到。

这种说法是错误的。

我想派生这些格式字符串:

您有%s 条未读消息

对不起,%s。恐怕我做不到。

这种说法是错误的。

哪些方法和/或算法可以在这里帮助我?

我的第一个想法是使用机器学习的东西,但我的直觉告诉我这可能是一个相当经典的问题。

一些额外的要求:

  • %s参数的类型无关紧要,即如果参数最初是,或者%d如果它被填充或对齐,我不需要信息。
  • 可以有多个参数(或根本没有)
  • 通常,数据由数千个格式化字符串组成,但只有几十个格式模式。
4

1 回答 1

1
  1. 通过某种相似性度量对字符串进行聚类(我会尝试最长公共子序列的长度,LCS)。如果您事先不知道,确定集群的数量是困难的部分。

  2. 在每个簇中,确定其中所有字符串的 LCS,记录出现的间隙的位置。用 替换间隙%s。(您可能希望构建一个函数,该函数返回基于 LCS 的格式字符串和fold/reduce在集群上。)

上面是一个贪心算法,给定 { foobar, fooBaR} 产生foo%sa%s。您可能希望用单个递归替换%s由单个字符(或单个非空白字符等)分隔的任何一对出现。%s

于 2011-02-11T09:04:31.187 回答