was ist die schnellste Stringsammlung Struktur / Algorithmus für Startswith und / oder enthält Suchvorgänge

9

Ich habe folgende Situation: Ich habe eine große Sammlung von Streichern (sagen wir 250.000+) mit einer durchschnittlichen Länge von vielleicht 30. Was ich tun muss, ist, viele Suchen innerhalb dieser zu machen .. meistens werden diese von StartsWith und Contains Art sein.

Die Sammlung ist zur Laufzeit statisch. Das bedeutet, dass das erste Lesen und Füllen der Sammlung der Wahl nur einmal durchgeführt wird. Daher ist die Leistung des Aufbaus der Datenstruktur absolut nicht wichtig. Speicher ist auch kein Problem: was bedeutet auch, dass es mir nichts ausmacht, zwei Sammlungen mit den gleichen Daten in jedem Fall (wie einer für die Startswith und andere für enthält). Wichtig ist nur die Durchführung der Suchen, die alle Elemente zurückgeben sollen, die der Suchbedingung entsprechen.

Für den Anfang traf ich auf einen Trie oder Radix-Baum .. aber vielleicht gibt es noch bessere Möglichkeiten?

Für contains .. Ich habe noch keine gute Idee (neben dem Ausführen einer linq Abfrage auf einer Liste, die nicht sehr schnell mit dieser Menge an Daten sein wird).

Vielen Dank im Voraus alle!

update: Ich habe einen wichtigen Teil vergessen: mit Contains meine ich keine genauen Übereinstimmungen in der Sammlung .. aber ich möchte alle Strings in der Sammlung finden, die den angegebenen Suchstring enthalten

    
Mikk 03.03.2013, 22:49
quelle

1 Antwort

3

Wenn Sie einen Suffixbaum erstellen, können Sie in O(1) parallel zu allen Strings eine Teilstringsuche durchführen. Das pedantische in mir kann nicht helfen, aber es ist wirklich O(n + m) , wobei n die Anzahl der Zeichenfolgen ist, die zu Ihrer Teilzeichenfolge passen und m die Größe der abgefragten Teilzeichenfolge ist.

Was ist ein Suffixbaum, den Sie fragen? In seiner grundlegendsten Implementierung ist es ein Trie mit einer schickeren Einfügemethode: Zusätzlich zum Hinzufügen eines Strings fügt er auch jedes mögliche Suffix dieses Strings zum Trie hinzu. Auf dieser Datenstruktur wird eine Teilstringsuche zu einer Präfixsuche aller möglichen Suffixe. Da Sie auch Präfixsuchen durchführen möchten, sollten Sie vor jeder eingefügten Zeichenfolge und den Abfrageteilstrings ein Sonderzeichen hinzufügen. Mit dem Sonderzeichen können Sie zwischen einem Suffix und einem vollständigen String unterscheiden.

Obwohl diese Implementierung einer Suffix-Struktur bemerkenswert einfach ist, ist sie auch sehr ineffizient ( O(n^2) Speicherplatz und Build-Zeit). Glücklicherweise gibt es andere effizientere Implementierungen, die die räumlichen und zeitlichen Grenzen stark reduzieren können. Einer davon, der Algorithmus von Ukkonen, ist in SO so gut erklärt antwort und bringt den gebundenen Bereich auf O(n) . Sie können auch in Suffix-Arrays schauen, die eine äquivalente, aber effizientere Darstellung von Suffix-Bäumen darstellen.

Obwohl ich weiß, dass es viel mehr Implementierungen von Suffix-Bäumen gibt (von denen eine wahrscheinlich den besten Punkt für Ihren Anwendungsfall treffen würde), kenne ich sie einfach nicht. Ich empfehle Ihnen, etwas zu diesem Thema zu recherchieren, bevor Sie sich auf eine Implementierung einigen.

    
Ze Blob 03.03.2013, 23:59
quelle