Bergmann89 - Mi 25.05.16 18:52
Titel: Kürzung einer Menge von Codewörtern

---

Hey Leute,

ich hab zur Zeit ein Problem für das mir keine richtige Lösung einfällt:

Ich habe eine Menge (M) von Codewörter mit den Zeichen [0,1,2] die alle die Länge (l) haben. Und ich suche eine Teilmenge (N) von (M) bei der alle Codeworte einen Hamming-Abstand von mindestens (x) haben. Die Menge (N) sollte möglichst klein sein, muss aber nicht das absolute Minimum sein.
Zur Zeit hab ich es so gelöst, das ich jedes Wort in einem Baum eintrage und beim Eintragen von neuen Wörtern gleichzeitig den Hamming-Abstand berechne und überprüfe. Ich prüfe also jedes neue Wort gegen alle vorhandenen Wörter und füge das neue nur ein wenn der Hamming-Abstand passt. Das bringt aber weder eine möglichst kleine Menge (N) noch ist es sonderlich schnell. Ich hatte überlegt ob man da nich was aus der Graphen-Theorie nehmen könnte. Mein Studium ist aber jetzt auch schon paar Jahre her und ich bin nicht mehr wirklich fit was Graphen angeht. Könnte mir vlt jmd die Richtung zu ner halbwegs passablen Lösung weißen? :)

MfG & Thx Bergmann.

Ralf Jansen - Mi 25.05.16 19:49

---

Verständnisfrage zu dem was du gerade hast (möglicherweise nur um rauszufinden das das nichts mit dem zu tun hat was du tatsächlich brauchst und deine Erklärung hier bei der Lösungssuche ignoriert werden sollte ;) )
Hamming Abstand zu was? Zu jedem anderen Wort der auch im Baum ist? Dann meinst du also nicht Abstand sondern Abstände? Was ist dann die Grundlage des Baums (wie ist die Wurzel definiert)? Sind nicht alle Worte gleich gewichtet und müssen deshalb woanders in den Baum? Oder meinst du tatsächlich nicht Baum sondern ein Netz wo Wörter mit Wörtern mit Hammingabstand 1 untereinander eine Kante definieren?

Bergmann89 - Mi 25.05.16 20:01

---

Der Hamming-Abstand eines Wortes in der Menge soll >= x zu allen anderen Worten in der Menge sein.
Den Baum hab ich nur als Optimierung. Hatte erst eine Liste. Im Baum ist jedes Blatt ein Zeichen im Wort. Also eigentlich nur für ne Art binäre Suche in den schon bekannten Wörtern.

Ralf Jansen - Mi 25.05.16 21:25

---

Ok. Nächste Frage. Bei deiner Fragestellung an den Konstrukt ist die Variable N eher fix oder die Variable x?

Also fragst du gib mir mindestens 10 Codewörter aus der Gesamtmenge mit dem dafür maximal möglichen Hamming Abstand untereinander.
Oder fragst du eher gib mir eine möglichst große/kleine Menge von Codewörtern mit mindestens Haming Abstand 10 untereinander?

Edit: Und das Mengengerüst wäre interessant. Also übliche Größen für die Anzahl Codewörter, deren Länge und der Ziel Hamming Abstand.

Bergmann89 - Do 26.05.16 18:27

---

Hey,

ich suche eine möglichst kleine Menge mit einem Mindest-Hamming-Abstand von x. Also ist x fix und N möglichst klein.

Es geht um 100.000-200.000 Wörter mit einer Länge von 13 (manchmal auch mehr, bis zu 16). Der Hamming-Abstand ist im Normalfall 3 bis 5 und ich suche nach einem Algorithmus, der in 2-3 Sekunden so wenig wie möglich Wörter findet. Das sollten dann so um die 4000-5000 Wörter sein.

OT: Happy Birthday Ralf :)

MfG Bergmann.