Částečné slovo - Partial word

v počítačová věda a studium kombinatorika slov, a částečné slovo je tětiva které mohou obsahovat řadu symbolů „nevím“ nebo „je mi to jedno“, tj. zástupné symboly v řetězci, kde hodnota symbolu není známa nebo není uvedena. Formálně je dílčí slovo a částečná funkce kde je nějaká konečná abeceda. Li u(k) pro některé není definován pak neznámý prvek na místě k v řetězci se nazývá „díra“. v regulární výrazy (v návaznosti na POSIX standard) díra je reprezentována metaznak "." Například, aab.ab.b je částečné slovo o délce 8 nad abecedou A ={A,b} ve kterém čtvrtý a sedmý znak jsou mezery.[1]

Algoritmy

Pro problém „shody řetězců s nestará se“ bylo vyvinuto několik algoritmů, ve kterých je vstupem dlouhý text a kratší dílčí slovo a cílem je najít v textu všechny řetězce, které odpovídají danému dílčímu slovu.[2][3][4]

Aplikace

Graf kompatibility dílčích slov

Říká se, že dvě dílčí slova jsou kompatibilní když mají stejnou délku a když každá pozice, která není zástupným znakem v obou, má v obou stejný znak. Pokud jeden tvoří neorientovaný graf s vrcholem pro každé dílčí slovo ve sbírce dílčích slov a hranou pro každý kompatibilní pár, pak kliky tohoto grafu pocházejí ze sad dílčích slov, která všechna odpovídají alespoň jednomu běžnému řetězci. Tato graficko-teoretická interpretace kompatibility dílčích slov hraje klíčovou roli v důkazu tvrdost aproximace z klika problém, ve kterém je kolekce dílčích slov představujících úspěšné běhy a pravděpodobnostně ověřitelný důkaz ověřovatel má velkou kliku právě tehdy, pokud existuje platný důkaz podkladu NP-kompletní problém.[5]

Tváře (subcubes) z -dimenzionální hyperkrychle lze popsat dílčími slovy délky nad binární abecedou, jejichž symboly jsou Kartézské souřadnice vrcholů hyperkrychlí (např. 0 nebo 1 pro a jednotková kostka ). Rozměr subkrychle se v tomto zobrazení rovná počtu symbolů, které obsahuje. Stejná reprezentace může být také použita k popisu implikanti z Booleovské funkce.[6]

Související pojmy

Dílčí slova lze zobecnit na slova parametrů, ve kterém jsou některé ze symbolů „nevím“ označeny jako vzájemně rovnocenné. Částečné slovo je speciální případ parametrického slova, ve kterém může být každý symbol neznám nahrazen znakem nezávisle na všech ostatních.[7]

Reference

  1. ^ Blanchet-Sadri, Francine (2008), Algoritmická kombinatorika na dílčích slovech, Diskrétní matematika a její aplikace, Boca Raton, Florida: Chapman & Hall / CRC, ISBN  978-1-4200-6092-8, PAN  2384993
  2. ^ Pinter, Ron Y. (1985), „Efektivní shoda řetězců s nezajímavými vzory“, Kombinatorické algoritmy slov (Maratea, 1984), NATO Adv. Sci. Inst. Ser. F Výpočet. Systems Sci., 12, Springer, Berlín, s. 11–29, PAN  0815329
  3. ^ Manber, Udi; Baeza-Yates, Ricardo (1991), "Algoritmus pro shodu řetězců se sekvencí se nestará", Dopisy o zpracování informací, 37 (3): 133–136, doi:10.1016 / 0020-0190 (91) 90032-D, PAN  1095695
  4. ^ Kalai, Adam (2002), „Efektivní porovnávání vzorů se nestará“, v Eppstein, David (vyd.), Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 6.-8. Ledna 2002, San Francisco, CA, USA, ACM a SIAM, s. 655–656
  5. ^ Feige, U.; Goldwasser, S.; Lovász, L.; Safra, S; Szegedy, M. (1991), „Přibližná klika je téměř NP úplná“, Proc. 32. IEEE Symp. o základech informatiky, s. 2–12, doi:10.1109 / SFCS.1991.185341, ISBN  0-8186-2445-0
  6. ^ Karnaugh, Maurice (1953), „Metoda mapy pro syntézu kombinačních logických obvodů“, Transakce amerického institutu elektrotechniků, část I: Komunikace a elektronika, 1953: 593–599, doi:10.1109 / TCE.1953.6371932, PAN  0069032
  7. ^ Prömel, Hans Jürgen (2002), „Velká čísla, Knuthova šípová notace a Ramseyova teorie“, Syntezátor, 133 (1–2): 87–105, doi:10.1023 / A: 1020879709125, JSTOR  20117296, PAN  1950045