Schnellster Algorithmus zum Suchen einer Zeichenfolge in einem String-Array?

Diese Frage bezieht sich nur auf den Algorithmus. In Pseudo-Code ist wie folgt:Schnellster Algorithmus zum Suchen einer Zeichenfolge in einem String-Array?

A = Array of strings; //let's say count(A) = N 
S = String to find; //let's say length(S) = M 

for (Index=0; Index<count(A); Index++) 
    if (A[Index]==S) { 
    print "First occurrence at index\x20"+Index; 
    break; 
    }

Dies erfordert für die Schleife N mal String-Vergleich (oder Byte-Vergleich N * M-mal, O (N * M)). Dies ist schlecht, wenn Array A viele Elemente enthält oder wenn String S zu lang ist.

Gibt es eine bessere Methode, um das erste Auftreten herauszufinden? Ein Algorithmus bei O (K * logK) ist OK, aber vorzugsweise bei O (K) oder am besten bei O (logK), wobei K entweder N oder M ist. Es macht mir nichts aus, andere Strukturen hinzuzufügen oder eine Datenverarbeitung vor der Vergleichsschleife durchführen.

Quelle

2012-04-28 jondinham

"Wenn String S ist zu lang" ist irrelevant, es sei denn, es gibt viele Strings in 'A 'mit der gleichen Länge und einem identischen langen Präfix. (String-Gleichheitsprüfungen können sofort beendet werden, wenn die Längen unterschiedlich sind oder sobald eine Abweichung gefunden wird.) – Dougal

Warum verwenden Sie '\ x20' anstelle eines Leerzeichens? Ich bin neugierig :-) –

oh ja, die Vergleichszeit hängt mehr von den Längen der Strings in Array A – jondinham

Sie könnten das gesamte Array von Strings in einen endlichen Automaten konvertieren, wobei die Übergänge die Zeichen der Strings sind und den kleinsten Index der Strings, die einen Zustand erzeugt haben, in den Zustand schreiben. Dies erfordert viel Zeit und kann als Indizierung angesehen werden.

Quelle

2012-04-28 18:42:49 Reactormonk

Häufiger bezeichnet als ein [Trie] (http://en.wikipedia.org/wiki/Trie). – Dougal

[f] lex kann Ihnen helfen, dieses DFA zu erstellen. – wildplasser

@Dougal Danke für den Namen, wusste das nicht. – Reactormonk

Setzen Sie die Strings in eine Hash-basierte Menge, und testen Sie, ob eine gegebene Zeichenfolge in der Menge enthalten ist, sollten Sie mehr oder weniger konstante Leistung geben, sobald die Menge erstellt wird.

Quelle

2012-04-28 18:40:46 Bill

Wenn Sie den Index finden möchten, verwenden Sie ein Hash-basiertes Wörterbuch von Strings -> ersten Auftreten. – Dougal

aber ich habe ein bisschen Angst, dass einige 2 Elemente den gleichen Hash-Wert haben können – jondinham

Nun, Sie müssen immer noch den endgültigen Vergleich, bei gleichen Hash-Werten. – wildplasser

Sie können zuerst das Array von Strings sortieren, das die Zeit O (m * nlogn) benötigt. Und nachdem A sortiert ist, können Sie anstelle der linearen Suche eine binäre Suche durchführen, die die Gesamtlaufzeit auf O (m * logn) reduzieren könnte.

Der Vorteil dieser Methode ist, dass es sehr einfach zu implementieren ist. Zum Beispiel in Java können Sie dies mit nur zwei Zeilen Code:

Arrays.sort(A); 
int index = Arrays.binarySearch(A, "S");

Quelle

2012-04-28 18:57:44 Nova2358

die Sortierung vor der binären Suche dauert eine große Zeit, nicht wahr – jondinham

@PaulDinh Es dauert O (M N log N) Zeit. – Dougal

@PaulDinh Ich denke in der Praxis ist die Zeit in Ordnung. Es dauert im schlimmsten Fall O (M N log N) Zeit. Aber das Laden der ganzen Zeichenfolge benötigt M * N Zeit, so dass es nur log n mal länger als IO ist. In den meisten Fällen ist log n wirklich klein, vielleicht sogar schneller als in der Praxis einen Trie oder eine Hashtable zu erstellen. Wenn Sie sich Gedanken über die Komplexität der theoretischen Zeit machen, kostet der Aufbau eines Trie oder Hashtables O (M * N) Zeit. – Nova2358

Sie ein Self-balancing binary search tree nutzen könnte. Die meisten Implementierungen haben O (log (n)) zum Einfügen und O (log (n)) zum Suchen.

Wenn Ihr Set nicht sehr groß ist und Sie eine gute Hash-Funktion für Ihre Werte haben, ist das Hash-basierte Set eine bessere Lösung, denn in diesem Fall müssen Sie O (1) einfügen und O (1) suchen. Aber wenn Ihre Hash-Funktion schlecht ist oder Ihre Menge zu groß ist, wird O (n) eingefügt und O (n) gesucht.

Quelle

2012-04-28 19:02:57

Der beste Weg, so schnell wie möglich zu suchen, das Array sortiert haben, ist, wie Sie beschreiben, scheint es von vornherein keine möglichen Informationen zu sein, die

Sortierung für einige Heuristik oder Einschränkungen bei der Suche erlauben würde, das Array zuerst (Quicksort zum Beispiel, O (NlogN)), und binäre Suche nächste O (log (N))

Quelle

2012-04-28 19:06:13 jpmuc

Schnellster Algorithmus zum Suchen einer Zeichenfolge in einem String-Array?

Antwort

Verwandte Themen