sortierte Folgen matchen

[ahussain]

Hallo, ich suche einen Algorithmus zu folgendem Problem:
Ich habe eine sortierte "Referenz-Folge" A von Elementen a1, a2, ... an.

Nun habe ich eine zweite, von A abweichende, ebenfalls sortierte Folge B von Elementen b1, b2, ..., bm.

Nun möchte ich die Elemente aus B auf die Elemente aus A abbilden, das heißt: ich suche für jedes Element aus B dasjenige aus A, welches am besten passt, so dass ich am Ende eine Folge von Abbildungen habe:

b1 -> x1, b2 -> x2, ..., bm -> xm, wobei für jede einzelne Abbildungt bi -> xi gilt:

1. xi ist ein Element aj aus A, dann gilt:

   match(A, bi) = aj

2. xi ist leer, dann gilt:

   match(A, bi) = EMPTY

Die Operation

match

sucht zu einem gegebenen Element aus B dasjenige Element aus A, welches am besten passt. Findet sie kein passendes, wird

EMPTY

zurückgegeben Die Kriterien, welche das am besten passende Element bestimmen, sind hier erst mal nicht so wichtig.

Ich kann mir jetzt auch selber irgendeinen Algorithmus schreiben, der das Problem löst. Aber vielleicht gibt es ja schon etwas passendes zu diesem Problem. Kennt da jemand was?

 

[Marco13]

Klingt ein bißchen wie Sequence alignment - Wikipedia, the free encyclopedia , wobei dort die Frage, was "passt", implizit mit dem verbunden ist, was vorher und nachher kommt....

 

[Landei]

Gibt es für das "Passen" eine Maßzahl? Dann könnte man eine Matrix mit den Maßen anlegen und versuchen, die Summe der Maßzahlen bei einer Zuordnung zu maximieren. Das wäre dann eine Art "Zuordnungsproblem" (zur Lösung kämen allgemeine Verfahren für lineare Optimierung oder vielleicht der Transportalgorithmus in Frage), oder vielleicht auch ein generalisiertes Zuordnungsproblem (GAP). Damit ist es passt, müsste man eventuell die "leere" Zuweisung mit Maßzahl 0 für alle B hinzufügen.

 

[ahussain]

Danke für die Tipps.

Man könnte durchaus eine Funktion schreiben, welche ein Element aus A mit einem aus B vergleicht und eine Zahl zurückliefert, die als Indikator dient, wie gut das eine zum Anderen passt.

Ich hatte gehofft, dass es schon eine fertige Bibliothek o.ä. gibt, welche als Eingabe

• die beiden Folgen A und B sowie
• eine Funktion zum Vergleichen zweier Elemente

erhält und als Ausgabe die "beste" (also am besten passende) Abbildungsfolge liefert.