사르디나스-패터슨 알고리즘

코딩 이론에서 사르디나스-패터슨 알고리즘은 주어진 가변 길이 코드가 고유하게 해독 가능한지를 다항 시간 내에 판단하기 위한 고전 알고리즘으로, 1953년 이를 발표한 아우구스트 알버트 사르디나스와 조지 W. 패터슨의 이름을 따서 명명되었다.^[1]이 알고리즘은 두 개의 다른 코드 워드로 분해되는 문자열을 체계적으로 검색한다.크누스의 보고대로 이 알고리즘은 약 10년 뒤인 1963년 플로이드에 의해 다시 발견되었는데, 당시는 이미 코딩 이론에서 잘 알려져 있었음에도 불구하고 이 알고리즘이 알고리즘은 약 10년 후인 1963년에 플로이드에 의해 재발견되었다.^[2]

알고리즘의 개념

Consider the code ${\displaystyle \{\,a\mapsto 1,b\mapsto 011,c\mapsto 01110,d\mapsto 1110,e\mapsto 10011\,\}}$. This code, which is based on an example by Berstel,^[3] is an example of a code which is not uniquely decodable, since the string

011101110011

암호의 배열로 해석할 수 있다.

01110 – 1110 – 011,

암호의 순서에 따라서도

011 – 1 – 011 – 10011.

따라서 이 인코딩된 문자열의 두 가지 가능한 해독은 cdb와 babe에 의해 주어진다.

일반적으로 암호는 다음과 같은 생각으로 찾을 수 있다.In the first round, we choose two codewords ${\displaystyle x_{1}}$ and ${\displaystyle y_{1}}$ such that ${\displaystyle x_{1}}$ is a prefix of ${\displaystyle y_{1}}$, that is, ${\displaystyle x_{1}w=y_{1}}$ for some "dangling suffix" ${\displaystyle w}$. If 첫 번째 $x{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$= ${\displaystyle 011}$ ${\displaystyle x_{1}=011},$ $y$ ${\displaystyle {1\mathrm{}}_{}}$= ${\displaystyle 01110}$ ${\displaystyle y_{1}=01110$ 매달린 접미사는 w${\displaystyle }$= ${\displaystyle 10}$ ${\displaystyle w=10}$이다$.$If we manage to find two sequences ${\displaystyle x_{2},\ldots ,x_{p}}$ and ${\displaystyle y_{2},\ldots ,y_{q}}$ of codewords such that ${\displaystyle x_{2}\cdots x_{p}=wy_{2}\cdots y_{q}}$, then we are finished:그 경우 $문자열{\displaystyle {x\mathrm{}}_{}}$ = ${\displaystyle {}_{}{}_{}}$ x ${\displaystyle {2\mathrm{}}_{}{x}_{}}$ x p$${\$displaystyle x${{$1}x_{$1}$x_{2}\cdots x_{p}}$을(를) y${\displaystyle {}_{}{1}_{}}$ ${\displaystyle {}_{}}$ 2 {$$y$q$ {\$displaysty y_{1$}y_{2}\cdots $y_{q$로 분해할 수 있으며$$, 원하는 문자열이 적어도 두 개 이상 있음을 확인했다.

두 번째 라운드에서 우리는 두 가지 다른 접근법을 시도한다: 첫 번째 실험은 접두사로 w가 있는 암호어를 찾는 것이다.그리고 나서 우리는 새로운 매달린 접미사 w'를 얻는데, 이 접미사로 우리는 검색을 계속할 수 있다.만약 우리가 결국 그 자체가 암호어(또는 빈 단어)인 매달린 접미사와 마주친다면, 우리가 알고 있듯이 두 개의 분해된 문자열이 존재하는 것처럼 검색은 종료될 것이다.두 번째 재판은 그 자체가 w의 접두어인 암호어를 구하는 것이다.이 예에서는 $w{\displaystyle }$= ${\displaystyle 10}$ ${\displaystyle w=10}$이$($가) 있으며, 시퀀스 1은 암호어다.따라서 w'=0을 새로운 매달림 접미사로 계속 진행할 수도 있다.

알고리즘에 대한 정확한 설명

알고리즘은 공식 언어의 인용구를 사용하여 가장 편리하게 설명된다.일반적으로 D와 N의 두 세트에 대해 (왼쪽)$인덱스{\displaystyle {}^{}}$N - ${\displaystyle {}^{}}$ D ${\displaystyle N^{-1}D}$는 N의 일부 접두사를 제거하여 D에서 얻은 잔차 워드로 정의된다$$.Formally, ${\displaystyle N^{-1}D=\{\,y\mid xy\in D~{\textrm {and}}~x\in N\,\}}$. Now let ${\displaystyle C}$ denote the (finite) set of codewords in the given code.

알고리즘은 라운드로 진행되는데, 여기서 우리는 위에서 설명한 대로 매달린 접미사 한 개뿐 아니라 모든 잠재적 매달린 접미사의 (핀라이트) 세트를 각 라운드에서 유지한다.라운드 $i{\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle i=1}$부터$,$ 잠재적 매달림 접미사 집합은 S ${\displaystyle i_{}}$ ${\$로 표시된다$.$$S{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$ 세트는 다음과 같이 유도적으로 정의된다$$.

${\displaystyle S_{}}$ ${\displaystyle {1\mathrm{}}_{}}$= ${\displaystyle {}^{}}$- ${\displaystyle 1^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle \setminus }${ ${\displaystyle \epsilon }$} ${\displaystyle S_{1}=C^{-1}C\setminus \{\varepsilon$ 여기서 기호 $symbol{\displaystyle }$ ${\displaysty \varepsilon \}$은 빈 단어를 나타낸다.

${\displaystyle {Si}_{}}$+ ${\displaystyle 1_{}}$= ${\displaystyle {}^{}}$- ${\displaystyle {}^{}{}_{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}}$ S ${\displaystyle i_{}^{}}$- ${\displaystyle 1_{}^{}}$ C ${\displaystyle S_{i+1}=C^{-1}S_{i}\컵 S_{i}^{$1}$C$ 모든 ${\displaystyle \mathrm{i}}$ ${\displaystyle \ge }$ 1 ${\displaystyle$ i$\geq$ 1$\}.$

알고리즘은 $설정{\displaystyle }$ ${\displaystyle {Si}_{}}$ ${\displaystyle$i}의$$ 증가 순서로 Si$${\$displaystyle S_{i}$를 계산한다$.$ ${\displaystyle {Si}_{}}$ ${\$ 중 하나가 C의 단어 또는 빈 단어를 포함하면$$ 알고리즘이 종료되고 주어진 코드를 해독할 수 없다는 답변을 한다.그렇지 않으면, 일단 세트 ${\displaystyle {Si}_{}}$ ${\$가j < i ${\displaystyle$ j$<i}$이(가) 있는 이전에 만났던 $세트{\displaystyle {}_{}}$ S ${\displaystyle j_{}}${\$displaystyle S_{j}$와 같다면 알고리즘은 원칙적으로 끝없는 루프를 입력하게 된다끝없이 계속되는 대신 주어진 코드가 독특하게 해독할 수 있다고 답한다.

알고리즘 종료 및 정확성

모든 세트 ${\displaystyle {Si}_{}}$ ${\$는 한정된 코드 워드의 접미사 집합이므로$$, ${\displaystyle {Si}_{}}$ ${\$의 후보 집합은 미세하게 많을 뿐이다$.$ 두 번째 세트 중 하나를 방문하면 알고리즘이 중단되기 때문에 알고리즘은 끝없이 계속될 수 없으며 따라서 항상 종료되어야 한다.te. 보다 정확히 말하면 알고리즘이 고려하는 매달린 접미사의 총 수는 입력에 있는 코드 워드의 길이의 총계와 최대 동일하므로 알고리즘은 이 입력 길이의 함수로서 다항식으로 실행된다.접미사 트리를 사용하여 각 매달린 접미사와 코드 워드의 비교 속도를 높임으로써 알고리즘에 대한 시간은 O(nk)로 경계할 수 있는데 여기서 n은 코드 워드의 총 길이, k는 코드 워드의 수입니다.^[4]알고리즘은 패턴 매칭 기계를 사용하여 구현할 수 있다.^[5] 알고리즘은 또한 로그 공간만을 사용하는 비결정론적 튜링 기계에서 실행되도록 구현될 수 있다; 고유한 해독성을 시험하는 문제는 NL-완전하므로 이 공간 바운드가 최적이다.^[6]

알고리즘이 정확하다는 증거, 즉 항상 정답을 준다는 증거는 살로마아와^[7] 베르스텔 등이 교과서에서 찾을 수 있다.^[8]

참고 항목

• 크래프트의 불평등은 특정 코드가 고유하게 해독될 수 있는 가능성을 배제할 수 있는 빠른 방법을 제공한다.
• 접두사 코드와 블록 코드는 정의에 따라 고유하게 해독할 수 있는 중요한 코드 종류다.
• 정보 이론 연대표

메모들

참조

• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Codes and automata. Encyclopedia of Mathematics and its Applications. Vol. 129. Cambridge: Cambridge University Press. ISBN 978-0-521-88831-8. Zbl 1187.94001.
• Berstel, Jean; Reutenauer, Christophe (2011). Noncommutative rational series with applications. Encyclopedia of Mathematics and Its Applications. Vol. 137. Cambridge: Cambridge University Press. ISBN 978-0-521-19022-0. Zbl 1250.68007.
• Knuth, Donald E. (December 2003). "Robert W Floyd, In Memoriam". SIGACT News. 34 (4): 3–13. doi:10.1145/954092.954488. S2CID 35605565.
• Rodeh, M. (1982). "A fast test for unique decipherability based on suffix trees (Corresp.)". IEEE Transactions on Information Theory. 28 (4): 648–651. doi:10.1109/TIT.1982.1056535..
• Apostolico, A.; Giancarlo, R. (1984). "Pattern matching machine implementation of a fast test for unique decipherability". Information Processing Letters. 18 (3): 155–158. doi:10.1016/0020-0190(84)90020-6..
• Rytter, Wojciech (1986). "The space complexity of the unique decipherability problem". Information Processing Letters. 23 (1): 1–3. doi:10.1016/0020-0190(86)90121-3. MR 0853618..
• Salomaa, Arto (1981). Jewels of Formal Language Theory. Pitman Publishing. ISBN 0-273-08522-0. Zbl 0487.68064.
• Sardinas, August Albert; Patterson, George W. (1953), "A necessary and sufficient condition for the unique decomposition of coded messages", Convention Record of the I.R.E., 1953 National Convention, Part 8: Information Theory, pp. 104–108.

추가 읽기

• 로버트 G. 갤러거:정보 이론과 신뢰할 수 있는 커뮤니케이션.와일리, 1968년