Parmi les algorithmes de recherche par correspondance de chaînes, les deux plus connus sont l'algorithme KMP (Knuth-Morris-Pratt) et l'algorithme BM (Boyer-Moore). Les deux algorithmes ont des temps de recherche linéaires dans le pire des cas. Cependant, en pratique, l'algorithme KMP n'est pas beaucoup plus rapide que la fonction strstr() la plus simple de la bibliothèque C, tandis que l'algorithme BM est souvent 3 à 5 fois plus rapide que l'algorithme KMP (pas personnellement pratiqué). Cependant, l'algorithme BM n'est pas encore l'algorithme le plus rapide. Voici un algorithme de recherche, l'algorithme Sunday, qui est plus rapide que l'algorithme BM.
L'idée de l'algorithme du dimanche est très similaire à l'idée des mauvais caractères dans l'algorithme BM. La seule différence est qu'une fois que l'algorithme Sunday ne parvient pas à correspondre, il prend le caractère une position derrière la partie actuelle de la chaîne cible qui correspond à la chaîne Pattern pour effectuer une mauvaise correspondance de caractères. Lorsqu'il s'avère que la correspondance échoue, il est jugé si le caractère au décalage actuel + longueur de la chaîne de motif + 1 (supposé être la position K) dans la chaîne parente existe dans la chaîne de motif. S'il existe, alignez la position avec le caractère dans la chaîne Pattern, puis faites la correspondance depuis le début ; si elle n'existe pas, déplacez la chaîne Pattern vers l'arrière, alignez-la avec le caractère en k+1 de la chaîne parent, puis correspondre. Répétez l'opération ci-dessus jusqu'à ce qu'elle soit trouvée ou que la chaîne parent soit trouvée. J'ai écrit un petit exemple pour implémenter l'algorithme suivant.
Dans le code, deux algorithmes de correspondance de chaînes sont implémentés, l'un est la méthode du dimanche et l'autre est la méthode ordinaire de déplacement d'un bit à la fois. La comparaison de l'efficacité des deux est affichée dans la fonction principale, toutes deux au niveau de la nanoseconde. . Les étapes détaillées de l'algorithme ont été ajoutées avec les commentaires correspondants dans le code. Concernant l'algorithme BM, nous comparerons et analyserons ensemble la prochaine fois lorsqu'il sera vide.
Copiez le code comme suit :
importer java.util.HashMap ;
importer java.util.LinkedList ;
importer java.util.List ;
importer java.util.Map ;
/**
* @auteur Scott
* @date 28 décembre 2013
* @description
*/
classe publique SundySearch {
Texte de chaîne = nul ;
Modèle de chaîne = nul ;
int posactuel = 0 ;
/**
* Liste des positions des premiers caractères de la sous-chaîne correspondante
*/
List<Integer> matchedPosList = new LinkedList<Integer>();
/**
* Carte des caractères correspondants, enregistre quels caractères se trouvent dans la chaîne correspondante et le dernier déplacement de chaque caractère
*/
Map<Character, Integer> map = new HashMap<Character, Integer>();
public SundySearch (texte de chaîne, modèle de chaîne) {
this.text = texte ;
this.motif = motif ;
this.initMap();
} ;
/**
* Lors de la correspondance dimanche, il est utilisé pour stocker la dernière position d'occurrence de chaque caractère dans Pattern, dans l'ordre de gauche à droite.
*/
privé vide initMap() {
pour (int i = 0; i < pattern.length(); i++) {
this.map.put(pattern.charAt(i), i);
}
}
/**
* Correspondance récursive de chaîne ordinaire, si la correspondance échoue, avancez d'une position
*/
public List<Integer> normalMatch() {
//Échec de la correspondance, continuez à descendre
si (!matchFromSpecialPos(currentPos)) {
Poseactuelle += 1 ;
if ((text.length() - currentPos) < pattern.length()) {
renvoie la listePosList correspondante ;
}
normalMatch();
} autre {
// Correspondance réussie, enregistrement de l'emplacement
matchedPosList.add(currentPos);
Poseactuelle += 1 ;
normalMatch();
}
renvoie la listePosList correspondante ;
}
/**
* Correspondance du dimanche, en supposant que la position du caractère K dans le texte est : décalage actuel + longueur de la chaîne de motif + 1
*/
public List<Integer> dimancheMatch() {
// Si aucune correspondance n'est réussie
si (!matchFromSpecialPos(currentPos)) {
// Si le caractère K dans Text n'apparaît pas dans la chaîne Pattern, ignorez toute la longueur de la chaîne Pattern.
if ((currentPos + pattern.length() + 1) < text.length()
&& !map.containsKey(text.charAt(currentPos + pattern.length() + 1))) {
currentPos += motif.longueur();
}autre {
// Si le caractère K dans Text apparaît dans la chaîne Pattern, alignez la position du caractère K dans Text avec la position du dernier caractère K dans la chaîne Pattern.
if ((currentPos + pattern.length() + 1) > text.length()) {
Poseactuelle += 1 ;
} autre {
currentPos += pattern.length() - (Integer) map.get(text.charAt(currentPos + pattern.length()));
}
}
// Une fois la correspondance terminée, renvoie le déplacement initial de toutes les correspondances réussies.
if ((text.length() - currentPos) < pattern.length()) {
renvoie la listePosList correspondante ;
}
dimancheMatch();
}autre {
//Si la correspondance réussit, avancez d'un bit puis faites à nouveau la correspondance
matchedPosList.add(currentPos);
Poseactuelle += 1 ;
dimancheMatch();
}
renvoie la listePosList correspondante ;
}
/**
* Vérifiez si la sous-chaîne commençant à partir du décalage spécifié du texte correspond au modèle
*/
public booléen matchFromSpecialPos (int pos) {
if ((text.length()-pos) < motif.length()) {
renvoie faux ;
}
pour (int i = 0; i < pattern.length(); i++) {
if (text.charAt(pos + i) == pattern.charAt(i)) {
si (je == (motif.longueur()-1)) {
renvoie vrai ;
}
continuer;
} autre {
casser;
}
}
renvoie faux ;
}
public static void main (String[] arguments) {
SundySearch sundySearch = new SundySearch("bonjour ah Adolf adfsadfklf adf234masdfsdfdsfdsfdsffwerwrewrerwerwerwerwerwerwersdf2666sdflsdfk", "adf");
début long = System.nanoTime();
System.out.println("NormalMatch:" + sundySearch.normalMatch());
System.out.println("NormalMatch:" + (System.nanoTime() - commencer));
commencer = System.nanoTime();
System.out.println("SundayMatch:" + sundySearch.sundayMatch());
System.out.println("SundayMatch:" + (System.nanoTime() - commencer));
}
}