Dan*_*ski 6 language-agnostic string algorithm pattern-matching format-string
我必须通过分析格式化结果来启发式地确定格式模式字符串.
例如,我有这些字符串:
你有3条未读消息.
您有10条未读消息.
对不起,戴夫.我恐怕不能那样做.
对不起,弗兰克.我恐怕不能那样做.
这句话是错误的.
我想导出这些格式字符串:
您有%s条未读邮件
对不起,%s.我恐怕不能那样做.
这句话是错误的.
哪种方法和/或算法可以帮助我？
我的第一个想法是使用机器学习的东西,但我的胆量告诉我这可能是一个相当经典的问题.
一些额外要求:
%s或者%d填充或对齐,我不需要信息.通过某种相似性度量对字符串进行聚类（我会尝试最长公共子序列的长度，LCS）。如果您事先不知道的话，确定簇的数量是困难的部分。
在每个簇内，确定其中所有字符串的 LCS，记录出现间隙的位置。将间隙替换为%s。（您可能想要构建一个返回基于 LCS 的格式字符串和fold/或reduce在集群上返回的函数。）
上面是一个贪心算法，给定 { foobar, fooBaR} 产生foo%sa%s。您可能希望以递归%s方式将由单个字符（或单个非空白字符等）分隔的任何一对出现的 替换为单个%s。