• DocumentCode
    3226226
  • Title

    A Simple Algorithm for Computing the Lempel Ziv Factorization

  • Author

    Crochemore, Maxime ; Ilie, Lucian ; Smyth, W.F.

  • Author_Institution
    King´´s Coll. London, London
  • fYear
    2008
  • fDate
    25-27 March 2008
  • Firstpage
    482
  • Lastpage
    488
  • Abstract
    We give a space-efficient simple algorithm for computing the Lempel-Ziv factorization of a string. For a string of length n over an integer alphabet, it runs in O(n) time independently of alphabet size and uses o(n) additional space.
  • Keywords
    computational complexity; data compression; Lempel-Ziv factorization; computational complexity; space-efficient simple algorithm; Automata; Computer science; Data compression; Dictionaries; Ecosystems; Educational institutions; Entropy; Software algorithms; Space technology; Tree data structures; Lempel--Ziv factorization; algorithms design; longest common prefix; longest previous factor; repetitions; runs; strings; suffix array;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Data Compression Conference, 2008. DCC 2008
  • Conference_Location
    Snowbird, UT
  • ISSN
    1068-0314
  • Print_ISBN
    978-0-7695-3121-2
  • Type

    conf

  • DOI
    10.1109/DCC.2008.36
  • Filename
    4483326
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3226226