Développement Java
  1. Développement Java
  3. Index Java de fonction plus efficace que Rabin-Karp? Efficacité de la recherche de texte
Intereting Posts
Clash de nom Java, effacement identique, ni cache l’autre Jackson Json Type Mapping Inner Class Différence entre objective-c et java JSP Google App Engine ne peut pas être déployé: java.lang.RuntimeException: impossible d’obtenir le compilateur Java système. Veuillez utiliser un JDK, pas un JRE Bibliothèque Java RRD Pourquoi les classes internes ne peuvent-elles pas déclarer des membres statiques? Pourquoi Java multi-catch ne peut-il pas traiter des types liés par sous-classement? Considérant l’encapsulation d’objects, les getters devraient-ils renvoyer une propriété immuable? Comment obtenir l’adresse MAC d’un client à partir de HttpServlet? Simuler la pluie Un grand chemin de classe de plusieurs fichiers jar (peut-être même inutilisés) est-il inefficace? Comment exclure module-info.java des vérifications du plugin checkstyle? Algorithme le plus rapide pour vérifier si un numéro est pandigital? java.lang.NullPointerException: tentative d’appel de la méthode virtuelle ‘android.view.View .MainActivity.findViewById (int)’ sur une référence d’object null Java isEmpty () non défini pour Ssortingng?

Index Java de fonction plus efficace que Rabin-Karp? Efficacité de la recherche de texte

Il y a quelques semaines, j’ai posé une question à Stackoverflow à propos de la création d’un algorithme efficace pour rechercher un motif dans une grande partie du texte. En ce moment, j’utilise la fonction Ssortingng indexOf pour effectuer la recherche. Une suggestion était d’utiliser Rabin-Karp comme alternative. J’ai écrit un petit programme de test comme suit pour tester une implémentation de Rabin-Karp comme suit. 

public static void main(Ssortingng[] args) { Ssortingng test = "Mary had a little lamb whose fleece was white as snow"; Ssortingng p = "was"; long start = Calendar.getInstance().getTimeInMillis(); for (int x = 0; x "+end); RabinKarp searcher = new RabinKarp("was"); start = Calendar.getInstance().getTimeInMillis(); for (int x = 0; x "+end); }

Et voici l’implémentation de Rabin-Karp que j’utilise: 

 import java.math.BigInteger; import java.util.Random; public class RabinKarp { private Ssortingng pat; // the pattern // needed only for Las Vegas private long patHash; // pattern hash value private int M; // pattern length private long Q; // a large prime, small enough to avoid long overflow private int R; // radix private long RM; // R^(M-1) % Q static private long dochash = -1L; public RabinKarp(int R, char[] pattern) { throw new RuntimeException("Operation not supported yet"); } public RabinKarp(Ssortingng pat) { this.pat = pat; // save pattern (needed only for Las Vegas) R = 256; M = pat.length(); Q = longRandomPrime(); // precompute R^(M-1) % Q for use in removing leading digit RM = 1; for (int i = 1; i <= M - 1; i++) RM = (R * RM) % Q; patHash = hash(pat, M); } // Compute hash for key[0..M-1]. private long hash(String key, int M) { long h = 0; for (int j = 0; j < M; j++) h = (R * h + key.charAt(j)) % Q; return h; } // Las Vegas version: does pat[] match txt[i..i-M+1] ? private boolean check(String txt, int i) { for (int j = 0; j < M; j++) if (pat.charAt(j) != txt.charAt(i + j)) return false; return true; } // check for exact match public int search(String txt) { int N = txt.length(); if (N < M) return -1; long txtHash; if (dochash == -1L) { txtHash = hash(txt, M); dochash = txtHash; } else txtHash = dochash; // check for match at offset 0 if ((patHash == txtHash) && check(txt, 0)) return 0; // check for hash match; if hash match, check for exact match for (int i = M; i < N; i++) { // Remove leading digit, add trailing digit, check for match. txtHash = (txtHash + Q - RM * txt.charAt(i - M) % Q) % Q; txtHash = (txtHash * R + txt.charAt(i)) % Q; // match int offset = i - M + 1; if ((patHash == txtHash) && check(txt, offset)) return offset; } // no match return -1; // was N } // a random 31-bit prime private static long longRandomPrime() { BigInteger prime = new BigInteger(31, new Random()); return prime.longValue(); } // test client }

L’implémentation de Rabin-Karp fonctionne en ce sens qu’elle renvoie le décalage correct de la chaîne que je recherche. Ce qui est surprenant pour moi, ce sont les statistiques de synchronisation qui se sont produites lors de l’exécution du programme de test. Les voici: 

 Standard Java Time->39 Rabin Karp time->409

C’était vraiment surprenant. Non seulement Rabin-Karp (du moins tel qu’il est mis en œuvre ici) n’est pas plus rapide que la fonction standard java indexOf Ssortingng, mais elle est plus lente d’un ordre de grandeur. Je ne sais pas ce qui ne va pas (si quelque chose). Quelqu’un a des pensées à ce sujet?

Merci,

Elliott

J’ai répondu à cette question plus tôt et Elliot a souligné que j’étais tout simplement faux. Je m’excuse auprès de la communauté.

Le code Ssortingng.indexOf n’a rien de magique. Ce n’est pas optimisé nativement ou quelque chose comme ça. Vous pouvez copier la méthode indexOf à partir du code source Ssortingng et elle s’exécute tout aussi rapidement.

Ce que nous avons ici, c’est la différence entre l’efficacité de O () et l’efficacité réelle. Rabin-Karp pour une chaîne de longueur N et un motif de longueur M, Rabin-Karp est O (N + M) et un des cas les plus défavorables de O (NM). Ssortingng.indexOf () a également un meilleur cas de O (N + M) et un pire cas de O (NM).

Si le texte contient de nombreuses correspondances partielles au début du motif, Rabin-Karp restra proche de sa performance optimale, contrairement à Ssortingng.indexOf. Par exemple, j’ai testé le code ci-dessus (correctement cette fois-ci :-)) sur un million de «0» suivis d’un seul «1», puis sur 1000 «0» suivis d’un seul «1». Cela a forcé le Ssortingng.indexOf à ses performances les plus défavorables. Pour ce test hautement dégénéré, l’algorithme de Rabin-Karp était environ 15 fois plus rapide qu’indexOf.

Pour le texte en langage naturel, Rabin-Karp restra proche du meilleur cas et indexOf ne se détériorera que légèrement. Le facteur déterminant est donc la complexité des opérations effectuées à chaque étape.

Dans sa boucle la plus interne, indexOf recherche un premier caractère correspondant. A chaque itération il faut:

  • incrémenter le compteur de boucles
  • effectuer deux tests logiques
  • faire un access tableau

Dans Rabin-Karp, chaque itération doit:

  • incrémenter le compteur de boucles
  • effectuer deux tests logiques
  • faire deux access au tableau (en fait deux invocations de méthode)
  • mettre à jour un hachage, ce qui nécessite plus de 9 opérations numériques

Par conséquent, à chaque itération, Rabin-Karp va encore plus loin. J’ai essayé de simplifier l’algorithme de hachage en utilisant uniquement des caractères XOR, mais je disposais toujours d’un access supplémentaire à la masortingce et de deux opérations numériques supplémentaires, donc c’était encore plus lent.

De plus, lorsqu’une correspondance est trouvée, Rabin-Karp ne connaît que la correspondance de hachage et doit donc tester chaque caractère, alors qu’indexF connait déjà les correspondances du premier caractère et a donc un test de moins à faire.

Ayant lu sur Wikipedia que Rabin-Karp est utilisé pour détecter le plagiat, j’ai pris le livre de Ruth de la Bible, enlevé toute ponctuation et tout en minuscule, ce qui laissait un peu moins de 10 000 caractères. J’ai ensuite cherché “andthewomenherneighboursgaveitaname” qui se produit vers la fin du texte. Ssortingng.indexOf était encore plus rapide, même avec le hachage XOR. Cependant, si je retirais l’avantage de Ssortingng.indexOfs de pouvoir accéder au tableau de caractères interne privé de Ssortingng et le forçait à copier le tableau de caractères, Rabin-Karp était finalement vraiment plus rapide.

Cependant, j’ai délibérément choisi ce texte car il y a 213 “et” s dans le livre de Ruth et 28 “et les” s. Si, au lieu de cela, je cherchais uniquement les derniers caractères “ursgaveitaname”, il n’y a que 3 “urs” dans le texte, donc indexOf se rapproche de son meilleur et gagne la course à nouveau.

En tant que test plus juste, j’ai choisi au hasard 20 chaînes de caractères de la seconde moitié du texte et les ai chronométrées. Rabin-Karp était environ 20% plus lent que l’algorithme indexOf exécuté en dehors de la classe Ssortingng et 70% moins rapide que l’algorithme réel indexOf. Ainsi, même dans le cas d’utilisation où cela est censé convenir, ce n’était toujours pas le meilleur choix.

Alors à quoi sert Rabin-Karp? Peu importe la longueur ou la nature du texte à rechercher, chaque personnage comparé sera plus lent. Quelle que soit la fonction de hachage que nous choisissons, nous sums sûrement obligés de faire un access supplémentaire au tableau et au moins deux opérations numériques. Une fonction de hachage plus complexe nous donnera moins de fausses correspondances, mais nécessitera plus d’opérateurs numériques. Il n’y a tout simplement pas moyen que Rabin-Karp puisse suivre.

Comme démontré ci-dessus, si nous avons besoin de trouver une correspondance préfixée par un bloc de texte souvent répété, indexOf peut être plus lent, mais si nous soaps que nous le faisons, nous aurions intérêt à utiliser indexOf pour rechercher le texte. sans le préfixe, puis vérifiez si le préfixe était présent.

Sur la base de mes investigations aujourd’hui, je ne vois aucun moment où la complexité supplémentaire de Rabin Karp sera payante.

Voici la source de java.lang.Ssortingng. indexOf est la ligne 1770.

Mon soupçon est que puisque vous l’utilisez sur une chaîne d’entrée aussi courte, la surcharge supplémentaire de l’algorithme Rabin-Karp sur l’implémentation apparemment naïve de l’indexOf de java.lang.Ssortingng, vous ne voyez pas les performances réelles de l’algorithme. Je suggérerais de l’essayer sur une chaîne d’entrée beaucoup plus longue pour comparer les performances.

De mon sharepoint vue, Rabin Karp est mieux utilisé lors de la recherche d’un bloc de texte pour des mots / phrases multiples.

Pensez à une mauvaise recherche de mots pour signaler un langage abusif.

Si vous avez une liste de 2000 mots, y compris les dérivations, vous devez appeler indexOf 2000, une fois pour chaque mot recherché.

RabinKarp aide à cela en effectuant la recherche inverse. Faites un hachage de 4 caractères pour chacun des 2 000 mots et mettez-le dans un dictionnaire avec une recherche rapide.

Maintenant, pour chaque 4 caractères du texte de recherche, le hachage et la comparaison avec le dictionnaire.

Comme vous pouvez le voir, la recherche est maintenant l’inverse – nous recherchons plutôt les 2000 mots pour une correspondance possible. Ensuite, nous obtenons la chaîne du dictionnaire et faisons un égal pour vérifier pour être sûr.

C’est aussi une recherche plus rapide de cette façon, car nous recherchons un dictionnaire au lieu de rechercher des chaînes.

Maintenant, imaginez le pire scénario de faire toutes ces recherches sur indexOf – le tout dernier mot que nous vérifions est une correspondance …

L’article de Wikipedia pour RabinKarp mentionne même l’infériorité dans la situation que vous décrivez. 😉 http://en.wikipedia.org/wiki/Rabin-Karp_algorithm

Mais ce n’est que naturel que cela arrive!
L’entrée de votre test est d’abord trop sortingviale.

indexOf renvoie l ‘index de la recherche dans un petit tampon (tableau de caractères interne de Ssortingng) alors que Rabin – Karp doit effectuer un prétraitement pour configurer ses données afin qu’elles fonctionnent, ce qui prend du temps supplémentaire.

Pour voir une différence, vous devrez tester un texte vraiment volumineux pour trouver des expressions.

Veuillez également noter que, lorsque vous utilisez un algorithme de recherche de chaînes plus sophistiqué, ils peuvent avoir une configuration / un prétraitement “coûteux” pour permettre une recherche très rapide.
Dans votre cas, vous venez de chercher un was dans une phrase. En tout cas, vous devez toujours prendre en compte les données

Sans regarder dans les détails, deux raisons me viennent à l’esprit:

  • Vous êtes très susceptible de surpasser les implémentations d’API standard uniquement dans des cas très particuliers. Je ne considère pas que “Marie avait un petit agneau dont la toison était blanche comme neige” pour être tel.
  • le microbenchmarking est très difficile et peut donner des résultats assez trompeurs. Voici une explication , voici une liste d’outils que vous pourriez utiliser

Non seulement essayez simplement une chaîne statique plus longue, mais essayez de générer des chaînes longues aléatoires et d’insérer la cible de recherche dans un emplacement aléatoire à chaque fois. Sans le randomiser, vous verrez un résultat fixe pour indexOf .

EDITED: Random est le mauvais concept. La plupart des textes ne sont pas vraiment aléatoires. Mais vous auriez besoin de beaucoup de longues chaînes pour être efficace, et pas seulement pour tester la même chaîne plusieurs fois. Je suis sûr qu’il existe des moyens d’extraire de grandes chaînes “aléatoires” à partir d’une source de texte encore plus grande, ou quelque chose du genre.

Pour ce type de recherche, Knuth-Morris-Pratt pourrait mieux fonctionner. En particulier si la sous-chaîne ne se contente pas de répéter les caractères, alors KMP doit surpasser indexOf (). Le pire cas (chaîne de tous les mêmes caractères) ce sera la même chose.