Decyzja, czy ciąg znaków zastępczych jest całkowicie dopasowany do innego ciągu znaków zastępczych w zestawie

Oto problem, który dręczy mnie od dłuższego czasu. Powiedzmy, że łańcuch jest sekwencją 1 i 0, a łańcuch wieloznaczny to sekwencja 1, 0 i? S. Wszystkie ciągi znaków i symbole wieloznaczne mają tę samą długość. Są to standardowe symbole wieloznaczne UNIX; 10 ?? 1 pasuje do 10011, 10111 itd. - a? dopasowuje 1 lub 0 w tej pozycji. Jeśli i są ciągami wieloznacznymi, to piszemy jeśli każdy ciąg pasujący do jest również dopasowany przez .$v$$w$$v \leq w$$v$$w$

Problemy : biorąc pod uwagę zestaw ciągów znaków wieloznacznych i zapytanie (również ciąg znaków zastępczych), czy istnieje takie, że ? A jeśli nie, czy możemy skutecznie dodać do ?$S$$v$$w \in S$$v \leq w$$v$$S$

Oto oczywiste rozwiązanie (gdzie jest rozmiarem ciągów, jest rozmiarem pamięci RAM (zwykle 32 lub 64)): przejdź przez każdy element listy i przetestuj warunek (który można wykonać w 2 lub 3 operacjach przy użyciu kręcenia bitów). Sprawdź także, czy ma miejsce dla dowolnego elementu podczas skanowania. Jeśli nie nasz test, a następnie dodać do zestawu i usunąć „s my oznaczone.$O(\frac{k}{m}n)$$k$$m$$v \geq w$$w$$v$$v$$w$

Ale to nie jest wystarczająco szybkie. Byłoby naprawdę fajnie, gdyby istniało rozwiązanie lub, w idealnym świecie, złożoność podobna do drzewa radix ( ). Jest również OK, aby zapytania były w przybliżeniu poprawne : to znaczy, jeśli , to zwróć tak lub nie; ale jeśli warunek się nie utrzyma, zdecydowanie zwróć nie.$O(\log n)$$O(k)$$v \leq w$

Chociaż nie pomaga to w najgorszym przypadku, można założyć, że wszystkie elementy w są ograniczone łańcuchem wieloznacznym; to znaczy istnieje takie , że dla wszystkich , .$S$$v$$w \in S$$v \geq w$

Pomysły, które próbowałem

• Ciągi znaków wieloznacznych tworzą łącznik-semilattice. Moglibyśmy mieć drzewo n-ary, które zawiera łańcuchy znaków wieloznacznych; liście byłyby symbolami wieloznacznymi, a gałęzie reprezentowałyby połączenie wszystkich dzieci. Jeśli zapytanie i sprzężenie są nieporównywalne, nie musimy tracić czasu na próby porównania ze wszystkimi dziećmi tego oddziału. Ponadto, jeśli dokonamy aktualizacji, a aktualizacja będzie większa niż złączenie, możemy po prostu usunąć cały oddział. Niestety w najgorszym przypadku jest to nadal i nie zawsze znajdujemy „najlepsze” połączenia, które należy wykonać podczas skanowania drzewa, aby dodać elementy.$O(n)$
• Można utworzyć Trie przelicznika . Wiemy, że jest ograniczony przez ciąg znaków wieloznacznych; Załóżmy, że jest to? 0? 0. Wtedy wszystkie gałęzie trie muszą znajdować się tylko na 1 i 3 bitach struny. Jeśli bieżącym bitem, w którym rozgałęziamy się zapytanie, jest 1, musimy sprawdzić? i 1 gałęzie; jeśli jest 0, sprawdzamy? i 0 oddziałów; jeśli tak jest, sprawdzamy tylko? Oddział. Ponieważ musimy potencjalnie wziąć wiele gałęzi, nie wydaje się to zbyt dobre (trudno jest zaktualizować trie z tego samego powodu). Ponieważ dopasowanie jest bardzo, bardzo szybką operacją, boli w porównaniu do naiwnej strategii wykonywania wielu ruchów w drzewie (podążanie za zestawem wskaźników jest znacznie droższe niż robienie niektórych OR i AND).$S$$S$

Powiązana praca

• W społeczności sieciowej problem ten przejawia się jako „klasyfikacja pakietów”, oto dobre badanie znanych algorytmów i struktur danych . Niestety, prawie zawsze przyjmuje się, że ciągi znaków wieloznacznych pasują tylko do przedrostków, a zapytanie jest krotką takich ciągów. Oczywiście zawsze możemy przekonwertować ogólny ciąg znaków zastępczych, aby spełnić następujące kryteria: 1? 00? 1 ?? to (1,?, 0, 0,?, 1,?,?). Nie byłoby to jednak skuteczne. Inne przyjęte założenie jest takie, że te krotki są powiązane z „kolorem”, a zapytanie powinno zwrócić kolor (nie tylko to, że pasuje). Sprawia to, że problem jest znacznie trudniejszy, ponieważ musimy zamówić krotki (lub nie jest jednoznaczne, które z (0,?) I (?, 1) pasuje (0, 1)).

• W społeczności algorytmów znalazłem wiele wyników związanych ze znajdowaniem podciągów pasujących do „nie przejmuj się”. Jest to znacznie trudniejszy problem i nie mogę tak naprawdę skorzystać z żadnej z technik.

Podsumowując

Dzięki za wszelką pomoc!

Co powiesz na użycie automatu skończonego? Język jest skończony, a zatem regularny. Nawet po poniższych przekształceniach nadal będzie on regularny. Tak więc po zwykłych krokach konwersji wyrażenia regularnego na deterministyczny automat skończony będziesz miał program rozpoznający to, co chcesz, działający w czasie . Mam nadzieję, że ten pomysł będzie nadal wykonalny, jeśli wystąpią błędy w tym, co zaproponowano poniżej.$S$$O(k)$

Zmarszczka to sposób postępowania z operatorem wieloznacznym:? Symbol wieloznaczny w łańcuchu wieloznacznym odpowiada 0 lub 1 w ciągu testowym. Ale ponieważ próbujemy rozpoznać ciągi symboli wieloznacznych, znak zastępczy w ciągu znaków zastępczych pasuje do 0, 1 lub? w innym ciągu symboli wieloznacznych. Ten zestaw jest nadal regularny, więc przekształcamy każde wystąpienie? do wyrażenia regularnego (0 | 1 |?), gdzie pionowy pasek jest zwykłym operatorem naprzemiennym. Jeśli więc cały zestaw wynosi {10 ?? 1, 0? 1? 0}, wynikowym wyrażeniem regularnym będzie (10 (0 | 1 |?) (0 | 1 |?) 1 | 0 (0 | 1 | ?) 1 (0 | 1 |?) 0)$S$

Jeśli chodzi o dodawanie ciągów do maszyny, ostatnio pracujemy nad stopniową zmianą automatu skończonego. Zobacz ten artykuł autorstwa Daciuk i in .: „Przyrostowa konstrukcja minimalnych acyklicznych automatów skończonych”.

czy to pomaga?