Поиск алгоритма соответствия кортежа

Мне нужно реализовать функцию сопоставления кортежей в памяти в C. Будет большой список кортежей, связанных с разными действиями, и большой объем событий, которые будут сопоставлены с этим списком.

Список кортежей:

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

( "один" , "два", "три", "четыре" ) должны соответствовать элементу списка ( "один" , "четыре" ) и ( "один" ) и ( "три" ), но не ( "четыре", "пять" ) и не ( "шесть" )

мой текущий подход использует карту всех значений поля кортежа в качестве ключей для списков каждого кортежа с использованием этого значения. существует много избыточного хеширования и вставки списка.

есть ли правильный или классический способ сделать это?

Ответ 1

Если у вас есть только небольшое количество возможных значений кортежа, имеет смысл написать какую-то функцию хэширования, которая может превратить их в целые индексы для быстрого поиска.

Если есть < 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;

Этот код никоим образом не проверен и, вероятно, имеет много небольших ошибок, но вы должны получить эту идею. (одна ошибка, которая была исправлена, была условием проверки соответствия кортежа)

Если скорость обработки событий имеет первостепенное значение, имеет смысл перебирать все ваши построенные кортежи, подсчитывать количество вхождений и проходить, возможно, переупорядочивая ключ один/ключ два из каждого кортежа, поэтому самое уникальное значение перечислено первым.

Ответ 2

Возможным решением было бы присвоить каждому из них уникальное простое число.

Затем, если вы умножаете слова вместе в каждом кортеже, у вас есть число, которое представляет слова в списке.

Разделите один список на другой, и если вы получите целочисленный остаток, то один список содержится в другом.

Ответ 3

Я не знаю какого-либо классического или правильного способа сделать это, поэтому вот что я буду делать: P

Похоже, вы хотите решить, является ли A надмножеством B, используя жаргон теории множеств. Один из способов сделать это - сортировать A и B и выполнять операцию сортировки слияния на A и B, в которой вы пытаетесь найти, где находится значение A в строке B. Те элементы B, которые также находятся в A, будут иметь дубликаты, а другие элементы не будут. Поскольку и A, и B сортируются, это не должно быть слишком ужасным.

Например, вы берете первое значение B и пропустите A до тех пор, пока не найдете его дубликат в A. Затем вы берете второе значение B и начинаете движение A от того места, где вы остановились ранее. Если вы дойдете до конца A, не найдя совпадения, то A не является надмножеством B, и вы вернете false.

Если эти кортежи могут сортироваться, стоимость сортировки возникает только один раз.

Ответ 4

Если у вас есть небольшое количество возможных строк, вы можете присвоить каждому индексу и использовать растровые изображения. Таким образом, простой поразрядный и скажет вам, если они перекрываются.

Если это непрактично, ваша инвертированная установка индекса, вероятно, будет трудно сопоставить для скорости, особенно если вам нужно только создать ее. (меняется ли список кортежей во время выполнения?)

Ответ 5

    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);
        }
    }