Algorithme rapide pour la recherche de sous-chaînes dans une chaîne de caractères

J'aimerais un algorithme efficace (ou bibliothèque) que je peux utiliser en Java pour la recherche de sous-chaînes dans une chaîne de caractères.

Ce que je voudrais faire c'est:

Donné une chaîne d'entrée - INSTR:

"BCDEFGH"

Et un ensemble de candidats cordes - CAND:

"AB", "CDE", "FG", "H", "IJ"

Trouver tout CAND chaînes qui correspondent comme des sous-chaînes dans INSTR

Dans cet exemple, je pourrait correspondre à "CDE", "FG" et "H" (mais pas "AB" et "IJ")

Il pourrait y avoir plusieurs milliers de candidats des chaînes de caractères (ACDN), mais plus important encore, je vais faire cette recherche plusieurs millions de fois, donc j'ai besoin d'être RAPIDE.

J'aimerais travailler avec des tableaux de char. Aussi, je ne suis pas intested dans les solutions architecturales, comme la distribution de la recherche - tout le plus efficace de la fonction/l'algorithme pour le faire localement.

En outre, toutes les chaînes de CAND et INSTR seront tous relativement faible (< 50 caractères) - c'est à dire la chaîne de caractères de l'INSTRUMENT n'est PAS longue par rapport à la candidat à cordes.

Mise à jour je devrais l'avoir mentionné, l'ensemble de l'ACDN chaînes est invariant à travers toutes les valeurs des INSTR.

Mise à jour j'ai seulement besoin de savoir qu'il y avait un match et je n'ai pas besoin de savoir ce que le match a été.

Dernière Mise À Jour
J'ai opté pour tenter AhoCorsick et de Rabin-Karp, en raison de la simplicité de mise en œuvre.
Parce que j'ai de longueur variable des modèles, j'ai utilisé une version modifiée de Rabin-Karp qui hache les n premiers caractères de chaque modèle, où n est la longueur du plus petit modèle, N est la longueur de mon roulement de chaîne de fenêtre de recherche.
Pour l'Aho Corsick j'ai utilisé cette

Dans mon test j'ai cherché pour 1000 modèles dans les deux documents news articles en papier, en moyenne sur 1000 itérations etc...
Normalisé fois pour terminer étaient:

AhoCorsick: 1

RabinKarp: 1.8

Naïf de Recherche (vérifiez chaque motif & utiliser des chaînes de caractères.contient): 50

*Certaines ressources décrivant les algos mentionnés dans les réponses ci-dessous:

http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module5/module5.html

http://www.cs.princeton.edu/courses/archive/spr09/cos226/lectures/18SubstringSearch-2x2.pdf

http://www-igm.univ-mlv.fr/~lecroq/string/index.html*

  • Combien de temps sont les chaînes d'entrée par rapport à la candidat à cordes?
  • Ils sont courts. Les chaînes d'entrée sont généralement moins de 40 caractères, que les candidats sont des chaînes de caractères.
  • mais il peut y avoir plusieurs milliers de candidats cordes, et je veux le faire à plusieurs reprises sur de nombreuses chaînes d'entrée des millions de fois.
  • Étant donné les détails d'un FSM est probablement votre meilleur choix.
  • Curieux de savoir à quoi vous attendre en tant que sortie. C'est de savoir que l'un a été trouvé assez bon ou avez-vous besoin de savoir ce qui a été trouvé? Avez-vous besoin de savoir combien de fois chaque sous-chaîne a été trouvé?
  • Oui, un match est assez bon avec un simple "vrai/faux" et pas les autres informations nécessaires.

InformationsquelleAutor |
  1. 26

    Lire sur le Aho-Corasick algorithme et la Rabin-Karp algorithme.

    Si l'entrée n'est pas trop gros, vous ne voulez pas répéter la recherche de nombreuses fois et vous n'avez pas beaucoup de modèles, il pourrait être une bonne idée d'utiliser un modèle unique algorithme plusieurs fois. Le Article de wikipédia sur les algorithmes de recherche donne de nombreux algorithmes pour la course et de prétraitement fois.

    Implémentations:

    Présentations:

    InformationsquelleAutor Daniel Brückner
  2. 11

    Convertir l'ensemble des candidats chaînes dans un déterministe finite state automaton puis exécutez à travers la chaîne d'entrée dans le temps linéaire. La conversion d'une chaîne unique dans un DFS est bien couverte dans la norme des livres. Vous pouvez convertir un ensemble de chaînes par construire un automate non déterministe et puis determinizing il. Qui peut créer exponentielle de blow-up, dans le pire des cas, la taille de l'automate, mais la recherche par la suite est rapide, surtout si l'objectif de la chaîne est longue et les candidats court qui va bien travailler.

    • +1 pour la mention de Smqs. Absolument la solution la plus rapide.
    • Est-ce que soln comme pertinent, étant donné que les chaînes d'entrée et candidat chaînes sont tous très court, par exemple < 50 caractères?
    • Je pense que cela dépend de ce que vous voulez dire quand vous écrivez ci-dessus que "je veux faire cela à plusieurs reprises dans de nombreuses chaînes d'entrée". Le DFS ne dépend pas de la chaîne d'entrée, de sorte que si l'ensemble des candidats de chaînes de caractères est constante à travers de multiples chaînes d'entrée alors que c'est équivalent à une longue chaîne d'entrée et donc la solution est certainement pertinente. Si toutes les chaînes sont courtes ET les candidats changer à chaque fois alors il pourrait ne pas être la solution optimale.
    • Comment cela se compare à l'Rabin-Karp multiples de la recherche du modèle algo suggéré ci-dessus? Étant donné le grand nombre de sous-chaînes possible, et la relativement courte inputstring longueur cela aurait paru une bonne solution?
    • Rabin-Karp est certainement une bonne solution, il vient de différentes comportement asymptotique. Le DFS solution a la meilleure complexité asymptotique pour la mise en correspondance, car il est O(n) dans la longueur de la chaîne d'entrée seulement. Rabin-Karp a termes supplémentaires dans la complexité. Cependant, il est plus simple à mettre en œuvre à partir de zéro.
    • plz, donner un lien ou le nom du livre, où la description comment convertir une chaîne unique de DFS est. Je ne le trouve pas....
    • Il est possible de convertir une chaîne de caractères à une machine à états finis, mais les experts en recherche de chaine tiens à souligner qu'il ya plusieurs façons de le faire. Knuth-Morris-Pratt (les deux seul motif de recherche) ou de Aho-Corasick (Multi-Pattern-Recherche) sont toutes basées sur un automate fini déterministe. Maj-Et est basé sur un automate fini non déterministe (et est aussi efficace lorsqu'il est utilisé avec des bits de parallélisme). Si cette réponse est strictement un double de l'reconnus.

    InformationsquelleAutor Antti Huima
  3. 6

    C'est ce que les expressions régulières sont pour. Comme indiqué ci-dessus, automates d'états finis sont ce à quoi vous avez besoin, mais c'est exactement la façon dont une norme regexp-matcher est mis en œuvre.

    En java, vous pouvez écrire quelque chose comme:

    StringBuilder sb = new StringBuilder();
bool first = true;
for (String subStr : substrings) {
    if (first)
        first = false;
    else
        sb.append('|');
    sb.append(escape(subStr));
}
Pattern p = Pattern.compile(sb.toString());

    la méthode escape doit s'échapper tous les caractères qui ont une signification particulière dans une regexp.

    • Je ne peux pas parler du pourquoi il était en bas voté mais je peux dire que, en raison de la façon dont Java regex est mis en œuvre, cette expression peut être de façon moins efficace que la recherche de chaque sous-chaîne individuellement.
    • J'aime cette solution et upvoted il. Cependant, je voudrais souligner deux problèmes potentiels: (1) compte tenu d'un millier de chaînes de recherche, il est possible que le modèle compilateur va exploser. Je m'inquiète à l'utilisation de la mémoire augmente de façon exponentielle avec la complexité de l'expression de mise en correspondance. (2) je crois que le FSM/DFS construit par le modèle compilateur à l'occasion de sauvegarder. Si c'est le cas, l'un des algorithmes spécialisés qui se déplace strictement de l'avant peut-être encore plus rapides.
    • Je ne prétends pas que ma solution est parfait. Il peut très bien être suffisant si. YMMV.
    • La façon regex exécute un modèle de type "a|b|c|d" est de commencer à la position 0, essayer toutes les options, passer à la position 1, essayer toutes les options, passer à la position 2, essayez toutes les options, etc.. plus Rapide des moyens de le faire sans un gros regex OU sont assez trivial à écrire je pense. Il ne sera jamais pire pour rechercher tous les INSTR pour CAND1, puis de rechercher les CAND2, etc. et souvent être beaucoup mieux. En outre, ce type de recherche est beaucoup plus facile à optimiser.
    • Je ne peux pas imaginer un réel regexp bibliothèque être mis en œuvre comme ça. De toute façon, si la vitesse est vraiment important, vous pouvez essayer [de cette bibliothèque][0]. [0]: brics.dk/automate
    • C'est bien. Vous pouvez regarder le code Java de la regex. Le problème est que le OU les nœuds ne sais pas ce que le "a", "b", "c", etc. les nœuds sont en train de faire. Aussi, vous poser la mauvaise question, "a|b|c|d" est demander pour le premier match de l'un de ceux-là... ce qui signifie à tout le moins vous avez à la recherche pour chacun d'eux avant de vous le savez (sauf si vous appuyez sur le premier caractère). L'affiche veut savoir si n'importe quel match à tous et il est plus rapide de test "a", "b", "c", etc. séparément par rapport à l'expression régulière. Il le sera toujours.
    • pour ce que ça vaut, j'ai eu exactement la même réaction quand notre regex gourou expliqué à moi, un moment de retour. 🙂
    • Java de la regex peut être très mal mis en oeuvre; je ne suis pas familier avec elle. Mais sauf que, regex doit donner la solution optimale. La compilation des regex devrait croître de façon linéaire en la longueur du motif (avec un peu de chance, sublinéaire), et certainement pas de façon exponentielle, et le temps de recherche est linéaire.

    InformationsquelleAutor Jørgen Fogh
  5. 2

    Vous voudrez peut-être regarder dans Aho-Corasick algorithme et liées à des algorithmes. Je ne sais pas du tout bibliothèques de mise en œuvre de cette, désinvolte, mais c'est la façon classique de la résolution de ce problème.

    InformationsquelleAutor Avi
  6. 2

    Également de vérifier la Boyer-Moore algorithme pour une seule chaîne de filtrage.

    InformationsquelleAutor spoulson
  7. 2

    On peut tirer avantage de la petite taille (< 50 caractères) des chaînes afin de construire un super rapide algo pour ce cas, le coût de la mémoire.

    Nous pouvons hachage de tous les sous-chaînes possible de l'INSTRUMENT dans une table de hachage d'un temps, d'un coût de O(n^2). Alors quel que soit le nombre de CAND chaînes, la recherche sera O(1). Il vaut la peine pour un très grand nombre de CAND chaînes.

    Si l'INSTRUMENT est grand, alors nous pouvons construire un suffixe tableau et non pas à les trier, de sorte que le premier élément est le plus long (=N) et le dernier élément est le dernier char de l'INSTRUMENT. Maintenant, pour chaque CANDIDAT de la chaîne, seulement rechercher depuis le haut aussi longtemps que la longueur(ACDN) <= longueur(suffixe). Chacune de ces comparaisons seront O(n).

    • Je suis un peu floue sur ce qui me permettrait d'être hors de la base ici, mais serait le hachage temps O(n+1)(n/2) au lieu de O(n^2) puisque c'est la façon dont beaucoup de différents sous-chaînes qu'il devrait être?
    • Big-O ignore les coefficients. Déposer les 1 et 2 de votre expression et vous êtes de gauche avec O((n)(n)) qui est le même que O(n^2).
    InformationsquelleAutor Joy Dutta
  8. 0

    Une autre solution est d'utiliser un suffixe tableau pour la INSTR.

    Depuis le INSTR est petite, vous pouvez les trier avec tri à bulles.

    Ensuite, vous pouvez rechercher un CAND chaîne en O(logN) temps,

    où N = longueur(suffix_array) = longueur(INSTR).

    InformationsquelleAutor Nick Dandoulakis
  9. 0

    Ici sont certains de la mise en œuvre rapide de la Chaîne d'algorithmes de recherche en Java.

    • où? Avez-vous oublié de copier coller le lien?
    • Si vous cliquer sur le "Ici", vous serez redirigé vers le site web avec les algorithmes.
    InformationsquelleAutor
  10. 0
    import java.util.Scanner;

public class StringMatch 
{
    static int temp,i=0,j=0; static boolean flag=true,matcher=false;

    static String str=null,mstr=null;static char astr[],amstr[];

    static void getter(){
        Scanner sc = new Scanner(System.in);
        str = sc.nextLine();
        //String str="today is Monday"; 
        astr=str.toCharArray();
         mstr = sc.nextLine();
        //String mstr="is"; 
         amstr=mstr.toCharArray();
    }

    static void stringMatch(){
        while(i<astr.length){
            if(astr[i]==amstr[j]){
            while((j!=amstr.length)&&flag){temp=i;
                if(astr[i]!=amstr[j]) {flag=false;matcher=false;}
                else{matcher=true;}
                i++;j++;
                //System.out.println(i+"\t"+j);
            }if(matcher==true)break;i=temp;}i++;j=0;flag=true;

        }
        if(matcher==true) {System.out.println("true");}
        else    {System.out.println("false");}
    }

    public static void main(String[] args) {

    StringMatch.getter();
    StringMatch.stringMatch();

    }
}
    InformationsquelleAutor