Algorithmus zum Auffinden des kleinsten Snippets beim Durchsuchen eines Dokuments?

Question

Ich habe Skienas ausgezeichnetes "The Algorithm Design Manual" durchgelesen und bin bei einer der Übungen hängen geblieben.

Die Frage ist: "Finden Sie bei einem Suchbegriff aus drei Wörtern den kleinsten Ausschnitt des Dokuments, der alle drei Suchbegriffe enthält, d. h. den Ausschnitt mit der geringsten Anzahl von Wörtern. Sie erhalten die Indexpositionen, an denen diese Wörter in den Suchstrings vorkommen, z. B. Wort1: (1, 4, 5), Wort2: (4, 9, 10) und Wort3: (5, 6, 15). Jede der Listen ist in der oben genannten Reihenfolge sortiert."

Alles, was mir einfällt, ist O(n^2)... Diese Frage steht im Kapitel "Sortieren und Suchen", also nehme ich an, dass es einen einfachen und cleveren Weg gibt, dies zu tun. Ich versuche gerade etwas mit Graphen, aber das scheint zu viel zu sein.

Ideen? Danke

Answer 1

Wenn ich nichts übersehen habe, gibt es einen einfachen O(n)-Algorithmus:

1. Wir stellen den Ausschnitt durch (x, y) dar, wobei x und y den Anfang bzw. das Ende des Ausschnitts bezeichnen.
2. Ein Snippet ist machbar, wenn es alle 3 Suchbegriffe enthält.
3. Wir beginnen mit dem nicht durchführbaren Ausschnitt (0,0).
4. Wiederholen Sie die folgenden Schritte, bis y das Ende der Zeichenkette erreicht:
   5. Wenn der aktuelle Ausschnitt (x, y) machbar ist, fahren Sie mit dem Ausschnitt (x+1, y) fort
      Andernfalls (der aktuelle Ausschnitt ist nicht durchführbar), weiter zum Ausschnitt (x, y+1)
5. Wählen Sie das kürzeste Snippet aus allen möglichen Snippets, die wir durchgesehen haben.

Dauer der Laufzeit - in jeder Iteration wird entweder x oder y um 1 erhöht, wobei x nicht größer als y und y nicht größer als die Länge der Zeichenkette sein darf, so dass die Gesamtzahl der Iterationen O(n) beträgt. Auch die Durchführbarkeit kann in diesem Fall mit O(1) geprüft werden, da wir verfolgen können, wie viele Vorkommen jedes Worts im aktuellen Snippet vorhanden sind. Mit jeder Erhöhung von x oder y um 1 können wir diese Zählung mit O(1) aufrechterhalten.

Korrektheit - Für jedes x berechnen wir den minimal machbaren Ausschnitt (x, ?). Wir müssen also über den minimalen Ausschnitt gehen. Wenn y das kleinste y ist, so dass (x, y) machbar ist, dann ist (x+1, y') ein machbarer Ausschnitt y' >= y (Deshalb ist dieser Algorithmus linear und die anderen nicht).

Answer 2

In dieser Antwort habe ich bereits einen recht einfachen Algorithmus beschrieben, der genau dieses Problem löst

Google-Suchergebnisse: Wie findet man das kleinste Fenster, das alle Suchbegriffe enthält?

In dieser Frage gingen wir jedoch davon aus, dass die Eingabe durch einen Textstrom dargestellt wird und die Wörter in einer leicht durchsuchbaren Menge gespeichert sind.

In Ihrem Fall wird die Eingabe etwas anders dargestellt: als ein Bündel von Vektoren mit sortierten Positionen für jedes Wort. Diese Darstellung lässt sich leicht in das umwandeln, was für den obigen Algorithmus benötigt wird, indem man einfach alle diese Vektoren zu einem einzigen Vektor von (position, word) Paare nach Position geordnet. Dies kann buchstäblich oder "virtuell" geschehen, indem die ursprünglichen Vektoren in die Prioritätswarteschlange gestellt werden (geordnet nach ihren ersten Elementen). Das Herausnehmen eines Elements aus der Warteschlange bedeutet in diesem Fall, dass das erste Element aus dem ersten Vektor in der Warteschlange herausgenommen wird und der erste Vektor möglicherweise entsprechend seinem neuen ersten Element in die Warteschlange aufgenommen wird.

Da Sie in Ihrer Aufgabenstellung die Anzahl der Wörter ausdrücklich als drei können Sie einfach die ersten Elemente aller drei Arrays überprüfen und bei jeder Iteration das kleinste Element löschen. Das gibt Ihnen eine O(N) Algorithmus, wobei N ist die Gesamtlänge aller Arrays.

Außerdem scheint Ihre Erklärung des Problems darauf hinzudeuten, dass sich die Zielwörter im Text überschneiden können, was ziemlich seltsam ist (da Sie den Begriff "Wort" verwenden). Ist das beabsichtigt? Auf jeden Fall stellt dies kein Problem für den oben verlinkten Algorithmus dar.

Answer 3

Aus der Frage geht hervor, dass Sie die Indexpositionen für jede Ihrer n "Suchwörter" (Wort1, Wort2, Wort3, ..., Wort n ) im Dokument. Mit Hilfe eines Sortieralgorithmus wird die n Unabhängige Arrays, die Suchwörtern zugeordnet sind, lassen sich leicht als ein einziges Array mit allen Indexpositionen in aufsteigender numerischer Reihenfolge und einer Wortbezeichnung darstellen, die jedem Index in dem Array zugeordnet ist (das Index-Array).

Der grundlegende Algorithmus:

(Diese Funktion ist so konzipiert, dass sie unabhängig davon funktioniert, ob der Fragesteller beabsichtigt, zwei verschiedene Suchbegriffe unter derselben Indexnummer nebeneinander zuzulassen).

Zunächst definieren wir eine einfache Funktion zur Messung der Länge eines Snippets, das alle n Etiketten mit einem Startpunkt im Index-Array. (Aus der Definition unseres Arrays ist ersichtlich, dass jeder Startpunkt im Array notwendigerweise der indizierte Ort eines der n Suchbezeichnungen). Die Funktion merkt sich einfach die eindeutigen Suchbezeichnungen, während die Funktion die Elemente im Array durchläuft, bis alle n Etiketten beobachtet worden. Die Länge des Snippets ist definiert als die Differenz zwischen dem Index des letzten gefundenen eindeutigen Labels und dem Index des Startpunktes im Index-Array (dem ersten gefundenen eindeutigen Label). Wenn alle n Beschriftungen nicht vor dem Ende des Arrays beobachtet werden, gibt die Funktion einen Nullwert zurück.

Jetzt kann die Funktion "Snippet-Länge" für jedes Element in Ihrem Array ausgeführt werden, um eine Snippet-Größe zuzuordnen, die alle n Suchwörter, beginnend mit jedem Element im Array. Der kleinste Wert, der nicht Null ist und von der Funktion snippet length über das gesamte Index-Array zurückgegeben wird, ist der gesuchte Ausschnitt in Ihrem Dokument.

Erforderliche Optimierungen:

1. Behält den Wert der aktuell kürzesten Snippet-Länge im Auge, so dass der Wert sofort bekannt ist, nachdem einmal durch das Index-Array iteriert wurde.
2. Wenn Sie durch Ihr Array iterieren, beenden Sie die Funktion "Snippet-Länge", wenn das aktuell untersuchte Snippet die Länge des kürzesten zuvor gesehenen Snippets überschreitet.
3. Wenn die Funktion "Snippetlänge" Null zurückgibt, weil nicht alle Snippets gefunden wurden n Suchwörter in den verbleibenden Index-Array-Elementen, assoziieren Sie eine Null-Snippet-Länge mit allen aufeinanderfolgenden Elementen im Index-Array.
4. Wenn die Funktion "Snippet-Länge" auf ein Wort-Etikett angewandt wird und das unmittelbar darauf folgende Etikett mit dem Start-Etikett identisch ist, wird dem Start-Etikett ein Nullwert zugewiesen und mit dem nächsten Etikett fortgefahren.

Computerkomplexität:

Offensichtlich kann der Sortierteil des Algorithmus in O( n Protokoll n ).

So würde ich die Zeitkomplexität des zweiten Teils des Algorithmus berechnen (für Kritik und Korrekturen wäre ich sehr dankbar).

Im besten Fall wendet der Algorithmus die Snippet-Längenfunktion nur auf das erste Element im Index-Array an und stellt fest, dass kein Snippet mit allen Suchwörtern existiert. Dieses Szenario würde in nur n Berechnungen, bei denen n ist die Größe des Index-Arrays. Noch schlimmer ist es, wenn das kleinste Snippet gleich der Größe des gesamten Arrays ist. In diesem Fall beträgt der Rechenaufwand etwas weniger als 2 n (einmal durch das Array, um die kleinste Snippetlänge zu finden, ein zweites Mal, um zu zeigen, dass keine anderen Snippets existieren). Je kürzer die durchschnittlich berechnete Snippetlänge ist, desto öfter muss die Snippetlängenfunktion auf das Index-Array angewendet werden. Wir können davon ausgehen, dass unser Worst-Case-Szenario der Fall sein wird, in dem die Snippet-Längenfunktion auf jedes Element im Index-Array angewendet werden muss. Um einen Fall zu entwickeln, in dem die Funktion auf jedes Element im Index-Array angewendet wird, müssen wir ein Index-Array entwerfen, bei dem die durchschnittliche Snippet-Länge über das gesamte Index-Array vernachlässigbar ist im Vergleich zur Größe des Index-Arrays insgesamt. In diesem Fall können wir unsere Berechnungskomplexität als O(C n ), wobei C eine Konstante ist, die deutlich kleiner ist als n . Daraus ergibt sich eine endgültige rechnerische Komplexität von:

O( n Protokoll n + C n )

Dónde:

C << n

Edit :

AndreyT weist zu Recht darauf hin, dass anstelle der Sortierung der Wortindizes in n Protokoll n Zeit, könnte man sie genauso gut zusammenführen (da die Unterfelder bereits sortiert sind) in n Protokoll m Zeit, in der m ist die Anzahl der Suchwortfelder, die zusammengeführt werden sollen. Dies beschleunigt den Algorithmus offensichtlich in Fällen, in denen m < n .

Answer 4

O(n log k) Lösung, wobei n die Gesamtzahl der Indizes und k die Anzahl der Wörter ist. Die Idee ist, einen Heap zu verwenden, um bei jeder Iteration den kleinsten Index zu ermitteln und gleichzeitig den maximalen Index im Heap zu verfolgen. Ich habe auch die Koordinaten jedes Wertes in den Heap eingetragen, um den nächsten Wert in konstanter Zeit abrufen zu können.

#include <algorithm>
#include <cassert>
#include <limits>
#include <queue>
#include <vector>

using namespace std;

int snippet(const vector< vector<int> >& index) {
    // (-index[i][j], (i, j))
    priority_queue< pair< int, pair<size_t, size_t> > > queue;
    int nmax = numeric_limits<int>::min();
    for (size_t i = 0; i < index.size(); ++i) {
        if (!index[i].empty()) {
            int cur = index[i][0];
            nmax = max(nmax, cur);
            queue.push(make_pair(-cur, make_pair(i, 0)));
        }
    }
    int result = numeric_limits<int>::max();
    while (queue.size() == index.size()) {
        int nmin = -queue.top().first;
        size_t i = queue.top().second.first;
        size_t j = queue.top().second.second;
        queue.pop();
        result = min(result, nmax - nmin + 1);
        j++;
        if (j < index[i].size()) {
            int next = index[i][j];
            nmax = max(nmax, next);
            queue.push(make_pair(-next, make_pair(i, j)));
        }
    }
    return result;
}

int main() {
    int data[][3] = {{1, 4, 5}, {4, 9, 10}, {5, 6, 15}};
    vector<vector<int> > index;
    for (int i = 0; i < 3; i++) {
        index.push_back(vector<int>(data[i], data[i] + 3));
    }
    assert(snippet(index) == 2);
}

Answer 5

Beispielimplementierung in Java (nur mit der Implementierung im Beispiel getestet, kann Fehler enthalten). Die Implementierung basiert auf den obigen Antworten.

import java.util.Arrays;

public class SmallestSnippet {
    WordIndex[] words; //merged array of word occurences

    public enum Word {W1, W2, W3};

    public SmallestSnippet(Integer[] word1, Integer[] word2, Integer[] word3) {
        this.words = new WordIndex[word1.length + word2.length + word3.length];
        merge(word1, word2, word3);
        System.out.println(Arrays.toString(words));
    }

    private void merge(Integer[] word1, Integer[] word2, Integer[] word3) {
        int i1 = 0;
        int i2 = 0;
        int i3 = 0;
        int wordIdx = 0;
        while(i1 < word1.length || i2 < word2.length || i3 < word3.length) {
            WordIndex wordIndex = null;
            Word word = getMin(word1, i1, word2, i2, word3, i3);
            if (word == Word.W1) {
                wordIndex = new WordIndex(word, word1[i1++]);
            }
            else if (word == Word.W2) {
                wordIndex = new WordIndex(word, word2[i2++]);
            }
            else {
                wordIndex = new WordIndex(word, word3[i3++]);
            }
            words[wordIdx++] = wordIndex;
        }       
    }

    //determine which word has the smallest index
    private Word getMin(Integer[] word1, int i1, Integer[] word2, int i2, Integer[] word3,
            int i3) {
        Word toReturn = Word.W1;
        if (i1 == word1.length || (i2 < word2.length && word2[i2] < word1[i1])) {
            toReturn  = Word.W2;
        }
        if (toReturn == Word.W1 && i3 < word3.length && word3[i3] < word1[i1])
        {
            toReturn = Word.W3;
        }
        else if (toReturn == Word.W2){
            if (i2 == word2.length || (i3 < word3.length && word3[i3] < word2[i2])) {
                toReturn = Word.W3;
            }
        }
        return toReturn;
    }

    private Snippet calculate() {
        int start = 0;
        int end = 0;
        int max = words.length;
        Snippet minimum = new Snippet(words[0].getIndex(), words[max-1].getIndex());
        while (start < max)
        {
            end = start;
            boolean foundAll = false;
            boolean found[] = new boolean[Word.values().length];
            while (end < max && !foundAll) {
                found[words[end].getWord().ordinal()] = true;
                boolean complete = true;
                for (int i=0 ; i < found.length && complete; i++) {
                    complete = found[i];
                }
                if (complete)
                {
                    foundAll = true;
                }
                else {
                    if (words[end].getIndex()-words[start].getIndex() == minimum.getLength())
                    {
                        // we won't find a minimum no need to search further
                        break;
                    }
                    end++;
                }
            }
            if (foundAll && words[end].getIndex()-words[start].getIndex() < minimum.getLength()) {
                minimum.setEnd(words[end].getIndex());
                minimum.setStart(words[start].getIndex());
            }
            start++;
        }
        return minimum;

    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        Integer[] word1 = {1,4,5};
        Integer[] word2 = {3,9,10};
        Integer[] word3 = {2,6,15};
        SmallestSnippet smallestSnippet = new SmallestSnippet(word1, word2, word3);
        Snippet snippet = smallestSnippet.calculate();
        System.out.println(snippet);

    }
}

Hilfsklassen:

public class Snippet {

    private int start;

    private int end;

//getters, setters etc

    public int getLength()
    {
        return Math.abs(end - start);
    }
}

public class WordIndex
{
    private SmallestSnippet.Word word;
    private int index;
    public WordIndex(SmallestSnippet.Word word, int index) {

        this.word = word;
        this.index = index;
    }
}