2

我的任务是通过它们的一些属性将多个事件（事实）相互匹配。 作为事件匹配的结果，应该生成一些动作。当所有存在类型的事件都匹配时，可以生成动作。

是否有任何算法可用于此类任务？或者有什么方向？

谢谢

示例： 我们有几个具有不同类型和属性的事件。类型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.
4

3 回答 3

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 的问题是开放的；我在这里假设这些字段是“按原样”合并的。

于 2009-09-30T20:10:10.727 回答
0

我不确定我是否正确理解了这个问题。似乎对于每个 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) - 但这是否正确描述了问题？

于 2010-01-22T10:10:50.433 回答
0

此伪代码可能会有所帮助：（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.
    }
}
于 2009-09-30T20:20:04.030 回答