Suchalgorithmus (Boyer-Moore-Horspool-Raita)

[Guest]

Hallo,
ich möchte eine Textsuche ein wenig schneller machen und versuche, die nicht von mir geschriebene Implementiereung des BMHR-Algorithmus dazu zu bringen, mir alle Trefferpositionen anzugeben.

Die Methode searchString liefert nur die Position des ersten Treffers oder -1, wenn es keinen Treffer gibt;

	private void searchTextNew(String pattern) {
		String text = g.getSelectedTab().getText();
		StringSearch ss = new BoyerMooreHorspoolRaita();
		patternLength = pattern.length();
		int textLength = text.length();
		int j = 0;

		while (true) {
			int i = ss.searchString(text, pattern);
			if (patternLength > text.length() || i == -1) {
				break;
			}
			matches.add(i);
			if (i + j > text.length()) {
				break;
			}
			text = text.substring(i + 1 + j);
			j = textLength - text.length();
		}

		for (int l : matches) {
			System.out.println(l);
		}

	}

Leider befinde ich mich da in einer Endlosschleife.

 

[SlaterB]

ist das eine Mitteilung oder eine Frage?
sind StringSearch und BoyerMooreHorspoolRaita Klassen die man kennen muss, oder tun die nicht zur Sache?

schreibe doch Ausgaben rein a la
System.out.println("neue while Runde");
System.out.println("i= "..);
System.out.println("text= "..);
System.out.println("j= "..);

gib ein Beispiel an und sage was passieren soll,
und teste was das Programm stattdessen macht

 

[Murray]

Muss es nicht heissen:

if (i + j >= text.length()) { //--- größer-gleich statt größer
  break;
}

Und die Abfrage

patternLength > text.length()

könnte auch vor die Suche direkt an den Anfag des Schleifenkörpers.

 

[Guest]

Ich habe noch mal ein paar Änderungen durchgeführt. Sie Ergebnisse sehen auch gut aus, bis

Fund bei Pos. -1
-641004 > 53872?
Exception in thread "AWT-EventQueue-0" java.lang.StringIndexOutOfBoundsException: String index out of range: -641004

irgendwann kommt.

private void searchText(String pattern) {

		if (g.getSelectedTab() == null) {
			return;
		}

		String text = g.getSelectedTab().getText();
		patternLength = pattern.length();
		matchNr = 0;

		for (int i = 0; i < text.length(); i++) {
			if (text.substring(i).length() < pattern.length()) {
				break;
			}

			if (text.substring(i, i + patternLength).equalsIgnoreCase(pattern)) {
				matches.add(i);
			}

		}
	}

 

[Guest]

Hoppla, das war die alte Version...

 

[Gast]

Hier die aktuelle:

	private void searchTextNew(String pattern) {
		String text = g.getSelectedTab().getText();
		StringSearch ss = new BoyerMooreHorspoolRaita();
		patternLength = pattern.length();
		int textLength = text.length();
		matchNr = 0;

		while (true) {
			int i = ss.searchString(text, pattern);
			if (patternLength > text.length() || i == -1) {
				System.out.println("Fertig");
				break;
			}
			System.out.println("textLength = " + textLength);
			System.out.println("text.length() = " + text.length());
			System.out.println("Fund bei Pos. " + (textLength - text.length() + i));
			matches.add(textLength - text.length() + i);
			System.out.println(i + 1 + " > " + text.length() + "?");
			if (i + 1 > text.length()) {
				break;
			}
			text = text.substring(i + 1);
			System.out.println("Textlänge: " + text.length());
			System.out.println("----------------------");
		}

		for (int l : matches) {
			System.out.println(l);
		}

	}

 

[SlaterB]

was ist i an dieser Stelle? -600.000irgendwas?
ist das ein erlaubter Wert?..
der kommt ja wohl aus der unbekannten Operation ss.searchString()

 

[Gast]

i ist die position, an der ein Treffer gefunden wurde. Also eigentlich immer >=0 oder -1.

 

[SlaterB]

toll und was erwarstet du nun?

System.out.println("i= " + i);

 

[Murray]

Ich habe noch mal ein paar Änderungen durchgeführt. Sie Ergebnisse sehen auch gut aus, bis

Fund bei Pos. -1
-641004 > 53872?
Exception in thread "AWT-EventQueue-0" java.lang.StringIndexOutOfBoundsException: String index out of range: -641004

Wenn die Ausschreibungen zum zuletzt geposteten Code passen, dann war i hier wohl -641005 und damit außerhalb des erwarteten Bereichs.