Positionen im String binär codiert

[diggaa1984]

hiho,

mir fiel die Wahl des Titels absolut nich leicht, weil wie soll man das denn umschreiben

Daher schieb ich auch ein wenig Code rein, der eventuell mein Vorgehen verdeutlicht:

private void searchForUnknownSubstring(String s) throws UnknownSubstringParseException {
	
		int indexCode = 0;		
		boolean derivFound;		
		
		//check each column
		for(int col=0; col < s.length(); col++) {
			derivFound = false;
			//for each character in string, set one bit to 1
			indexCode |= (1 << col);
			System.out.print("\n" + indexCode);

			for(int row=0; row <= col; row++) {
				if (matrix.get(col).get(row).size() > 0)
					derivFound = true;
				
				if (derivFound) {
					//set according bits to zero if derivation was found
					indexCode ^= (1 << row);
					System.out.print(" : " + indexCode);
				}
			}//for			
		}//for

//<Auswertung von indexCode>
}

/* Beispiel-Matrix
 *
 * A X ( f )  <-- String s auf dessen Basis die Matrix erstellt wird
 * 0 1 0 0 0
 * - 0 0 0 0
 * - - 1 0 0
 * - - - 1 0
 * - - - - 1
 */

So das wäre ein Bsp um das Vorgehen vom Algorithmus nachzuvollziehen.
Der Algorithmus setzt für jedes Zeichen im String 1 bit in dem Integer. Bei A würde das 0. Zeichen im String dem 1. Bit (lowest) im Integer indexCode entsprechen, das bedeutet durch die Bit-Oparationen ändere ich indexCode zu 1. Beim 2. Zeichen würde ich das 2. Bit ändern und indexCode wird dementsprechend zu 3.

So nun prüfe ich weiterhin quasi die Einsen in der Matrix (es handelt sich dabei um Listen von Strings, wir betrachten die 1 hier einfach mal als Mächtigkeit der Liste, also deren Anzahl an Elementen). Wenn eine nicht-leere Liste gefunden wird, so setze ich alle entsprechenden Bits in indexCode wieder auf 0. In dem Beispel wäre also indexCode = 3 und ich würde nun in die 2. for-schleife kommen und merken, ah bei row = 0 hab ich eine nicht-leere Liste, also setze ich die entsprechenden Bits wieder auf 0. Weiterhin werden alle folgenden Bits (bis die for-schleife mit row aufhört) ebenfalls auf 0, denn wie in dem Bsp oben, bedeutet der Eintrag an Stelle 0,2 (also die 1 bei X), dass das Zeichen davor mit zum erkannten Teilstring gehört, welcher abgeleitet werden kann, also muss auch dieses Bit gelöscht werden.

So .. lange Reder kurzer Sinn, hier mal eine Ausgabe zum oben genutzten String:

1 - A wird nicht erkannt
3 : 2 : 0 - AX wird erkannt
4 : 0 - ( wird erkannt
8 : 0 - f wird erkannt
16 : 0 - ) wird erkannt

nach jedem Doppelpunkt wurde ein Bit zurückgesetzt.
Wenn indexCode am Ende 0 entspricht, dann gibt es keine unbekannten Teilstrings in s.
So nun ist aber die Frage wie kann ich bspw. aus einer Zahl != 0 herausbekommen wo das 1. Bit 1 ist und wieviele darauffolgende ebenfalls noch 1 gesetzt sind. Das wäre dann ein kompletter Teilstring der nicht erkannt werden kann, also fehlerhaft ist. In dem Fall gibt es eine Nachricht für den Nutzer, mit entsprechendem Teilstring aus s. Und damit ich diesen identifizieren kann, kann ich die Bitpositionen mit 1 in indexCode nutzen.

Ändern wir das Bsp oben ab und schauen was die Ausgabe sagt:

AX(ff) --- ff wird nicht als gültig erkannt, folglich muss indexCode != 0 sein

1 - A wird nicht erkannt
3 : 2 : 0 - AX wird erkannt
4 : 0 - ( wird nicht erkannt
8 - f wird nicht erkannt
24 - ff bzw f wird nicht erkannt
56 : 24 - ) wird erkannt


( f f ) X A ... Veranschaulichung von indexCode
0 1 1 0 0 0 = 24

Wie kann ich nun aus der 24 möglichst simpel herausbekommen, dass es sich um das 4. und 5. bit handet ^^ .. das entspräche dann s.substring(3,5);

Bzw: wenn indexCode = 38 ist (zB: 0100110) wie kann ich da das 2. und 3. bit (6) als zusammenhängend erkennen, das würde ja reichen, oder ich kann auch nur das 1 bit vorne nehmen (32) ist egal, ist ja beides fehlerhaft . Wichtig ist eben ohne grossen Aufwand ne Folge von Einsen zu erkennen

Vielen Dank fürs geduldige Lesen

 

[Marco13]

KONTEXT???? :autsch:

Also, worum es da mit den Strings und indexCodes und substrings geht, habe ich nichtmal Ansatzweise nachvollziehen können... aber bezug nehmend auf den letzten Absatz...

Bzw: wenn indexCode = 38 ist (zB: 0100110) wie kann ich da das 2. und 3. bit (6) als zusammenhängend erkennen, das würde ja reichen, oder ich kann auch nur das 1 bit vorne nehmen (32) ist egal, ist ja beides fehlerhaft . Wichtig ist eben ohne grossen Aufwand ne Folge von Einsen zu erkennen

klingt es, erst, als wolltest du (die längsten?) Folgen von gesetzen Bits erkennen - aber mit der Aussage, dass "ja beides fehlerhaft" ist, kann ich da jetzt nichts anfangen... ???:L Wie du erkennst, dass ein bestimmtes Bit gesetzt ist, weißt du wahrscheinlich - aber im Moment ist das IMHO die einzige Antwort, die man darauf geben kann:

Mit
if ((n & (1<<i)) != 0) { ... }
kann man testen, ob das i-te bit in n gesetzt ist.

(Sag' jetzt bitte nicht, dass das deine Frage schon beantwortet )

 

[diggaa1984]

KONTEXT???? :autsch:

Also, worum es da mit den Strings und indexCodes und substrings geht, habe ich nichtmal Ansatzweise nachvollziehen können... aber bezug nehmend auf den letzten Absatz...

hm verdammt, hab doch eigentlich alles erzählt was zum Algorithmus gehört ^^, ja gut is schon n bissel rumgewurschtel dabei, kann ich gut verstehen.

klingt es, erst, als wolltest du (die längsten?) Folgen von gesetzen Bits erkennen

korrekt ... es muss nicht die längste in der ganzen Binärdarstellung sein, aber es sollte schon eine komplette Folge von Einsen sein, sprich wenn 4 in Folge auftauchen, auch 4 als solche erkennen, und nicht nur 3

aber mit der Aussage, dass "ja beides fehlerhaft" ist, kann ich da jetzt nichts anfangen... ???:L

Ja das bezog sich darauf, dass es egal ist, welche Folge von Einsen ich aus der binären Darstellung rausfische, denn sie stellen beide Fehler in dem zugrundegelegten String s dar, die der Nutzer beheben muss. Wenn der nutzer das behoben hat, wird automatisch wieder der String kontrolliert (geparsed) und ich komme erneut während des parsens in die oben angegebene Methode hinein, sodass spät. dann die andere Folge von Einsen dem Nutzer Aufschluss über den restlichen fehlerhaften Teilstring gibt. Also es reicht eine von x Folgen zu erkennen.

Wie du erkennst, dass ein bestimmtes Bit gesetzt ist, weißt du wahrscheinlich - aber im Moment ist das IMHO die einzige Antwort, die man darauf geben kann:

Mit
if ((n & (1<<i)) != 0) { ... }
kann man testen, ob das i-te bit in n gesetzt ist.

(Sag' jetzt bitte nicht, dass das deine Frage schon beantwortet )

aeh ja gut, das ist ja die Suche nach der Folge .. ich dachte eben, dass man diese Suche elegant umgehen kann

Aber nett, dass du versucht hast zu verstehen was ich eigentlich mache :toll:

 

[Marco13]

Naja, überprüfen OB ein Bit in der Zahl gesetzt ist, reduziert sich ja auf ein
if (n != 0)

Danach noch rausfinden welche Bits gesetzt sind, geht vmtl. nur mit einer Schleife vernünftig... man könnte zwar schauen, ob's da irgendwelche Bit Twiddling Hacks gibt, aber so spontan wüßte ich nicht, wie man sowas bei diesem Problem vernünftig einsetzen sollte.... :bahnhof:

 

[diggaa1984]

habs nun s gelöst, falls es wen interessiert .. liest sich zumindest gut als code ^^

/*Use binary representation of indexCode to get marked positions of unknown substrings
  for example: 110010 => the 2nd, 5th, 6th string-characters are faulty =>
  lookup for first zero that indicates the first valid character closest to the end of the 
  string, thus s.substring(binary.length()-tempIndex,binary.length()) is faulty.
  The binary string will start with zero if and only if it represents 0. */
if (indexCode > 0) {
	String binary = Integer.toBinaryString(indexCode);
	int tempIndex = binary.indexOf('0');		
			
	throw new UnknownSubstringParseException("\"" + 
			s.substring(binary.length()-tempIndex,binary.length()) + "\" kann nicht " +
			"zugeordnet werden.",binary.length()-tempIndex, binary.length());
}//while

fällt mir grad auf, das ding funktioniert nicht wenn das aller erste zeichen als einziges falsch ist, dann ist indexCode = "1" in der binärdarstellung und da gibts gar kein indexOf("0") ... wie ich sone sonderfälle liebe ^^