Алгоритм сопоставления нескольких событий

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

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

Спасибо

Пример. У нас есть несколько событий с разными типами и свойствами. Тип SEEN является кумулятивным событием (несколько событий могут быть объединены для сопоставления), а тип FOUND — нет.

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.

matching algorithm
person Andrey Vityuk    schedule 30.09.2009    source источник
comment
Вы неадекватно указываете значение ВИДЕНО против НАЙДЕННОГО. Ваш пример выглядит некорректным. Событие 1 вызывает LEFT_SOCK_COLOR=RED. Событие 3 вызывает LEFT_SOCK_COLOR=BLUE. Я не понимаю, как вы объединили эти два события.   -  person John R. Strohm    schedule 30.09.2009
comment
Пожалуйста, объясните правила, по которым Событие 3 может соответствовать действию 1_2_3.   -  person Douglas Leeder    schedule 30.09.2009
comment
Извините за этот беспорядок, на самом деле событие с типом SEEN является кумулятивным событием. Это означает, что в процессе сопоставления мы можем составить любое количество таких событий.   -  person Andrey Vityuk    schedule 01.10.2009
comment
Вас может заинтересовать этот вопрос: stackoverflow.com/questions /1154565/   -  person Daniel C. Sobral    schedule 03.03.2010

Ответы (3)


arrow_upward
1
arrow_downward

в вашем случае каждые два события либо совместимы, либо нет; мы можем обозначить это через 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 открыт; Я предполагаю, что поля объединены «как есть».

person Antti Huima    schedule 30.09.2009
comment
Спасибо, я думаю, что в качестве первого шага поиск с возвратом - это довольно простой алгоритм. - person Andrey Vityuk; 01.10.2009

arrow_upward
0
arrow_downward

Этот псевдокод может помочь: (синтаксис 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.
    }
}
person John Fisher    schedule 30.09.2009
comment
Да, но может быть любое количество типов событий, таких как Found и Seen - person Andrey Vityuk; 01.10.2009
comment
Если у каждого типа есть свое действие, вам нужно что-то закодировать для каждого из них. Таким образом, несколько блоков, подобных этому, были бы одним решением. - person John Fisher; 01.10.2009

arrow_upward
0
arrow_downward

Я не уверен, что правильно понял вопрос. Кажется, что для каждого события 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 (n * m) - но правильно ли это описывает проблему?

person Beni Cherniavsky-Paskin    schedule 22.01.2010