Afin d'étudier les algorithmes et la grammaire Java, nous avons implémenté la méthode Boyer-Moore, qui est l'un des algorithmes de recherche de chaînes! !!

Qu'est-ce que la méthode Boyer-Moore?

Loi Boyer Moore (1976) Proposé par R.S.Boyer et J.S.Moore Algorithme plus rapide qu'un simple algorithme de recherche Changer la position à décaler en fonction du résultat de la comparaison des caractères Le temps de calcul est inférieur à celui de l'algorithme de recherche simple

Il existe divers autres algorithmes de recherche de chaînes de caractères tels que la méthode de recherche simple et la méthode Rabincarp.

Passer la table

Créez une table de sauts avant de rechercher.

Motif de recherche: ighi

Si c'est le cas

modèle	i	g	h	i
Largeur de décalage	3	2	1	0

Cependant, s'il y a des chaînes de caractères en double, la plus petite a la priorité.

Donc,

modèle	g	h	i	Défaut
Largeur de décalage	2	1	0	4

Ce sera.

La valeur par défaut est fournie pour passer au point où les comparaisons de caractères ne se chevauchent pas. Il s'agit de la valeur lorsque le motif est compté comme un nombre naturel.

Exemple de recherche

Première fois

Cible de recherche	a	b	c	d	e	f	g	i	g	h	i
modèle	i	g	h	i

La recherche commence au début et compare la cible de la recherche à la fin du modèle. Puisque la chaîne de caractères à rechercher et la fin de la cible de recherche sont "d" et "i", sautez par défaut "4".

Deuxième fois

Cible de recherche	a	b	c	d	e	i	g	i	g	h	i
modèle					i	g	h	i

Avec «i» et «i», la table de saut est «0», comparez donc les lettres adjacentes. Ils sont différents parce qu'ils sont "g" et "h". En regardant la table Skip, quand il est "g", Skip est "1". Ne sautez qu'un seul.

Troisième fois

Cible de recherche	a	b	c	d	e	i	g	i	g	h	i
modèle						i	g	h	i

Avec "g" et "i", la table Skip est "2", alors sautez deux.

4e

Cible de recherche	a	b	c	d	e	i	g	i	g	h	i
modèle								i	g	h	i

Avec "i" et "i", la table Skip est "0", comparez donc les chaînes adjacentes. Puisque «h» et «h» sont identiques, comparez les chaînes de caractères adjacentes. Puisque «g» et «g» sont identiques, comparez les chaînes de caractères adjacentes. Puisque «i» et «i» sont identiques, la recherche est terminée.

Maintenant que vous avez une image, je voudrais l'implémenter dans le code à partir d'ici.

Définition variable

`python`


public final static int bmTableSize = 1_114_111;
public final static String txt = "Aiue Oppao"; //Cible de recherche
public final static char[] txtChar = txt.toCharArray(); //Diviser en type de caractère
public final static String pattern = "Oppao"; //modèle
public final static char[] patternChar = pattern.toCharArray();

C'était un peu ennuyeux de pouvoir rechercher uniquement ASCII, donc j'aimerais également prendre en charge le japonais.

En regardant le type de caractère de référence Java,

La documentation de l'API Java SE utilise des points de code Unicode pour les valeurs de caractère dans la plage U + 0000-U + 10FFFF et des unités de code Unicode pour les valeurs de caractères 16 bits, qui sont les unités de code pour le codage UTF-16. Pour plus d'informations sur les termes Unicode, consultez le glossaire Unicode.

Jeu de caractères: Unicode '' Et Méthode d'encodage: UTF-16 '' Tu peux voir ça

J'ai donc converti 10FFFF en décimal et défini la taille de la table (bmTableSize) sur `` 1,114,111 ''.

Créer une table

`BoyerMooreTableInit`


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

        /*Pour les caractères qui ne figurent pas dans le modèle, décalez la longueur de la chaîne de caractères du modèle sur la largeur.*/・ ・ ・ ①
        for(count = 0; count < bmTableSize; count++){
            table[count] = ptnLen;
        }

        /*Déterminez la largeur de décalage des caractères inclus dans le motif*/・ ・ ・ ②
        for(count = 0; count < ptnLen; count++){
            table[(int)patternChar[count]] = ptnLen - count - 1;
        }

        /*Sortie de débogage*/
        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;
}

Passer la table,

modèle	Oh	Tsu	Pennsylvanie	Oh
Largeur de décalage	3	2	1	0

S'il y a des caractères en double, le plus petit aura la priorité.

modèle	Tsu	Pennsylvanie	Oh	Défaut
Largeur de décalage	2	1	0	4

Finalement, ce sera comme ça.

Concernant (1), le "4" par défaut est mis dans toutes les tables.

Concernant ②, table [(int) patternChar [count]] = ptnLen --count --1;

[O, pa, tsu, o] est inclus dans patternChar [count]. Si vous transtypez ceci en type int, la valeur convertie de UTF-16 en nombre décimal sera renvoyée.

"Tsu" ... table[12387] = 2
"Pa" ... table[12401] = 1
"O" ... table[12362] = 0
Tableau "Par défaut" ...[Lieux autres que les trois ci-dessus] = 4

Implémentation de la recherche

`BoyerMooreSearch`


public static int BoyerMooreSearch(char[] txtChar, char[] patternChar) {
        int table[] = new int[bmTableSize];
        int txtLen = 0;
        int ptnLen = 0;
        int i = 0; /*Position de comparaison de texte*/
        int j = 0; /*Position de comparaison de modèle*/

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

        /*Créer une table de travail*/
        table = BoyerMooreTableInit(table, patternChar, ptnLen);

        /*Traitement de comparaison*/
        i = j = ptnLen - 1; /*Faire de la position de comparaison la fin du motif*/
        while((i < txtLen) && (j >= 0)){
            PrintCompareProcess(txt, pattern, i, j);

            if(txtChar[i] != patternChar[j]){
                /*Reportez-vous au tableau des décalages et définissez la position de comparaison suivante*/
                i += next_step(table, txtChar[i], (ptnLen - j));
                j = ptnLen - 1;   /*Faire de la position de comparaison la fin du motif*/
            }else{
                /*Puisque les personnages correspondent, nous assemblerons les personnages précédents*/
                j--;
                i--;
            }
        }

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

・ Première comparaison

Cible de recherche	Ah	je	U	e	Pennsylvanie	Tsu	Oh	Tsu	Pennsylvanie	Oh
modèle	Oh	Tsu	Pennsylvanie	Oh

Comme les terminaisons «e» et «o» sont différentes et que la chaîne de caractères n'existe pas dans le modèle, Sautez 4 caractères.

・ Deuxième comparaison

Cible de recherche	Ah	je	U	e	Pennsylvanie	Tsu	Oh	Tsu	Pennsylvanie	Oh
modèle					Oh	Tsu	Pennsylvanie	Oh

Le caractère qui se termine par le motif est "tsu" = 2, donc La phrase à deux caractères est ignorée.

・ Troisième comparaison

Cible de recherche	Ah	je	U	e	Pennsylvanie	Tsu	Oh	Tsu	Pennsylvanie	Oh
modèle							Oh	Tsu	Pennsylvanie	Oh

Puisque la fin est le caractère qui existe dans le motif et que "pa" = 1, Une phrase de caractère est ignorée.

・ Quatrième comparaison

Cible de recherche	Ah	je	U	e	Pennsylvanie	Tsu	Oh	Tsu	Pennsylvanie	Oh
modèle							Oh	Tsu	Pennsylvanie	Oh

Puisque la fin est "O" = 0, le caractère suivant est recherché.

・・・ Répétez ci-dessous

Au final, ça ressemble à ça.

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 + "C'était deuxième! !!");
		}else {
			System.out.println("Je n'ai pas pu le trouver");
		}

	}

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

	    /*Pour les caractères qui ne figurent pas dans le modèle, décalez la longueur de la chaîne de caractères du modèle sur la largeur.*/
	    for(count = 0; count < bmTableSize; count++){
	    	table[count] = ptnLen;
	    }

	    /*Déterminez la largeur de décalage des caractères inclus dans le motif*/
	    for(count = 0; count < ptnLen; count++){
	    	table[(int)patternChar[count]] = ptnLen - count - 1;
	    }

	    /*Sortie de débogage*/
	    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);

	    /*Superposer des motifs aux positions de comparaison*/
	    System.out.printf(" pattern :");
	    for(count = 0; count < (i - j); count++) System.out.print("　"); //Décalage demi-largeur pleine largeur.
	    System.out.printf("%s\n", pattern);

	    /*Marquer le point de comparaison*/
	    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) {
	    /*Vérifiez pour éviter les boucles*/
	    if(table[(int)target] > remain){
	        /*Obtenez la valeur de la table des équipes*/
	        return(table[(int)target]);
	    }else{
	        /*Passer au caractère suivant du point où le classement a commencé*/
	        return(remain);
	    }
	}

	public static int BoyerMooreSearch(char[] txtChar, char[] patternChar) {
		int table[] = new int[bmTableSize];
		int txtLen = 0;
		int ptnLen = 0;
		int i = 0; /*Position de comparaison de texte*/
		int j = 0; /*Position de comparaison de modèle*/

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

	    /*Créer une table de travail*/
		table = BoyerMooreTableInit(table, patternChar, ptnLen);

	    /*Traitement de comparaison*/
	    i = j = ptnLen - 1; /*Faire de la position de comparaison la fin du motif*/
	    while((i < txtLen) && (j >= 0)){
	    	PrintCompareProcess(txt, pattern, i, j);

	        if(txtChar[i] != patternChar[j]){
	            /*Reportez-vous au tableau des décalages et définissez la position de comparaison suivante*/
	            i += next_step(table, txtChar[i], (ptnLen - j));
	            j = ptnLen - 1;   /*Faire de la position de comparaison la fin du motif*/
	        }else{
	            /*Puisque les personnages correspondent, nous assemblerons les personnages précédents*/
	            j--;
	            i--;
	        }
	    }

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

Résultat de sortie

[text]   :Aiue Pappa
[pattern]:Oppao
[table]  : default: step=4
         : char=Oh: table[12362]: step=0
         : char=Tsu: table[12387]: step=2
         : char=Pennsylvanie: 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
         :　　　　　　^
C'était 7e! !!

J'espère que cela vous aidera.

Les références

Référence du type de caractère Java ・ [Méthode d'algorithme de langage C-BM](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)
Table des codes de caractères compatibles Unicode ・ Le type de caractère [Java] peut être converti en type int

Implémentation Boyer-Moore en Java