Angenommen, ich habe eine Liste von Zeichenfolgen, bei denen jede Zeichenfolge @ is

genau 4 Zeichen lang und einzigartig in der Liste.

Für jede dieser Zeichenfolgen möchte ich die Position der Zeichen in der Zeichenfolge identifizieren, die die Zeichenfolge eindeutig machen.

So für eine Liste von drei Zeichenfolgen

abcd
abcc
bbcb

Für die erste Zeichenfolge möchte ich das Zeichen an 4. Stelle identifizierend schon seitd steht in keinem anderen String an vierter Stelle.

Für die zweite Zeichenfolge möchte ich das Zeichen an 4. Stelle identifizierenc.

Für die dritte Zeichenfolge möchte ich das Zeichen an der ersten Position identifizierenb UND das Zeichen an vierter Stelle, auchb.

Dies könnte prägnant dargestellt werden als

abcd -> ...d
abcc -> ...c
bbcb -> b..b

Wenn Sie das gleiche Problem betrachten, aber mit einer Liste von Binärzahlen

0101
0011
1111

Dann wäre das gewünschte Ergebnis

0101 -> ..0.
0011 -> .0..
1111 -> 1...

it dem binären Thema kann ich XOR verwenden, um zu identifizieren, welche Bits innerhalb von @ eindeutig sinzwe Binärzahlen seit

0101 ^ 0011 = 0110

was ich so interpretieren kann, dass in diesem Fall das 2. und 3. Bit (Lesen von links nach rechts) zwischen diesen beiden Binärzahlen eindeutig sind. Diese Technik könnte ein roter Hering sein, es sei denn, sie kann irgendwie auf die größere Liste ausgedehnt werden.

Ein Brute-Force-Ansatz besteht darin, jede Zeichenfolge nacheinander zu betrachten und den Rest der Zeichenfolgen in der Liste durch vertikale Segmente zu iterieren.

So für die Liste

abcd
abcc
bbcb

Ich würde mit @ beginn

abcd

und iterieren durch vertikale Scheiben von

abcc
bbcb

wo diese vertikalen Scheiben wären

a | b | c | c
b | b | c | b

oder in Listenform "ab", "bb", "cc", "cb".

Dies würde zu vier Vergleichen führen

a : ab -> . (a is not unique)
b : bb -> . (b is not unique)
c : cc -> . (c is not unique)
d : cb -> d (d is unique)

oder prägnant

abcd -> ...d

Möglicherweise ist es Wunschdenken, aber ich habe das Gefühl, dass es eine elegante und allgemeine Lösung geben sollte, die für eine beliebig große Liste von Zeichenfolgen (oder Binärzahlen) gilt. Aber wenn ja, konnte ich es noch nicht sehen.

Ich hoffe, mit diesem Algorithmus minimale Signaturen aus einer Sammlung eindeutiger Bilder (Bitmaps) ableiten zu können, um diese Bilder zu einem späteren Zeitpunkt effizient identifizieren zu können. Wenn die Zukunftseffizienz keine Rolle spielen würde, würde ich von jedem Bild einen einfachen Hash verwenden.

Kannst du Brute Force verbessern?

Bearbeite Der Ansatz, auf den ich mich einlasse, ist das Erstellen einer Pixelkarte für Bilder

sprawl[Tuple<x=10, y=33,color=f1fefd>] => {
     image17,
     image23,
     ...
}

sprawl[Tuple<x=10, y=34,color=f1fef0>] => {
     image11
     ...
}

und verwenden Sie dann diese Karte, um den minimalen Satz von Signaturpixeln für jedes Bild zu identifizieren.

Wenn ein Pixel (gekennzeichnet durch x, y, Farbe) nur ein Bild referenziert, habe ich eine perfekte (minimale) Signatur für dieses Bild gefunden.

Es ist komplizierter, wenn ein Bild keine eindeutigen Pixel enthält. Da jedoch bekannt ist, dass alle Bilder in der Liste eindeutig sind, sollte es mir möglich sein, zwei oder mehr Pixelreferenzen (aber so wenig wie möglich) zu kombinieren, um das Bild abzuleiten.

Aktualisiere

Ich habe an einem Algorithmus dafür gearbeitet. Mein Problem ist sehr ähnlich zudiese, und ich habe meinen Algorithmus als @ geschrieb Antwort auf diese Frage. Dieses Update soll die Aufmerksamkeit von Personen auf sich ziehen, die noch folgen (ich sehe fünf Lesezeichen). Ich arbeite isoliert daran, daher sind alle Rückmeldungen willkommen, auch wenn ich nur feststelle, dass ich mich nicht klar ausgedrückt habe!