부분어

컴퓨터 과학과 단어에 대한 콤비네이터의 연구에서 부분 단어는 "모른다" 또는 "상관없다" 기호를 여러 개 포함할 수 있는 문자열, 즉 기호 값을 알 수 없거나 지정하지 않은 문자열의 자리 표시자를 의미한다.보다 공식적으로 부분적인 단어는 부분 함수 $u:\{0,\ldots ,n-1\}\rightarrow A$ : $u:\{0,\ldots ,n-1\}\rightarrow A$ { 0 $u:\{0,\ldots ,n-1\}\rightarrow A$ , $u:\{0,\ldots ,n-1\}\rightarrow A$ … , $u:\{0,\ldots ,n-1\}\rightarrow A$ - $u:\{0,\ldots ,n-1\}\rightarrow A$ → $u:\{0,\ldots ,n-1\}\rightarrow A$ ${\displaystyle u:\\{0,\ldots,n-1\}\오른쪽 화살표$ A $}$ 이며, $A$ 서 $u:\{0,\ldots ,n-1\}\rightarrow A$ A ${\\displaystyle A}$ 은 $A$ (는) 일부 유한한 알파벳이다. $k\in \{0,\ldots ,n-1\}$ (k)가 일부 k $k\in \{0,\ldots ,n-1\}$ { $k\in \{0,\ldots ,n-1\}$ , $k\in \{0,\ldots ,n-1\}$ … , $k\in \{0,\ldots ,n-1\}$ n - 1 } ${\displaystyle$ k\in \{ $0,\ldots,n-1\}$ 에 대해 정의되지 않은 경우 문자열의 $k\in \{0,\ldots ,n-1\}$ place k에 있는 알 수 없는 요소를 "구멍"이라고 한다.정규식(POSIX 표준에 따름)에서 구멍은 메타카로터 "."로 표현된다. 예를 들어 aab.ab.b는 4번째와 7번째 문자가 구멍인 알파벳 A ={a,b}에 걸쳐 길이 8의 일부 단어다.^[1]

알고리즘

입력은 긴 텍스트와 짧은 부분 단어로서 주어진 부분 단어와 일치하는 모든 문자열을 텍스트에서 찾는 것이 목표인 "상관없음과의 문자열 매칭" 문제에 대해 여러 알고리즘이 개발되었다.^[2]^[3]^[4]

적용들

부분 단어의 호환성 그래프

두 개의 부분적인 단어는 길이가 같을 때와 둘 다에서 비와일드카드인 모든 포지션에 동일한 문자가 있을 때 양립할 수 있다고 한다.부분 단어 모음에서 각 부분 단어에 대한 꼭지점과 호환되는 각 쌍에 대한 가장자리를 가진 비방향 그래프를 형성하는 경우, 이 그래프의 분류는 모두 하나 이상의 공통 문자열과 일치하는 부분 단어의 집합에서 나온다.부분 단어의 호환성에 대한 이 그래프 이론적 해석은 clique 문제의 근사치의 경도 입증에 핵심적인 역할을 하며, 확률적으로 확인할 수 있는 검증기의 성공적인 실행을 나타내는 부분 단어의 집합은 기초 N에 대한 유효한 증거가 존재하는 경우에만 큰 clique를 갖는다.P-완전 문제.^[5]

$n$ $n$ -차원 $n$ 하이퍼큐브의 면(하위 큐브)은 이진 알파벳에 대한 $n$ 길이 $n$ $n$ 의 부분 단어로 설명할 수 있으며, 이 기호들은 하이퍼큐브 정점의 데카르트 좌표(예: 단위 큐브의 경우 0 또는 1)이다.이 표현에서 하위 큐브의 치수는 하위 큐브에 포함된 관리 안 함 기호 수와 동일하다.부울 함수의 내연성 설명에도 동일한 표현을 사용할 수 있다.^[6]

참조

^ Blanchet-Sadri, Francine (2008), Algorithmic Combinatorics on Partial Words, Discrete Mathematics and its Applications, Boca Raton, Florida: Chapman & Hall/CRC, ISBN 978-1-4200-6092-8, MR 2384993
^ Pinter, Ron Y. (1985), "Efficient string matching with don't-care patterns", Combinatorial algorithms on words (Maratea, 1984), NATO Adv. Sci. Inst. Ser. F Comput. Systems Sci., vol. 12, Springer, Berlin, pp. 11–29, MR 0815329
^ Manber, Udi; Baeza-Yates, Ricardo (1991), "An algorithm for string matching with a sequence of don't cares", Information Processing Letters, 37 (3): 133–136, doi:10.1016/0020-0190(91)90032-D, MR 1095695
^ Kalai, Adam (2002), "Efficient pattern-matching with don't cares", in Eppstein, David (ed.), Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA, ACM and SIAM, pp. 655–656
^ Feige, U.; Goldwasser, S.; Lovász, L.; Safra, S; Szegedy, M. (1991), "Approximating clique is almost NP-complete", Proc. 32nd IEEE Symp. on Foundations of Computer Science, pp. 2–12, doi:10.1109/SFCS.1991.185341, ISBN 0-8186-2445-0
^ Karnaugh, Maurice (1953), "The map method for synthesis of combinational logic circuits", Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics, 1953: 593–599, doi:10.1109/TCE.1953.6371932, MR 0069032
^ Prömel, Hans Jürgen (2002), "Large numbers, Knuth's arrow notation, and Ramsey theory", Synthese, 133 (1–2): 87–105, doi:10.1023/A:1020879709125, JSTOR 20117296, MR 1950045

[1] Blanchet-Sadri, Francine (2008), Algorithmic Combinatorics on Partial Words, Discrete Mathematics and its Applications, Boca Raton, Florida: Chapman & Hall/CRC, ISBN 978-1-4200-6092-8, MR 2384993

[2] Pinter, Ron Y. (1985), "Efficient string matching with don't-care patterns", Combinatorial algorithms on words (Maratea, 1984), NATO Adv. Sci. Inst. Ser. F Comput. Systems Sci., vol. 12, Springer, Berlin, pp. 11–29, MR 0815329

[3] Manber, Udi; Baeza-Yates, Ricardo (1991), "An algorithm for string matching with a sequence of don't cares", Information Processing Letters, 37 (3): 133–136, doi:10.1016/0020-0190(91)90032-D, MR 1095695

[4] Kalai, Adam (2002), "Efficient pattern-matching with don't cares", in Eppstein, David (ed.), Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA, ACM and SIAM, pp. 655–656

[5] Feige, U.; Goldwasser, S.; Lovász, L.; Safra, S; Szegedy, M. (1991), "Approximating clique is almost NP-complete", Proc. 32nd IEEE Symp. on Foundations of Computer Science, pp. 2–12, doi:10.1109/SFCS.1991.185341, ISBN 0-8186-2445-0

[6] Karnaugh, Maurice (1953), "The map method for synthesis of combinational logic circuits", Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics, 1953: 593–599, doi:10.1109/TCE.1953.6371932, MR 0069032

[7] Prömel, Hans Jürgen (2002), "Large numbers, Knuth's arrow notation, and Ramsey theory", Synthese, 133 (1–2): 87–105, doi:10.1023/A:1020879709125, JSTOR 20117296, MR 1950045

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Search

부분어

네임스페이스

더

목차

알고리즘

적용들

관련개념

참조