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

あなたの場合、2つのイベントごとに互換性があるかどうかです。これは、イベント e がイベント e' と互換性があることを意味する C(e,e') で表すことができます。もちろん、互換性のあるイベントの最大セットを反復して構築できます。互換性のあるイベントのセット {e1,e2,...,en} がある場合、e' がすべての e1,...,en と互換性がある場合にのみ、e' をセットに追加できます。つまり、C(ei ,e') はすべての 1<=i<=n に対して真です。

残念ながら、あなたの場合、互換性のあるイベントの最大セットの数は、イベントの数の指数関数になる可能性があります.その他の 2 つのイベント。このセットでは、すでに 6 つの異なる「アクション」を取得しており、それらは互いに重なり合っています。

簡単なアルゴリズムは、イベントを 1 つずつ見込みのある「アクション」に追加する再帰検索を行うことです。これ以上イベントを追加できない場合は、アクションを登録します。その後、バックトラックします。それは「バックトラック検索」と呼ばれます。一致するイベントを「すばやく」検索するための適切なデータ構造によって、実行時間を改善できます。

コメントのように、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 に答える