Quel est l'algorithme de recherche de sous-chaîne le plus rapide ?

Question

OK, pour ne pas passer pour un idiot, je vais énoncer le problème/les exigences de manière plus explicite :

• Needle (motif) et haystack (texte à rechercher) sont tous deux des chaînes de caractères à terminaison nulle de style C. Aucune information sur la longueur n'est fournie ; si nécessaire, elle doit être calculée.
• La fonction doit retourner un pointeur vers la première correspondance, ou NULL si aucune correspondance n'est trouvée.
• Les cas d'échec ne sont pas autorisés. Cela signifie que tout algorithme ayant des besoins de stockage non constants (ou constants importants) devra avoir un cas de repli en cas d'échec de l'allocation (et les performances du cas de repli contribuent ainsi aux performances du pire cas).
• L'implémentation doit être en C, mais une bonne description de l'algorithme (ou un lien vers celle-ci) sans code est également acceptable.

...ainsi que ce que j'entends par "le plus rapide" :

• Déterministe O(n) donde n = longueur de la meule de foin. (Mais il peut être possible d'utiliser des idées provenant d'algorithmes qui sont normalement O(nm) (par exemple le rolling hash) s'ils sont combinés avec un algorithme plus robuste pour donner des résultats déterministes. O(n) résultats).
• Ne fonctionne jamais (de manière mesurable ; quelques horloges pour les if (!needle[1]) etc. sont acceptables) pire que l'algorithme naïf de force brute, en particulier sur les aiguilles très courtes qui sont probablement le cas le plus courant. (Des frais de prétraitement lourds et inconditionnels sont mauvais, tout comme le fait d'essayer d'améliorer le coefficient linéaire pour les aiguilles pathologiques au détriment des aiguilles probables).
• Pour une aiguille et une botte de foin arbitraires, des performances comparables ou supérieures (pas moins de 50% de temps de recherche en plus) à celles de tout autre algorithme largement implémenté.
• En dehors de ces conditions, je laisse la définition de "plus rapide" ouverte. Une bonne réponse devrait expliquer pourquoi vous considérez l'approche que vous proposez comme "la plus rapide".

Mon implémentation actuelle tourne en gros entre 10% plus lentement et 8 fois plus vite (selon l'entrée) que l'implémentation de la glibc pour Two-Way.

Mise à jour : Mon algorithme optimal actuel est le suivant :

• Pour les aiguilles de longueur 1, utilisez strchr .
• Pour les aiguilles de longueur 2-4, utilisez des mots machine pour comparer 2-4 octets à la fois comme suit : Préchargez l'aiguille dans un entier de 16 ou 32 bits avec des décalages de bits et faites sortir l'ancien octet et entrer les nouveaux octets de la botte de foin à chaque itération. Chaque octet de la botte de foin est lu exactement une fois et subit une vérification de 0 (fin de chaîne) et une comparaison de 16 ou 32 bits.
• Pour les aiguilles de longueur >4, utiliser l'algorithme Two-Way avec une mauvaise table de décalage (comme Boyer-Moore) qui est appliquée uniquement au dernier octet de la fenêtre. Pour éviter la surcharge de l'initialisation d'une table de 1kb, qui serait une perte nette pour beaucoup d'aiguilles de longueur moyenne, je garde un tableau de bits (32 octets) marquant quelles entrées dans la table de décalage sont initialisées. Les bits qui ne sont pas initialisés correspondent à des valeurs d'octets qui n'apparaissent jamais dans l'aiguille, pour lesquelles un décalage de toute la longueur de l'aiguille est possible.

Les grandes questions qui restent dans mon esprit sont :

• Existe-t-il un moyen de mieux utiliser la mauvaise table de décalage ? Boyer-Moore l'utilise au mieux en balayant à l'envers (de droite à gauche) mais Two-Way nécessite un balayage de gauche à droite.
• Les deux seuls algorithmes candidats viables que j'ai trouvés pour le cas général (pas de conditions de performance hors mémoire ou quadratiques) sont les suivants Deux voies y Correspondance de chaînes de caractères sur des alphabets ordonnés . Mais existe-t-il des cas facilement détectables où des algorithmes différents seraient optimaux ? Il est certain que de nombreux O(m) (où m est la longueur de l'aiguille) dans les algorithmes spatiaux pourraient être utilisés pour m<100 ou plus. Il serait également possible d'utiliser des algorithmes qui sont quadratiques dans le pire des cas s'il existe un test facile pour les aiguilles qui ne demandent qu'un temps linéaire.

Des points bonus pour :

• Pouvez-vous améliorer les performances en supposant que l'aiguille et la botte de foin sont toutes deux des UTF-8 bien formés (avec des caractères de différentes longueurs d'octets, le fait d'être bien formé impose certaines exigences d'alignement de chaîne entre l'aiguille et la botte de foin et permet des décalages automatiques de 2 à 4 octets lorsqu'un octet de tête non conforme est rencontré. Mais ces contraintes vous apportent-elles beaucoup/quelque chose de plus que ce que les calculs de suffixes maximaux, les bons décalages de suffixes, etc. vous donnent déjà avec divers algorithmes) ?

Note : Je suis bien conscient de la plupart des algorithmes existants, mais pas de leurs performances dans la pratique. Voici une bonne référence pour que les gens ne continuent pas à me donner des références sur les algorithmes dans leurs commentaires/réponses : http://www-igm.univ-mlv.fr/~lecroq/string/index.html

Answer 1

Constituez une bibliothèque de tests d'aiguilles et de bottes de foin probables. Profilez les tests sur plusieurs algorithmes de recherche, y compris la force brute. Choisissez celui qui donne les meilleurs résultats avec vos données.

Boyer-Moore utilise une mauvaise table de caractères avec une bonne table de suffixes.

Boyer-Moore-Horspool utilise une mauvaise table de caractères.

Knuth-Morris-Pratt utilise une table de correspondance partielle.

Rabin-Karp utilise des hachages courants.

Ils échangent tous, à des degrés divers, des frais généraux contre des comparaisons réduites, de sorte que les performances réelles dépendront de la longueur moyenne de l'aiguille et de la botte de foin. Plus la surcharge initiale est importante, mieux c'est avec des entrées plus longues. Avec des aiguilles très courtes, la force brute peut gagner.

Edita:

Un algorithme différent pourrait être meilleur pour trouver des paires de bases, des phrases anglaises ou des mots isolés. S'il existait un seul algorithme optimal pour toutes les entrées, il aurait été rendu public.

Réfléchissez au petit tableau suivant. Chaque point d'interrogation peut avoir un meilleur algorithme de recherche différent.

                 short needle     long needle
short haystack         ?               ?
long haystack          ?               ?

Il devrait s'agir d'un graphique, avec une gamme d'entrées plus courtes ou plus longues sur chaque axe. Si vous tracez chaque algorithme sur un tel graphique, chacun aura une signature différente. Certains algorithmes souffrent d'un fort taux de répétition dans le modèle, ce qui peut affecter des utilisations telles que la recherche de gènes. D'autres facteurs qui affectent les performances globales sont la recherche du même motif plus d'une fois et la recherche de différents motifs en même temps.

Si j'avais besoin d'un ensemble d'échantillons, je pense que je ferais du scrapping sur un site comme google ou wikipedia, puis je retirerais le html de toutes les pages de résultats. Pour un site de recherche, tapez un mot puis utilisez l'une des phrases de recherche suggérées. Choisissez quelques langues différentes, le cas échéant. En utilisant des pages Web, tous les textes seraient courts ou moyens, alors fusionnez suffisamment de pages pour obtenir des textes plus longs. Vous pouvez également trouver des livres du domaine public, des documents juridiques et d'autres grands volumes de texte. Vous pouvez aussi générer du contenu aléatoire en choisissant des mots dans un dictionnaire. Mais l'objectif du profilage est de tester le type de contenu que vous allez rechercher, alors utilisez des échantillons du monde réel si possible.

J'ai laissé des vagues courtes et longues. Pour l'aiguille, je pense que la courte est inférieure à 8 caractères, la moyenne est inférieure à 64 caractères et la longue est inférieure à 1 000. Pour la botte de foin, je pense que la courte est inférieure à 2^10, la moyenne inférieure à 2^20, et la longue jusqu'à 2^30 caractères.

Answer 2

Publié en 2011, je pense qu'il pourrait très bien être la "Correspondance simple et en temps réel de chaînes de caractères à espace constant" algorithme par Dany Breslauer, Roberto Grossi et Filippo Mignosi.

Mise à jour :

En 2014, les auteurs ont publié cette amélioration : Vers une correspondance optimale des chaînes de caractères emballées .

Answer 3

J'ai été surpris de voir notre rapport technique cité dans cette discussion ; je suis l'un des auteurs de l'algorithme qui a été nommé Sustik-Moore ci-dessus. (Nous n'avons pas utilisé ce terme dans notre article).

Je voulais ici souligner que pour moi la caractéristique la plus intéressante de l'algorithme est qu'il est assez simple de prouver que chaque lettre est examinée au plus une fois. Pour les versions précédentes de Boyer-Moore, ils ont prouvé que chaque lettre est examinée au maximum 3 et plus tard 2 fois au maximum, et ces preuves étaient plus complexes (voir les citations dans l'article). Par conséquent, je vois aussi une valeur didactique dans la présentation/étude de cette variante.

Dans cet article, nous décrivons également d'autres variations qui visent à améliorer l'efficacité tout en assouplissant les garanties théoriques. Il s'agit d'un article court et, à mon avis, le matériel devrait être compréhensible pour un diplômé moyen du secondaire.

Notre objectif principal était de porter cette version à l'attention d'autres personnes qui pourraient l'améliorer. La recherche de chaînes de caractères a tellement de variantes et nous ne pouvons pas penser à tous les cas où cette idée pourrait apporter des avantages. (Texte fixe et motif changeant, motif fixe et texte différent, prétraitement possible/non possible, exécution parallèle, recherche de sous-ensembles correspondants dans des textes volumineux, prise en compte des erreurs, correspondances proches etc. etc.)

Answer 4

En http://www-igm.univ-mlv.fr/~lecroq/string/index.html Le lien que vous indiquez est une excellente source et un résumé de certains des algorithmes de correspondance de chaînes de caractères les plus connus et les plus étudiés les plus connus et les plus étudiés.

Les solutions à la plupart des problèmes de recherche impliquent des compromis en ce qui concerne les frais de prétraitement, le temps et l'espace nécessaires. d'espace. Aucun algorithme algorithme ne sera optimal ou pratique dans tous les cas.

Si votre objectif est de concevoir un algorithme spécifique pour la recherche de chaînes de caractères, ignorez alors l'option le reste de ce que j'ai à dire, si vous voulez développer un service généralisé de recherche de chaînes de caractères. alors essayez ce qui suit :

Passez un peu de temps à examiner les forces et les faiblesses spécifiques des éléments suivants des algorithmes que vous avez déjà référencés. Effectuez cette l'objectif de trouver un ensemble d'algorithmes algorithmes qui couvrent la gamme et l'étendue des recherches de chaînes de caractères qui vous qui vous intéressent. Ensuite, construisez un sélecteur de recherche frontal basé sur une fonction de classificateur pour cibler le meilleur algorithme pour les entrées données. afin de cibler le meilleur algorithme pour les entrées données. De cette façon, vous pouvez utiliser l'algorithme le plus efficace pour effectuer le travail. Cette méthode est particulièrement efficace lorsqu'un algorithme est très bon pour certaines recherches mais se dégrade peu. Pour Par exemple, la force brute est probablement la meilleure pour les aiguilles de longueur 1, mais elle se dégrade rapidement lorsque la longueur des aiguilles augmente. mais se dégrade rapidement lorsque la longueur des aiguilles augmente. algorithme sustik-moore peut devenir plus efficace (sur les petits alphabets), alors pour les aiguilles plus longues et les grands alphabets, les algorithmes KMP ou Boyer-Moore peuvent être meilleurs. Ce ne sont que des exemples pour illustrer une stratégie possible.

L'approche de l'algorithme multiple n'est pas une idée nouvelle. Je crois qu'elle a été employée par quelques paquets commerciaux de tri/recherche (par exemple, SYNCSORT, couramment utilisé sur les ordinateurs centraux, met en œuvre plusieurs algorithmes de tri et utilise une méthode heuristique). plusieurs algorithmes de tri et utilise une heuristique pour choisir le "meilleur" pour les entrées données).

Chaque algorithme de recherche se décline en plusieurs variantes qui peuvent faire des différences significatives dans ses performances, comme, par exemple, ce papier illustre.

Évaluez votre service afin de déterminer les domaines dans lesquels des stratégies de recherche supplémentaires sont nécessaires ou pour mieux d'affiner votre fonction de sélection. Cette approche n'est ni rapide ni facile, mais si elle est bien menée, elle peut donner de très bons résultats.

Answer 5

Je sais que c'est une vieille question, mais la plupart des tableaux de décalage mauvais sont à un seul caractère. Si cela a un sens pour votre jeu de données (par exemple, surtout s'il s'agit de mots écrits), et si vous avez l'espace disponible, vous pouvez obtenir une accélération spectaculaire en utilisant une mauvaise table de décalage faite de n-grammes plutôt que de caractères uniques.