Sequitur algorithm: Difference between revisions

Revision as of 15:17, 10 September 2016

Latest revision as of 00:53, 6 December 2024

(11 intermediate revisions by 9 users not shown)

Line 1:

'''Sequitur''' (or '''Nevill-ManningManning–Witten algorithm''') is a recursive algorithm developed by [[Craig Nevill-Manning]] and [[Ian H. Witten]] in 1997<ref name=Nevill-manning1997>{{cite journal

| author = [[Craig Nevill-Manning|Nevill-Manning, C.G.]]

| author-link = Craig Nevill-Manning

| author2 = Witten, I.H.

| year = 1997

| title = Identifying Hierarchical Structure in Sequences: A linear-time algorithm

| arxiv = cs/9709102

| bibcode= 1997cs........9102N

}}</ref> that infers a hierarchical structure ([[context-free grammar]]) from a sequence of discrete symbols. The algorithm operates in linear space and time. It can be used in [[data compression]] software applications.<ref name=Nevill-manning1997_2>{{cite journalbook

| doi = 10.1109/DCC.1997.581951

| author = [[Craig Nevill-Manning|Nevill-Manning, C.G.]]

| author-link = Craig Nevill-Manning

| title = Proceedings DCC '97. Data Compression Conference

| pages = 3–11

| author2=Witten, I.H.

| year = 1997

| titlechapter = Linear-Time, Incremental Hierarchy Inference for Compression

| isbn = 978-0-8186-7761-8

| citeseerx = 10.1.1.30.2305

| s2cid = 14324301

}}</ref>

Line 37 ⟶ 45:

* [[Lossless compression|Lossless data compression]]

* [[Straight-line grammar]]

* [[Byte pair encoding]]

==References==

{{reflistReflist}}

==External links==

* [http://www.sequitur.info/ sequitur.info – the reference Sequitur algorithm implementation in C++, Java, and other languages]

{{Compression methods}}

[[Category:Lossless compression algorithms]]

[[Category:Data compression]]