Множественный алгоритм сопоставления событий

Question

У меня есть задача сопоставить несколько событий (фактов) друг с другом некоторыми их свойствами. В результате события, соответствующие некоторому действию, должны быть сгенерированы. Действие может быть создано при сопоставлении событий всех существующих типов.

Есть ли какой-либо алгоритм, который можно было бы использовать для такой задачи? Или в любом направлении?

Благодаря

Пример: У нас есть несколько событий с различными типами и свойствами. Тип SEEN is Накопительное Событие (возможно объединение нескольких событий для соответствия) и типа НАЙТИ.

Event 1 (SEEN): 
DATE="2009-09-30" 
EYES_COLOR="BLUE" 
LEFT_SOCK_COLOR="RED" 

Event 2 (SEEN): 
DATE="2009-09-30" 
EYES_COLOR="BLUE" 
RIGHT_SOCK_COLOR="GREEN" 

Event 3 (FOUND): 
DATE="2009-09-30" 
EYES_COLOR="BLUE" 
LEFT_SOCK_COLOR="BLUE" 
RIGHT_SOCK_COLOR="GREEN" 
PLACE="MARKET" 

Event 4 (FOUND): 
DATE="2009-09-30" 
EYES_COLOR="BLUE" 
LEFT_SOCK_COLOR="GREEN" 
PLACE="SHOP" 

Event 5 (FOUND): 
DATE="2009-09-30" 
EYES_COLOR="BLUE" 
PLACE="AIRPORT" 

Для вышеуказанных событий таких действий должны быть сформированы (сочинение совпавших событий):

Action 1_2_3: 
DATE="2009-09-30" 
EYES_COLOR="BLUE" 
LEFT_SOCK_COLOR="RED" 
RIGHT_SOCK_COLOR="GREEN" 
PLACE="MARKET" 

Action 2_4: 
DATE="2009-09-30" 
EYES_COLOR="BLUE" 
LEFT_SOCK_COLOR="GREEN" 
PLACE="SHOP" 

Средство:

Event 1 + Event 2 + Event 3 => Action 1_2_3 
Event 2 + Event 4 => Action 2_4 
Event 5 does not match with anything. 

Answer 1

в вашем случае каждые два события, либо совместимы или нет; мы можем обозначить это через C (e, e '), что означает, что событие e совместимо с событием e'. Вы можете построить максимальный набор совместимых событий, конечно, итеративно; когда у вас есть набор {e1, e2, ..., en} совместимых событий, вы можете добавить e 'в набор тогда и только тогда, когда e' совместимо с каждым e1, ..., en, т.е. C (ei , e ') верно для всех 1 < = i < = n.

К сожалению, в вашем случае число максимальных наборов совместимых событий может быть экспоненциальным по отношению к числу событий, так как вы можете иметь, например, события e1, e2, e3 и e4, так что они все совместимы с маской, но ни одна из них не совместима с двумя другими событиями; для этого набора вы уже получите 6 разных «действий», и они перекрывают друг друга.

Простой алгоритм состоит в том, чтобы иметь рекурсивный поиск, в котором вы добавляете события один за другим в проспективное «действие», и когда вы не можете добавлять какие-либо события, вы регистрируете действие; то ты возвращаешься. Это называется поиском обратного отслеживания. Вы можете улучшить свое время работы, а затем правильными структурами данных для «быстрого» поиска соответствующих событий.

Как и в комментарии, вопрос о SEEN/FOUND открыт; Я предполагаю, что поля объединяются «как есть».

Answer 2

Этот псевдо-код может помочь: (C# синтаксис)

foreach (var found in events.Where(x => x.EventType == "Found")) 
{ 
    var matches = events.Where(x => x.EventType == "Seen" 
           && x.Whatever == found.Whatever); 
    if (matches.Count() > 0) 
    { 
     // Create an action based on the single "Found" event 
     // and the multiple matching "Seen" events. 
    } 
} 

Answer 3

Я не уверен, что понял вопрос правильно. Кажется, что для каждого события FOUND вы хотите определить все соответствующие события SEEN и объединить их? код Python:

# assume events are dictionaries, and you have 2 lists of them by type: 

# (omitting DATE because it's always "2009-09-03" in your example) 
seen_events = [ 
    { 
     "EYES_COLOR": "BLUE", 
     "LEFT_SOCK_COLOR": "RED", 
    }, 
    { 
     "EYES_COLOR": "BLUE", 
     "RIGHT_SOCK_COLOR": "GREEN", 
    }, 
] 

found_events = [  
    { 
     "EYES_COLOR": "BLUE", 
     "LEFT_SOCK_COLOR": "BLUE", 
     "RIGHT_SOCK_COLOR": "GREEN", 
     "PLACE": "MARKET", 
    }, 
    { 
     "EYES_COLOR": "BLUE", 
     "LEFT_SOCK_COLOR": "GREEN", 
     "PLACE": "SHOP", 
    }, 
    { 
     "EYES_COLOR": "BLUE", 
     "PLACE": "AIRPORT", 
    }, 
] 

def do_action(seen_events, found): 
    """DUMMY""" 
    for seen in seen_events: 
     print seen 
    print found 
    print 

# brute force 
for found in found_events: 
    matching = [] 
    for seen in seen_events: 
     for k in found: 
      if k in seen and seen[k] != found[k]: 
       break 
     else: # for ended without break (Python syntax) 
      matching.append(seen) 
    if matching: 
     do_action(matching, found) 

который печатает:

{'EYES_COLOR': 'BLUE', 'RIGHT_SOCK_COLOR': 'GREEN'} 
{'EYES_COLOR': 'BLUE', 'PLACE': 'MARKET', 'LEFT_SOCK_COLOR': 'BLUE', 'RIGHT_SOCK_COLOR': 'GREEN'} 

{'EYES_COLOR': 'BLUE', 'RIGHT_SOCK_COLOR': 'GREEN'} 
{'EYES_COLOR': 'BLUE', 'PLACE': 'SHOP', 'LEFT_SOCK_COLOR': 'GREEN'} 

{'EYES_COLOR': 'BLUE', 'LEFT_SOCK_COLOR': 'RED'} 
{'EYES_COLOR': 'BLUE', 'RIGHT_SOCK_COLOR': 'GREEN'} 
{'EYES_COLOR': 'BLUE', 'PLACE': 'AIRPORT'} 

Право, это не эффективна - O (Н * м) - но это даже описать проблему правильно?