Entscheiden, ob eine Platzhalterzeichenfolge vollständig mit einer anderen Platzhalterzeichenfolge in einem Satz übereinstimmt

Hier ist ein Problem, das mich schon eine Weile nervt. Angenommen, eine Zeichenfolge ist eine Folge von 1s und 0s, und eine Platzhalterzeichenfolge ist eine Folge von 1, 0 und? S. Alle Zeichenfolgen und Platzhalterzeichenfolgen haben dieselbe Länge. Dies sind Standard-UNIX-Platzhalter. 10 ?? 1 entspricht 10011, 10111 usw. - a? entspricht einer 1 oder einer 0 an dieser Position. Wenn und Platzhalterzeichenfolgen sind, schreiben wir wenn jede Zeichenfolge, die mit übereinstimmt, auch mit übereinstimmt .$v$$w$$v \leq w$$v$$w$

Die Probleme : Gibt es bei einer Menge von Platzhalterzeichenfolgen und einer Abfrage v (auch eine Platzhalterzeichenfolge) ein w ∈ S, so dass v ≤ w ist ? Und wenn nicht, können wir V effizient zu S hinzufügen ?$S$$v$$w \in S$$v \leq w$$v$$S$

Hier ist das offensichtliche Lösung (wobeikdie Größe der Zeichenfolgen ist,mdie Wortgröße des RAM ist (normalerweise 32 oder 64)): Gehen Sie jedes Element der Liste durch und testen Sie die Bedingung (die in 2 oder 3 Operationen ausgeführt werden kann mit Bit-Twiddling). Testen Sie auch, obv≥wfür ein Elementw gilt,während wir scannen. Wennvunserem Test nicht, fügendannvauf den Satz, und entfernendiew‚s wir markiert.$O(\frac{k}{m}n)$$k$$m$$v \geq w$$w$$v$$v$$w$

Das geht aber nicht schnell genug. Es wäre wirklich cool, wenn es eine -Lösung oder in einer perfekten Welt eine Komplexität ähnlich einem Radix-Baum ( O ( k ) ) gäbe . Es ist auch in Ordnung , wenn die Abfragen ungefähr korrekt sind : Wenn v ≤ w ist , geben Sie yes oder no zurück. aber wenn die Bedingung nicht definitiv gilt, geben Sie nein zurück.$O(\log n)$$O(k)$$v \leq w$

Obwohl dies im schlimmsten Fall nicht zur Komplexität beiträgt, können Sie davon ausgehen, dass alle Elemente in durch eine Platzhalterzeichenfolge begrenzt sind. Das heißt, es gibt einige v , so dass für alle w ∈ S , v ≥ w .$S$$v$$w \in S$$v \geq w$

Ideen, die ich ausprobiert habe

• Platzhalterzeichenfolgen bilden ein Join-Halbgitter. Wir könnten einen Baum haben, der Platzhalterzeichenfolgen enthält. Die Blätter wären Platzhalterzeichenfolgen, und die Zweige würden die Verbindung aller Kinder darstellen. Wenn die Abfrage und der Join nicht vergleichbar sind, müssen wir keine Zeit damit verschwenden, mit allen untergeordneten Elementen dieses Zweigs zu vergleichen. Wenn wir ein Update durchführen und das Update größer als ein Join ist, können wir einfach den gesamten Zweig löschen. Leider ist dies im schlimmsten Fall immer noch , und wir finden nicht immer die "besten" Verknüpfungen, die beim Durchsuchen des Baums zum Hinzufügen von Elementen vorgenommen werden müssen.$O(n)$
• Man könnte einen Radix-Versuch von . Wir wissen, dass S durch eine Platzhalterzeichenfolge begrenzt ist. Angenommen, es ist? 0? 0. Dann müssen sich alle Zweige des Tries nur auf dem 1. und 3. Bit der Saiten befinden. Wenn das aktuelle Bit, auf das wir in der Abfrage verzweigen, eine 1 ist, müssen wir das? und die 1 Zweige; Wenn es 0 ist, überprüfen wir das? und die 0 Zweige; Wenn es? ist, überprüfen wir nur das? Ast. Da wir möglicherweise mehrere Zweige nehmen müssen, scheint dies nicht sehr gut zu sein (es ist aus demselben Grund schwierig, den Versuch zu aktualisieren). Da das Matching eine sehr sehr schnelle Operation ist, tut es im Vergleich zur naiven Strategie weh, viel in einem Baum zu durchlaufen (das Folgen einer Reihe von Zeigern ist viel teurer als das Durchführen einiger OPs und ANDs).$S$$S$

Verwandte Arbeiten

• In der Netzwerkgemeinschaft manifestiert sich dieses Problem als "Paketklassifizierung". Hier finden Sie eine gute Übersicht über die bekannten Algorithmen und Datenstrukturen . Leider wird fast immer davon ausgegangen, dass die Platzhalterzeichenfolgen nur mit Präfixen übereinstimmen, und die Abfrage ist ein Tupel solcher Zeichenfolgen. Natürlich können wir immer eine allgemeine Platzhalterzeichenfolge konvertieren, um diese Kriterien zu erfüllen: 1? 00? 1 ?? ist (1, & agr;, 0, 0, & agr;, 1, & agr;, & agr;). Dies wäre jedoch nicht effizient. Die andere Annahme ist, dass diese Tupel einer "Farbe" zugeordnet sind und das Abfragen die Farbe zurückgeben sollte (nicht nur, dass sie übereinstimmt). Dies macht das Problem viel schwieriger, weil wir die Tupel ordnen müssen (oder es ist nicht eindeutig, welche von (0 ,?) Und (?, 1) mit (0, 1) übereinstimmt).

• In der Algorithmus-Community habe ich viele Ergebnisse im Zusammenhang mit der Suche nach Teilzeichenfolgen gefunden, die mit "egal" übereinstimmen. Dies ist ein erheblich schwierigeres Problem, und ich kann keine der Techniken wirklich anwenden.

Abschließend

Vielen Dank für jede Hilfe!

$S$$O(k)$

$S$

Was das Hinzufügen von Zeichenfolgen zur Maschine betrifft, gibt es einige neuere Arbeiten zum schrittweisen Ändern eines Automaten mit endlichen Zuständen. Siehe dieses Papier von Daciuk et al.: "Inkrementelle Konstruktion minimaler azyklischer endlicher Automaten".

Hilft das?