3

我有一个旨在查找应用程序搜索功能中的错误的函数，它从非控制 UTF-8 可能性生成一个可变长度的搜索字符串。在此函数上运行 pytest 迭代，提交用于搜索的随机 UTF-8 字符串大约每 500 次搜索生成一次调试错误。

由于我可以抓取导致错误的每个字符串，因此我想确定这些字符串中真正引起错误的字符的最小子系列是什么。换句话说，（在 pytest 循环内）：

def fumble_towards_ecstasy(string_that_breaks):
    # iterate over both length and content of the string
        nugget = # minimum series of characters that break the search
        return nugget

我是否应该将字符串切成两半并削减每一边并重新提交直到它失败，从它的 (len() - 1) 中选择随机字符，然后如果没有发生错误则备份？蛮力组合？解决这个问题的最佳方法是什么？

谢谢。

4

3 回答 3

2

如果存在导致失败的两个字符序列，并且该序列恰好位于中间，则将字符串分成两半将失败。每一半都成功，但组合字符串失败。

这是一种可以找到局部最小值的算法：

尝试依次删除每个字符。

  • 如果删除字符仍然导致失败，请保留新的较短字符串并在此新字符串上重复算法。
  • 如果删除字符不再导致失败，请将其放回并尝试删除下一个字符。继续前进，直到没有更多的角色可以尝试。当您到达字符串的末尾时，您知道删除任何一个字符都会导致搜索成功。
于 2012-08-25T23:48:59.733 回答
1

我会使用“从双方削减”的方法。拆分字符串总是会冒着破坏导致错误的子字符串的风险。我的方法是：

  1. 尽可能多地从字符串左侧弹出字符，同时仍确保字符串会导致错误。
  2. 对右侧做同样的事情。
  3. 理论上，您只剩下导致错误的最小子字符串。

希望有帮助！

于 2012-08-25T23:54:11.290 回答
0

首先值得注意的是，解决方案可能不是唯一的，即可能存在两个或多个损坏的子串。

另一个建议（对 Xavier 和 Mark 的好答案）是运行递归方法。使用导致错误的有限字符串子集重复采样。一旦发现另一个错误，重复直到达到最小子字符串。这种方法足够强大，可以处理更复杂的用例，其中错误可能存在于两个不相邻的条目中。我认为这里不是这种情况，但是有一个通用的 purpopse 方法很好。

于 2013-05-07T14:34:15.633 回答