Częściowe słowo

W informatyce i badaniu kombinatoryki na słowach słowo częściowe to ciąg , który może zawierać pewną liczbę symboli „nie wiem” lub „nie obchodzi mnie to”, tj. symbole zastępcze w ciągu, w których wartość symbolu nie jest znana lub nie jest określona . Bardziej formalnie, częściowe słowo jest funkcją częściową ${\ Displaystyle u: \ {0, \ ldots, n-1 \} \ rightarrow A}$ gdzie ${\ displaystyle A}$ to jakiś skończony alfabet. Jeśli u ( k ) nie jest zdefiniowane dla jakiegoś ${\ Displaystyle k \ w \ {0, \ ldots, n-1 \}},$ to nieznany element w miejscu k w łańcuchu to zwany „dziurą”. W wyrażeniach regularnych (zgodnie ze standardem POSIX ) dziura jest reprezentowana przez metaznak „.”. Na przykład aab.ab.b jest częściowym słowem o długości 8 nad alfabetem A = { a , b }, w którym czwarty i siódmy znak to dziury.

Algorytmy

Opracowano kilka algorytmów dla problemu „dopasowywania ciągów z nie obchodzi”, w którym dane wejściowe to długi tekst i krótsze słowo częściowe, a celem jest znalezienie wszystkich ciągów w tekście, które pasują do danego słowa częściowego.

Aplikacje

Wykres zgodności słów częściowych

Mówi się, że dwa częściowe słowa są zgodne , gdy mają taką samą długość i gdy każda pozycja, która nie jest symbolem wieloznacznym w obu z nich, ma ten sam znak w obu. Jeśli utworzy się graf nieskierowany z wierzchołkiem dla każdego słowa częściowego w zbiorze słów częściowych i krawędzią dla każdej kompatybilnej pary, to kliki tego grafu pochodzą ze zbiorów częściowych słów, które wszystkie pasują do co najmniej jednego wspólnego ciągu. Ta grafowo-teoretyczna interpretacja zgodności słów częściowych odgrywa kluczową rolę w dowodzie twardości aproksymacji problemu kliki , w którym zbiór częściowych słów reprezentujących udane przebiegi probabilistycznie sprawdzalnego weryfikatora dowodu ma dużą klikę wtedy i tylko wtedy, gdy istnieje ważny dowód podstawowego problemu NP-zupełnego .

Ściany (podsześciany) $-wymiarowego$ hipersześcianu można opisać za pomocą częściowych słów o długości $nad$ binarnym, którego symbolami są współrzędne kartezjańskie wierzchołków hipersześcianu (np. 0 1 dla sześcianu jednostkowego ). Wymiar podsześcianu w tej reprezentacji jest równy liczbie zawartych w nim symboli „nie przejmuj się”. Tej samej reprezentacji można również użyć do opisania implikantów funkcji boolowskich .

Pojęcia pokrewne

Słowa częściowe można uogólnić na słowa parametryczne , w których niektóre symbole „nie wiem” są oznaczone jako sobie równe. Słowo częściowe jest szczególnym przypadkiem słowa parametrycznego, w którym każdy nieznany symbol może być zastąpiony znakiem niezależnie od wszystkich pozostałych.