Untertitel in einer größeren Sammlung finden?

491
Quelle (EN)
Steve Jackson

Ich habe ein flaches Array von <1000 Elementen und muss die Indizes eines kleineren Tupels / Arrays innerhalb des Arrays finden. Das zu findende Tupel kann eine unterschiedliche Länge haben (im Allgemeinen zwischen 2 und 5 Elementen, Reihenfolge ist wichtig).

Dies ist meine erste naive Implementierung. Meine Hauptanliegen sind:

  1. Dies scheint ein CS 101-Problem zu sein, daher bin ich mir ziemlich sicher, dass ich es übertreibe.
  2. Lesbarkeit. Ich kann das in kleinere Methoden unterteilen, aber es ist im Wesentlichen eine Hilfsfunktion in einer viel größeren Klasse. Ich denke, ich könnte es in seine eigene Klasse extrahieren, aber das fühlt sich auch wie übertrieben an. Es ist einfach zu lang für mich, das Ganze in einem Durchgang zu erledigen.

public int[] findIndices(final Object[] toSearch, final Object[] toFind) 
{
    Object first = toFind[0];

    List<Integer> possibleStartIndices = new ArrayList<Integer>();
    int keyListSize = toFind.length;
    for (int i = 0; i <= toSearch.length - keyListSize; i++) 
    {
        if (first.equals(toSearch[i])) 
        {
            possibleStartIndices.add(i);
        }
    }

    int[] indices = new int[0];
    for (int startIndex : possibleStartIndices) 
    {
        int endIndex = startIndex + keyListSize;
        Object[] possibleMatch = Arrays.copyOfRange(toSearch, startIndex, endIndex);
        if (Arrays.equals(toFind, possibleMatch)) {
            indices = toIndexArray(startIndex, endIndex);
            break;
        }
    }
    return indices;
}

private int[] toIndexArray(final int startIndex, final int endIndex) 
{
    int[] indices = new int[endIndex - startIndex];
    for (int i = 0; i < indices.length; i++)
        indices[i] = startIndex + i;

    return indices;
}
Antworten
14
Was ist mit dem "überlappenden" Fall, dh, sollte die Suche nach "AA" in "AAA" 0 und 1 als "Start" -Indizes zurückgeben? Wie es derzeit in Ihrem Code enthalten ist, sollte dies der Fall sein. Wenn es sich jedoch nicht um eine Anforderung handelt (dh der gesuchte String kann nur ein "Stapel" von gesuchten String-Kopien mit einigen anderen Strings außerhalb und zwischen ihnen sein), kann dies möglicherweise Auswirkungen auf die Wirksamkeit des Algorithmus und die Größe des implementierenden Codes. mlvljr vor 9 Jahren 1
@mlvljr Überlappungen sind in dieser Datenmenge kein Problem. es bricht ab und fällt zurück, sobald der Suchschlüssel übereinstimmt Steve Jackson vor 9 Jahren 0
Dies scheint ein guter Ort für die Suche nach Boyer-Moore zu sein. mtnygard vor 9 Jahren 0
sehr verlockend. Meine Angst ist, ich werde die Wartungsprogrammierer verwirren, wenn sie zum Code zurückkehren und meinen Link zu einem String-Suchalgorithmus in Code finden, der keine Strings analysiert (die Objekte sind unterschiedliche Typen). Wenn dies geschäftskritisch wäre, würde ich es trotzdem funktionieren lassen. Auch großes +1 für das Ausheben der Antwort auf # 1 aus meinem neuronalen Offline-Speicher (wahrscheinlich Band). Steve Jackson vor 9 Jahren 0

4 Antworten auf die Frage

5
Ron

Hier ist eine O (mn) -Lösung. In Anbetracht der Tatsache, dass der Heuhaufen etwa 1000 lang ist und die Nadel 5 oder kleiner ist, ist der einfachste Code für die Suche wahrscheinlich der beste. Wenn Gleichheitstests jedoch teuer sind, können wir dies abschwächen, auch wenn ich mir nicht sicher bin, ob der Wechsel zu KMP oder BM angesichts der Tatsache, dass wir uns hier mit Object beschäftigen, so sehr helfen wird.

// assumes no null entries
// returns starting index of first occurrence of needle within haystack or -1
public int indexOf(final Object[] haystack, final Object[] needle) 
{
    foo: for (int a = 0; a < haystack.length - needle.length; a++) {
        for (int b = 0; b < needle.length; b++) {
            if (!haystack[a+b].equals(needle[b])) continue foo;
        }
        return a;
    }
    return -1;
}
+1 für den Verzicht auf `copyOfRange / Arrays.equals`, das vorzeitige Stoppen von search needle.length und die korrekte Behandlung wiederholter Werte in der Suchzeichenfolge. Ich denke jedoch, dass ein BM-Impl hilfreich sein kann. Bert F vor 9 Jahren 0
Vielen Dank für Ihren Kommentar. Ich stimme zu, dass BM von Nutzen sein könnte. Ich habe es im Kontext von Object-Elementen nicht als Zeichen gefunden, aber es sieht nach einem Gewinn aus. Ron vor 9 Jahren 0
Ich werde mit diesem gehen. Ich bin nicht sicher, was die Lesbarkeit angeht (normalerweise vermeide ich Etiketten), aber es ist definitiv besser als meine. Steve Jackson vor 9 Jahren 0
Sollte das nicht "b <(needle.length + a)" sein? mlvljr vor 9 Jahren 1
@ Bert F Worum geht es beim Umgang mit wiederholten Werten in Suchstring? mlvljr vor 9 Jahren 0
@mlvljr - Der anfängliche Stich der Suchalgorithmen einer Person kann einen wiederholten Wert in der Suchzeichenfolge häufig nicht verarbeiten, z. B. `indexOf (" aaab "," aab ")` sollte [1] `zurückgeben. Bei einigen Versuchen wird die mögliche Übereinstimmung bei [1] versäumt, da eine teilweise Übereinstimmung ([0] bis [1]) bis [2] erfolgreich ist. Bert F vor 9 Jahren 0
@Steve das Label könnte vermieden werden: bewegen Sie decl 'int b' außerhalb der inneren Schleife, ändern Sie 'weiter Foo;' in 'Brechen; `, ändern Sie' A 'zurück in'` Wenn (b> = needle.length) geben Sie a zurück ; `. Es ist Ihr Aufruf, ob das Ergebnis besser lesbar ist als das Etikett. Bert F vor 9 Jahren 0
@Bert Ok, danke. Übrigens, ist es nur mir auf der "needle.length + a" vs. "needle.length" verdächtig? Warum verwenden Sie nicht nur eine separate Routine wie: `boolean is_at (finales Objekt [] Heuhaufen, finales Objekt [] Nadel, int haystack_index)`? mlvljr vor 9 Jahren 0
@mlvljr du hast recht - es ist kaputt. Ich denke, der Fix sollte sein: `int b = a` sollte sich in` int b = 0` ändern und `haystack [b]` sollte in `haystack [a + b]` geändert werden. "b" ist der Index in "needle", also muss "b" von "0" bis "needle.length" reichen. "a" ist der Index für "Heuhaufen" und die innere Schleife muss den Versatz "b" hinzufügen. Der Index in "Heuhaufen" sollte also "a + b" sein. Ich habe eine Bearbeitung eingereicht, um das Problem zu beheben. Bert F vor 9 Jahren 1
Ich habe eine BM-Version implementiert, die jedoch sehr viel komplexer ist (nur in einigen Testfällen schlechter). Bert F vor 9 Jahren 1
4
Pablo

Als schnellen Tipp würde ich vorschlagen, dass Sie den Schritt des Auffindens möglicher Startindizes überspringen.

Stattdessen durchsuchen Sie die gesamte Liste bereits, um mögliche Startindizes zu finden. Warum prüfen Sie dann diesen Index nicht sofort, wenn Sie ihn finden? Wäre so etwas wie:

public int[] findIndices(final Object[] toSearch, final Object[] toFind) 
{
    Object first = toFind[0];

    int keyListSize = toFind.length;
    for (int startIndex = 0; startIndex <= toSearch.length - keyListSize; startIndex++) 
    {
        if (first.equals(toSearch[startIndex])) 
        {
            int endIndex = startIndex + keyListSize;
            Object[] possibleMatch = Arrays.copyOfRange(toSearch, startIndex, endIndex);
            if (Arrays.equals(toFind, possibleMatch)) {
                return toIndexArray(startIndex, endIndex);
            }
        }
    }

    return new int[0];
}
Guter Fang. Als ich anfing, es zu schreiben, plante ich, es mehrere Male abzubilden / zu verkleinern, um deutlich zu machen, was passiert. Ich habe in der Mitte den Kurs gewechselt, aber nicht umgestaltet. Steve Jackson vor 9 Jahren 0
3
Marcus Frödin

Originalcode bearbeiten ist falsch. Unten besser hinzugefügt.

So etwas könnte es in einem Durchgang tun (ich denke, ich habe es nicht zu Tode geprüft). Beachten Sie, dass ich nur den ersten Index zurückgeben kann, da die nächsten einfach berechnet werden können, indem Sie einfach ein neues Array i, i + 1, ..., i + n-1 usw. erstellen. Einfacher (und langsamer) als Boyer Moore, aber immer noch O (n):

public static <T> int indexOf(final T[] target, final T[] candidate) {

    for (int t = 0, i = 0; i < target.length; i++) {
        if (target[i].equals(candidate[t])) {
            t++;
            if (t == candidate.length) {
                return i-t+1;
            }
        } else {
            t = 0;
        }
    }

    return -1;
}

Edit: Das sollte besser funktionieren, nein? Es ist nicht so sauber und einfach, aber jetzt bin ich sicherer, dass es tatsächlich stimmt. Was passiert ist, wenn wir ausfallen, gehen wir zurück und starten neu.

public static <T> int indexOf(final T[] target, final T[] candidate) {
    int t = 0, i = 0;    
    while (i < target.length)
    {
        if (target[i].equals(candidate[t])) {
            t++;
            if (t == candidate.length) {
                return i-t+1;
            }
        } else {
            i -= t;
            t = 0;
        }
        i++;
    }    
    return -1;
}
Schlägt fehl, wenn wiederholte Werte in der Suchzeichenfolge angezeigt werden: `indexOf (" aaab "," aab ")` sollte 1 zurückgeben. Bert F vor 9 Jahren 0
Guter Fang. Entsprechend aktualisiert. Marcus Frödin vor 9 Jahren 0
Ich vermute, es wird immer noch mit mir rauskommen und einige Invarianten vermissen und mir wieder einen Arsch machen ... Ich werde den Mund halten. Marcus Frödin vor 9 Jahren 0
1
MattGrommes

Bei weniger als 1000 Artikeln würde ich sagen, dass Pablo die richtige Idee hat, nur den ersten Durchlauf zu prüfen, es sei denn, die Überprüfung jedes Artikels ist zu teuer. Dies eliminiert O (n) aus dem Algorithmus. Für eine größere Liste oder wenn die Überprüfung der einzelnen Elemente teuer ist, kann etwas komplizierteres Vorgehen wie ein Boyer-Moore-Algorithmus, wie er von mtnygard vorgeschlagen wird, angebracht sein.

Verwandte Probleme