dc.contributor.author | Nevill-Manning, Craig G. | |
dc.contributor.author | Witten, Ian H. | |
dc.date.accessioned | 2008-10-29T02:54:24Z | |
dc.date.available | 2008-10-29T02:54:24Z | |
dc.date.issued | 1996-11 | |
dc.identifier.citation | Nevill-Manning, C. G. & Witten, I. H. (1996). Authorship patterns in information systems. (Working paper 96/25). Hamilton, New Zealand: University of Waikato, Department of Computer Science. | en_US |
dc.identifier.issn | 1170-487X | |
dc.identifier.uri | https://hdl.handle.net/10289/1186 | |
dc.description.abstract | This paper describes an algorithm that infers a hierarchical structure from a sequence of discrete symbols by replacing phrases which appear more than once by a grammatical rule that generates the phrase, and continuing this process recursively. The result is a hierarchical representation of the original sequence. The algorithm works by maintaining two constraints: every diagram in the grammar must be unique, and every rule must be used more than once. It breaks new ground by operating incrementally. Moreover, its simple structure permits a proof that it operates in space and time that is linear in the size of the input. Our implementation can process 10,000 symbols/second and has been applied to an extensive range of sequences encountered in practice. | en_US |
dc.format.mimetype | application/pdf | |
dc.language.iso | en | |
dc.relation.ispartofseries | Computer Science Working Papers | |
dc.subject | computer science | en_US |
dc.subject | sequence learning | en_US |
dc.subject | grammatical inference | en_US |
dc.subject | linear-time learning algorithms | en_US |
dc.subject | Machine learning | |
dc.title | Identifying hierarchical structure in sequences: a linear-time algorithm | en_US |
dc.type | Working Paper | en_US |
dc.identifier.doi | 10.1613/jair.374 | en_NZ |
uow.relation.series | 96/25 | |
dc.relation.isPartOf | Journal of Artificial Intelligence Research | en_NZ |
pubs.begin-page | 67 | en_NZ |
pubs.elements-id | 39440 | |
pubs.end-page | 82 | en_NZ |
pubs.issue | 7 | en_NZ |
pubs.volume | . | en_NZ |