Datensatz filtern/kürzen

Bergmann89 · Verfasst: Mi 20.03.13 20:05

Hey,

ich hab einen relativ Großen Datensatz. Dieser enthält bis zu 1mio Einträge. Ein Eintrag besteht aus n*z Zeichen, wobei z € [0, 1, 2]. Die Anzahl (n) der Zeichen jedes Eintrags ist gleich und wird vorm Erzeugen der Daten vom Nutzer festgelegt. Nun möchte ich diesen Datensatz auf ein Minimum zusammen kürzen, sodass jeder Eintrag mindestens x Zeichen Unterschied zu allen anderen Einträgen hat hat. x kann dabei auch vom Nutzer bestimmt werden. Zur Zeit füge ich die Einträge der Reihe nach in einen Suchbaum ein, wenn der Eintrag die Bedingung erfüllt. Aber das liefert leider nicht die minimale Lösung

Hier mal n Bsp. wie die Daten aussehen:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

n = 5; x = 2;
1 1 1 1 1
0 0 1 1 1
2 2 1 1 1
0 1 0 1 1
1 0 0 1 1
2 1 2 1 1
1 2 2 1 1
0 1 1 0 1
1 0 1 0 1
1 1 0 0 1

n = 6; x = 5;
1 1 1 1 1 1 1
0 0 0 0 0 1 1
2 2 2 2 2 1 1
2 0 0 1 1 0 0
1 2 1 0 0 0 0
0 1 2 0 1 2 0
0 1 1 2 2 0 2
1 2 0 2 1 2 2

Im Normalfall ist n = 13 und x = 2. Das ergibt 3^13 = 1.594.323 Einträge im Datensatz. Die laufen dann noch durch verschiedene Filter, das am Ende ca. 1mio Einträge übrig bleiben, die dann noch auf die Unterschiede gebrüft bzw. minimiert werden müssen. Hat jmd ne Ahnung wie ich das gewünschte Ergebnis mit ner vertretbaren Laufzeit ermitteln kann?

MfG & Thx Bergmann.

_________________
Ich weiß nicht viel, lern aber dafür umso schneller^^

jfheins · Beiträge: 918 Erhaltene Danke: 158 Win 10 VS 2013, VS2015

Dein Problem hängt mit der Hamming-Distanz zusammen. In diesem Sinne kann dein Problem umformuliert werden zu:

Zitat:

Ich möchte alle Codewörter der Länge n mit einer Hamming-Distanz von x.

Eine Frage, auf die es leider - soweit ich das überblicke - keine schnelle Antwort gibt. (Durchiterieren und ggf. verwerfen hast du ja schon) Du kannst so Pi*Daumen abschätzen, dass es bei einer Blocklänge von n und einem Hamming-Abstand von x maximal 3^(n-x+1) Nachrichten (= verschiedene Codewörter) gibt. ( de.wikipedia.org/wiki/Singleton-Schranke )

Also für dein Beispiel n = 5; x = 2; kann es nach der Formel maximal 81 Codewörter geben. Für dein zweites Beispiel maximal 9.
Beim ersten ist das wohl nicht sonderlich hilfreich, es ist wie gesagt eine obere Schranke ;-)

Die beliebige Generierung eines passenden Codes nach den Parametern Distanz und Gesamtlänge scheint kein einfaches Unterfangen zu sein. Aber vielleicht kannst du aus dem Gebiet ein paar Ansätze mitnehmen:
de.wikipedia.org/wiki/Hamming-Abstand
de.wikipedia.org/wiki/Reed-Solomon-Code
Das meiste Zeug ist leider auf binäre Code zugeschnitten, aber hier ist noch ein toller:
en.wikipedia.org/wiki/Ternary_Golay_code
Immerhin mal ternär, geht aber eher in die Richtung "Voll cool dass wir da mal einen entdeckt haben der gut ist." und weniger "Wir können beliebige Codes nach Anforderung generieren"

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme