Wavelet Tree - Versionsgeschichte

SchlurcherBot: Bot: http → https

2025-04-21T13:18:40Z

Bot: http → https

← Nächstältere Version		Version vom 21. April 2025, 15:18 Uhr
Zeile 59:		Zeile 59:

	== Weblinks ==		== Weblinks ==
	* [~~http~~://www.alexbowe.com/wavelet-trees Wavelet Trees]. Blog, der die Konstruktion und Anfragen eines Wavelet Trees mit Beispielen beschreibt.		* [https://www.alexbowe.com/wavelet-trees Wavelet Trees]. Blog, der die Konstruktion und Anfragen eines Wavelet Trees mit Beispielen beschreibt.

	== Einzelnachweise ==		== Einzelnachweise ==
	<references>		<references>
	<ref name="GGV03">		<ref name="GGV03">
	R. Grossi, A. Gupta, and J. S. Vitter, [~~http~~://www.di.unipi.it/~grossi/PAPERS/sodaconf03FINAL-LATEST.pdf High-order entropy-compressed text indexes] (PDF; 292 kB), ''Proceedings of the 14th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA)'', January 2003, 841-850		R. Grossi, A. Gupta, and J. S. Vitter, [https://www.di.unipi.it/~grossi/PAPERS/sodaconf03FINAL-LATEST.pdf High-order entropy-compressed text indexes] (PDF; 292 kB), ''Proceedings of the 14th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA)'', January 2003, 841-850
	</ref>		</ref>
	<ref name="CB88">		<ref name="CB88">
Zeile 70:		Zeile 70:
	</ref>		</ref>
	<ref name="FGM09">		<ref name="FGM09">
	P. Ferragina, R. Giancarlo, G. Manzini, [~~http~~://www.ittc.ku.edu/~jsv/Papers/FGM09.wavelettrees.pdf The myriad virtues of Wavelet Trees] (PDF; 529 kB), ''Information and Computation'', Volume 207, Issue 8, August 2009, Pages 849-866		P. Ferragina, R. Giancarlo, G. Manzini, [https://www.ittc.ku.edu/~jsv/Papers/FGM09.wavelettrees.pdf The myriad virtues of Wavelet Trees] (PDF; 529 kB), ''Information and Computation'', Volume 207, Issue 8, August 2009, Pages 849-866
	</ref>		</ref>
	<ref name="Navarro12">		<ref name="Navarro12">
	G. Navarro, [~~http~~://www.dcc.uchile.cl/~gnavarro/ps/cpm12.pdf Wavelet Trees for All] (PDF; 397 kB), ''Proceedings of 23rd Annual Symposium on Combinatorial Pattern Matching (CPM)'', 2012		G. Navarro, [https://www.dcc.uchile.cl/~gnavarro/ps/cpm12.pdf Wavelet Trees for All] (PDF; 397 kB), ''Proceedings of 23rd Annual Symposium on Combinatorial Pattern Matching (CPM)'', 2012
	</ref>		</ref>
	<ref name="Jacobson89">		<ref name="Jacobson89">
Zeile 79:		Zeile 79:
	</ref>		</ref>
	<ref name="Clark96">		<ref name="Clark96">
	D. Clark, [~~http~~://uwspace.uwaterloo.ca/bitstream/10012/64/1/nq21335.pdf Compact Pat Tree] (PDF; 6,7 MB), ''University of Waterloo, Canada'', 1996		D. Clark, [https://uwspace.uwaterloo.ca/bitstream/10012/64/1/nq21335.pdf Compact Pat Tree] (PDF; 6,7 MB), ''University of Waterloo, Canada'', 1996
	</ref>		</ref>
	<ref name="Munro96">		<ref name="Munro96">

Invisigoth67: typo

2024-10-14T13:54:53Z

typo

← Nächstältere Version		Version vom 14. Oktober 2024, 15:54 Uhr
Zeile 38:		Zeile 38:
	<math>select_q(i)</math>: Position des i-ten Vorkommens vom Zeichen q in der Zeichenfolge.		<math>select_q(i)</math>: Position des i-ten Vorkommens vom Zeichen q in der Zeichenfolge.

	Um diese Position zu bestimmen beginnt der Algorithmus bei dem Blatt, das q repräsentiert. Nun durchläuft der Algorithmus die Knoten rekursiv zur Wurzel: Falls der Knoten ein linkes Kind ist, so ergibt sich die neue Position im Elternknoten <math>i_0</math> aus der Position der i-ten <math>0</math> im zugehörigen Bitvektor. Ist das Kind ein rechter Nachfolger, so ergibt sich die neue Position <math>i_1</math> aus der Position der i-ten <math>1</math>. Diese Selekt-Operation auf einem Bitvektor<ref name="Clark96"/><ref name="Munro96" /> kann in konstanter Zeit mit zusätzlichen <math>n+o(n)</math> ausgeführt werden.		Um diese Position zu bestimmen, beginnt der Algorithmus bei dem Blatt, das q repräsentiert. Nun durchläuft der Algorithmus die Knoten rekursiv zur Wurzel: Falls der Knoten ein linkes Kind ist, so ergibt sich die neue Position im Elternknoten <math>i_0</math> aus der Position der i-ten <math>0</math> im zugehörigen Bitvektor. Ist das Kind ein rechter Nachfolger, so ergibt sich die neue Position <math>i_1</math> aus der Position der i-ten <math>1</math>. Diese Selekt-Operation auf einem Bitvektor<ref name="Clark96"/><ref name="Munro96" /> kann in konstanter Zeit mit zusätzlichen <math>n+o(n)</math> ausgeführt werden.

	== Kompression ==		== Kompression ==

CountCountBot: Bot: Ersetze obsolete URL zu www.springerlink.com durch durch URL zu link.springer.com (siehe Botanfrage)

2020-07-24T13:51:36Z

Bot: Ersetze obsolete URL zu www.springerlink.com durch durch URL zu link.springer.com (siehe Botanfrage)

← Nächstältere Version		Version vom 24. Juli 2020, 15:51 Uhr
Zeile 93:		Zeile 93:

	<ref name="GAGR07">		<ref name="GAGR07">
	A. Golynski, R. Grossi, A. Gupta, R. Raman, [~~http~~://~~www~~.~~springerlink~~.com/~~content/8j2xk76439461r06~~/ On the Size of Succinct Indices], ''Springer Heidelberg'', 2007, Pages 371-382		A. Golynski, R. Grossi, A. Gupta, R. Raman, [https://link.springer.com/chapter/10.1007%2F978-3-540-75520-3_34 On the Size of Succinct Indices], ''Springer Heidelberg'', 2007, Pages 371-382
	</ref>		</ref>

Girus: lf

2018-08-30T06:01:00Z

← Nächstältere Version		Version vom 30. August 2018, 08:01 Uhr
Zeile 1:		Zeile 1:
	[[~~File~~:Wavelet tree.png\|~~frame~~\|Ein Wavelet Tree aus der Zeichenfolge "abracadabra". Jeder Knoten unterteilt die Zeichenfolge abhängig vom Alphabet in zwei Teile. Ein Bitvektor ordnet jedes Zeichen aus der Folge seinem Bereich zu. Dabei ist zu beachten, dass die Datenstruktur nicht den Baum, sondern nur die Topologie und die Bitvektoren speichert. Die Zeichenfolgen in den Knoten dienen ausschließlich der Illustration. ]]		[[Datei:Wavelet tree.png\|mini\|Ein Wavelet Tree aus der Zeichenfolge "abracadabra". Jeder Knoten unterteilt die Zeichenfolge abhängig vom Alphabet in zwei Teile. Ein Bitvektor ordnet jedes Zeichen aus der Folge seinem Bereich zu. Dabei ist zu beachten, dass die Datenstruktur nicht den Baum, sondern nur die Topologie und die Bitvektoren speichert. Die Zeichenfolgen in den Knoten dienen ausschließlich der Illustration. ]]

	In der Informatik versteht man unter einem '''Wavelet Tree''' eine kompakte Datenstruktur, um Zeichenfolgen komprimiert abzuspeichern. Er erweitert die Methoden <math>\mathbf{access, rang_q}</math> und <math>\mathbf{select_q}</math> von einem [[Bitvektor]] auf ein beliebiges [[Alphabet (Informatik)\|Alphabet]].		In der Informatik versteht man unter einem '''Wavelet Tree''' eine kompakte Datenstruktur, um Zeichenfolgen komprimiert abzuspeichern. Er erweitert die Methoden <math>\mathbf{access, rang_q}</math> und <math>\mathbf{select_q}</math> von einem [[Bitvektor]] auf ein beliebiges [[Alphabet (Informatik)\|Alphabet]].
Zeile 21:		Zeile 21:

	== Operationen ==		== Operationen ==
	Der Wavelet Tree unterstützt die Operationen <math>\mathbf{access, rang_q}</math>, und <math>\mathbf{select}_q</math> in <math>O(\log \sigma)</math> Zeit, falls ein [[~~Balancierter Baum\|~~balancierter Baum]] konstruiert wurde.		Der Wavelet Tree unterstützt die Operationen <math>\mathbf{access, rang_q}</math>, und <math>\mathbf{select}_q</math> in <math>O(\log \sigma)</math> Zeit, falls ein [[balancierter Baum]] konstruiert wurde.

	=== Access ===		=== Access ===
	<math>access(i)</math>: Direktzugriff auf das i'te Element in der Zeichenfolge.		<math>access(i)</math>: Direktzugriff auf das i'te Element in der Zeichenfolge.

IvanP: Apostroph entfernt

2018-08-29T18:10:59Z

Apostroph entfernt

← Nächstältere Version		Version vom 29. August 2018, 20:10 Uhr
Zeile 32:		Zeile 32:
	<math>rang_q(i)</math>: Anzahl der Zeichen <math>q</math> bis zur Position i in der Zeichenfolge.		<math>rang_q(i)</math>: Anzahl der Zeichen <math>q</math> bis zur Position i in der Zeichenfolge.

	Die Bestimmung des Rangs erfolgt analog zur Access-Operation. Nach Ausführung des Access-Algorithmus' ergibt sich der Rang aus der Anzahl der Vorkommen von <math>B_{v_{Blatt}}[i]</math> bis zur Position i im Blattknoten.		Die Bestimmung des Rangs erfolgt analog zur Access-Operation. Nach Ausführung des Access-Algorithmus ergibt sich der Rang aus der Anzahl der Vorkommen von <math>B_{v_{Blatt}}[i]</math> bis zur Position i im Blattknoten.

	=== Select ===		=== Select ===

Luke081515Bot: Bot: Ein Weblink wurde korrigiert

2016-03-21T04:04:32Z

Bot: Ein Weblink wurde korrigiert

← Nächstältere Version		Version vom 21. März 2016, 06:04 Uhr
Zeile 66:		Zeile 66:
	</ref>		</ref>
	<ref name="CB88">		<ref name="CB88">
	B. Chazelle, [http://citeseerx.ist.psu.edu/viewdoc/download~~;jsessionid=2D434EF4D6F1D6ACB3BA56EB66281982~~?doi=10.1.1.133.9153&rep=rep1&type=pdf A functional approach to data structures and its use in multidimensional searching], ''SIAM Journal on Computing'', Volume 17, Issue 3, June 1988, Pages 427-462		B. Chazelle, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.9153&rep=rep1&type=pdf A functional approach to data structures and its use in multidimensional searching], ''SIAM Journal on Computing'', Volume 17, Issue 3, June 1988, Pages 427-462
	</ref>		</ref>
	<ref name="FGM09">		<ref name="FGM09">

Giftmischer: Auszeichnungsfehler korrigiert/ Umbruch

2015-10-15T13:42:28Z

Auszeichnungsfehler korrigiert/ Umbruch

← Nächstältere Version		Version vom 15. Oktober 2015, 15:42 Uhr
Zeile 85:		Zeile 85:

	<ref name="Navarro05">		<ref name="Navarro05">
	V.Mäkinen, G. Navarro, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.144.3754&rep=rep1&type=pdf Position-Restricted Substring Searching], ''Springer Heidelberg, Technische Fakultät		V.Mäkinen, G. Navarro, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.144.3754&rep=rep1&type=pdf Position-Restricted Substring Searching], ''Springer Heidelberg, Technische Fakultät Universität Bielefeld'', 2006, Pages 703-714
	Universität Bielefeld'', 2006, Pages 703-714
	</ref>		</ref>
	<ref name="Navarro07">		<ref name="Navarro07">

KLBot2: Bot: 1 Interwiki-Link(s) nach Wikidata (:d:Q2552862) migriert

2013-04-04T14:55:08Z

Bot: 1 Interwiki-Link(s) nach Wikidata (d:Q2552862) migriert

← Nächstältere Version		Version vom 4. April 2013, 16:55 Uhr
Zeile 112:		Zeile 112:

	[[Kategorie:Datenstruktur]]		[[Kategorie:Datenstruktur]]

	[[en:Wavelet Tree]]

Gooodguy: /* Access */

2013-03-14T15:18:17Z

Access

← Nächstältere Version		Version vom 14. März 2013, 17:18 Uhr
Zeile 25:		Zeile 25:
	<math>access(i)</math>: Direktzugriff auf das i'te Element in der Zeichenfolge.		<math>access(i)</math>: Direktzugriff auf das i'te Element in der Zeichenfolge.

	Um das Zeichen an der Position <math>S[i]</math> zu berechnen, wird der Bitvektor <math>B_v{_{root}}[i]</math> betrachtet. Falls der Wert an dieser Position <math>0</math> ist, so ist <math>S[i]\leq(\sigma + 1)/2</math> und wir führen das Vorgehen auf dem linken Kind-Knoten rekursiv weiter, andernfalls gilt <math>S[i]>(\sigma + 1)/2</math> und der Algorithmus bearbeitet das rechte Kind. Dazu muss die neue Position von <math>i</math> im Bitvektor <math>B_v{_{Kind}}[i]</math> ermittelt werden. Die neue Position <math>i_0</math> ist die Anzahl der Nullen im Vektor <math>B_v{_{root}}</math> bis zur Position i, falls <math>B_v{_{root}}[i] = 0</math> gilt. Wird rekursiv das rechte Kind bearbeitet, so müssen die Vorkommen der ~~Eines~~ aufsummiert werden. Dazu dient die Funktion <math>rang_0(B,i)</math> respektive <math>rang_1(B,i)</math> auf einem Bitvektor.		Um das Zeichen an der Position <math>S[i]</math> zu berechnen, wird der Bitvektor <math>B_v{_{root}}[i]</math> betrachtet. Falls der Wert an dieser Position <math>0</math> ist, so ist <math>S[i]\leq(\sigma + 1)/2</math> und wir führen das Vorgehen auf dem linken Kind-Knoten rekursiv weiter, andernfalls gilt <math>S[i]>(\sigma + 1)/2</math> und der Algorithmus bearbeitet das rechte Kind. Dazu muss die neue Position von <math>i</math> im Bitvektor <math>B_v{_{Kind}}[i]</math> ermittelt werden. Die neue Position <math>i_0</math> ist die Anzahl der Nullen im Vektor <math>B_v{_{root}}</math> bis zur Position i, falls <math>B_v{_{root}}[i] = 0</math> gilt. Wird rekursiv das rechte Kind bearbeitet, so müssen die Vorkommen der Einsen aufsummiert werden. Dazu dient die Funktion <math>rang_0(B,i)</math> respektive <math>rang_1(B,i)</math> auf einem Bitvektor.

	Die Rang-Funktion auf Bitvektoren kann in konstanter Zeit<ref name="Jacobson89"/> mithilfe von zusätzlichen <math>n+o(n)</math> Bits ausgewertet werden.		Die Rang-Funktion auf Bitvektoren kann in konstanter Zeit<ref name="Jacobson89"/> mithilfe von zusätzlichen <math>n+o(n)</math> Bits ausgewertet werden.

Gooodguy am 14. März 2013 um 14:35 Uhr

2013-03-14T14:35:07Z

← Nächstältere Version		Version vom 14. März 2013, 16:35 Uhr
Zeile 1:		Zeile 1:
	[[File:Wavelet tree.png\|frame\|Ein Wavelet Tree aus der Zeichenfolge "abracadabra". Jeder Knoten unterteilt die Zeichenfolge abhängig vom Alphabet in zwei Teile. Ein ~~Bitkevotor~~ ordnet jedes Zeichen aus der Folge seinem Bereich zu. Dabei ist zu beachten, dass die Datenstruktur nicht den Baum, sondern nur die Topologie und die Bitvektoren speichert. Die Zeichenfolgen in den Knoten dienen ausschließlich der Illustration. ]]		[[File:Wavelet tree.png\|frame\|Ein Wavelet Tree aus der Zeichenfolge "abracadabra". Jeder Knoten unterteilt die Zeichenfolge abhängig vom Alphabet in zwei Teile. Ein Bitvektor ordnet jedes Zeichen aus der Folge seinem Bereich zu. Dabei ist zu beachten, dass die Datenstruktur nicht den Baum, sondern nur die Topologie und die Bitvektoren speichert. Die Zeichenfolgen in den Knoten dienen ausschließlich der Illustration. ]]

	In der Informatik versteht man unter einem '''Wavelet Tree''' eine kompakte Datenstruktur, um Zeichenfolgen komprimiert abzuspeichern. Er erweitert die Methoden <math>\mathbf{access, rang_q}</math> und <math>\mathbf{select_q}</math> von einem [[Bitvektor]] auf ein beliebiges [[Alphabet (Informatik)\|Alphabet]].		In der Informatik versteht man unter einem '''Wavelet Tree''' eine kompakte Datenstruktur, um Zeichenfolgen komprimiert abzuspeichern. Er erweitert die Methoden <math>\mathbf{access, rang_q}</math> und <math>\mathbf{select_q}</math> von einem [[Bitvektor]] auf ein beliebiges [[Alphabet (Informatik)\|Alphabet]].