Auflösen mehrdeutiger Kategorien in einer geordneten Liste

Question

Nehmen wir ein konkretes Beispiel und hoffe, dass ich klar sein kann. Angenommen, die (geordnete) Liste der Monate:

Januar < Februar < März < ... < Dezember

(mit ganzen Zahlen, die für die Monate stehen, Null-basiert), so dass

Jan 0, Februar 1, ... Dec ist 11.

Jetzt nehme ich haben keinen Zugang zu den vollständigen Namen der Monate und bin in der folgenden Liste gegeben, wo Monaten ihre ersten Buchstaben verkürzt wurden und e für eine leere Kategorie steht, wie folgt aus:

e, f, e, e, e

Wenn ich eine Liste von "unzweideutig Monaten" build (f: 1, n: 8, O: 9 n: 10, D: 11), I kann die leeren Kategorien füllen, indem zuerst die erste Kategorie berechnet wird (mit Subtraktion und Mod 12), und dann den Rest von dort schreiben. Allerdings nehme ich die Liste gegeben bin

E, A, e, e, J, e

Dann kann ich (intuitiv) berechnen, dass, obwohl A mehrdeutig ist (könnte April sein oder August), in diesem Zusammenhang kann es nur April sein, da August keine J s folgt nach 2 Kategorien hat. Sobald ich das finde, kann ich von Anfang an alles neu berechnen.

Meine Frage ist schließlich: gibt es eine analytische Lösung (Funktion, Algorithmus) für dieses Problem, oder ist meine einzige Hoffnung, rohe Gewalt zu verwenden, um jede mögliche Beziehung zu definieren? Bei einigen Beispielen kann keine Begriffsklärung Algorithmus/Funktion arbeiten: den Fall betrachtet, wo ich ein J gefolgt von 11 e ‚s, gefolgt von einem J von 11 e gefolgt‘ s ... Da es ist ein Jahr dazwischen, kann ich J nicht im Januar, Juni oder Juli disambiguieren.

Antwort: Ich habe die Antwort von Il-Bhima gecoded, weil für diesen Fall insbesondere die Regexs ok sind, sogar bei einer höheren Laufzeit O (mn). Allerdings akzeptierte ich Bens Antwort als die richtige Antwort, weil sie die anderen subsumiert (erwähnt die Regex-Lösung), schlägt aber auch einen besseren Weg vor, indem sie den KMP-Algorithmus O (m + n) verwendet, obwohl dies für größere Zahlen der Zeichenkette gilt um dem Muster zu entsprechen. Danke an alle.

Answer 1

Ich bin mir nicht sicher, ob dies genau das ist, was Sie suchen, aber Sie könnten eine modifizierte KMP string search algorithm verwenden, um dieses Problem zu lösen.

Die Änderung wäre, alles gegen die leere Kategorie zu entsprechen. Es könnte sogar alle möglichen Werte für dich finden, wie das J mit 11 e wie du erwähnt hast.

Sie könnten auch eine finite state machine verwenden, um Möglichkeiten zu ermitteln, das ist, was ein regular expression tun würde.

Answer 2

Der einfachste Weg, dies zu tun, ist die Verwendung von regulären Ausdrücken. Angenommen, Sie möchten e, A, e, e, J, e übereinstimmen.

Konstruieren Sie den folgenden regulären Ausdruck: r = ".A..J."

Let c unserer Kontrolle String sein:

c = "JFMAMJJASONDJFMAMJJASOND" 

Jetzt suchen wir für alle Spiele von r im String c, wo der Startindex eines Spiels innerhalb ist die erste Hälfte von c.

Im Allgemeinen ist dies möglicherweise nicht die effizienteste Methode. Die naivste Lösung, die versucht, das Muster mit jeder zyklischen Verschiebung der Steuerzeichenfolge "JFMAMJJASOND" zu vergleichen, läuft in O(nm) Zeit, wobei n die Länge des Musters ist, m ist die Länge der Steuerzeichenfolge (in unserem Fall JFMAMJJASOND).

Answer 3

Wir können auf Il-Bhimas Antwort ein wenig für den allgemeinen Fall aufbauen. Zuerst erkennen wir, dass die einzigen wirklich mehrdeutigen Paare von A, M oder J zwei J sind, die sechs Monate auseinander liegen oder zwei gleiche Buchstaben, die ein Jahr auseinander liegen. Jede andere Kombination ergibt eine eindeutige Übereinstimmung in der Kontrollzeichenfolge. (Ich baute eine Tabelle aller möglichen Kombinationen, um das zu beweisen.)

Alles, was du von deiner gesamten Startliste brauchst, sind zwei Monate, deren Distanzmod 12 nicht 0 oder 6 ist. Du kannst dann einen kleinen regulären Ausdruck erstellen um mit der Kontrollzeichenfolge übereinzustimmen. Alternativ können Sie eine Nachschlagetabelle erstellen, die das geordnete Paar und die Abstände zwischen den Monaten enthält.