如何在Python中进行如下有序子集元素测试？

Question

我有一个字典（称为 dict），其键是表示特征名称的字符串，其值是表示每个特征计数的浮点数。

这是我的字典 (dict) 的示例：

{'11268-238-1028': 2.0, '1028': 10.0, '10295': 2.0, '1781': 2.0, '11268-238': 3.0, '6967-167': 1.0, '9742-232-788': 1.0, '8542': 4.0, '238-1028': 5.0, '1028-122': 1.0}

在此示例中，“10295”被视为一级特征，“6967-167”被视为二级特征，而“9742-232-788”被视为三级特征。如果我们有'x-x-x-x-x-x-x'，那么它就是一个七度特征。换句话说，对于任何 n 度特征，该特征具有 (n-1) 个破折号 ('-')。

'11268-238-1028': 2.0表示3度特征'11268-238-1028'的计数为2.那么我们看到'11268-238':3.0,表示'11268' -238' 出现 3 次。然而，这是一些重复计算问题，因为在 3 次出现的“11268-238”中，有 2 次实际上是由于“11268-238-1028”的出现。因此，我们要将'11268-238'的计数改为它的实际计数，即3-2 = 1。

同样，'238-1028'的实际计数不是5，因为'238-1028'是'11268-238-1028'的一部分，而'11268-238-1028'的计数为2 . 所以，'238-1028'的真实计数应该是(5-2 = 3)。

另一个例子是特征'1028'，它的实际计数不应该是10。'1028'是3度特征'11268-238-1028'的一部分，它的计数为2。' 1028'也是计数为5的2度特征'238-1028'的一部分。'1028'也是计数为1的2度特征'1028-122'的一部分。因此，实际计数1 度特征“1028”应该是 (10-2-5-1 = 2)。

我应该用什么样的算法来解决这个问题？

我考虑过将每个键转换为一组由破折号分割的 1 度特征，然后针对每个集合，对所有其他具有更高长度的集合进行子集成员资格测试。但是，set 存储无序元素，但我关心顺序。例如，特征 '11268-238-1028' 转换为集合将是 (['11268', '238', '1028']);转换为集合的另一个特征 '11268-1028' 是 (['11268', '1028'])。如果我对这两个特征集执行子集测试，我会得出结论，(['11268', '1028']) 是 (['11268', '238', '1028']) 的子集。但是，特征“11268-1028”不是特征“11268-238-1028”的子集，因为在“11268”和“1028”之间，还有一个东西“238”，即顺序应该很重要。

那我该如何解决这个问题呢？

非常感谢！

Answer 1

将您的问题分解成更小、更简单的问题

首先让我们编写一个辅助函数来实际调整我们的数据字典

# this assumes we have one big feature (ie 3) and several smaller features(ie 2&1)
def adjust_data(big_feature,smaller_features,data):
    for feature in smaller_features:
        if feature.count("-") == big_feature.count("-"):
           continue # skip any features that are the same size as our target
        #3 cases for a sub feature it starts with ends with or is contained
        # we use delimiters to eliminate partial matches
        does_start = big_feature.startswith(feature+"-") 
        does_end = bigfeature.endswith("-"+feature) 
        does_contain = "-"+feature+"-" in big_feature
        if does_start or does_end or does_contain :
            # one of our cases match so this is a sub feature of our big feature
            data[feature] -= data[big_feature]

现在，在使用它之前，我们需要组织我们的数据，以便对其进行适当的排序。

 sorted_keys = sorted(my_data_dict.keys(),
                      key=lambda key:key.count("-"), 
                      reversed=True) #we want bigger features on top

现在沿着我们排序的 data_list

  for i,key in enumerate(sorted_keys,1):
      adjust_data(key,sorted_keys[i:],my_data_dict)

这只是蛮力，所以它不会那么快，但它会完成工作

Answer 2

在第一次创建 dict 时防止重复计数比以后撤消要容易得多。

但是假设不能重新创建dict。这是一个解决方案。它不假设对于每个较高度数的特征，每个度数都保证有较低度数的对应物（即，对于特征 A1-A2-...-An，您可能会遗漏 A1、A1-A2 中的任何一个等，直至 A1-A2-...-An-1)。如果这个假设确实成立，一些 try-except 可以简化掉。

def undo_double_counting(d):
    sorted_features = sorted(d, key=lambda f: f.count('-'), reverse=True)
    for f in sorted_features:
        if '-' not in f:
            return d
        feature_below, _ = f.rsplit('-', 1)
        while True:
            try:
                d[feature_below] -= d[f]
            except KeyError:
                # if the feature one degree below isn't actually in d,
                # we keep trying lower degrees until we know that we
                # can't go lower any more (by hitting ValueError)
                try:
                    feature_below, _ = feature_below.rsplit('-', 1)
                except ValueError:
                    break
            else:
                break
    # if there are no degree-1 features in d, return here
    return d

在您的数据上尝试（顺便说一句，为什么是浮点数，而不是整数？）：

{'1028': 9.0,
 '1028-122': 1.0,
 '10295': 2.0,
 '11268-238': 1.0,
 '11268-238-1028': 2.0,
 '1781': 2.0,
 '238-1028': 5.0,
 '6967-167': 1.0,
 '8542': 4.0,
 '9742-232-788': 1.0}

如何在Python中进行如下有序子集元素测试？

How to perform the following ordered subset element test in Python?

python

dictionary

set

subset

python-2.7