我需要在C中实现内存中的字符串元组匹配功能。将有大量的元组与不同的动作相关联，并且有大量的事件要与该列表进行匹配。

元组列表：

("one", "four")
("one")
("three")
("four", "five")
("six")

事件("一个"，"两个"，"三个"，"四个")应与列表项("一个"，"四个")和("一个")和("三个")匹配，但不与列表项("四个"， "五个")而不是("六个")

我当前的方法使用所有元组字段值的映射作为使用该值的每个元组列表的键。有很多冗余的哈希和列表插入。

有没有正确或者经典的方式来做到这一点？

解决方案

我不知道这样做的任何经典方法或者正确方法，所以这是我会做的：P

似乎我们想使用集合论术语来确定A是否为B的超集。做到这一点的一种方法是对A和B进行排序，并对A和B进行合并排序排序操作，因为我们尝试查找B中的值在A中的位置。 B中也位于A中的那些元素将具有重复项，而其他元素则不会。由于A和B都已排序，所以这应该不太可怕。

例如，我们取B的第一个值，然后走A直到在A中找到它的重复项。然后取B的第二个值，并从先前离开的地方开始走A。如果我们未找到匹配项而到达A的末尾，则A不是B的超集，并且我们返回false。

如果这些元组可以保持排序，则排序成本仅产生一次。

如果我们只有少量的可能的元组值，那么编写某种散列函数可能会有意义，该函数可以将它们变成整数索引以便快速搜索。

如果值小于32，则可以使用位掩码进行操作：

unsigned int hash(char *value){...}

typedef struct _tuple {
    unsigned int bitvalues;
    void * data
} tuple;

tuple a,b,c,d;
a.bitvalues  = hash("one");
a.bitvalues |= hash("four");
//a.data = something;

unsigned int event = 0;
//foreach value in event;
event |= hash(string_val);

// foreach tuple
if(x->bitvalues & test == test)
{
     //matches
}

如果值太多，无法执行位掩码解决方案，则可以使用一系列链接列表。浏览事件中的每个项目。如果项与key_one相匹配，请使用第一个键浏览元组并检查第二个键的事件：

typedef struct _tuple {
    unsigned int key_one;
    unsigned int key_two;
    _tuple *next;
    void * data;
} tuple;

tuple a,b,c,d;
a.key_one = hash("one");
a.key_two = hash("four");

tuple * list = malloc(/*big enough for all hash indexes*/
memset(/*clear list*/);

//foreach touple item
if(list[item->key_one])
   put item on the end of the list;
else
   list[item->key_one] = item;

//foreach event
   //foreach key
      if(item_ptr = list[key])
        while(item_ptr.next)
           if(!item_ptr.key_two || /*item has key_two*/)
              //match
           item_ptr = item_ptr.next;

此代码未经测试，可能有许多小错误，但是我们应该明白这一点。 (已纠正的一个错误是元组匹配的测试条件)

如果事件处理的速度至关重要，那么遍历所有构造的元组，计算出现次数并可能对每个元组的键一/键二进行重新排序就很有意义，因此，最独特的值将首先列出。

如果可能的字符串数量很少，则可以为每个字符串分配一个索引并使用位图。这样简单的按位操作，就会告诉我们是否存在重叠。

如果这不切实际，那么倒排索引设置可能很难与速度匹配，特别是如果我们只需要构建一次的话。 (元组列表在运行时是否会更改？)

public static void Main()
    {
        List<List<string>> tuples = new List<List<string>>();

        string [] tuple = {"one", "four"};
        tuples.Add(new List<string>(tuple));

        tuple = new string [] {"one"};
        tuples.Add(new List<string>(tuple));

        tuple = new string [] {"three"};
        tuples.Add(new List<string>(tuple));

        tuple = new string[]{"four", "five"};
        tuples.Add(new List<string>(tuple));

        tuple = new string[]{"six"};
        tuples.Add(new List<string>(tuple));

        tuple = new string[] {"one", "two", "three", "four"};

        List<string> checkTuple = new List<string>(tuple);

        List<List<string>> result = new List<List<string>>();

        foreach (List<string> ls in tuples)
        {
            bool ok = true;
            foreach(string s in ls)
                if(!checkTuple.Contains(s))
                {
                    ok = false;
                    break;
                }
            if (ok)
                result.Add(ls);
        }
    }

一种可能的解决方案是为每个单词分配唯一的质数。

然后，如果将每个元组中的单词相乘，那么我们将获得一个代表列表中单词的数字。

将一个列表除以另一个，如果得到整数余数，则一个列表将包含在另一个列表中。