Um den Algorithmus und die Java-Grammatik zu studieren, haben wir die Boyer-Moore-Methode implementiert, die einer der String-Suchalgorithmen ist! !!

Was ist die Boyer-Moore-Methode?

Boyer Moore Act (1976) Vorgeschlagen von R.S.Boyer und J.S.Moore Schnellerer Algorithmus als einfacher Suchalgorithmus Ändern Sie die zu verschiebende Position abhängig vom Vergleichsergebnis der Zeichen Der Zeitberechnungsbetrag ist geringer als der einfache Suchalgorithmus

Es gibt verschiedene andere Zeichenfolgensuchalgorithmen wie die einfache Suchmethode und die Rabincarp-Methode.

Tabelle überspringen

Erstellen Sie vor der Suche eine Sprungtabelle.

Suchmuster: ighi

Wenn ja

Muster	i	g	h	i
Schichtbreite	3	2	1	0

Wenn jedoch doppelte Zeichenfolgen vorhanden sind, hat die kleinere Priorität.

Deshalb,

Muster	g	h	i	Standard
Schichtbreite	2	1	0	4

Es wird sein.

Die Standardeinstellung ist, um zu dem Punkt zu springen, an dem sich Zeichenvergleiche nicht überschneiden. Dies ist der Wert, wenn das Muster als natürliche Zahl gezählt wird.

Suchbeispiel

Erstes Mal

Suchziel	a	b	c	d	e	f	g	i	g	h	i
Muster	i	g	h	i

Die Suche beginnt am Anfang und vergleicht das Suchziel mit dem Ende des Musters. Da die zu durchsuchende Zeichenfolge und das Ende des Suchziels "d" und "i" sind, überspringen Sie standardmäßig "4".

Zweites Mal

Suchziel	a	b	c	d	e	i	g	i	g	h	i
Muster					i	g	h	i

Bei "i" und "i" ist die Tabelle "Überspringen" "0". Vergleichen Sie also die benachbarten Zeichen. Sie sind unterschiedlich, weil sie "g" und "h" sind. Wenn Sie sich die Tabelle "Überspringen" ansehen, ist "Überspringen" "1". Überspringe nur einen.

Drittes Mal

Suchziel	a	b	c	d	e	i	g	i	g	h	i
Muster						i	g	h	i

Bei "g" und "i" ist die Tabelle "Überspringen" "2". Überspringen Sie also zwei.

4 ..

Suchziel	a	b	c	d	e	i	g	i	g	h	i
Muster								i	g	h	i

Bei "i" und "i" ist die Tabelle "Überspringen" "0". Vergleichen Sie also die benachbarten Zeichenfolgen. Da "h" und "h" identisch sind, vergleichen Sie die benachbarten Zeichenketten. Da "g" und "g" identisch sind, vergleichen Sie die benachbarten Zeichenketten. Da "i" und "i" identisch sind, ist die Suche abgeschlossen.

Nachdem Sie ein Bild haben, möchte ich es von hier aus in Code implementieren.

Variablendefinition

`python`


public final static int bmTableSize = 1_114_111;
public final static String txt = "Aiue Oppao"; //Suchziel
public final static char[] txtChar = txt.toCharArray(); //In Char-Typ aufteilen
public final static String pattern = "Oppao"; //Muster
public final static char[] patternChar = pattern.toCharArray();

Es war etwas langweilig, nur ASCII durchsuchen zu können, daher möchte ich auch Japanisch unterstützen.

Betrachtet man den Java-Referenzzeichentyp,

Die Java SE API-Dokumentation verwendet Unicode-Codepunkte für Zeichenwerte im Bereich U + 0000-U + 10FFFF und Unicode-Codeeinheiten für 16-Bit-Zeichenwerte, die die Codeeinheiten für die UTF-16-Codierung sind. Weitere Informationen zu Unicode-Begriffen finden Sie im Unicode-Glossar.

Zeichensatz: Unicode Und Codierungsmethode: UTF-16 Sie können sehen, dass

Also habe ich 10FFFF in eine Dezimalzahl konvertiert und die Tabellengröße (bmTableSize) auf 1.114.111 gesetzt.

Tabelle erstellen

`BoyerMooreTableInit`


public static int[] BoyerMooreTableInit(int[] table, char[] patternChar, int ptnLen) {
        int count = 0;

        /*Verschieben Sie bei Zeichen, die nicht im Muster enthalten sind, die Länge der Musterzeichenfolge auf die Breite.*/・ ・ ・ ①
        for(count = 0; count < bmTableSize; count++){
            table[count] = ptnLen;
        }

        /*Bestimmen Sie die Verschiebungsbreite der im Muster enthaltenen Zeichen*/・ ・ ・ ②
        for(count = 0; count < ptnLen; count++){
            table[(int)patternChar[count]] = ptnLen - count - 1;
        }

        /*Debug-Ausgabe*/
        System.out.printf("[table]  : default: step=%d\n", ptnLen);
        for(count = 0; count < bmTableSize; count++){
            if(table[count] != ptnLen)
                System.out.printf("         : char=%c: table[%03d]: step=%d\n",
                                 (char)count,count,(int)table[count]);
        }
   return table;
}

Tabelle überspringen,

Muster	Oh	Tsu	Pa	Oh
Schichtbreite	3	2	1	0

Wenn es doppelte Zeichen gibt, wird dem kleineren Vorrang eingeräumt.

Muster	Tsu	Pa	Oh	Standard
Schichtbreite	2	1	0	4

Irgendwann wird es so sein.

In Bezug auf (1) wird in allen Tabellen die Standardeinstellung "4" eingefügt.

In Bezug auf ② ist table [(int) patternChar [count]] = ptnLen --count --1;

[O, pa, tsu, o] ist in patternChar [count] enthalten. Wenn Sie dies in den Typ int umwandeln, wird der von UTF-16 in Dezimalzahl konvertierte Wert zurückgegeben.

"Tsu" ... Tisch[12387] = 2
"Pa" ... Tisch[12401] = 1
"O" ... Tisch[12362] = 0
"Standard" ... Tabelle[Andere Orte als die oben genannten drei] = 4

Suche Implementierung

`BoyerMooreSearch`


public static int BoyerMooreSearch(char[] txtChar, char[] patternChar) {
        int table[] = new int[bmTableSize];
        int txtLen = 0;
        int ptnLen = 0;
        int i = 0; /*Textvergleichsposition*/
        int j = 0; /*Mustervergleichsposition*/

        txtLen = txtChar.length;
        ptnLen = patternChar.length;

        /*Erstellen Sie eine Schichttabelle*/
        table = BoyerMooreTableInit(table, patternChar, ptnLen);

        /*Vergleichsverarbeitung*/
        i = j = ptnLen - 1; /*Machen Sie die Vergleichsposition zum Ende des Musters*/
        while((i < txtLen) && (j >= 0)){
            PrintCompareProcess(txt, pattern, i, j);

            if(txtChar[i] != patternChar[j]){
                /*Beziehen Sie sich auf die Verschiebungstabelle und stellen Sie die nächste Vergleichsposition ein*/
                i += next_step(table, txtChar[i], (ptnLen - j));
                j = ptnLen - 1;   /*Machen Sie die Vergleichsposition zum Ende des Musters*/
            }else{
                /*Da die Zeichen übereinstimmen, werden die vorherigen Zeichen sortiert*/
                j--;
                i--;
            }
        }

        if(j < 0) {
            return i + 2;
        }else {
            return 0;
        }
    }
}

・ Erster Vergleich

Suchziel	Ah	ich	U.	e	Pa	Tsu	Oh	Tsu	Pa	Oh
Muster	Oh	Tsu	Pa	Oh

Da die Endungen "e" und "o" unterschiedlich sind und die Zeichenfolge im Muster nicht vorhanden ist, Überspringe 4 Zeichen.

・ Zweiter Vergleich

Suchziel	Ah	ich	U.	e	Pa	Tsu	Oh	Tsu	Pa	Oh
Muster					Oh	Tsu	Pa	Oh

Das Zeichen, das im Muster endet, ist "tsu" = 2, also Der zweistellige Satz wird übersprungen.

・ Dritter Vergleich

Suchziel	Ah	ich	U.	e	Pa	Tsu	Oh	Tsu	Pa	Oh
Muster							Oh	Tsu	Pa	Oh

Da das Ende das Zeichen ist, das im Muster existiert und "pa" = 1 ist, Ein Zeichensatz wird übersprungen.

・ Vierter Vergleich

Suchziel	Ah	ich	U.	e	Pa	Tsu	Oh	Tsu	Pa	Oh
Muster							Oh	Tsu	Pa	Oh

Da das Ende "O" = 0 ist, suchen Sie nach dem nächsten Zeichen.

・・・ Wiederholen Sie unten

Am Ende sieht es so aus.

Code

`Main.java`


import java.io.UnsupportedEncodingException;

public class Main {
	public final static int bmTableSize = 1_114_111;
	public final static String txt = "Aiue Pappa";
	public final static char[] txtChar = txt.toCharArray();
	public final static String pattern = "Oppao";
	public final static char[] patternChar = pattern.toCharArray();

	public static void main(String[] args) throws UnsupportedEncodingException {
		int result;

		System.out.printf("[text]   :%s\n", txt);
		System.out.printf("[pattern]:%s\n", pattern);

		result = BoyerMooreSearch(txtChar, patternChar);

		if (0 < result) {
			System.out.println(result + "Es war der zweite! !!");
		}else {
			System.out.println("Ich konnte es nicht finden");
		}

	}

	public static int[] BoyerMooreTableInit(int[] table, char[] patternChar, int ptnLen) {
		int count = 0;

	    /*Verschieben Sie bei Zeichen, die nicht im Muster enthalten sind, die Länge der Musterzeichenfolge auf die Breite.*/
	    for(count = 0; count < bmTableSize; count++){
	    	table[count] = ptnLen;
	    }

	    /*Bestimmen Sie die Verschiebungsbreite der im Muster enthaltenen Zeichen*/
	    for(count = 0; count < ptnLen; count++){
	    	table[(int)patternChar[count]] = ptnLen - count - 1;
	    }

	    /*Debug-Ausgabe*/
	    System.out.printf("[table]  : default: step=%d\n", ptnLen);
	    for(count = 0; count < bmTableSize; count++){
	        if(table[count] != ptnLen)
	        	System.out.printf("         : char=%c: table[%03d]: step=%d\n",
	        					 (char)count,count,(int)table[count]);
	    }

	    return table;
	}

	public static void PrintCompareProcess(String txt, String pattern, int i, int j) {
	    int count = 0;

	    System.out.printf("-----------------------------------\n");
	    System.out.printf("[compare]:(text i=%d)(pattern j=%d)\n", i+1, j+1);
	    System.out.printf(" text    :%s\n", txt);

	    /*Überlagerungsmuster an Vergleichspositionen*/
	    System.out.printf(" pattern :");
	    for(count = 0; count < (i - j); count++) System.out.print("　"); //Verschiebung in voller Breite und halber Breite.
	    System.out.printf("%s\n", pattern);

	    /*Markieren Sie den Vergleichspunkt*/
	    System.out.printf("         :");
	    for(count = 0; count < i; count++) System.out.printf("　");
	    System.out.printf("^\n");
	}

	public static int next_step(int[] table, char target, int remain) {
	    /*Überprüfen Sie, um Schleifen zu vermeiden*/
	    if(table[(int)target] > remain){
	        /*Holen Sie sich den Wert aus der Verschiebungstabelle*/
	        return(table[(int)target]);
	    }else{
	        /*Fahren Sie mit dem nächsten Zeichen des Punktes fort, an dem die Sortierung begonnen hat*/
	        return(remain);
	    }
	}

	public static int BoyerMooreSearch(char[] txtChar, char[] patternChar) {
		int table[] = new int[bmTableSize];
		int txtLen = 0;
		int ptnLen = 0;
		int i = 0; /*Textvergleichsposition*/
		int j = 0; /*Mustervergleichsposition*/

		txtLen = txtChar.length;
		ptnLen = patternChar.length;

	    /*Erstellen Sie eine Schichttabelle*/
		table = BoyerMooreTableInit(table, patternChar, ptnLen);

	    /*Vergleichsverarbeitung*/
	    i = j = ptnLen - 1; /*Machen Sie die Vergleichsposition zum Ende des Musters*/
	    while((i < txtLen) && (j >= 0)){
	    	PrintCompareProcess(txt, pattern, i, j);

	        if(txtChar[i] != patternChar[j]){
	            /*Beziehen Sie sich auf die Verschiebungstabelle und stellen Sie die nächste Vergleichsposition ein*/
	            i += next_step(table, txtChar[i], (ptnLen - j));
	            j = ptnLen - 1;   /*Machen Sie die Vergleichsposition zum Ende des Musters*/
	        }else{
	            /*Da die Zeichen übereinstimmen, werden die vorherigen Zeichen sortiert*/
	            j--;
	            i--;
	        }
	    }

	    if(j < 0) {
	    	return i + 2;
	    }else {
		    return 0;
	    }
	}
}

Ausgabeergebnis

[text]   :Aiue Pappa
[pattern]:Oppao
[table]  : default: step=4
         : char=Oh: table[12362]: step=0
         : char=Tsu: table[12387]: step=2
         : char=Pa: table[12401]: step=1
-----------------------------------
[compare]:(text i=4)(pattern j=4)
 text    :Aiue Pappa
 pattern :Oppao
         :　　　^
-----------------------------------
[compare]:(text i=8)(pattern j=4)
 text    :Aiue Pappa
 pattern :Oppao
         :　　　　　　　^
-----------------------------------
[compare]:(text i=10)(pattern j=4)
 text    :Aiue Pappa
 pattern :Oppao
         :　　　　　　　　　^
-----------------------------------
[compare]:(text i=9)(pattern j=3)
 text    :Aiue Pappa
 pattern :Oppao
         :　　　　　　　　^
-----------------------------------
[compare]:(text i=8)(pattern j=2)
 text    :Aiue Pappa
 pattern :Oppao
         :　　　　　　　^
-----------------------------------
[compare]:(text i=7)(pattern j=1)
 text    :Aiue Pappa
 pattern :Oppao
         :　　　　　　^
Es war der 7.! !!

Ich hoffe, Sie finden es hilfreich.

Verweise

Java Character Type Reference ・ [C-Sprachalgorithmus-BM-Methode](http://capm-network.com/?tag=C%E8%A8%80%E8%AA%9E%E3%82%A2%E3%83%AB%E3 % 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0-BM% E6% B3% 95)
Unicode-kompatible Zeichencodetabelle ・ [Java] char-Typ kann in int-Typ umgewandelt werden

Boyer-Moore-Implementierung in Java