我有一堆回归测试数据。每个测试只是消息列表(关联数组)，将消息字段名称映射为值。这些数据中有很多重复项。

例如

test1 = [
      { sender => 'client',  msg => '123',  arg => '900', foo => 'bar', ... },
      { sender => 'server',  msg => '456',  arg => '800', foo => 'bar', ... },
      { sender => 'client',  msg => '789',  arg => '900', foo => 'bar', ... },
   ]

我想表示现场数据(作为最小深度决策树？)，以便可以使用最少数量的参数以编程方式重新生成每条消息。例如，在上面

• foo始终是" bar"，因此我无需提及
• 发件人和客户之间是相关的，所以我只需要提及一个或者另一个
• 味精每次都不同

因此，我希望能够使用以下程序通过程序重新生成这些消息：

write_msg( 'client', '123' )
write_msg( 'server', '456' )
write_msg( 'client', '789' )

其中write_msg函数由嵌套的if语句或者使用参数的子函数调用组成。

根据原始数据，如何确定"最重要"的参数集，即可以让我使用最少数量的参数来重新创建数据集的参数？

解决方案

这看起来与数据库规范化非常相似。

我们有一个关系(测试数据集)，以及一些已知的功能依赖性({sender} => arg，{} => foo以及可能的{msg} => sender。如果测试的顺序很重要，请添加{testNr} => msg。)，我们想消除冗余。

将测试集视为数据库表，应用规范化规则并为每个联接创建等效函数(getArgFromSender(sender)等)。

如果字段和记录的数量很少：

通过遍历字段的每个组合来强行使用它，并针对每个组合检测列表中是否存在多个映射到相同值的项。

如果我们可以选择相当不错的字段：

首先假设我们需要所有字段。然后，随机选择一个字段，看看是否可以消除它；如果可以的话，将其划掉字段范围。否则，请随机选择另一个字段，然后重试。如果我们发现没有可以消除的字段，那么我们已经找到了一组合理的字段。如果我们首先选择了其他领域，则可能会找到更好的解决方案。我们可以重复整个过程几次，并根据需要选择最佳解决方案。这种方法称为爬山。

(我怀疑这个问题是NP完整的，即我们可能不知道有效而强大的解决方案，因此不应该因为梦想出一个完美的解决方案而失去睡眠)

以下论文描述了用于发现功能依赖项的算法：

Y. Huhtala, J. K?rkk?inen, P. Porkka,
  and H. Toivonen.  TANE: An efficient
  algorithm for discovering functional 
  and approximate dependencies. The
  Computer Journal,  42(2):100–111,
  1999, doi:10.1093/comjnl/42.2.100.
  
  I. Savnik and P. A. Flach. Bottom-up
  induction of functional  dependencies
  from relations. In Proc. AAAI-93 Workshop:
  Knowledge Discovery in Databases,
  pages 174–185, Washington,  DC, USA,
  1993. 
  
  C. Wyss, C. Giannella, and E.
  Robertson. FastFDs: A 
  Heuristic-Driven, Depth-First
  Algorithm for Mining Functional
  Dependencies from Relation Instances.
  In Proc. Data Warehousing and Knowledge Discovery, pages 101–110, Munich,
  Germany, 2001, doi:10.1007/3-540-44801-2.
  
  Hong Yao and Howard J. Hamilton. "Mining functional dependencies from data."  Data Mining and Knowledge Discovery, 2008, doi:10.1007/s10618-007-0083-9.

在发现多值依赖项方面也有一些工作：

I. Savnik and P. A. Flach. "Discovery
  of Mutlivalued Dependencies from
  Relations." Intelligent Data Analysis
  Journal, 4(3):195–211, IOS Press, 2000.