Moyen efficace de rechercher une chaîne dans un flux

Question

Supposons qu'un flux de texte (ou d'un Lecteur en Java) que je voudrais pour rechercher une chaîne de caractères particulière. Le flux de texte peut être très grande, de sorte que dès que la chaîne de recherche est trouvé que j'aimerais retourner true et aussi essayer d'éviter le stockage de l'ensemble de l'entrée dans la mémoire.

Naïvement, je pourrais essayer de faire quelque chose comme ceci (en Java):

public boolean streamContainsString(Reader reader, String searchString) throws IOException {
    char[] buffer = new char[1024];
    int numCharsRead;
    while((numCharsRead = reader.read(buffer)) > 0) {
        if ((new String(buffer, 0, numCharsRead)).indexOf(searchString) >= 0)
            return true;
    }
    return false;
}

Bien sûr, cela ne parvient pas à détecter la chaîne de recherche donnée, si elle se produit à la limite de l'1k de mémoire tampon:

Texte recherché: "stackoverflow"
Mémoire tampon du flux 1: "abc.........la pile"
De la mémoire tampon 2: "dépassement de capacité.......xyz"

Comment puis-je modifier ce code pour qu'il soit correctement trouve la chaîne de recherche-delà de la limite de la mémoire tampon, mais sans charger la totalité du flux de données en mémoire?

Edit: Remarque lors de la recherche d'un flux de données pour une chaîne de caractères, nous essayons de minimiser le nombre de lectures à partir du flux (pour éviter la latence dans un réseau/disque) et de garder l'utilisation de la mémoire constante quelle que soit la quantité de données dans le flux. Réelle efficacité de la chaîne de l'algorithme de mise en correspondance est secondaire, mais bien évidemment, il serait agréable de trouver une solution qui utilisaient un des plus efficace de ces algorithmes.

Answer 1

Il y a trois bonnes solutions ici:

1. Si vous voulez quelque chose qui est facile et assez rapide, aller avec pas de tampon, et au lieu de mettre en œuvre un simple nondeterminstic finis de l'état de la machine. Votre état sera une liste d'indices dans la chaîne que vous êtes à la recherche, et votre logique ressemble à quelque chose comme ceci (pseudo-code):

   String needle;
   n = needle.length();
   
   
   for every input character c do
     add index 0 to the list
     for every index i in the list do
       if c == needle[i] then
         if i + 1 == n then
           return true
         else
           replace i in the list with i + 1
         end
       else
         remove i from the list
       end
     end
   end
   

   Cela permettra de trouver la chaîne si elle existe et vous n'aurez plus jamais besoin d'un de la mémoire tampon.

2. Un peu plus de travail, mais aussi plus rapide: faire une NFA-à-DFA conversion des données chiffrées à l'avance ce que la liste des indices sont possibles, et attribuer à chacun un à un petit entier. (Si vous lisez à propos de la chaîne de recherche sur Wikipedia, ce qui est appelé l' ensemble des parties de la construction.) Ensuite, vous avez un seul etat et de vous faire un état de transition d'état sur chaque nouveau personnage. La NFA vous voulez c'est juste la DFA pour la chaîne précédé d'un état qui nondeterministically soit gouttes d'un personnage ou essaie de consommer le caractère courant. Vous aurez envie d'une erreur explicite de l'état ainsi.

3. Si vous voulez quelque chose de plus rapide, de créer une zone tampon dont la taille est au moins deux fois par n, et à l'utilisateur de Boyer-Moore pour compiler une machine à états à partir d' needle. Vous aurez beaucoup plus embêtant car Boyer-Moore n'est pas trivial à mettre en œuvre (bien que vous aurez à trouver un code en ligne) et parce que vous devrez vous arranger pour faire glisser la chaîne de caractères dans la mémoire tampon. Vous aurez à construire ou trouver une circulaire de la mémoire tampon qui peut "slide" sans copier; sinon, vous êtes susceptible de redonner de la performance des gains que vous pourriez obtenir à partir d'Boyer-Moore.

Answer 2

J'ai fait quelques changements à la Knuth, Morris-Pratt algorithme pour une partie de la recherche. Depuis la comparaison de la position est toujours inférieure ou égale à la prochaine, il n'est pas nécessaire pour la mémoire supplémentaire. Le code avec un Makefile est également disponible sur github et il est écrit dans Haxe pour cibler plusieurs langages de programmation à la fois, y compris Java.

J'ai aussi écrit un article connexe: recherche de sous-chaînes dans les cours d'eau: une légère modification de l'Knuth-Morris-Pratt de l'algorithme dans Haxe. L'article parle de l' Jakarta RegExp, maintenant à la retraite et de repos dans l'Apache Grenier. Le Jakarta Regexp bibliothèque "match" de la méthode dans l'RE de la classe utilise un CharacterIterator en tant que paramètre.

class StreamOrientedKnuthMorrisPratt {
    var m: Int;
    var i: Int;
    var ss:
    var table: Array<Int>;

    public function new(ss: String) {
        this.ss = ss;
        this.buildTable(this.ss);
    }

    public function begin() : Void {
        this.m = 0;
        this.i = 0;
    }

    public function partialSearch(s: String) : Int {
        var offset = this.m + this.i;

        while(this.m + this.i - offset < s.length) {
            if(this.ss.substr(this.i, 1) == s.substr(this.m + this.i - offset,1)) {
                if(this.i == this.ss.length - 1) {
                    return this.m;
                }
                this.i += 1;
            } else {
                this.m += this.i - this.table[this.i];
                if(this.table[this.i] > -1)
                    this.i = this.table[this.i];
                else
                    this.i = 0;
            }
        }

        return -1;
    }

    private function buildTable(ss: String) : Void {
        var pos = 2;
        var cnd = 0;

        this.table = new Array<Int>();
        if(ss.length > 2)
            this.table.insert(ss.length, 0);
        else
            this.table.insert(2, 0);

        this.table[0] = -1;
        this.table[1] = 0;

        while(pos < ss.length) {
            if(ss.substr(pos-1,1) == ss.substr(cnd, 1))
            {
                cnd += 1;
                this.table[pos] = cnd;
                pos += 1;
            } else if(cnd > 0) {
                cnd = this.table[cnd];
            } else {
                this.table[pos] = 0;
                pos += 1;
            }
        }
    }

    public static function main() {
        var KMP = new StreamOrientedKnuthMorrisPratt("aa");
        KMP.begin();
        trace(KMP.partialSearch("ccaabb"));

        KMP.begin();
        trace(KMP.partialSearch("ccarbb"));
        trace(KMP.partialSearch("fgaabb"));

    }
}

Answer 3

L' algorithme de recherche Knuth-Morris-Pratt ne sauvegarde jamais; c'est juste la propriété que vous voulez pour votre recherche de flux. Je l'ai déjà utilisé pour résoudre ce problème, bien qu'il puisse exister des moyens plus simples d'utiliser les bibliothèques Java disponibles. (Quand cela m'est arrivé, je travaillais en C dans les années 90.)

Le KMP est par essence un moyen rapide de créer un DFA correspondant aux chaînes, comme le suggère la suggestion n ° 2 de Norman Ramsey.

Answer 4

Cette réponse appliquées à la version initiale de la question " d'où la clé a été de lire le flux seulement autant qu'il est nécessaire de match sur une Chaîne, si cette Chaîne était présent. Cette solution ne serait pas répondre à l'exigence de garantie fixe de la mémoire d'utilisation, mais peut être utile d'envisager si vous avez trouvé cette question et ne sont pas liés par cette contrainte.

Si vous êtes lié par la constante de l'utilisation de la mémoire de contrainte, Java stocke des tableaux de n'importe quel type sur le tas, et en tant que tel micropression la référence ne désalloue la mémoire en aucune façon; je pense que toute solution impliquant un tableau dans une boucle consomment de la mémoire sur le tas et nécessitent GC.

---

Pour la simplicité de mise en oeuvre, peut-être Java 5 du Scanner qui peut accepter un InputStream et utiliser un java.util.regex.Motif de la recherche de l'entrée pourrait vous faire économiser de s'inquiéter de la mise en œuvre de détails.

Voici un exemple d'un potentiel de mise en œuvre:

public boolean streamContainsString(Reader reader, String searchString)
            throws IOException {
      Scanner streamScanner = new Scanner(reader);
      if (streamScanner.findWithinHorizon(searchString, 0) != null) {
		return true;
      } else {
		return false;
      }
}

Je pense regex parce qu'il sonne comme un travail pour un Finite State Automaton, de quelque chose qui commence dans l'état initial, changement d'état, caractère par caractère jusqu'à ce qu'il soit rejette la chaîne (pas de correspondance) ou de l'état.

Je pense que c'est probablement le plus efficace logique de correspondance que vous pourriez utiliser, et comment vous organiser la lecture de ces informations ne peut être dissociée de la logique de correspondance pour l'optimisation des performances.

C'est aussi la façon regexes travail.

Answer 5

Je crois que la meilleure solution à ce problème est d'essayer de garder les choses simples. Rappelez-vous, dans la mesure où je suis en train de lire à partir d'un flux, je veux garder le nombre de lectures à partir du flux à un minimum (comme le réseau ou le disque de latence peut être un problème), tout en gardant la quantité de mémoire utilisée constante (comme le flux peut être de très grande taille). Efficacité réelle de la correspondance de chaîne n'est pas l'objectif numéro un (comme cela a été étudié à la mort déjà).

Basé sur AlbertoPL de la suggestion, voici une solution simple qui compare la mémoire tampon à l'encontre de la recherche de la chaîne caractère par caractère. La clé est que parce que la recherche n'est fait que d'un seul caractère à la fois, aucun suivi n'est nécessaire et, par conséquent, aucune circulaire tampons, ou des tampons de taille spécifique sont nécessaires.

Maintenant, si quelqu'un peut venir avec une mise en œuvre similaire basé sur Knuth-Morris-Pratt algorithme de recherche, nous aurions une belle solution efficace ;)

public boolean streamContainsString(Reader reader, String searchString) throws IOException {
    char[] buffer = new char[1024];
    int numCharsRead;
    int count = 0;
    while((numCharsRead = reader.read(buffer)) > 0) {
        for (int c = 0; c < numCharsRead; c++) {
            if (buffer[c] == searchString.charAt(count))
                count++;
            else
                count = 0;
            if (count == searchString.length()) return true;
        }
    }
    return false;
}