Data compression - Revision history

Jiffles1: Reverted edits by 88.131.7.246 (talk): editing tests (HG) (3.4.12)

2025-05-19T22:09:26Z

Reverted edits by 88.131.7.246 (talk): editing tests (HG) (3.4.12)

← Previous revision		Revision as of 22:09, 19 May 2025
Line 3:		Line 3:
	{{Use American English\|date=March 2021}}		{{Use American English\|date=March 2021}}

	~~[[Andreas Rörqvist\|~~In]] [[information theory]], '''data compression''', '''source coding''',<ref name="Wade"/> or '''bit-rate reduction''' is the process of encoding [[information]] using fewer [[bit]]s than the original representation.<ref name="mahdi53"/> Any particular compression is either [[lossy]] or [[lossless]]. Lossless compression reduces bits by identifying and eliminating [[Redundancy (information theory)\|statistical redundancy]]. No information is lost in lossless compression. Lossy compression reduces bits by removing unnecessary or less important information.<ref name="PujarKadlaskar"/> Typically, a device that performs data compression is referred to as an encoder, and one that performs the reversal of the process (decompression) as a decoder.		In [[information theory]], '''data compression''', '''source coding''',<ref name="Wade"/> or '''bit-rate reduction''' is the process of encoding [[information]] using fewer [[bit]]s than the original representation.<ref name="mahdi53"/> Any particular compression is either [[lossy]] or [[lossless]]. Lossless compression reduces bits by identifying and eliminating [[Redundancy (information theory)\|statistical redundancy]]. No information is lost in lossless compression. Lossy compression reduces bits by removing unnecessary or less important information.<ref name="PujarKadlaskar"/> Typically, a device that performs data compression is referred to as an encoder, and one that performs the reversal of the process (decompression) as a decoder.

	The process of reducing the size of a [[data file]] is often referred to as data compression. In the context of [[data transmission]], it is called source coding: encoding is done at the source of the data before it is stored or transmitted.<ref name="Salomon"/> Source coding should not be confused with [[channel coding]], for error detection and correction or [[line coding]], the means for mapping data onto a signal.		The process of reducing the size of a [[data file]] is often referred to as data compression. In the context of [[data transmission]], it is called source coding: encoding is done at the source of the data before it is stored or transmitted.<ref name="Salomon"/> Source coding should not be confused with [[channel coding]], for error detection and correction or [[line coding]], the means for mapping data onto a signal.

88.131.7.246 at 22:05, 19 May 2025

2025-05-19T22:05:05Z

← Previous revision		Revision as of 22:05, 19 May 2025
Line 3:		Line 3:
	{{Use American English\|date=March 2021}}		{{Use American English\|date=March 2021}}

	In [[information theory]], '''data compression''', '''source coding''',<ref name="Wade"/> or '''bit-rate reduction''' is the process of encoding [[information]] using fewer [[bit]]s than the original representation.<ref name="mahdi53"/> Any particular compression is either [[lossy]] or [[lossless]]. Lossless compression reduces bits by identifying and eliminating [[Redundancy (information theory)\|statistical redundancy]]. No information is lost in lossless compression. Lossy compression reduces bits by removing unnecessary or less important information.<ref name="PujarKadlaskar"/> Typically, a device that performs data compression is referred to as an encoder, and one that performs the reversal of the process (decompression) as a decoder.		[[Andreas Rörqvist\|In]] [[information theory]], '''data compression''', '''source coding''',<ref name="Wade"/> or '''bit-rate reduction''' is the process of encoding [[information]] using fewer [[bit]]s than the original representation.<ref name="mahdi53"/> Any particular compression is either [[lossy]] or [[lossless]]. Lossless compression reduces bits by identifying and eliminating [[Redundancy (information theory)\|statistical redundancy]]. No information is lost in lossless compression. Lossy compression reduces bits by removing unnecessary or less important information.<ref name="PujarKadlaskar"/> Typically, a device that performs data compression is referred to as an encoder, and one that performs the reversal of the process (decompression) as a decoder.

	The process of reducing the size of a [[data file]] is often referred to as data compression. In the context of [[data transmission]], it is called source coding: encoding is done at the source of the data before it is stored or transmitted.<ref name="Salomon"/> Source coding should not be confused with [[channel coding]], for error detection and correction or [[line coding]], the means for mapping data onto a signal.		The process of reducing the size of a [[data file]] is often referred to as data compression. In the context of [[data transmission]], it is called source coding: encoding is done at the source of the data before it is stored or transmitted.<ref name="Salomon"/> Source coding should not be confused with [[channel coding]], for error detection and correction or [[line coding]], the means for mapping data onto a signal.

AnomieBOT: Dating maintenance tags: {{Cn}}

2025-05-15T01:03:50Z

Dating maintenance tags: {{Cn}}

← Previous revision		Revision as of 01:03, 15 May 2025
Line 16:		Line 16:
	The [[Lempel–Ziv]] (LZ) compression methods are among the most popular algorithms for lossless storage.<ref name="Optimized LZW"/> [[DEFLATE]] is a variation on LZ optimized for decompression speed and compression ratio,<ref>{{Cite book \|title=Document Management - Portable document format - Part 1: PDF1.7 \|date=July 1, 2008 \|publisher=Adobe Systems Incorporated \|edition=1st \|language=English}}</ref> but compression can be slow. In the mid-1980s, following work by [[Terry Welch]], the [[Lempel–Ziv–Welch]] (LZW) algorithm rapidly became the method of choice for most general-purpose compression systems. LZW is used in [[GIF]] images, programs such as [[PKZIP]], and hardware devices such as modems.<ref>{{Cite book\|last=Stephen\|first=Wolfram\|url=https://www.wolframscience.com/nks/p1069--data-compression/\|title=New Kind of Science\|year=2002\|isbn=1-57955-008-8\|publisher=Wolfram Media\|location=Champaign, IL\|pages=1069}}</ref> LZ methods use a table-based compression model where table entries are substituted for repeated strings of data. For most LZ methods, this table is generated dynamically from earlier data in the input. The table itself is often [[Huffman coding\|Huffman encoded]]. [[Grammar-based codes]] like this can compress highly repetitive input extremely effectively, for instance, a biological [[data collection]] of the same or closely related species, a huge versioned document collection, internet archival, etc. The basic task of grammar-based codes is constructing a context-free grammar deriving a single string. Other practical grammar compression algorithms include [[Sequitur algorithm\|Sequitur]] and [[Re-Pair]].		The [[Lempel–Ziv]] (LZ) compression methods are among the most popular algorithms for lossless storage.<ref name="Optimized LZW"/> [[DEFLATE]] is a variation on LZ optimized for decompression speed and compression ratio,<ref>{{Cite book \|title=Document Management - Portable document format - Part 1: PDF1.7 \|date=July 1, 2008 \|publisher=Adobe Systems Incorporated \|edition=1st \|language=English}}</ref> but compression can be slow. In the mid-1980s, following work by [[Terry Welch]], the [[Lempel–Ziv–Welch]] (LZW) algorithm rapidly became the method of choice for most general-purpose compression systems. LZW is used in [[GIF]] images, programs such as [[PKZIP]], and hardware devices such as modems.<ref>{{Cite book\|last=Stephen\|first=Wolfram\|url=https://www.wolframscience.com/nks/p1069--data-compression/\|title=New Kind of Science\|year=2002\|isbn=1-57955-008-8\|publisher=Wolfram Media\|location=Champaign, IL\|pages=1069}}</ref> LZ methods use a table-based compression model where table entries are substituted for repeated strings of data. For most LZ methods, this table is generated dynamically from earlier data in the input. The table itself is often [[Huffman coding\|Huffman encoded]]. [[Grammar-based codes]] like this can compress highly repetitive input extremely effectively, for instance, a biological [[data collection]] of the same or closely related species, a huge versioned document collection, internet archival, etc. The basic task of grammar-based codes is constructing a context-free grammar deriving a single string. Other practical grammar compression algorithms include [[Sequitur algorithm\|Sequitur]] and [[Re-Pair]].

	The strongest modern lossless compressors use [[Randomized algorithm\|probabilistic]] models, such as [[prediction by partial matching]]. The [[Burrows–Wheeler transform]] can also be viewed as an indirect form of statistical modelling.{{cn}} In a further refinement of the direct use of [[probabilistic model]]ling, statistical estimates can be coupled to an algorithm called [[arithmetic coding]]. Arithmetic coding is a more modern coding technique that uses the mathematical calculations of a [[finite-state machine]] to produce a string of encoded bits from a series of input data symbols. It can achieve superior compression compared to other techniques such as the better-known Huffman algorithm. It uses an internal memory state to avoid the need to perform a one-to-one mapping of individual input symbols to distinct representations that use an integer number of bits, and it clears out the internal memory only after encoding the entire string of data symbols. Arithmetic coding applies especially well to adaptive data compression tasks where the statistics vary and are context-dependent, as it can be easily coupled with an adaptive model of the [[probability distribution]] of the input data. An early example of the use of arithmetic coding was in an optional (but not widely used) feature of the [[JPEG]] image coding standard.<ref name=TomLane/> It has since been applied in various other designs including [[H.263]], [[H.264/MPEG-4 AVC]] and [[HEVC]] for video coding.<ref name="HEVC"/>		The strongest modern lossless compressors use [[Randomized algorithm\|probabilistic]] models, such as [[prediction by partial matching]]. The [[Burrows–Wheeler transform]] can also be viewed as an indirect form of statistical modelling.{{cn\|date=May 2025}} In a further refinement of the direct use of [[probabilistic model]]ling, statistical estimates can be coupled to an algorithm called [[arithmetic coding]]. Arithmetic coding is a more modern coding technique that uses the mathematical calculations of a [[finite-state machine]] to produce a string of encoded bits from a series of input data symbols. It can achieve superior compression compared to other techniques such as the better-known Huffman algorithm. It uses an internal memory state to avoid the need to perform a one-to-one mapping of individual input symbols to distinct representations that use an integer number of bits, and it clears out the internal memory only after encoding the entire string of data symbols. Arithmetic coding applies especially well to adaptive data compression tasks where the statistics vary and are context-dependent, as it can be easily coupled with an adaptive model of the [[probability distribution]] of the input data. An early example of the use of arithmetic coding was in an optional (but not widely used) feature of the [[JPEG]] image coding standard.<ref name=TomLane/> It has since been applied in various other designs including [[H.263]], [[H.264/MPEG-4 AVC]] and [[HEVC]] for video coding.<ref name="HEVC"/>

	Archive software typically has the ability to adjust the "dictionary size", where a larger size demands more [[random-access memory]] during compression and decompression, but compresses stronger, especially on repeating patterns in files' content.<ref>{{cite web\| url = https://www.winrar-france.fr/winrar_instructions_for_use/source/html/HELPArcOptimal.htm\| title = How to choose optimal archiving settings – WinRAR}}</ref><ref>{{cite web\| url = https://sevenzip.osdn.jp/chm/cmdline/switches/method.htm\| title = (Set compression Method) switch – 7zip\| access-date = 2021-11-07\| archive-date = 2022-04-09\| archive-url = https://web.archive.org/web/20220409225619/https://sevenzip.osdn.jp/chm/cmdline/switches/method.htm\| url-status = dead}}</ref>		Archive software typically has the ability to adjust the "dictionary size", where a larger size demands more [[random-access memory]] during compression and decompression, but compresses stronger, especially on repeating patterns in files' content.<ref>{{cite web\| url = https://www.winrar-france.fr/winrar_instructions_for_use/source/html/HELPArcOptimal.htm\| title = How to choose optimal archiving settings – WinRAR}}</ref><ref>{{cite web\| url = https://sevenzip.osdn.jp/chm/cmdline/switches/method.htm\| title = (Set compression Method) switch – 7zip\| access-date = 2021-11-07\| archive-date = 2022-04-09\| archive-url = https://web.archive.org/web/20220409225619/https://sevenzip.osdn.jp/chm/cmdline/switches/method.htm\| url-status = dead}}</ref>
Line 30:		Line 30:
	Lossy image compression is used in [[digital camera]]s, to increase storage capacities. Similarly, [[DVD]]s, [[Blu-ray]] and [[streaming video]] use lossy [[video coding format]]s. Lossy compression is extensively used in video.		Lossy image compression is used in [[digital camera]]s, to increase storage capacities. Similarly, [[DVD]]s, [[Blu-ray]] and [[streaming video]] use lossy [[video coding format]]s. Lossy compression is extensively used in video.

	In lossy audio compression, methods of psychoacoustics are used to remove non-audible (or less audible) components of the [[audio signal]]. Compression of human speech is often performed with even more specialized techniques; [[speech coding]] is distinguished as a separate discipline from general-purpose audio compression. Speech coding is used in [[internet telephony]], for example, audio compression is used for CD ripping and is decoded by the audio players.{{cn}}		In lossy audio compression, methods of psychoacoustics are used to remove non-audible (or less audible) components of the [[audio signal]]. Compression of human speech is often performed with even more specialized techniques; [[speech coding]] is distinguished as a separate discipline from general-purpose audio compression. Speech coding is used in [[internet telephony]], for example, audio compression is used for CD ripping and is decoded by the audio players.{{cn\|date=May 2025}}

	Lossy compression can cause [[generation loss]].		Lossy compression can cause [[generation loss]].

Headbomb: -predatory source

2025-05-15T00:43:45Z

-predatory source

← Previous revision		Revision as of 00:43, 15 May 2025
Line 16:		Line 16:
	The [[Lempel–Ziv]] (LZ) compression methods are among the most popular algorithms for lossless storage.<ref name="Optimized LZW"/> [[DEFLATE]] is a variation on LZ optimized for decompression speed and compression ratio,<ref>{{Cite book \|title=Document Management - Portable document format - Part 1: PDF1.7 \|date=July 1, 2008 \|publisher=Adobe Systems Incorporated \|edition=1st \|language=English}}</ref> but compression can be slow. In the mid-1980s, following work by [[Terry Welch]], the [[Lempel–Ziv–Welch]] (LZW) algorithm rapidly became the method of choice for most general-purpose compression systems. LZW is used in [[GIF]] images, programs such as [[PKZIP]], and hardware devices such as modems.<ref>{{Cite book\|last=Stephen\|first=Wolfram\|url=https://www.wolframscience.com/nks/p1069--data-compression/\|title=New Kind of Science\|year=2002\|isbn=1-57955-008-8\|publisher=Wolfram Media\|location=Champaign, IL\|pages=1069}}</ref> LZ methods use a table-based compression model where table entries are substituted for repeated strings of data. For most LZ methods, this table is generated dynamically from earlier data in the input. The table itself is often [[Huffman coding\|Huffman encoded]]. [[Grammar-based codes]] like this can compress highly repetitive input extremely effectively, for instance, a biological [[data collection]] of the same or closely related species, a huge versioned document collection, internet archival, etc. The basic task of grammar-based codes is constructing a context-free grammar deriving a single string. Other practical grammar compression algorithms include [[Sequitur algorithm\|Sequitur]] and [[Re-Pair]].		The [[Lempel–Ziv]] (LZ) compression methods are among the most popular algorithms for lossless storage.<ref name="Optimized LZW"/> [[DEFLATE]] is a variation on LZ optimized for decompression speed and compression ratio,<ref>{{Cite book \|title=Document Management - Portable document format - Part 1: PDF1.7 \|date=July 1, 2008 \|publisher=Adobe Systems Incorporated \|edition=1st \|language=English}}</ref> but compression can be slow. In the mid-1980s, following work by [[Terry Welch]], the [[Lempel–Ziv–Welch]] (LZW) algorithm rapidly became the method of choice for most general-purpose compression systems. LZW is used in [[GIF]] images, programs such as [[PKZIP]], and hardware devices such as modems.<ref>{{Cite book\|last=Stephen\|first=Wolfram\|url=https://www.wolframscience.com/nks/p1069--data-compression/\|title=New Kind of Science\|year=2002\|isbn=1-57955-008-8\|publisher=Wolfram Media\|location=Champaign, IL\|pages=1069}}</ref> LZ methods use a table-based compression model where table entries are substituted for repeated strings of data. For most LZ methods, this table is generated dynamically from earlier data in the input. The table itself is often [[Huffman coding\|Huffman encoded]]. [[Grammar-based codes]] like this can compress highly repetitive input extremely effectively, for instance, a biological [[data collection]] of the same or closely related species, a huge versioned document collection, internet archival, etc. The basic task of grammar-based codes is constructing a context-free grammar deriving a single string. Other practical grammar compression algorithms include [[Sequitur algorithm\|Sequitur]] and [[Re-Pair]].

	The strongest modern lossless compressors use [[Randomized algorithm\|probabilistic]] models, such as [[prediction by partial matching]]. The [[Burrows–Wheeler transform]] can also be viewed as an indirect form of statistical modelling.~~<ref name="mahmud2"/>~~ In a further refinement of the direct use of [[probabilistic model]]ling, statistical estimates can be coupled to an algorithm called [[arithmetic coding]]. Arithmetic coding is a more modern coding technique that uses the mathematical calculations of a [[finite-state machine]] to produce a string of encoded bits from a series of input data symbols. It can achieve superior compression compared to other techniques such as the better-known Huffman algorithm. It uses an internal memory state to avoid the need to perform a one-to-one mapping of individual input symbols to distinct representations that use an integer number of bits, and it clears out the internal memory only after encoding the entire string of data symbols. Arithmetic coding applies especially well to adaptive data compression tasks where the statistics vary and are context-dependent, as it can be easily coupled with an adaptive model of the [[probability distribution]] of the input data. An early example of the use of arithmetic coding was in an optional (but not widely used) feature of the [[JPEG]] image coding standard.<ref name=TomLane/> It has since been applied in various other designs including [[H.263]], [[H.264/MPEG-4 AVC]] and [[HEVC]] for video coding.<ref name="HEVC"/>		The strongest modern lossless compressors use [[Randomized algorithm\|probabilistic]] models, such as [[prediction by partial matching]]. The [[Burrows–Wheeler transform]] can also be viewed as an indirect form of statistical modelling.{{cn}} In a further refinement of the direct use of [[probabilistic model]]ling, statistical estimates can be coupled to an algorithm called [[arithmetic coding]]. Arithmetic coding is a more modern coding technique that uses the mathematical calculations of a [[finite-state machine]] to produce a string of encoded bits from a series of input data symbols. It can achieve superior compression compared to other techniques such as the better-known Huffman algorithm. It uses an internal memory state to avoid the need to perform a one-to-one mapping of individual input symbols to distinct representations that use an integer number of bits, and it clears out the internal memory only after encoding the entire string of data symbols. Arithmetic coding applies especially well to adaptive data compression tasks where the statistics vary and are context-dependent, as it can be easily coupled with an adaptive model of the [[probability distribution]] of the input data. An early example of the use of arithmetic coding was in an optional (but not widely used) feature of the [[JPEG]] image coding standard.<ref name=TomLane/> It has since been applied in various other designs including [[H.263]], [[H.264/MPEG-4 AVC]] and [[HEVC]] for video coding.<ref name="HEVC"/>

	Archive software typically has the ability to adjust the "dictionary size", where a larger size demands more [[random-access memory]] during compression and decompression, but compresses stronger, especially on repeating patterns in files' content.<ref>{{cite web\| url = https://www.winrar-france.fr/winrar_instructions_for_use/source/html/HELPArcOptimal.htm\| title = How to choose optimal archiving settings – WinRAR}}</ref><ref>{{cite web\| url = https://sevenzip.osdn.jp/chm/cmdline/switches/method.htm\| title = (Set compression Method) switch – 7zip\| access-date = 2021-11-07\| archive-date = 2022-04-09\| archive-url = https://web.archive.org/web/20220409225619/https://sevenzip.osdn.jp/chm/cmdline/switches/method.htm\| url-status = dead}}</ref>		Archive software typically has the ability to adjust the "dictionary size", where a larger size demands more [[random-access memory]] during compression and decompression, but compresses stronger, especially on repeating patterns in files' content.<ref>{{cite web\| url = https://www.winrar-france.fr/winrar_instructions_for_use/source/html/HELPArcOptimal.htm\| title = How to choose optimal archiving settings – WinRAR}}</ref><ref>{{cite web\| url = https://sevenzip.osdn.jp/chm/cmdline/switches/method.htm\| title = (Set compression Method) switch – 7zip\| access-date = 2021-11-07\| archive-date = 2022-04-09\| archive-url = https://web.archive.org/web/20220409225619/https://sevenzip.osdn.jp/chm/cmdline/switches/method.htm\| url-status = dead}}</ref>
Line 30:		Line 30:
	Lossy image compression is used in [[digital camera]]s, to increase storage capacities. Similarly, [[DVD]]s, [[Blu-ray]] and [[streaming video]] use lossy [[video coding format]]s. Lossy compression is extensively used in video.		Lossy image compression is used in [[digital camera]]s, to increase storage capacities. Similarly, [[DVD]]s, [[Blu-ray]] and [[streaming video]] use lossy [[video coding format]]s. Lossy compression is extensively used in video.

	In lossy audio compression, methods of psychoacoustics are used to remove non-audible (or less audible) components of the [[audio signal]]. Compression of human speech is often performed with even more specialized techniques; [[speech coding]] is distinguished as a separate discipline from general-purpose audio compression. Speech coding is used in [[internet telephony]], for example, audio compression is used for CD ripping and is decoded by the audio players.~~<ref name="mahmud2"/>~~		In lossy audio compression, methods of psychoacoustics are used to remove non-audible (or less audible) components of the [[audio signal]]. Compression of human speech is often performed with even more specialized techniques; [[speech coding]] is distinguished as a separate discipline from general-purpose audio compression. Speech coding is used in [[internet telephony]], for example, audio compression is used for CD ripping and is decoded by the audio players.{{cn}}

	Lossy compression can cause [[generation loss]].		Lossy compression can cause [[generation loss]].
Line 232:		Line 232:

	<ref name="Wolfram">{{cite book\|last=Wolfram\|first=Stephen\|title=A New Kind of Science\|publisher=Wolfram Media, Inc.\|year=2002\|page=[https://archive.org/details/newkindofscience00wolf/page/1069 1069]\|isbn=978-1-57955-008-0\|url-access=registration\|url=https://archive.org/details/newkindofscience00wolf/page/1069}}</ref>		<ref name="Wolfram">{{cite book\|last=Wolfram\|first=Stephen\|title=A New Kind of Science\|publisher=Wolfram Media, Inc.\|year=2002\|page=[https://archive.org/details/newkindofscience00wolf/page/1069 1069]\|isbn=978-1-57955-008-0\|url-access=registration\|url=https://archive.org/details/newkindofscience00wolf/page/1069}}</ref>

	<ref name="mahmud2">{{cite journal\|last=Mahmud\|first=Salauddin\|title=An Improved Data Compression Method for General Data\|journal=International Journal of Scientific & Engineering Research\|date=March 2012\|volume=3\|issue=3\|page=2\|url=http://www.ijser.org/researchpaper%5CAn-Improved-Data-Compression-Method-for-General-Data.pdf \|archive-url=https://web.archive.org/web/20131102022116/http://www.ijser.org/researchpaper%5CAn-Improved-Data-Compression-Method-for-General-Data.pdf \|archive-date=2013-11-02 \|url-status=live\|access-date=6 March 2013}}</ref>

	<ref name=TomLane>{{cite web\|last=Lane\|first=Tom\|title=JPEG Image Compression FAQ, Part 1\|url=http://www.faqs.org/faqs/jpeg-faq/part1/\|work=Internet FAQ Archives\|publisher=Independent JPEG Group\|access-date=6 March 2013}}</ref>		<ref name=TomLane>{{cite web\|last=Lane\|first=Tom\|title=JPEG Image Compression FAQ, Part 1\|url=http://www.faqs.org/faqs/jpeg-faq/part1/\|work=Internet FAQ Archives\|publisher=Independent JPEG Group\|access-date=6 March 2013}}</ref>

Headbomb: /* Machine learning */ | Altered template type. Add: class, date, title, eprint, authors 1-12. Removed parameters. Some additions/deletions were parameter name changes. | Use this tool. Report bugs. | #UCB_Gadget

2025-05-15T00:43:03Z

Machine learning: | Altered template type. Add: class, date, title, eprint, authors 1-12. Removed parameters. Some additions/deletions were parameter name changes. | Use this tool. Report bugs. | #UCB_Gadget

← Previous revision		Revision as of 00:43, 15 May 2025
Line 50:		Line 50:
	Data compression aims to reduce the size of data files, enhancing storage efficiency and speeding up data transmission. K-means clustering, an unsupervised machine learning algorithm, is employed to partition a dataset into a specified number of clusters, k, each represented by the [[centroid]] of its points. This process condenses extensive datasets into a more compact set of representative points. Particularly beneficial in [[Image processing\|image]] and [[signal processing]], k-means clustering aids in data reduction by replacing groups of data points with their centroids, thereby preserving the core information of the original data while significantly decreasing the required storage space.<ref>{{Cite web \|date=2023-05-25 \|title=Differentially private clustering for large-scale datasets \|url=https://blog.research.google/2023/05/differentially-private-clustering-for.html \|access-date=2024-03-16 \|website=blog.research.google \|language=en}}</ref>		Data compression aims to reduce the size of data files, enhancing storage efficiency and speeding up data transmission. K-means clustering, an unsupervised machine learning algorithm, is employed to partition a dataset into a specified number of clusters, k, each represented by the [[centroid]] of its points. This process condenses extensive datasets into a more compact set of representative points. Particularly beneficial in [[Image processing\|image]] and [[signal processing]], k-means clustering aids in data reduction by replacing groups of data points with their centroids, thereby preserving the core information of the original data while significantly decreasing the required storage space.<ref>{{Cite web \|date=2023-05-25 \|title=Differentially private clustering for large-scale datasets \|url=https://blog.research.google/2023/05/differentially-private-clustering-for.html \|access-date=2024-03-16 \|website=blog.research.google \|language=en}}</ref>

	[[Large language model]]s (LLMs) are also efficient lossless data compressors on some data sets, as demonstrated by [[DeepMind]]'s research with the Chinchilla 70B model. Developed by DeepMind, Chinchilla 70B effectively compressed data, outperforming conventional methods such as [[Portable Network Graphics]] (PNG) for images and [[Free Lossless Audio Codec]] (FLAC) for audio. It achieved compression of image and audio data to 43.4% and 16.4% of their original sizes, respectively. There is, however, some reason to be concerned that the data set used for testing overlaps the LLM training data set, making it possible that the Chinchilla 70B model is only an efficient compression tool on data it has already been trained on.<ref>{{Cite web \|last=Edwards \|first=Benj \|date=2023-09-28 \|title=AI language models can exceed PNG and FLAC in lossless compression, says study \|url=https://arstechnica.com/information-technology/2023/09/ai-language-models-can-exceed-png-and-flac-in-lossless-compression-says-study/ \|access-date=2024-03-07 \|website=Ars Technica \|language=en-us}}</ref><ref>{{Cite ~~web~~ \|~~title~~=~~Language~~ ~~Modeling~~ Is ~~Compression~~ \|~~url~~=~~https://arxiv.org/html/2309.10668v2#S3~~ \|~~access~~-~~date~~=~~2025-01~~-30 \|~~website~~=~~arxiv~~.~~org~~}}</ref>		[[Large language model]]s (LLMs) are also efficient lossless data compressors on some data sets, as demonstrated by [[DeepMind]]'s research with the Chinchilla 70B model. Developed by DeepMind, Chinchilla 70B effectively compressed data, outperforming conventional methods such as [[Portable Network Graphics]] (PNG) for images and [[Free Lossless Audio Codec]] (FLAC) for audio. It achieved compression of image and audio data to 43.4% and 16.4% of their original sizes, respectively. There is, however, some reason to be concerned that the data set used for testing overlaps the LLM training data set, making it possible that the Chinchilla 70B model is only an efficient compression tool on data it has already been trained on.<ref>{{Cite web \|last=Edwards \|first=Benj \|date=2023-09-28 \|title=AI language models can exceed PNG and FLAC in lossless compression, says study \|url=https://arstechnica.com/information-technology/2023/09/ai-language-models-can-exceed-png-and-flac-in-lossless-compression-says-study/ \|access-date=2024-03-07 \|website=Ars Technica \|language=en-us}}</ref><ref>{{Cite arXiv \|eprint=2309.10668 \|last1=Delétang \|first1=Grégoire \|last2=Ruoss \|first2=Anian \|last3=Duquenne \|first3=Paul-Ambroise \|last4=Catt \|first4=Elliot \|last5=Genewein \|first5=Tim \|last6=Mattern \|first6=Christopher \|last7=Grau-Moya \|first7=Jordi \|author8=Li Kevin Wenliang \|last9=Aitchison \|first9=Matthew \|last10=Orseau \|first10=Laurent \|last11=Hutter \|first11=Marcus \|last12=Veness \|first12=Joel \|title=Language Modeling is Compression \|date=2023 \|class=cs.LG }}</ref>

	=== Data differencing ===		=== Data differencing ===

Tisykfylde: /* History */

2025-05-12T09:22:48Z

History

← Previous revision		Revision as of 09:22, 12 May 2025
Line 183:		Line 183:
	The most popular [[video coding standard]]s used for codecs have been the [[MPEG]] standards. [[MPEG-1]] was developed by the [[Motion Picture Experts Group]] (MPEG) in 1991, and it was designed to compress [[VHS]]-quality video. It was succeeded in 1994 by [[MPEG-2]]/[[H.262]],<ref name="history"/> which was developed by a number of companies, primarily [[Sony]], [[Technicolor SA\|Thomson]] and [[Mitsubishi Electric]].<ref name="mp2-patents">{{cite web \|title=MPEG-2 Patent List \|url=https://www.mpegla.com/wp-content/uploads/m2-att1.pdf \|archive-url=https://web.archive.org/web/20190529164140/https://www.mpegla.com/wp-content/uploads/m2-att1.pdf \|archive-date=2019-05-29 \|url-status=live \|website=[[MPEG LA]] \|access-date=7 July 2019}}</ref> MPEG-2 became the standard video format for [[DVD]] and [[SD digital television]].<ref name="history"/> In 1999, it was followed by [[MPEG-4 Visual\|MPEG-4]]/[[H.263]].<ref name="history"/> It was also developed by a number of companies, primarily Mitsubishi Electric, [[Hitachi]] and [[Panasonic]].<ref name="mp4-patents">{{cite web \|title=MPEG-4 Visual - Patent List \|url=https://www.mpegla.com/wp-content/uploads/m4v-att1.pdf \|archive-url=https://web.archive.org/web/20190706184528/https://www.mpegla.com/wp-content/uploads/m4v-att1.pdf \|archive-date=2019-07-06 \|url-status=live \|website=[[MPEG LA]] \|access-date=6 July 2019}}</ref>		The most popular [[video coding standard]]s used for codecs have been the [[MPEG]] standards. [[MPEG-1]] was developed by the [[Motion Picture Experts Group]] (MPEG) in 1991, and it was designed to compress [[VHS]]-quality video. It was succeeded in 1994 by [[MPEG-2]]/[[H.262]],<ref name="history"/> which was developed by a number of companies, primarily [[Sony]], [[Technicolor SA\|Thomson]] and [[Mitsubishi Electric]].<ref name="mp2-patents">{{cite web \|title=MPEG-2 Patent List \|url=https://www.mpegla.com/wp-content/uploads/m2-att1.pdf \|archive-url=https://web.archive.org/web/20190529164140/https://www.mpegla.com/wp-content/uploads/m2-att1.pdf \|archive-date=2019-05-29 \|url-status=live \|website=[[MPEG LA]] \|access-date=7 July 2019}}</ref> MPEG-2 became the standard video format for [[DVD]] and [[SD digital television]].<ref name="history"/> In 1999, it was followed by [[MPEG-4 Visual\|MPEG-4]]/[[H.263]].<ref name="history"/> It was also developed by a number of companies, primarily Mitsubishi Electric, [[Hitachi]] and [[Panasonic]].<ref name="mp4-patents">{{cite web \|title=MPEG-4 Visual - Patent List \|url=https://www.mpegla.com/wp-content/uploads/m4v-att1.pdf \|archive-url=https://web.archive.org/web/20190706184528/https://www.mpegla.com/wp-content/uploads/m4v-att1.pdf \|archive-date=2019-07-06 \|url-status=live \|website=[[MPEG LA]] \|access-date=6 July 2019}}</ref>

	[[H.264/MPEG-4 AVC]] was developed in 2003 by a number of organizations, primarily Panasonic, [[Godo kaisha\|Godo Kaisha IP Bridge]] and [[LG Electronics]].<ref name="avc-patents">{{cite web \|title=AVC/H.264 {{ndash}} Patent List \|url=https://www.mpegla.com/wp-content/uploads/avc-att1.pdf \|website=MPEG LA \|access-date=6 July 2019}}</ref> AVC commercially introduced the modern [[context-adaptive binary arithmetic coding]] (CABAC) and [[context-adaptive variable-length coding]] (CAVLC) algorithms. AVC is the main video encoding standard for [[Blu-ray Disc]]s, and is widely used by video sharing websites and streaming internet services such as [[YouTube]], [[Netflix]], [[Vimeo]], and [[iTunes Store]], web software such as [[Adobe Flash Player]] and [[Microsoft Silverlight]], and various [[HDTV]] broadcasts over terrestrial and satellite television.		[[H.264/MPEG-4 AVC]] was developed in 2003 by a number of organizations, primarily Panasonic, [[Godo kaisha\|Godo Kaisha IP Bridge]] and [[LG Electronics]].<ref name="avc-patents">{{cite web \|title=AVC/H.264 {{ndash}} Patent List \|url=https://www.mpegla.com/wp-content/uploads/avc-att1.pdf \|website=MPEG LA \|access-date=6 July 2019}}</ref> AVC commercially introduced the modern [[context-adaptive binary arithmetic coding]] (CABAC) and [[context-adaptive variable-length coding]] (CAVLC) algorithms. AVC is the main video encoding standard for [[Blu-ray Disc]]s, and is widely used by video sharing websites and streaming internet services such as [[YouTube]], [[Netflix]], [[Vimeo]], and [[iTunes Store]], web software such as [[Adobe Flash Player]] and [[Microsoft Silverlight]], and various [[HDTV]] broadcasts over terrestrial and satellite television.{{Citation needed\|date=May 2025}}

	===Genetics===		===Genetics===

LooksGreatInATurtleNeck: There was a Script warning on the page from a citation template, "numeric names: authors list" caused by numbers in a surname1= field, fixed by using Accept-this-as-written markup

2025-04-05T19:48:13Z

There was a Script warning on the page from a citation template, "numeric names: authors list" caused by numbers in a surname1= field, fixed by using Accept-this-as-written markup

← Previous revision		Revision as of 19:48, 5 April 2025
Line 284:		Line 284:
	}}</ref>		}}</ref>

	<ref name="JPEG">{{citation\|~~surname1~~=CCITT Study Group VIII und die Joint Photographic Experts Group (JPEG) von ISO/IEC Joint Technical Committee 1/Subcommittee 29/Working Group 10\|title=Recommendation T.81: Digital Compression and Coding of Continuous-tone Still images – Requirements and guidelines\|pages=54 ff\|contribution=Annex D – Arithmetic coding\|date=1993 \|url=https://www.w3.org/Graphics/JPEG/itu-t81.pdf \|access-date=2009-11-07		<ref name="JPEG">{{citation\|author=((CCITT Study Group VIII und die Joint Photographic Experts Group (JPEG) von ISO/IEC Joint Technical Committee 1/Subcommittee 29/Working Group 10))\|title=Recommendation T.81: Digital Compression and Coding of Continuous-tone Still images – Requirements and guidelines\|pages=54 ff\|contribution=Annex D – Arithmetic coding\|date=1993 \|url=https://www.w3.org/Graphics/JPEG/itu-t81.pdf \|access-date=2009-11-07
	}}</ref>		}}</ref>

LooksGreatInATurtleNeck: There was a Script warning on the page from a cite book template, location= was used without the prerequisite publisher=, so added publisher

2025-04-05T19:41:51Z

There was a Script warning on the page from a cite book template, location= was used without the prerequisite publisher=, so added publisher

← Previous revision		Revision as of 19:41, 5 April 2025
Line 14:		Line 14:
	[[Lossless data compression]] [[algorithm]]s usually exploit [[Redundancy (information theory)\|statistical redundancy]] to represent data without losing any [[Self-information\|information]], so that the process is reversible. Lossless compression is possible because most real-world data exhibits statistical redundancy. For example, an image may have areas of color that do not change over several pixels; instead of coding "red pixel, red pixel, ..." the data may be encoded as "279 red pixels". This is a basic example of [[run-length encoding]]; there are many schemes to reduce file size by eliminating redundancy.		[[Lossless data compression]] [[algorithm]]s usually exploit [[Redundancy (information theory)\|statistical redundancy]] to represent data without losing any [[Self-information\|information]], so that the process is reversible. Lossless compression is possible because most real-world data exhibits statistical redundancy. For example, an image may have areas of color that do not change over several pixels; instead of coding "red pixel, red pixel, ..." the data may be encoded as "279 red pixels". This is a basic example of [[run-length encoding]]; there are many schemes to reduce file size by eliminating redundancy.

	The [[Lempel–Ziv]] (LZ) compression methods are among the most popular algorithms for lossless storage.<ref name="Optimized LZW"/> [[DEFLATE]] is a variation on LZ optimized for decompression speed and compression ratio,<ref>{{Cite book \|title=Document Management - Portable document format - Part 1: PDF1.7 \|date=July 1, 2008 \|publisher=Adobe Systems Incorporated \|edition=1st \|language=English}}</ref> but compression can be slow. In the mid-1980s, following work by [[Terry Welch]], the [[Lempel–Ziv–Welch]] (LZW) algorithm rapidly became the method of choice for most general-purpose compression systems. LZW is used in [[GIF]] images, programs such as [[PKZIP]], and hardware devices such as modems.<ref>{{Cite book\|last=Stephen\|first=Wolfram\|url=https://www.wolframscience.com/nks/p1069--data-compression/\|title=New Kind of Science\|year=2002\|isbn=1-57955-008-8\|location=Champaign, IL\|pages=1069}}</ref> LZ methods use a table-based compression model where table entries are substituted for repeated strings of data. For most LZ methods, this table is generated dynamically from earlier data in the input. The table itself is often [[Huffman coding\|Huffman encoded]]. [[Grammar-based codes]] like this can compress highly repetitive input extremely effectively, for instance, a biological [[data collection]] of the same or closely related species, a huge versioned document collection, internet archival, etc. The basic task of grammar-based codes is constructing a context-free grammar deriving a single string. Other practical grammar compression algorithms include [[Sequitur algorithm\|Sequitur]] and [[Re-Pair]].		The [[Lempel–Ziv]] (LZ) compression methods are among the most popular algorithms for lossless storage.<ref name="Optimized LZW"/> [[DEFLATE]] is a variation on LZ optimized for decompression speed and compression ratio,<ref>{{Cite book \|title=Document Management - Portable document format - Part 1: PDF1.7 \|date=July 1, 2008 \|publisher=Adobe Systems Incorporated \|edition=1st \|language=English}}</ref> but compression can be slow. In the mid-1980s, following work by [[Terry Welch]], the [[Lempel–Ziv–Welch]] (LZW) algorithm rapidly became the method of choice for most general-purpose compression systems. LZW is used in [[GIF]] images, programs such as [[PKZIP]], and hardware devices such as modems.<ref>{{Cite book\|last=Stephen\|first=Wolfram\|url=https://www.wolframscience.com/nks/p1069--data-compression/\|title=New Kind of Science\|year=2002\|isbn=1-57955-008-8\|publisher=Wolfram Media\|location=Champaign, IL\|pages=1069}}</ref> LZ methods use a table-based compression model where table entries are substituted for repeated strings of data. For most LZ methods, this table is generated dynamically from earlier data in the input. The table itself is often [[Huffman coding\|Huffman encoded]]. [[Grammar-based codes]] like this can compress highly repetitive input extremely effectively, for instance, a biological [[data collection]] of the same or closely related species, a huge versioned document collection, internet archival, etc. The basic task of grammar-based codes is constructing a context-free grammar deriving a single string. Other practical grammar compression algorithms include [[Sequitur algorithm\|Sequitur]] and [[Re-Pair]].

	The strongest modern lossless compressors use [[Randomized algorithm\|probabilistic]] models, such as [[prediction by partial matching]]. The [[Burrows–Wheeler transform]] can also be viewed as an indirect form of statistical modelling.<ref name="mahmud2"/> In a further refinement of the direct use of [[probabilistic model]]ling, statistical estimates can be coupled to an algorithm called [[arithmetic coding]]. Arithmetic coding is a more modern coding technique that uses the mathematical calculations of a [[finite-state machine]] to produce a string of encoded bits from a series of input data symbols. It can achieve superior compression compared to other techniques such as the better-known Huffman algorithm. It uses an internal memory state to avoid the need to perform a one-to-one mapping of individual input symbols to distinct representations that use an integer number of bits, and it clears out the internal memory only after encoding the entire string of data symbols. Arithmetic coding applies especially well to adaptive data compression tasks where the statistics vary and are context-dependent, as it can be easily coupled with an adaptive model of the [[probability distribution]] of the input data. An early example of the use of arithmetic coding was in an optional (but not widely used) feature of the [[JPEG]] image coding standard.<ref name=TomLane/> It has since been applied in various other designs including [[H.263]], [[H.264/MPEG-4 AVC]] and [[HEVC]] for video coding.<ref name="HEVC"/>		The strongest modern lossless compressors use [[Randomized algorithm\|probabilistic]] models, such as [[prediction by partial matching]]. The [[Burrows–Wheeler transform]] can also be viewed as an indirect form of statistical modelling.<ref name="mahmud2"/> In a further refinement of the direct use of [[probabilistic model]]ling, statistical estimates can be coupled to an algorithm called [[arithmetic coding]]. Arithmetic coding is a more modern coding technique that uses the mathematical calculations of a [[finite-state machine]] to produce a string of encoded bits from a series of input data symbols. It can achieve superior compression compared to other techniques such as the better-known Huffman algorithm. It uses an internal memory state to avoid the need to perform a one-to-one mapping of individual input symbols to distinct representations that use an integer number of bits, and it clears out the internal memory only after encoding the entire string of data symbols. Arithmetic coding applies especially well to adaptive data compression tasks where the statistics vary and are context-dependent, as it can be easily coupled with an adaptive model of the [[probability distribution]] of the input data. An early example of the use of arithmetic coding was in an optional (but not widely used) feature of the [[JPEG]] image coding standard.<ref name=TomLane/> It has since been applied in various other designs including [[H.263]], [[H.264/MPEG-4 AVC]] and [[HEVC]] for video coding.<ref name="HEVC"/>

LooksGreatInATurtleNeck: There was a Script warning on the page from a cite book template, "Category:CS1 maint: date and year", fixed by removing the redundant year= field as date= was already set

2025-04-05T19:39:43Z

There was a Script warning on the page from a cite book template, "Category:CS1 maint: date and year", fixed by removing the redundant year= field as date= was already set

← Previous revision		Revision as of 19:39, 5 April 2025
Line 14:		Line 14:
	[[Lossless data compression]] [[algorithm]]s usually exploit [[Redundancy (information theory)\|statistical redundancy]] to represent data without losing any [[Self-information\|information]], so that the process is reversible. Lossless compression is possible because most real-world data exhibits statistical redundancy. For example, an image may have areas of color that do not change over several pixels; instead of coding "red pixel, red pixel, ..." the data may be encoded as "279 red pixels". This is a basic example of [[run-length encoding]]; there are many schemes to reduce file size by eliminating redundancy.		[[Lossless data compression]] [[algorithm]]s usually exploit [[Redundancy (information theory)\|statistical redundancy]] to represent data without losing any [[Self-information\|information]], so that the process is reversible. Lossless compression is possible because most real-world data exhibits statistical redundancy. For example, an image may have areas of color that do not change over several pixels; instead of coding "red pixel, red pixel, ..." the data may be encoded as "279 red pixels". This is a basic example of [[run-length encoding]]; there are many schemes to reduce file size by eliminating redundancy.

	The [[Lempel–Ziv]] (LZ) compression methods are among the most popular algorithms for lossless storage.<ref name="Optimized LZW"/> [[DEFLATE]] is a variation on LZ optimized for decompression speed and compression ratio,<ref>{{Cite book \|title=Document Management - Portable document format - Part 1: PDF1.7 \|date=July 1, 2008 \|publisher=Adobe Systems Incorporated ~~\|year=2008~~ \|edition=1st \|language=English}}</ref> but compression can be slow. In the mid-1980s, following work by [[Terry Welch]], the [[Lempel–Ziv–Welch]] (LZW) algorithm rapidly became the method of choice for most general-purpose compression systems. LZW is used in [[GIF]] images, programs such as [[PKZIP]], and hardware devices such as modems.<ref>{{Cite book\|last=Stephen\|first=Wolfram\|url=https://www.wolframscience.com/nks/p1069--data-compression/\|title=New Kind of Science\|year=2002\|isbn=1-57955-008-8\|location=Champaign, IL\|pages=1069}}</ref> LZ methods use a table-based compression model where table entries are substituted for repeated strings of data. For most LZ methods, this table is generated dynamically from earlier data in the input. The table itself is often [[Huffman coding\|Huffman encoded]]. [[Grammar-based codes]] like this can compress highly repetitive input extremely effectively, for instance, a biological [[data collection]] of the same or closely related species, a huge versioned document collection, internet archival, etc. The basic task of grammar-based codes is constructing a context-free grammar deriving a single string. Other practical grammar compression algorithms include [[Sequitur algorithm\|Sequitur]] and [[Re-Pair]].		The [[Lempel–Ziv]] (LZ) compression methods are among the most popular algorithms for lossless storage.<ref name="Optimized LZW"/> [[DEFLATE]] is a variation on LZ optimized for decompression speed and compression ratio,<ref>{{Cite book \|title=Document Management - Portable document format - Part 1: PDF1.7 \|date=July 1, 2008 \|publisher=Adobe Systems Incorporated \|edition=1st \|language=English}}</ref> but compression can be slow. In the mid-1980s, following work by [[Terry Welch]], the [[Lempel–Ziv–Welch]] (LZW) algorithm rapidly became the method of choice for most general-purpose compression systems. LZW is used in [[GIF]] images, programs such as [[PKZIP]], and hardware devices such as modems.<ref>{{Cite book\|last=Stephen\|first=Wolfram\|url=https://www.wolframscience.com/nks/p1069--data-compression/\|title=New Kind of Science\|year=2002\|isbn=1-57955-008-8\|location=Champaign, IL\|pages=1069}}</ref> LZ methods use a table-based compression model where table entries are substituted for repeated strings of data. For most LZ methods, this table is generated dynamically from earlier data in the input. The table itself is often [[Huffman coding\|Huffman encoded]]. [[Grammar-based codes]] like this can compress highly repetitive input extremely effectively, for instance, a biological [[data collection]] of the same or closely related species, a huge versioned document collection, internet archival, etc. The basic task of grammar-based codes is constructing a context-free grammar deriving a single string. Other practical grammar compression algorithms include [[Sequitur algorithm\|Sequitur]] and [[Re-Pair]].

	The strongest modern lossless compressors use [[Randomized algorithm\|probabilistic]] models, such as [[prediction by partial matching]]. The [[Burrows–Wheeler transform]] can also be viewed as an indirect form of statistical modelling.<ref name="mahmud2"/> In a further refinement of the direct use of [[probabilistic model]]ling, statistical estimates can be coupled to an algorithm called [[arithmetic coding]]. Arithmetic coding is a more modern coding technique that uses the mathematical calculations of a [[finite-state machine]] to produce a string of encoded bits from a series of input data symbols. It can achieve superior compression compared to other techniques such as the better-known Huffman algorithm. It uses an internal memory state to avoid the need to perform a one-to-one mapping of individual input symbols to distinct representations that use an integer number of bits, and it clears out the internal memory only after encoding the entire string of data symbols. Arithmetic coding applies especially well to adaptive data compression tasks where the statistics vary and are context-dependent, as it can be easily coupled with an adaptive model of the [[probability distribution]] of the input data. An early example of the use of arithmetic coding was in an optional (but not widely used) feature of the [[JPEG]] image coding standard.<ref name=TomLane/> It has since been applied in various other designs including [[H.263]], [[H.264/MPEG-4 AVC]] and [[HEVC]] for video coding.<ref name="HEVC"/>		The strongest modern lossless compressors use [[Randomized algorithm\|probabilistic]] models, such as [[prediction by partial matching]]. The [[Burrows–Wheeler transform]] can also be viewed as an indirect form of statistical modelling.<ref name="mahmud2"/> In a further refinement of the direct use of [[probabilistic model]]ling, statistical estimates can be coupled to an algorithm called [[arithmetic coding]]. Arithmetic coding is a more modern coding technique that uses the mathematical calculations of a [[finite-state machine]] to produce a string of encoded bits from a series of input data symbols. It can achieve superior compression compared to other techniques such as the better-known Huffman algorithm. It uses an internal memory state to avoid the need to perform a one-to-one mapping of individual input symbols to distinct representations that use an integer number of bits, and it clears out the internal memory only after encoding the entire string of data symbols. Arithmetic coding applies especially well to adaptive data compression tasks where the statistics vary and are context-dependent, as it can be easily coupled with an adaptive model of the [[probability distribution]] of the input data. An early example of the use of arithmetic coding was in an optional (but not widely used) feature of the [[JPEG]] image coding standard.<ref name=TomLane/> It has since been applied in various other designs including [[H.263]], [[H.264/MPEG-4 AVC]] and [[HEVC]] for video coding.<ref name="HEVC"/>

ZalnaRs: fixed typo

2025-03-19T20:05:43Z

fixed typo

← Previous revision		Revision as of 20:05, 19 March 2025
Line 23:		Line 23:
	{{Main\|Lossy compression}}		{{Main\|Lossy compression}}

	[[File:Comparison of JPEG and PNG.png\|thumb\|Composite image showing JPG and PNG image compression. Left side of the image is from a JPEG image, showing lossy ~~artefacts~~; the right side is from a PNG image.]]		[[File:Comparison of JPEG and PNG.png\|thumb\|Composite image showing JPG and PNG image compression. Left side of the image is from a JPEG image, showing lossy artifacts; the right side is from a PNG image.]]
	In the late 1980s, digital images became more common, and standards for lossless [[image compression]] emerged. In the early 1990s, lossy compression methods began to be widely used.<ref name="Wolfram"/> In these schemes, some loss of information is accepted as dropping nonessential detail can save storage space. There is a corresponding [[trade-off]] between preserving information and reducing size. Lossy data compression schemes are designed by research on how people perceive the data in question. For example, the human eye is more sensitive to subtle variations in [[luminance]] than it is to the variations in color. JPEG image compression works in part by rounding off nonessential bits of information.<ref name="Arcangel"/> A number of popular compression formats exploit these perceptual differences, including [[psychoacoustics]] for sound, and [[psychovisual]]s for images and video.		In the late 1980s, digital images became more common, and standards for lossless [[image compression]] emerged. In the early 1990s, lossy compression methods began to be widely used.<ref name="Wolfram"/> In these schemes, some loss of information is accepted as dropping nonessential detail can save storage space. There is a corresponding [[trade-off]] between preserving information and reducing size. Lossy data compression schemes are designed by research on how people perceive the data in question. For example, the human eye is more sensitive to subtle variations in [[luminance]] than it is to the variations in color. JPEG image compression works in part by rounding off nonessential bits of information.<ref name="Arcangel"/> A number of popular compression formats exploit these perceptual differences, including [[psychoacoustics]] for sound, and [[psychovisual]]s for images and video.

← Previous revision		Revision as of 19:41, 5 April 2025
Line 14:		Line 14:
	[[Lossless data compression]] [[algorithm]]s usually exploit [[Redundancy (information theory)\|statistical redundancy]] to represent data without losing any [[Self-information\|information]], so that the process is reversible. Lossless compression is possible because most real-world data exhibits statistical redundancy. For example, an image may have areas of color that do not change over several pixels; instead of coding "red pixel, red pixel, ..." the data may be encoded as "279 red pixels". This is a basic example of [[run-length encoding]]; there are many schemes to reduce file size by eliminating redundancy.		[[Lossless data compression]] [[algorithm]]s usually exploit [[Redundancy (information theory)\|statistical redundancy]] to represent data without losing any [[Self-information\|information]], so that the process is reversible. Lossless compression is possible because most real-world data exhibits statistical redundancy. For example, an image may have areas of color that do not change over several pixels; instead of coding "red pixel, red pixel, ..." the data may be encoded as "279 red pixels". This is a basic example of [[run-length encoding]]; there are many schemes to reduce file size by eliminating redundancy.

	The [[Lempel–Ziv]] (LZ) compression methods are among the most popular algorithms for lossless storage.<ref name="Optimized LZW"/> [[DEFLATE]] is a variation on LZ optimized for decompression speed and compression ratio,<ref>{{Cite book \|title=Document Management - Portable document format - Part 1: PDF1.7 \|date=July 1, 2008 \|publisher=Adobe Systems Incorporated \|edition=1st \|language=English}}</ref> but compression can be slow. In the mid-1980s, following work by [[Terry Welch]], the [[Lempel–Ziv–Welch]] (LZW) algorithm rapidly became the method of choice for most general-purpose compression systems. LZW is used in [[GIF]] images, programs such as [[PKZIP]], and hardware devices such as modems.<ref>{{Cite book\|last=Stephen\|first=Wolfram\|url=https://www.wolframscience.com/nks/p1069--data-compression/\|title=New Kind of Science\|year=2002\|isbn=1-57955-008-8\|location=Champaign, IL\|pages=1069}}</ref> LZ methods use a table-based compression model where table entries are substituted for repeated strings of data. For most LZ methods, this table is generated dynamically from earlier data in the input. The table itself is often [[Huffman coding\|Huffman encoded]]. [[Grammar-based codes]] like this can compress highly repetitive input extremely effectively, for instance, a biological [[data collection]] of the same or closely related species, a huge versioned document collection, internet archival, etc. The basic task of grammar-based codes is constructing a context-free grammar deriving a single string. Other practical grammar compression algorithms include [[Sequitur algorithm\|Sequitur]] and [[Re-Pair]].		The [[Lempel–Ziv]] (LZ) compression methods are among the most popular algorithms for lossless storage.<ref name="Optimized LZW"/> [[DEFLATE]] is a variation on LZ optimized for decompression speed and compression ratio,<ref>{{Cite book \|title=Document Management - Portable document format - Part 1: PDF1.7 \|date=July 1, 2008 \|publisher=Adobe Systems Incorporated \|edition=1st \|language=English}}</ref> but compression can be slow. In the mid-1980s, following work by [[Terry Welch]], the [[Lempel–Ziv–Welch]] (LZW) algorithm rapidly became the method of choice for most general-purpose compression systems. LZW is used in [[GIF]] images, programs such as [[PKZIP]], and hardware devices such as modems.<ref>{{Cite book\|last=Stephen\|first=Wolfram\|url=https://www.wolframscience.com/nks/p1069--data-compression/\|title=New Kind of Science\|year=2002\|isbn=1-57955-008-8\|publisher=Wolfram Media\|location=Champaign, IL\|pages=1069}}</ref> LZ methods use a table-based compression model where table entries are substituted for repeated strings of data. For most LZ methods, this table is generated dynamically from earlier data in the input. The table itself is often [[Huffman coding\|Huffman encoded]]. [[Grammar-based codes]] like this can compress highly repetitive input extremely effectively, for instance, a biological [[data collection]] of the same or closely related species, a huge versioned document collection, internet archival, etc. The basic task of grammar-based codes is constructing a context-free grammar deriving a single string. Other practical grammar compression algorithms include [[Sequitur algorithm\|Sequitur]] and [[Re-Pair]].

	The strongest modern lossless compressors use [[Randomized algorithm\|probabilistic]] models, such as [[prediction by partial matching]]. The [[Burrows–Wheeler transform]] can also be viewed as an indirect form of statistical modelling.<ref name="mahmud2"/> In a further refinement of the direct use of [[probabilistic model]]ling, statistical estimates can be coupled to an algorithm called [[arithmetic coding]]. Arithmetic coding is a more modern coding technique that uses the mathematical calculations of a [[finite-state machine]] to produce a string of encoded bits from a series of input data symbols. It can achieve superior compression compared to other techniques such as the better-known Huffman algorithm. It uses an internal memory state to avoid the need to perform a one-to-one mapping of individual input symbols to distinct representations that use an integer number of bits, and it clears out the internal memory only after encoding the entire string of data symbols. Arithmetic coding applies especially well to adaptive data compression tasks where the statistics vary and are context-dependent, as it can be easily coupled with an adaptive model of the [[probability distribution]] of the input data. An early example of the use of arithmetic coding was in an optional (but not widely used) feature of the [[JPEG]] image coding standard.<ref name=TomLane/> It has since been applied in various other designs including [[H.263]], [[H.264/MPEG-4 AVC]] and [[HEVC]] for video coding.<ref name="HEVC"/>		The strongest modern lossless compressors use [[Randomized algorithm\|probabilistic]] models, such as [[prediction by partial matching]]. The [[Burrows–Wheeler transform]] can also be viewed as an indirect form of statistical modelling.<ref name="mahmud2"/> In a further refinement of the direct use of [[probabilistic model]]ling, statistical estimates can be coupled to an algorithm called [[arithmetic coding]]. Arithmetic coding is a more modern coding technique that uses the mathematical calculations of a [[finite-state machine]] to produce a string of encoded bits from a series of input data symbols. It can achieve superior compression compared to other techniques such as the better-known Huffman algorithm. It uses an internal memory state to avoid the need to perform a one-to-one mapping of individual input symbols to distinct representations that use an integer number of bits, and it clears out the internal memory only after encoding the entire string of data symbols. Arithmetic coding applies especially well to adaptive data compression tasks where the statistics vary and are context-dependent, as it can be easily coupled with an adaptive model of the [[probability distribution]] of the input data. An early example of the use of arithmetic coding was in an optional (but not widely used) feature of the [[JPEG]] image coding standard.<ref name=TomLane/> It has since been applied in various other designs including [[H.263]], [[H.264/MPEG-4 AVC]] and [[HEVC]] for video coding.<ref name="HEVC"/>

← Previous revision		Revision as of 19:39, 5 April 2025
Line 14:		Line 14:
	[[Lossless data compression]] [[algorithm]]s usually exploit [[Redundancy (information theory)\|statistical redundancy]] to represent data without losing any [[Self-information\|information]], so that the process is reversible. Lossless compression is possible because most real-world data exhibits statistical redundancy. For example, an image may have areas of color that do not change over several pixels; instead of coding "red pixel, red pixel, ..." the data may be encoded as "279 red pixels". This is a basic example of [[run-length encoding]]; there are many schemes to reduce file size by eliminating redundancy.		[[Lossless data compression]] [[algorithm]]s usually exploit [[Redundancy (information theory)\|statistical redundancy]] to represent data without losing any [[Self-information\|information]], so that the process is reversible. Lossless compression is possible because most real-world data exhibits statistical redundancy. For example, an image may have areas of color that do not change over several pixels; instead of coding "red pixel, red pixel, ..." the data may be encoded as "279 red pixels". This is a basic example of [[run-length encoding]]; there are many schemes to reduce file size by eliminating redundancy.

	The [[Lempel–Ziv]] (LZ) compression methods are among the most popular algorithms for lossless storage.<ref name="Optimized LZW"/> [[DEFLATE]] is a variation on LZ optimized for decompression speed and compression ratio,<ref>{{Cite book \|title=Document Management - Portable document format - Part 1: PDF1.7 \|date=July 1, 2008 \|publisher=Adobe Systems Incorporated ~~\|year=2008~~ \|edition=1st \|language=English}}</ref> but compression can be slow. In the mid-1980s, following work by [[Terry Welch]], the [[Lempel–Ziv–Welch]] (LZW) algorithm rapidly became the method of choice for most general-purpose compression systems. LZW is used in [[GIF]] images, programs such as [[PKZIP]], and hardware devices such as modems.<ref>{{Cite book\|last=Stephen\|first=Wolfram\|url=https://www.wolframscience.com/nks/p1069--data-compression/\|title=New Kind of Science\|year=2002\|isbn=1-57955-008-8\|location=Champaign, IL\|pages=1069}}</ref> LZ methods use a table-based compression model where table entries are substituted for repeated strings of data. For most LZ methods, this table is generated dynamically from earlier data in the input. The table itself is often [[Huffman coding\|Huffman encoded]]. [[Grammar-based codes]] like this can compress highly repetitive input extremely effectively, for instance, a biological [[data collection]] of the same or closely related species, a huge versioned document collection, internet archival, etc. The basic task of grammar-based codes is constructing a context-free grammar deriving a single string. Other practical grammar compression algorithms include [[Sequitur algorithm\|Sequitur]] and [[Re-Pair]].		The [[Lempel–Ziv]] (LZ) compression methods are among the most popular algorithms for lossless storage.<ref name="Optimized LZW"/> [[DEFLATE]] is a variation on LZ optimized for decompression speed and compression ratio,<ref>{{Cite book \|title=Document Management - Portable document format - Part 1: PDF1.7 \|date=July 1, 2008 \|publisher=Adobe Systems Incorporated \|edition=1st \|language=English}}</ref> but compression can be slow. In the mid-1980s, following work by [[Terry Welch]], the [[Lempel–Ziv–Welch]] (LZW) algorithm rapidly became the method of choice for most general-purpose compression systems. LZW is used in [[GIF]] images, programs such as [[PKZIP]], and hardware devices such as modems.<ref>{{Cite book\|last=Stephen\|first=Wolfram\|url=https://www.wolframscience.com/nks/p1069--data-compression/\|title=New Kind of Science\|year=2002\|isbn=1-57955-008-8\|location=Champaign, IL\|pages=1069}}</ref> LZ methods use a table-based compression model where table entries are substituted for repeated strings of data. For most LZ methods, this table is generated dynamically from earlier data in the input. The table itself is often [[Huffman coding\|Huffman encoded]]. [[Grammar-based codes]] like this can compress highly repetitive input extremely effectively, for instance, a biological [[data collection]] of the same or closely related species, a huge versioned document collection, internet archival, etc. The basic task of grammar-based codes is constructing a context-free grammar deriving a single string. Other practical grammar compression algorithms include [[Sequitur algorithm\|Sequitur]] and [[Re-Pair]].

	The strongest modern lossless compressors use [[Randomized algorithm\|probabilistic]] models, such as [[prediction by partial matching]]. The [[Burrows–Wheeler transform]] can also be viewed as an indirect form of statistical modelling.<ref name="mahmud2"/> In a further refinement of the direct use of [[probabilistic model]]ling, statistical estimates can be coupled to an algorithm called [[arithmetic coding]]. Arithmetic coding is a more modern coding technique that uses the mathematical calculations of a [[finite-state machine]] to produce a string of encoded bits from a series of input data symbols. It can achieve superior compression compared to other techniques such as the better-known Huffman algorithm. It uses an internal memory state to avoid the need to perform a one-to-one mapping of individual input symbols to distinct representations that use an integer number of bits, and it clears out the internal memory only after encoding the entire string of data symbols. Arithmetic coding applies especially well to adaptive data compression tasks where the statistics vary and are context-dependent, as it can be easily coupled with an adaptive model of the [[probability distribution]] of the input data. An early example of the use of arithmetic coding was in an optional (but not widely used) feature of the [[JPEG]] image coding standard.<ref name=TomLane/> It has since been applied in various other designs including [[H.263]], [[H.264/MPEG-4 AVC]] and [[HEVC]] for video coding.<ref name="HEVC"/>		The strongest modern lossless compressors use [[Randomized algorithm\|probabilistic]] models, such as [[prediction by partial matching]]. The [[Burrows–Wheeler transform]] can also be viewed as an indirect form of statistical modelling.<ref name="mahmud2"/> In a further refinement of the direct use of [[probabilistic model]]ling, statistical estimates can be coupled to an algorithm called [[arithmetic coding]]. Arithmetic coding is a more modern coding technique that uses the mathematical calculations of a [[finite-state machine]] to produce a string of encoded bits from a series of input data symbols. It can achieve superior compression compared to other techniques such as the better-known Huffman algorithm. It uses an internal memory state to avoid the need to perform a one-to-one mapping of individual input symbols to distinct representations that use an integer number of bits, and it clears out the internal memory only after encoding the entire string of data symbols. Arithmetic coding applies especially well to adaptive data compression tasks where the statistics vary and are context-dependent, as it can be easily coupled with an adaptive model of the [[probability distribution]] of the input data. An early example of the use of arithmetic coding was in an optional (but not widely used) feature of the [[JPEG]] image coding standard.<ref name=TomLane/> It has since been applied in various other designs including [[H.263]], [[H.264/MPEG-4 AVC]] and [[HEVC]] for video coding.<ref name="HEVC"/>