세키투르 알고리즘

Sequitur algorithm

Sequitur(또는 Nevill-Manning 알고리즘)는 크레이그 네빌-매닝과 Ian H. Witten이 1997년에[1] 개발한 재귀 알고리즘으로, 일련의 이산 기호로부터 계층 구조(문법)를 주입한다. 알고리즘은 선형 공간과 시간으로 작동한다. 데이터 압축 소프트웨어 애플리케이션에서 사용할 수 있다.[2]

제약

시퀀스 알고리즘은 주어진 시퀀스의 반복 구문을 새로운 규칙으로 대체하여 문법을 구성하므로 시퀀스를 간결하게 표현한다. 예를 들어, 시퀀스가

S→abcab,

알고리즘이 생성될 것이다.

S→AcA, A→ab.

입력 시퀀스를 스캔하는 동안 알고리즘은 효율적으로 문법을 생성하기 위한 두 가지 제약조건인 digram 고유성과 규칙 효용성을 따른다.

디그람 고유성

시퀀스에서 새 기호를 스캔할 때마다 마지막 스캔 기호가 추가되어 새 디그람을 형성한다. 만약 이 digram이 일찍 형성되었다면, digram의 두 발생을 모두 대체하는 새로운 규칙이 만들어진다. 따라서 문법에서 한 번 이상 디그람이 발생하지 않도록 보장한다. 예를 들어, S→abaaaba 순서에서는 처음 4개의 기호가 이미 스캔되었을 때 형성된 digram은 ab, ba, aa이다. 다섯 번째 기호를 읽으면 이미 존재하는 새로운 디그람 'ab'이 형성된다. 따라서 'ab'의 두 인스턴스 모두 S의 새로운 규칙(예: A)으로 대체된다. 이제 문법은 S→AaAa, A→ab이 되고, 문법에 반복적인 디그람이 존재하지 않을 때까지 그 과정은 계속된다.

규칙 유틸리티

이 제약조건은 모든 문법 생산의 오른쪽 면에 모든 규칙이 두 번 이상 사용되도록 보장한다. 즉, 규칙이 한 번만 발생하면 문법에서 제거되어야 하고 그 발생은 문법이 만들어진 기호로 대체되어야 한다. 예를 들어 위의 예에서 마지막 기호를 스캔하여 'Aa'에 대해 digram 고유성을 적용하면 문법은 S→BB, A→ab, B→Aa를 생성한다. 이제 규칙 'A'는 B→Aa의 문법에서 단 한 번만 발생한다. 따라서 A는 삭제되고 최종적으로 문법이 된다.

S→BB, B→aba.

이 제약조건은 문법상의 규칙의 수를 줄이는 데 도움이 된다.

방법 요약

이 알고리즘은 일련의 단자 기호들을 스캔하고 그것이 읽은 모든 기호 쌍들의 목록을 만드는 것으로 작동한다. 한 쌍의 두 번째 발생이 발견될 때마다, 두 개의 발생은 발명된 비단어 기호에 의해 순차적으로 대체되고, 기호 쌍의 목록은 새로운 순서에 맞게 조정되며, 스캔은 계속된다. 쌍의 비터미널 기호가 방금 만든 기호의 정의에만 사용되는 경우, 사용된 기호는 정의로 대체되고 기호는 정의된 비터미널 기호에서 제거된다. 스캔이 완료되면 변형된 시퀀스는 원래 시퀀스에 대한 문법에서 최상위 규칙으로 해석할 수 있다. 포함된 비터미널 기호에 대한 규칙 정의는 기호 쌍 목록에서 찾을 수 있다. 이러한 규칙 정의 자체는 규칙 정의를 기호 쌍 목록의 다른 곳에서 읽을 수 있는 추가 비단어 기호를 포함할 수 있다.[3]

참고 항목

참조

  1. ^ Nevill-Manning, C.G.; Witten, I.H. (1997). "Identifying Hierarchical Structure in Sequences: A linear-time algorithm". arXiv:cs/9709102. Bibcode:1997cs........9102N. Cite 저널은 필요로 한다. journal= (도움말)
  2. ^ Nevill-Manning, C.G.; Witten, I.H. (1997). "Linear-Time, Incremental Hierarchy Inference for Compression". Proceedings DCC '97. Data Compression Conference. pp. 3–11. CiteSeerX 10.1.1.30.2305. doi:10.1109/DCC.1997.581951. ISBN 978-0-8186-7761-8.
  3. ^ GrammarViz 2.0 – Java, Sequitur 기반 시계열 패턴 검색에서 Sequitur 및 병렬 Sequitur 구현

외부 링크