| dbo:abstract
|
- The Lempel–Ziv complexity is a measure that was first presented in the article On the Complexity of Finite Sequences (IEEE Trans. On IT-22,1 1976), by two Israeli computer scientists, Abraham Lempel and Jacob Ziv. This complexity measure is related to Kolmogorov complexity, but the only function it uses is the recursive copy (i.e., the shallow copy). The underlying mechanism in this complexity measure is the starting point for some algorithms for lossless data compression, like LZ77, LZ78 and LZW. Even though it is based on an elementary principle of words copying, this complexity measure is not too restrictive in the sense that it satisfies the main qualities expected by such a measure: sequences with a certain regularity do not have a too large complexity, and the complexity grows as the sequence grows in length and irregularity. The Lempel–Ziv complexity can be used to measure the repetitiveness of binary sequences and text, like song lyrics or prose. Fractal dimension estimates of real-world data have also been shown to correlate with Lempel–Ziv complexity. (en)
- La complexité de Lempel-Ziv est présentée pour la première fois dans l'article On the Complexity of Finite Sequences (IEEE Trans. On IT-22,1 1976), par deux informaticiens israéliens, Abraham Lempel et Jacob Ziv. Cette mesure de complexité est liée à la complexité de Kolmogorov, mais elle n'utilise comme seule fonction que la copie récursive. Le mécanisme mis en œuvre dans cette mesure de complexité est à l'origine des algorithmes de compression de données sans perte LZ77, LZ78 et LZW. Bien que ne reposant que sur un principe élémentaire de recopie de mots, cette mesure de complexité n'est pas trop restrictive en ce sens qu'elle respecte les principales qualités attendues d'une telle mesure : elle n'octroie pas aux séquences avec certaines régularités une grande complexité et cette complexité est d'autant plus grande que la séquence est longue et peu régulière. (fr)
- Сложность Лемпеля-Зива (Lempel-Ziv Complexity) - алгоритм для вычисления Колмогоровской сложности, который может быть исполнен на любом языке программирования, поддерживающем операции копирования и вставки в строку. Несмотря на простоту данного алгоритма, он является очень мощным и быстрым. Сложность Лемпеля-Зива была впервые представлена в статье под названием On the Complexity of Finite Sequences (IEEE Trans. On IT-22,1 1976) двумя израильскими учеными, Авраамом Лемпелем и Яаковом Зивом. Данная мера сложности связана с Колмогоровской сложностью, но единственная функция, которую она использует - рекурсивная копия. Механизм, лежащий в основе данного измерения сложности, является отправной точкой для некоторых алгоритмов сжатия без потерь, таких как LZ77, LZ78 и LZW. Несмотря на то, что она основана на элементарном принципе копирования слов, эта мера сложности не слишком ограничительна в том смысле, что она удовлетворяет основным качествам, ожидаемым такой мерой: последовательности с определенной регулярностью не имеют слишком большой сложности, и сложность возрастает по мере увеличения длины и неоднородности. Сложность Лемпеля-Зива можно использовать для измерения повторяемости бинарных последовательностей и текста, например, текстов песен. (ru)
|
| rdfs:comment
|
- The Lempel–Ziv complexity is a measure that was first presented in the article On the Complexity of Finite Sequences (IEEE Trans. On IT-22,1 1976), by two Israeli computer scientists, Abraham Lempel and Jacob Ziv. This complexity measure is related to Kolmogorov complexity, but the only function it uses is the recursive copy (i.e., the shallow copy). The Lempel–Ziv complexity can be used to measure the repetitiveness of binary sequences and text, like song lyrics or prose. Fractal dimension estimates of real-world data have also been shown to correlate with Lempel–Ziv complexity. (en)
- La complexité de Lempel-Ziv est présentée pour la première fois dans l'article On the Complexity of Finite Sequences (IEEE Trans. On IT-22,1 1976), par deux informaticiens israéliens, Abraham Lempel et Jacob Ziv. Cette mesure de complexité est liée à la complexité de Kolmogorov, mais elle n'utilise comme seule fonction que la copie récursive. (fr)
- Сложность Лемпеля-Зива (Lempel-Ziv Complexity) - алгоритм для вычисления Колмогоровской сложности, который может быть исполнен на любом языке программирования, поддерживающем операции копирования и вставки в строку. Несмотря на простоту данного алгоритма, он является очень мощным и быстрым. Сложность Лемпеля-Зива можно использовать для измерения повторяемости бинарных последовательностей и текста, например, текстов песен. (ru)
|
