Aufgaben:Exercise 2.13: Inverse Burrows-Wheeler Transformation - Revision history

Maintenance script: Fix interlanguage link: resolve redirect chain

2026-03-16T15:54:23Z

Fix interlanguage link: resolve redirect chain

← Older revision		Revision as of 17:54, 16 March 2026
Line 96:		Line 96:

	[[Category:Information Theory: Exercises\|^2.4 Further Source Coding Methods^]]		[[Category:Information Theory: Exercises\|^2.4 Further Source Coding Methods^]]
	[[de:Aufgaben:2.~~13_Burrows~~-Wheeler-Rücktransformation]]		[[de:Aufgaben:Aufgabe 2.13: Burrows-Wheeler-Rücktransformation]]

Maintenance script: Add German interlanguage link

2026-03-16T12:30:59Z

Add German interlanguage link

← Older revision		Revision as of 14:30, 16 March 2026
Line 96:		Line 96:

	[[Category:Information Theory: Exercises\|^2.4 Further Source Coding Methods^]]		[[Category:Information Theory: Exercises\|^2.4 Further Source Coding Methods^]]
			[[de:Aufgaben:2.13_Burrows-Wheeler-Rücktransformation]]

Hwang at 12:45, 17 November 2022

2022-11-17T12:45:00Z

← Older revision		Revision as of 14:45, 17 November 2022
Line 15:		Line 15:


	The graphic shows the result of a BWT, more precisely its L column.  The original text is to be reconstructed from this according to the description on the theory ~~page~~  [[Information_Theory/Further_Source_Coding_Methods#Burrows.E2.80.93Wheeler_transformation\|Burrows–Wheeler Transformation]],		The graphic shows the result of a BWT, more precisely its L column.  The original text is to be reconstructed from this according to the description in the theory section  [[Information_Theory/Further_Source_Coding_Methods#Burrows.E2.80.93Wheeler_transformation\|Burrows–Wheeler Transformation]],
	*in subtask  '''(2)'''  with the primary index  $I = 7$,		*in subtask  '''(2)'''  with the primary index  $I = 7$,
	*in subtask  '''(3)'''    $I = 0$  is to be assumed.		*in subtask  '''(3)'''    $I = 0$  is to be assumed.
Line 27:		Line 27:
	<u>Hints:</u>		<u>Hints:</u>
	*The exercise belongs to the chapter  [[Information_Theory/Further_Source_Coding_Methods\|Further Source Coding Methods]].		*The exercise belongs to the chapter  [[Information_Theory/Further_Source_Coding_Methods\|Further Source Coding Methods]].
	*In particular, reference is made to the ~~page~~  [[Information_Theory/Further_Source_Coding_Methods#Burrows.E2.80.93Wheeler_transformation\|Burrows–Wheeler Transformation]].		*In particular, reference is made to the section  [[Information_Theory/Further_Source_Coding_Methods#Burrows.E2.80.93Wheeler_transformation\|Burrows–Wheeler Transformation]].

Javier: Text replacement - "analyse" to "analyze"

2021-09-22T11:47:48Z

Text replacement - "analyse" to "analyze"

← Older revision		Revision as of 13:47, 22 September 2021
Line 3:		Line 3:
	}}		}}

	[[File:EN_Inf_A_2_14.png\|right\|frame\|BWT result to be ~~analysed~~]]		[[File:EN_Inf_A_2_14.png\|right\|frame\|BWT result to be analyzed]]
	The  "Burrows–Wheeler Transformation" – abbreviated  $\rm BWT$  – causes a blockwise sorting of the characters of a text with the aim of preparing the text for efficient data compression with the help of run-length coding or entropy coding.		The  "Burrows–Wheeler Transformation" – abbreviated  $\rm BWT$  – causes a blockwise sorting of the characters of a text with the aim of preparing the text for efficient data compression with the help of run-length coding or entropy coding.

Guenter at 14:11, 13 August 2021

2021-08-13T14:11:51Z

← Older revision		Revision as of 16:11, 13 August 2021
Line 73:		Line 73:


	:[[File:~~P_ID2479__Inf_A_2_14b~~.png\|right\|frame\|Inverse BWT with  $I = 7$  (left) or  $I = 0$  (right)]]		:[[File:Inf_Z_2_14b_v2.png\|right\|frame\|Inverse BWT with  $I = 7$  (left) or  $I = 0$  (right)]]

	'''(2)'''  The <u>solution suggestion 1</u> is correct:   <b>MEINDEINSEIN</b>, as can be seen from the left-hand representation of the following diagram. <br>Note that the top line represents the line number  $I = 0$  in each case. For explanation:		'''(2)'''  The <u>solution suggestion 1</u> is correct:   <b>MEINDEINSEIN</b>, as can be seen from the left-hand representation of the following diagram. <br>Note that the top line represents the line number  $I = 0$  in each case. For explanation:

Guenter at 08:57, 13 August 2021

2021-08-13T08:57:49Z

← Older revision		Revision as of 10:57, 13 August 2021
Line 66:		Line 66:
	===Solution===		===Solution===
	{{ML-Kopf}}		{{ML-Kopf}}
	'''(1)'''  <u>~~Solution~~ suggestion 3</u> is correct:		'''(1)'''  The <u>solution suggestion 3</u> is correct:
	*The first column of the BWT matrix is also called the  F~~–~~column  and the last column the  L~~–~~column  (from "~~<i>~~First~~</i>~~" or "~~<i>~~Last~~</i>~~").		*The first column of the BWT matrix is also called the  "F column"  and the last column the  "L column"  (from  "First"  or  "Last").
	*Only the  L~~–~~column is passed on to the next coding level.		*Only the  "L column" is passed on to the next coding level.
	*The  F~~–~~column, which is also needed for the reverse transformation, results from the  L~~–~~column  by ~~lexicographic~~ sorting.		*The  "F column", which is also needed for the reverse transformation, results from the  "L column"  by lexicographically sorting.



	'''(2)''' <u>Solution suggestion 1</u> is correct:   <b>MEINDEINSEIN</b> is correct, as can be seen from the left-hand representation of the following diagram. <br>Note that the top line represents the line number  $I = 0$  in each case. For explanation:		:[[File:P_ID2479__Inf_A_2_14b.png\|right\|frame\|Inverse BWT with  $I = 7$  (left) or  $I = 0$  (right)]]
	:[[File:P_ID2479__Inf_A_2_14b.png\|right\|frame\|~~BW back transformation~~ with  $I = 7$  (left) or  $I = 0$  (right)]]
	* Start the decoding with the line  $I = 7$  of the F–column.  The content is "M".
	* Search for the corresponding "M" in the L–column and find it in line number "1".
	* From line 1 of the L–column one goes horizontally to the  F–column  and finds the symbol  "E".
	* Similarly, one finds the third output symbol  "I"  in line 4 of theF–column.
	* The decoding algorithm ends with the output symbol  "N"  in the third last row.

			'''(2)'''  The <u>solution suggestion 1</u> is correct:   <b>MEINDEINSEIN</b>, as can be seen from the left-hand representation of the following diagram. <br>Note that the top line represents the line number  $I = 0$  in each case. For explanation:
			* Start the decoding with the line  $I = 7$  of the  "F column".  <br>The content is  $\rm M$.
			* Search for the corresponding  $\rm M$  in the  "L column"  and find it in line number  "1".
			* From line 1 of the  "L column"  one goes horizontally to the  "F column"  and finds the symbol  $\rm E$.
			* Similarly, one finds the third output symbol  $\rm I$  in line 4 of the  "F column".
			* The decoding algorithm ends with the output symbol  $\rm N$  in the third last row.


	'''(3)'''  Correct is the <u>proposed solution 2</u>:   ~~<br><br>~~$\rm DEINSEINMEIN$, as shown in the graph on the right.
			'''(3)'''  Correct is the <u>proposed solution 2</u>:   $\rm DEINSEINMEIN$, as shown in the graph on the right.
	<br clear=all>		<br clear=all>

	'''(4)'''  Correct is the <u>suggested solution 3</u>:		'''(4)'''  Correct is the <u>suggested solution 3</u>:
	*In BWT, four characters here are equal to their predecessors, in the original none.		*In BWT, four characters here are equal to their predecessors, in the original none.
	*In the F&~~ndash~~;column , even more characters would be the same as their respective predecessors (6 in total) due to the lexicographical sorting, but this sorting cannot be reversed without loss.		*In the  "F column",  even more characters would be the same as their respective predecessors  (6 in total)  due to the lexicographical sorting, but this sorting cannot be reversed without loss.
	*Solution suggestion 1 is ~~also~~ wrong:   ~~the~~ original and BWT contain exactly the same characters  $($three times  $\rm E$,  three times  $\rm I$,  three times  $\rm N$ and one each of  $\rm D$,  $\rm M$  and  $\rm S)$.		*Solution suggestion 1 is wrong too:   <br>The original and BWT contain exactly the same characters  $($three times  $\rm E$,  three times  $\rm I$,  three times  $\rm N$ and one each of  $\rm D$,  $\rm M$  and  $\rm S)$.
	{{ML-Fuß}}		{{ML-Fuß}}

Guenter at 08:37, 13 August 2021

2021-08-13T08:37:08Z

← Older revision		Revision as of 10:37, 13 August 2021
Line 25:		Line 25:


	Hints:		<u>Hints:</u>
	*The exercise belongs to the chapter  [[Information_Theory/Further_Source_Coding_Methods\|Further Source Coding Methods]].		*The exercise belongs to the chapter  [[Information_Theory/Further_Source_Coding_Methods\|Further Source Coding Methods]].
	*In particular, reference is made to the page  [[Information_Theory/Further_Source_Coding_Methods#Burrows.E2.80.93Wheeler_transformation\|Burrows–Wheeler Transformation]].		*In particular, reference is made to the page  [[Information_Theory/Further_Source_Coding_Methods#Burrows.E2.80.93Wheeler_transformation\|Burrows–Wheeler Transformation]].
	*Further information can be found in the two publications mentioned below:
	: '''(1)'''   Abel, J.: ''Verlustlose Datenkompression auf Grundlage der Burrows-Wheeler-Transformation''. <br>            In: PIK - Praxis der Informationsverarbeitung und Kommunikation, no. 3, vol. 26, S. 140–144, Sept. 2003.
	: '''(2)'''   Abel, J.: ''Grundlagen des Burrows-Wheeler-Kompressionsalgorithmus''. <br>            In: Informatik Forschung & Entwicklung, no. 2, vol. 18, S. 80–87, Jan. 2004.


Line 36:		Line 33:

	<quiz display=simple>		<quiz display=simple>
	{What is the  $\text{F~~–Spalte~~}$ associated with the given  $\text{L~~–Spalte~~}$ ?		{What is the  $\text{F column}$ associated with the given  $\text{L column}$ ?
	\|type="()"}		\|type="()"}
	- $\rm SEINMEINDEIN$,		- $\rm SEINMEINDEIN$,
Line 50:		Line 47:


	{What happens if the reconstruction  $\text{(BWT ~~back~~ transformation})$  starts from the wrong primary index  $I = 0$ ?		{What happens if the reconstruction  $\text{(inverse BWT transformation})$  starts from the wrong primary index  $I = 0$ ?
	\|type="[]"}		\|type="[]"}
	- ~~The result is the original text~~, ~~read from back to front.~~		- $\rm MEINDEINSEIN$,
	+ ~~The result is a cyclic permutation of the original~~.		+ $\rm DEINSEINMEIN$,
			- $\rm NIESNIEDNIEM$.


	Why is the Burrows–Wheeler ~~transform~~ better suited than the original with regard to a later data compression?		{Why is the Burrows–Wheeler transformation better suited than the original with regard to a later data compression?
	\|type="[]"}		\|type="[]"}
	- It results in more favourable character frequencies.		- It results in more favourable character frequencies.

Guenter at 08:25, 13 August 2021

2021-08-13T08:25:50Z

← Older revision		Revision as of 10:25, 13 August 2021
Line 15:		Line 15:


	The graphic shows the result of a BWT, more precisely its L column.  The original text is to be reconstructed from this according to the description on the theory page  [[Information_Theory/~~Weitere_Quellencodierverfahren~~#Burrows.E2.80.~~93Wheeler.E2.80.93Transformation~~\|Burrows–Wheeler Transformation]],		The graphic shows the result of a BWT, more precisely its L column.  The original text is to be reconstructed from this according to the description on the theory page  [[Information_Theory/Further_Source_Coding_Methods#Burrows.E2.80.93Wheeler_transformation\|Burrows–Wheeler Transformation]],
	*in subtask  '''(2)'''  with the primary index  $I = 7$,		*in subtask  '''(2)'''  with the primary index  $I = 7$,
	*in subtask  '''(3)'''    $I = 0$  is to be assumed.		*in subtask  '''(3)'''    $I = 0$  is to be assumed.
Line 27:		Line 27:
	Hints:		Hints:
	*The exercise belongs to the chapter  [[Information_Theory/Further_Source_Coding_Methods\|Further Source Coding Methods]].		*The exercise belongs to the chapter  [[Information_Theory/Further_Source_Coding_Methods\|Further Source Coding Methods]].
	*In particular, reference is made to the page  [[Information_Theory/Further_Source_Coding_Methods#Burrows.E2.80.~~93Wheeler.E2.80.93Transformation~~\|Burrows–Wheeler Transformation]].		*In particular, reference is made to the page  [[Information_Theory/Further_Source_Coding_Methods#Burrows.E2.80.93Wheeler_transformation\|Burrows–Wheeler Transformation]].
	*Further information can be found in the two publications mentioned below:		*Further information can be found in the two publications mentioned below:
	: '''(1)'''   Abel, J.: ''Verlustlose Datenkompression auf Grundlage der Burrows-Wheeler-Transformation''. <br>            In: PIK - Praxis der Informationsverarbeitung und Kommunikation, no. 3, vol. 26, S. 140–144, Sept. 2003.		: '''(1)'''   Abel, J.: ''Verlustlose Datenkompression auf Grundlage der Burrows-Wheeler-Transformation''. <br>            In: PIK - Praxis der Informationsverarbeitung und Kommunikation, no. 3, vol. 26, S. 140–144, Sept. 2003.

Guenter at 08:24, 13 August 2021

2021-08-13T08:24:18Z

← Older revision		Revision as of 10:24, 13 August 2021
Line 26:		Line 26:

	Hints:		Hints:
	*The exercise belongs to the chapter  [[Information_Theory/~~Weitere_Quellencodierverfahren~~\|~~Other source coding methods~~]].		*The exercise belongs to the chapter  [[Information_Theory/Further_Source_Coding_Methods\|Further Source Coding Methods]].
	*In particular, reference is made to the page  [[Information_Theory/~~Weitere_Quellencodierverfahren~~#Burrows.E2.80.93Wheeler.E2.80.93Transformation\|Burrows–Wheeler Transformation]].		*In particular, reference is made to the page  [[Information_Theory/Further_Source_Coding_Methods#Burrows.E2.80.93Wheeler.E2.80.93Transformation\|Burrows–Wheeler Transformation]].
	*Further information can be found in the two publications mentioned below:		*Further information can be found in the two publications mentioned below:
	: '''(1)'''   Abel, J.: ''Verlustlose Datenkompression auf Grundlage der Burrows-Wheeler-Transformation''. <br>            In: PIK - Praxis der Informationsverarbeitung und Kommunikation, no. 3, vol. 26, S. 140–144, Sept. 2003.		: '''(1)'''   Abel, J.: ''Verlustlose Datenkompression auf Grundlage der Burrows-Wheeler-Transformation''. <br>            In: PIK - Praxis der Informationsverarbeitung und Kommunikation, no. 3, vol. 26, S. 140–144, Sept. 2003.

Guenter at 08:21, 13 August 2021

2021-08-13T08:21:58Z

← Older revision		Revision as of 10:21, 13 August 2021
Line 3:		Line 3:
	}}		}}

	[[File:EN_Inf_A_2_14.png\|right\|frame\|To be analysed ~~<br>BWT result~~]]		[[File:EN_Inf_A_2_14.png\|right\|frame\|BWT result to be analysed]]
	~~Die~~  ''Burrows–Wheeler~~–~~Transformation'' – abbreviated  $\rm BWT$  – causes a blockwise sorting of the characters of a text with the aim of preparing the text for efficient data compression with the help of run-length coding or entropy coding.		The  "Burrows–Wheeler Transformation" – abbreviated  $\rm BWT$  – causes a blockwise sorting of the characters of a text with the aim of preparing the text for efficient data compression with the help of run-length coding or entropy coding.

	* First, an  $N×N$~~–~~ matrix is generated from a block of length  $N$ , with each row of this first~~–~~matrix resulting from the preceding row by cyclic left shift.		* First, an  $N×N$ matrix is generated from a block of length  $N$,  with each row of this first matrix resulting from the preceding row by cyclic left shift.

	* Then the matrix is sorted lexicographically  (without special characters:   alphabetically) .  The result of the BWT is the last row of the new BWT matrix, the so-called  $\text{L~~–~~column}$  (from "Last"~~,   last row of the BWT–matrix~~).		* Then the matrix is sorted lexicographically  (without special characters:   alphabetically) .  The result of the BWT is the last row of the new BWT matrix, the so-called  $\text{L column}$  (from "Last").

	* Further, this task refers to the  $\text{F~~–~~column}$  (from "First", first row of the BWT matrix), which is needed for the inverse Burrows–Wheeler~~–~~Transformation   ⇒   reconstruction of the original text from the L~~–~~column.		* Further, this task refers to the  $\text{F column}$  (from "First", first row of the BWT matrix), which is needed for the inverse Burrows–Wheeler Transformation   ⇒   reconstruction of the original text from the L column.

	* For the inverse BWT, the so-called ~~<i>~~primary index~~</i>~~  $I$ is also required.  This indicates the row of the BWT matrix in which the algorithm must be started.		* For the inverse BWT, the so-called  "primary index"  $I$  is also required.  This indicates the row of the BWT matrix in which the algorithm must be started.


	The graphic shows the result of a BWT, more precisely its L~~–~~column.  The original text is to be reconstructed from this according to the description on the theory page  [[Information_Theory/Weitere_Quellencodierverfahren#Burrows.E2.80.93Wheeler.E2.80.93Transformation\|Burrows–Wheeler Transformation]]~~ ~~,		The graphic shows the result of a BWT, more precisely its L column.  The original text is to be reconstructed from this according to the description on the theory page  [[Information_Theory/Weitere_Quellencodierverfahren#Burrows.E2.80.93Wheeler.E2.80.93Transformation\|Burrows–Wheeler Transformation]],
	*~~where~~ in subtask  '''(2)'''  ~~from~~ the primary index  $I = 7$		*in subtask  '''(2)'''  with the primary index  $I = 7$,
	*~~and~~ in subtask  '''(3)'''    $I = 0$  is to be assumed.		*in subtask  '''(3)'''    $I = 0$  is to be assumed.