Datenstruktur oder Algorithmus zum schnellen Auffinden von Unterschieden zwischen Zeichenfolgen

19

Ich habe ein Array von 100.000 Zeichenfolgen, die alle die Länge . Ich möchte jede Zeichenfolge mit jeder anderen Zeichenfolge vergleichen, um festzustellen, ob sich zwei Zeichenfolgen um ein Zeichen unterscheiden. Im Moment, wenn ich jede Zeichenfolge zum Array hinzufüge, überprüfe ich sie mit jeder Zeichenfolge, die sich bereits im Array befindet und eine zeitliche Komplexität von .n ( n - 1 )kn(n-1)2k

Gibt es eine Datenstruktur oder einen Algorithmus, mit denen Zeichenfolgen schneller miteinander verglichen werden können, als ich es bereits tue?

Einige zusätzliche Informationen:

  • Reihenfolge ist wichtig: abcdeund xbcdeunterscheiden sich um 1 Zeichen, während abcdeund edcbaunterscheiden sich um 4 Zeichen.

  • Für jedes Zeichenfolgenpaar, das sich um ein Zeichen unterscheidet, entferne ich eine dieser Zeichenfolgen aus dem Array.

  • Im Moment suche ich nach Zeichenfolgen, die sich nur um 1 Zeichen unterscheiden. Es wäre jedoch schön, wenn der Unterschied von 1 Zeichen auf beispielsweise 2, 3 oder 4 Zeichen erhöht werden könnte. In diesem Fall ist jedoch die Effizienz meiner Meinung nach wichtiger als die Möglichkeit, das Zeichenunterschiedslimit zu erhöhen.

  • k liegt üblicherweise im Bereich von 20 bis 40.

JGut
quelle
4
Das Durchsuchen eines String-Wörterbuchs mit 1 Fehler ist ein bekanntes Problem, z. B. cs.nyu.edu/~adi/CGL04.pdf
KWillets
1
20-40 Meter können ein gutes Stück Platz beanspruchen. Sie können sich einen Bloom-Filter ( en.wikipedia.org/wiki/Bloom_filter ) ansehen, um zu testen, ob entartete Zeichenfolgen - die Menge aller Elemente aus einer, zwei oder mehr Ersetzungen auf einem Test-Mer - "Vielleicht-In" oder "Auf jeden Fall" sind -nicht-in "eine Reihe von kmers. Wenn Sie ein "Vielleicht-in" erhalten, vergleichen Sie die beiden Zeichenfolgen weiter, um festzustellen, ob es sich um ein falsches Positiv handelt oder nicht. Die "definitiv nicht in" -Fälle sind echte Negative, die die Gesamtzahl der von Ihnen durchgeführten buchstabenweisen Vergleiche verringern, indem Vergleiche nur auf die potenziellen "vielleicht in" -Hits beschränkt werden.
Alex Reynolds
Wenn Sie mit einem kleineren Bereich von k arbeiten, können Sie mithilfe eines Bitsets eine Hash-Tabelle mit Booleschen Werten für alle entarteten Zeichenfolgen speichern (z. B. github.com/alexpreynolds/kmer-boolean für ein Spielzeugbeispiel). Für k = 20-40 ist der Platzbedarf für einen Bitsatz einfach zu groß.
Alex Reynolds

Antworten:

12

Es ist möglich, die Worst-Case-Laufzeit von zu erreichen .O(nkLogk)

Fangen wir einfach an. Wenn Sie sich für eine einfach zu implementierende Lösung interessieren, die für viele Eingaben, aber nicht für alle, effizient ist, finden Sie hier eine einfache, pragmatische und einfach zu implementierende Lösung, die in der Praxis für viele Situationen ausreicht. Im schlimmsten Fall wird jedoch auf die quadratische Laufzeit zurückgegriffen.

Nehmen Sie jede Zeichenfolge und speichern Sie sie in einer Hash-Tabelle, die auf der ersten Hälfte der Zeichenfolge angegeben ist. Dann iterieren Sie über die Eimer mit den Hashtabellen. Überprüfen Sie für jedes Zeichenfolgenpaar im selben Bucket, ob sie sich in einem Zeichen unterscheiden (dh, ob sich ihre zweite Hälfte in einem Zeichen unterscheidet).

Nehmen Sie dann jede Zeichenfolge und speichern Sie sie in einer Hash-Tabelle, diesmal in der zweiten Hälfte der Zeichenfolge. Überprüfen Sie erneut jedes Saitenpaar im selben Eimer.

Unter der Annahme , werden die Saiten gut verteilt ist , wird die Laufzeit wahrscheinlich etwa . Wenn es ein Paar von Zeichenfolgen gibt, die sich um 1 Zeichen unterscheiden, wird es in einem der beiden Durchgänge gefunden (da sie sich nur um 1 Zeichen unterscheiden, muss sich dieses unterschiedliche Zeichen entweder in der ersten oder in der zweiten Hälfte der Zeichenfolge befinden). Die zweite oder erste Hälfte der Zeichenfolge muss also identisch sein. Im ungünstigsten Fall (z. B. wenn alle Zeichenfolgen mit denselben k / 2 Zeichen beginnen oder enden ) wird die Laufzeit auf 0 ( n 2 k ) herabgesetzt, sodass die Laufzeit im ungünstigsten Fall keine Verbesserung der Brute Force darstellt .O(nk)k/2O(n2k)

Wenn in einem Bucket zu viele Zeichenfolgen enthalten sind, können Sie zur Leistungsoptimierung denselben Vorgang rekursiv wiederholen, um nach einem Paar zu suchen, das sich um ein Zeichen unterscheidet. Der rekursive Aufruf erfolgt auf Zeichenketten der Länge .k/2

Wenn Ihnen die Worst-Case-Laufzeit am Herzen liegt:

Mit der obigen Leistungsoptimierung glaube ich, dass die Laufzeit im ungünstigsten Fall .O(nkLogk)

DW
quelle
3
Wenn sich Strings die gleiche erste Hälfte teilen, was im wirklichen Leben durchaus vorkommen kann, haben Sie die Komplexität nicht verbessert. Ω(n)
einpoklum - wieder Monica
@einpoklum, sicher! Deshalb schrieb ich in meinem zweiten Satz die Aussage, dass es im schlimmsten Fall auf die quadratische Laufzeit zurückgreift, sowie in meinem letzten Satz, wie man die Komplexität von schlimmsten Fall erreicht, wenn es dich interessiert über den schlimmsten Fall. Aber ich glaube, ich habe das nicht sehr deutlich ausgedrückt - also habe ich meine Antwort entsprechend bearbeitet. Ist es jetzt besser? O(nkLogk)
DW
15

Meine Lösung ähnelt der von j_random_hacker, verwendet jedoch nur einen einzigen Hash-Satz.

Ich würde einen Hash-Satz von Zeichenfolgen erstellen. Fügen Sie für jede Zeichenfolge in der Eingabe die Menge Zeichenfolgen hinzu. Ersetzen Sie in jeder dieser Zeichenfolgen einen der Buchstaben durch ein Sonderzeichen, das in keiner der Zeichenfolgen enthalten ist. Überprüfen Sie beim Hinzufügen, ob sie nicht bereits im Satz enthalten sind. Wenn dies der Fall ist, haben Sie zwei Zeichenfolgen, die sich nur um (höchstens) ein Zeichen unterscheiden.k

Ein Beispiel mit Strings 'abc', 'adc'

Für abc fügen wir '* bc', 'a * c' und 'ab *' hinzu

Für adc addieren wir '* dc', 'a * c' und 'ad *'

Wenn wir 'a * c' zum zweiten Mal hinzufügen, bemerken wir, dass es bereits in der Menge enthalten ist, sodass wir wissen, dass es zwei Zeichenfolgen gibt, die sich nur durch einen Buchstaben unterscheiden.

Die Gesamtlaufzeit dieses Algorithmus beträgt . Dies liegt daran, dass wir k neue Zeichenfolgen für alle n Zeichenfolgen in der Eingabe erstellen . Für jede dieser Zeichenfolgen müssen wir den Hash berechnen, der normalerweise O ( k ) -Zeit benötigt.O(nk2)knO(k)

Das Speichern aller Zeichenfolgen benötigt Platz.O(nk2)

Weitere Verbesserungen

Wir können den Algorithmus weiter verbessern, indem wir die geänderten Zeichenfolgen nicht direkt speichern, sondern ein Objekt mit einem Verweis auf die ursprüngliche Zeichenfolge und den Index des maskierten Zeichens. Auf diese Weise brauchen wir nicht alle Saiten zu schaffen und wir brauchen nur Raum alle Objekte zu speichern.O(nk)

Sie müssen eine benutzerdefinierte Hash-Funktion für die Objekte implementieren. Wir können die Java-Implementierung als Beispiel nehmen, siehe die Java-Dokumentation . Der Java-Hashcode multipliziert den Unicode-Wert jedes Zeichens mit (wobei k die Zeichenfolgenlänge und i der Index des Zeichens auf einer Basis ist. Beachten Sie, dass sich jede geänderte Zeichenfolge nur um ein Zeichen vom Original unterscheidet. Wir können dies leicht berechnen den Beitrag dieses Zeichens zum Hash-Code. Wir können diesen subtrahieren und stattdessen unser Maskierungszeichen hinzufügen. Für die Berechnung wird O ( 1 ) benötigt . Dadurch können wir die Gesamtlaufzeit auf O ( n) verringern31k-ichkichO(1)O(nk)

Simon Prins
quelle
4
@ JollyJoker Ja, Raum ist ein Problem mit dieser Methode. Sie können den Speicherplatz reduzieren, indem Sie nicht die geänderten Zeichenfolgen, sondern ein Objekt mit einem Verweis auf die Zeichenfolge und den maskierten Index speichern. Das sollte dir O (nk) Raum lassen.
Simon Prins
Um die Hashes für jede Zeichenfolge in O ( k ) zu berechnen , benötigen Sie vermutlich eine spezielle hausgemachte Hash-Funktion (z. B. den Hash der ursprünglichen Zeichenfolge in O ( k ) zu berechnen und ihn dann mit jeder gelöschten XOR-Funktion zu versehen Zeichen jeweils in O ( 1 ) (obwohl dies auf andere Weise wahrscheinlich eine ziemlich schlechte Hash-Funktion ist). Übrigens ist dies meiner Lösung ziemlich ähnlich, aber mit einer einzelnen Hash-Tabelle anstelle von k separaten und Ersetzen eines Zeichens durch "*", anstatt es zu löschen. kO(k)O(k)O(1)k
j_random_hacker
@ SimonPrins Mit benutzerdefinierten equalsund hashCodeMethoden, die funktionieren könnten. Nur die a * b-artige Zeichenfolge in diesen Methoden zu erstellen, sollte es kugelsicher machen; Ich vermute, dass einige der anderen Antworten hier Hash-Kollisionsprobleme haben werden.
JollyJoker
1
@DW Ich habe meinen Beitrag geändert, um der Tatsache Rechnung zu tragen, dass die Berechnung der Hashes -Zeit benötigt, und eine Lösung hinzugefügt, um die Gesamtlaufzeit wieder auf O ( n k ) zu senken . O(k)O(nk)
Simon Prins
1
@SimonPrins Der schlimmste Fall könnte möglicherweise nk ^ 2 sein, da die String-Gleichheit in hashset.contains überprüft wird, wenn Hashes kollidieren. Natürlich ist der schlimmste Fall , wenn jede Saite exakt das gleiche Hash hat, der einen ziemlich handgefertigt Satz Saiten erfordern würde, vor allem für den gleichen Hash zu erhalten *bc, a*c, ab*. Ich frage mich, ob es unmöglich gezeigt werden könnte?
JollyJoker
7

Ich würde Hashtabellen H 1 , ... , H k erstellen , von denen jede eine ( k - 1 ) -lange Zeichenfolge als Schlüssel und eine Liste von Zahlen (Zeichenfolgen-IDs) als Wert hat. Die Hash-Tabelle H i enthält alle Zeichenfolgen, die bisher verarbeitet wurden, jedoch mit dem Zeichen an der Position, an der ich gelöscht habe . Wenn beispielsweise k = 6 ist , enthält H 3 [ A B D E F ] eine Liste aller bisher gesehenen Zeichenfolgen mit dem Muster AkH1,,Hk(k-1)Hichichk=6H3[EINBDEF] , wobei "beliebiges Zeichen" bedeutet. Dann, um die j- te Eingabezeichenfolge s j zu verarbeiten :EINBDEFjsj

  1. Für jedes im Bereich von 1 bis k : ichk
    • Bilden Sie die Zeichenfolge indem Sie das i- te Zeichen aus s j löschen .sjichsj
    • Suchen Sie nach . Jede String-ID identifiziert hier einen Original-String, der entweder gleich s ist oder sich nur an Position i unterscheidet . Geben Sie diese als Übereinstimmungen für die Zeichenfolge s j aus . (Wenn Sie exakte Duplikate ausschließen möchten, machen Sie den Werttyp der Hashtabellen zu einem Paar (Zeichenfolgen-ID, gelöschtes Zeichen), damit Sie testen können, ob das gleiche Zeichen gelöscht wurde, wie wir es gerade aus s j gelöscht haben .)Hich[sj]sichsjsj
    • Legen Sie in H i für zukünftige Anfragen zu verwenden.jHich

Wenn wir jeden Hash-Schlüssel explizit speichern, müssen wir den -Raum verwenden und damit mindestens zeitliche Komplexität haben. Aber wie von Simon Prins beschrieben , ist es möglich, eine Reihe von Modifikationen an einer Zeichenkette (in seinem Fall als Ändern einzelner Zeichen in , in meinem Fall als Löschen beschrieben) implizit so darzustellen, dass alle k Hash-Schlüssel für eine bestimmte Zeichenkette nur brauchen O ( k ) Raum, was zu O ( n k ) Raum insgesamt führt und die Möglichkeit von O ( n k ) eröffnetO(nk2)*kO(k)O(nk)O(nk)Zeit auch. Um diese Zeitkomplexität zu erreichen, müssen die Hashes für alle Variationen einer Länge k in O ( k ) berechnet werden. Dies kann beispielsweise mithilfe von Polynom-Hashes erfolgen, wie von DW vorgeschlagen (und das ist der Fall) wahrscheinlich viel besser als einfach das gelöschte Zeichen mit dem Hash für die ursprüngliche Zeichenkette zu XOREN.kkO(k)

Der implizite Repräsentationstrick von Simon Prins bedeutet auch, dass das "Löschen" der einzelnen Zeichen nicht tatsächlich ausgeführt wird, sodass wir die übliche Array-basierte Repräsentation einer Zeichenfolge ohne Leistungseinbußen verwenden können (anstelle von verknüpften Listen, wie ich ursprünglich vorgeschlagen hatte).

j_random_hacker
quelle
2
Gute Lösung. Ein Beispiel für eine geeignete maßgeschneiderte Hash-Funktion wäre ein Polynom-Hash.
DW
Thanks @DW Könnten Sie vielleicht ein bisschen klarstellen, was Sie unter "Polynom-Hash" verstehen? Wenn ich den Begriff google, habe ich nichts gefunden, was definitiv schien. (Wenn Sie möchten, können Sie meinen Beitrag auch direkt bearbeiten.)
j_random_hacker
1
Lesen Sie die Zeichenfolge einfach als Basis number modulo p , wobei p eine Primzahl ist, die kleiner als Ihre Hashmap-Größe ist, und q eine primitive Wurzel von p ist und q größer als die Alphabetgröße ist. Es wird "Polynom-Hash" genannt, weil es der Auswertung des Polynoms gleicht, dessen Koeffizienten durch die Zeichenfolge bei q gegeben sind . Ich lasse es als Übung, um herauszufinden, wie alle gewünschten Hashes in O ( k ) -Zeit berechnet werden. Beachten Sie, dass dieser Ansatz nicht immun gegen einen Gegner ist, es sei denn, Sie wählen beide p , q zufällig aus, um die gewünschten Bedingungen zu erfüllen.qppqpqqO(k)p,q
user21820
1
Ich denke, diese Lösung kann weiter verfeinert werden, indem beobachtet wird, dass nur eine der k Hash-Tabellen gleichzeitig vorhanden sein muss, wodurch der Speicherbedarf verringert wird.
Michael Kay
1
@MichaelKay: Das funktioniert nicht, wenn Sie die Hashes der möglichen Änderungen eines Strings in der O ( k ) -Zeit berechnen möchten . Sie müssen sie noch irgendwo aufbewahren. Wenn Sie also jeweils nur eine Position prüfen, benötigen Sie k- mal so lange, wie Sie alle Positionen zusammen mit k- mal so vielen Hashtabelleneinträgen prüfen . kO(k)kk
user21820
2

Hier ist ein robusterer Hashtable-Ansatz als die Polynom-Hash-Methode. Generieren Sie zunächst zufällige positive ganze Zahlen r 1 .. k , die mit der Hash-Tabellengröße M übereinstimmen . Es gilt nämlich 0 r i < M . Dann hash jede Saite x 1 .. k bis ( Σ k i = 1 x i r i ) mod M . Es gibt fast nichts, was ein Gegner tun kann, um sehr ungleichmäßige Kollisionen zu verursachen, da Sie zur Laufzeit r 1 .. k und damit k erzeugenkr1..kM0ri<Mx1..k(ich=1kxichrich)modMr1 ..kkerhöht die maximale Wahrscheinlichkeit einer Kollision zweier beliebiger von verschiedenen Saiten schnell geht . Es ist auch offensichtlich, wie in O ( k ) -Zeit alle möglichen Hashes für jede Zeichenfolge mit einem geänderten Zeichen berechnet werden .1/MO(k)

Wenn Sie wirklich ein einheitliches Hashing garantieren möchten, können Sie für jedes Paar ( i , c ) für i von 1 bis k und für jedes Zeichen c eine zufällige natürliche Zahl kleiner als M generieren und dann jede Zeichenfolge hashen x 1 .. k bis ( k i = 1 r ( i , x i ) ) mod Mr(ich,c)M(ich,c)ich1kcx1 ..k(ich=1kr(ich,xich))modM. Dann ist die Wahrscheinlichkeit der Kollision zweier beliebiger von verschiedenen Zeichenfolgen genau . Dieser Ansatz ist besser, wenn Ihr Zeichensatz im Vergleich zu n relativ klein ist .1/Mn

user21820
quelle
2

Viele der hier veröffentlichten Algorithmen belegen ziemlich viel Platz in Hash-Tabellen. Hier ist ein einfacher -Zusatzspeicher- O ( ( n lg n ) k 2 ) -Laufzeitalgorithmus.O(1)O((nlgn)k2)

Der Trick besteht darin, , einen Komparator zwischen zwei Werten a und b , der true zurückgibt, wenn a < b (lexikographisch), während das k- te Zeichen ignoriert wird . Dann ist der Algorithmus wie folgt.Ck(ein,b)einbein<bk

Sortieren Sie zunächst die Zeichenfolgen regelmäßig und führen Sie einen linearen Scan durch, um alle Duplikate zu entfernen.

Dann gilt für jedes :k

  1. Sortieren Sie die Zeichenfolgen mit als Komparator.Ck

  2. Zeichenfolgen, die sich nur in liegen jetzt nebeneinander und können in einem linearen Scan erkannt werden.k

orlp
quelle
1

Zwei Zeichenfolgen der Länge k , die sich in einem Zeichen unterscheiden, teilen sich ein Präfix der Länge l und ein Suffix der Länge m, so dass k = l + m + 1 ist .

Die Antwort von Simon Prins kodiert das alles durch das Speichern Präfix / Suffix - Kombinationen explizit, dh abcwird *bc, a*cund ab*. Das ist k = 3, l = 0,1,2 und m = 2,1,0.

Wie valarMorghulis betont, können Sie Wörter in einem Präfixbaum organisieren. Es gibt auch den sehr ähnlichen Suffixbaum. Es ist ziemlich einfach, den Baum mit der Anzahl der Blattknoten unter jedem Präfix oder Suffix zu erweitern. Dies kann in O (k) aktualisiert werden, wenn ein neues Wort eingefügt wird.

Der Grund, warum Sie diese Anzahl von Geschwistern wünschen, ist, dass Sie bei einem neuen Wort wissen, ob Sie alle Zeichenfolgen mit demselben Präfix oder alle Zeichenfolgen mit demselben Suffix aufzählen möchten. ZB für "abc" als Eingabe sind die möglichen Präfixe "", "a" und "ab", während die entsprechenden Suffixe "bc", "c" und "" sind. Wie es offensichtlich ist, ist es für kurze Suffixe besser, Geschwister im Präfixbaum aufzulisten und umgekehrt.

Wie @einpoklum hervorhebt, ist es durchaus möglich, dass alle Zeichenfolgen dasselbe k / 2- Präfix haben. Das ist für diesen Ansatz kein Problem. Der Präfixbaum ist linear bis zur Tiefe k / 2, wobei jeder Knoten bis zur Tiefe k / 2 der Vorfahr von 100.000 Blattknoten ist. Infolgedessen wird der Suffixbaum bis zu einer Tiefe von (k / 2-1) verwendet, was gut ist, da sich die Zeichenfolgen in ihren Suffixen unterscheiden müssen, da sie Präfixe gemeinsam haben.

[Bearbeiten] Wenn Sie als Optimierung das kürzeste eindeutige Präfix eines Strings ermittelt haben, wissen Sie, dass es das letzte Zeichen des Präfixes sein muss , wenn es ein anderes Zeichen gibt, und Sie hätten das nahezu doppelte gefunden, wenn Überprüfung eines kürzeren Präfixes. Wenn "abcde" also das kürzeste eindeutige Präfix "abc" hat, bedeutet dies, dass es andere Zeichenfolgen gibt, die mit "ab?" Beginnen. aber nicht mit "abc". Wenn sie sich also nur in einem Zeichen unterscheiden würden, wäre dies das dritte Zeichen. Sie müssen nicht mehr nach "abc? E" suchen.

Wenn Sie nach der gleichen Logik feststellen würden, dass "cde" ein eindeutiges kürzestes Suffix ist, müssen Sie nur das Präfix "ab" der Länge 2 und nicht die Präfixe der Länge 1 oder 3 überprüfen.

Beachten Sie, dass diese Methode nur für genau einen Zeichenunterschied funktioniert und nicht auf zwei Zeichenunterschiede verallgemeinert wird. Dabei wird ein einziges Zeichen als Trennung zwischen identischen Präfixen und identischen Suffixen verwendet.

MSalters
quelle
Schlagen Sie vor, dass wir für jede Zeichenkette und jede 1 i k den Knoten P [ s 1 , , s i - 1 ] finden , der dem Längen- ( i - 1 ) -Präfix im Präfix-Trie entspricht, und das Knoten S [ s i + 1 , ... , s k ] entsprechend der längen- ( k - i - 1 )s1ichkP[s1,,sich-1](ich-1)S[sich+1,,sk](k-ich-1)Suffix im Suffix-Trie (jedes benötigt die amortisierte -Zeit) und vergleicht die Anzahl der Nachkommen von jedem, wählt diejenige aus, die weniger Nachkommen hat, und "tastet" dann nach dem Rest des Strings in diesem Trie? O(1)
j_random_hacker
1
Was ist die Laufzeit Ihres Ansatzes? Für mich sieht es so aus, als wäre es im schlimmsten Fall quadratisch: Überlegen Sie, was passiert, wenn jeder String mit denselben Zeichen beginnt und endet . k/4
DW
Die Optimierungsidee ist clever und interessant. Hatten Sie eine spezielle Möglichkeit, den Mtaches-Check durchzuführen? Wenn "abcde" das kürzeste eindeutige Präfix "abc" hat, sollten wir nach einer anderen Zeichenfolge der Form "ab? De" suchen. Hatten Sie einen bestimmten Weg im Sinn, der effizient sein wird? Was ist die resultierende Laufzeit?
DW
@DW: Die Idee ist, dass Sie, um Zeichenfolgen in der Form "ab? De" zu finden, den Präfixbaum überprüfen, wie viele Blattknoten unter "ab" und im Suffixbaum, wie viele Knoten unter "de" vorhanden sind, und dann auswählen kleinste der beiden aufzuzählen. Wenn alle Zeichenfolgen mit denselben k / 4-Zeichen beginnen und enden; Das bedeutet, dass die ersten k / 4 Knoten in beiden Bäumen jeweils ein Kind haben. Und ja, jedes Mal, wenn Sie diese Bäume brauchen, müssen diese durchquert werden, was ein O (n * k) -Schritt ist.
MSalters
Um nach einer Zeichenfolge der Form "ab? De" im Präfix-Trie zu suchen, reicht es aus, zum Knoten für "ab" zu gelangen, und dann für jedes seiner untergeordneten prüfen, ob der Pfad "de" unter v vorhanden ist . Das heißt, Sie müssen keine anderen Knoten in diesen Unterträgern aufzählen. Dies dauert O ( a h ) Zeit, wobei a die Alphabetgröße und h die Höhe des Anfangsknotens in der Trie ist. h ist O ( k ) , wenn also die Alphabetgröße O ( n ) ist, dann ist es tatsächlich O ( n k )vvO(einh)einhhO(k)O(n)O(nk)Zeit insgesamt, aber kleinere Alphabete sind üblich. Die Anzahl der Kinder (keine Nachkommen) ist ebenso wichtig wie die Größe.
j_random_hacker
1

Das Speichern von Zeichenfolgen in Eimern ist ein guter Weg (es gibt bereits unterschiedliche Antworten, die dies umreißen).

Eine alternative Lösung könnte darin bestehen, Zeichenfolgen in einer sortierten Liste zu speichern . Der Trick besteht darin, nach einem lokalitätsabhängigen Hashing-Algorithmus zu sortieren . Dies ist ein Hash-Algorithmus, der ähnliche Ergebnisse liefert, wenn die Eingabe ähnlich ist [1].

Jedes Mal, wenn Sie eine Zeichenfolge untersuchen möchten, können Sie ihren Hash berechnen und die Position dieses Hashs in Ihrer sortierten Liste nachschlagen (wobei Sie für Arrays oder O ( n ) für verknüpfte Listen verwenden). Wenn Sie feststellen, dass die Nachbarn (unter Berücksichtigung aller engen Nachbarn, nicht nur derjenigen mit einem Index von +/- 1) dieser Position ähnlich sind (um ein Zeichen versetzt), haben Sie Ihre Übereinstimmung gefunden. Wenn es keine ähnlichen Zeichenfolgen gibt, können Sie die neue Zeichenfolge an der gefundenen Position einfügen (wobei O ( 1 ) für verknüpfte Listen und O ( n ) für Arrays verwendet wird).O(lOG(n))O(n)O(1)O(n)

Ein möglicher lokalitätsabhängiger Hashing-Algorithmus könnte Nilsimsa sein (mit Open-Source-Implementierung, die beispielsweise in Python verfügbar ist ).

[1]: Beachten Sie, dass häufig Hash-Algorithmen wie SHA1 auf das Gegenteil ausgelegt sind: Sie erzeugen sehr unterschiedliche Hashes für ähnliche, aber nicht gleiche Eingaben.

Haftungsausschluss: Um ehrlich zu sein, würde ich persönlich eine der verschachtelten / baumstrukturierten Bucket-Lösungen für eine Produktionsanwendung implementieren. Die sortierte Listenidee erschien mir jedoch als interessante Alternative. Beachten Sie, dass dieser Algorithmus stark vom gewählten Hash-Algorithmus abhängt. Nilsimsa ist ein Algorithmus, den ich gefunden habe - es gibt jedoch noch viele andere (zum Beispiel TLSH, Ssdeep und Sdhash). Ich habe nicht überprüft, ob Nilsimsa mit meinem beschriebenen Algorithmus funktioniert.

tessi
quelle
1
Interessante Idee, aber ich denke, wir müssten ein paar Grenzen haben, wie weit zwei Hash-Werte voneinander entfernt sein können, wenn sich ihre Eingaben nur um ein Zeichen unterscheiden - dann scannen Sie alles innerhalb dieses Bereichs von Hash-Werten, anstatt nur die Nachbarn. (Es ist unmöglich, eine Hash-Funktion zu haben, die benachbarte Hash-Werte für alle möglichen Paare von Zeichenfolgen erzeugt, die sich um 1 Zeichen unterscheiden. Berücksichtigen Sie die Länge-2-Zeichenfolgen in einem binären Alphabet: 00, 01, 10 und 11. Wenn h (00) ist neben beiden h (10) und h (01) muss es dann zwischen ihnen sein, in welchem ​​Fall h (11) nicht neben beiden sein kann, und umgekehrt.)
j_random_hacker
Nachbarn anzuschauen ist nicht ausreichend. Betrachten Sie die Liste abcd, acef, agcd. Es gibt ein passendes Paar, aber Ihre Prozedur wird es nicht finden, da abcd kein Nachbar von agcd ist.
DW
Sie haben beide recht! Mit Nachbarn meinte ich nicht nur "direkte Nachbarn", sondern dachte an "eine Nachbarschaft" von engen Positionen. Ich habe nicht angegeben, wie viele Nachbarn angeschaut werden müssen, da dies vom Hash-Algorithmus abhängt. Aber du hast recht, ich sollte das wahrscheinlich in meiner Antwort vermerken. Danke :)
Tessi
1
"LSH ... ähnliche Elemente werden mit hoher Wahrscheinlichkeit denselben" Buckets "zugeordnet" - da es sich um einen Wahrscheinlichkeitsalgorithmus handelt, kann das Ergebnis nicht garantiert werden. Es kommt also auf TS an, ob er 100% ige Lösung benötigt oder 99,9% ausreichen.
Bulat
1

Man könnte die Lösung in erzielt Zeit und O ( n k ) Raum unter Verwendung von verbesserten Suffixarray ( Suffixarray zusammen mit dem LCP - Array ) , die konstante Zeit LCP (längster gemeinsamen Präfix) Abfrage ermöglicht (dh Für zwei gegebene Indizes eines Strings, wie lang ist das längste Präfix der Suffixe, die bei diesen Indizes beginnen? Hier könnten wir die Tatsache ausnutzen, dass alle Saiten gleich lang sind. Speziell,O(nk+n2)O(nk)

  1. Erstellen Sie das erweiterte Suffix-Array aller zusammen verketteten Zeichenfolgen. Sei X = x 1 . x 2 . x 3 . . . . x n wobei x i , 1 i n eine Zeichenfolge in der Auflistung ist. Baue das Suffix - Array und LCP - Array für X .nX=x1.x2.x3....xnxich,1ichnX

  2. Nun beginnt jedes an der Position ( i - 1 ) k in der auf Null basierenden Indizierung. Nehmen Sie für jede Zeichenfolge x i LCP mit jeder Zeichenfolge x j, so dass j < i ist . Wenn LCP über das Ende von x j hinausgeht, ist x i = x j . Andernfalls liegt eine Nichtübereinstimmung vor (z. B. x i [ p ] x j [ p ]).xich(i1)kxixjj<ixjxi=xjxi[p]xj[p]); Nehmen Sie in diesem Fall ein weiteres LCP, beginnend an den entsprechenden Positionen nach der Nichtübereinstimmung. Wenn die zweite LCP über das Ende geht dann x i und x j von nur ein Zeichen unterscheiden; Ansonsten gibt es mehr als eine Fehlanpassung.xjxichxj

    for (i=2; i<= n; ++i){
        i_pos = (i-1)k;
        for (j=1; j < i; ++j){
            j_pos = (j-1)k;
            lcp_len = LCP (i_pos, j_pos);
            if (lcp_len < k) { // mismatch
                if (lcp_len == k-1) { // mismatch at the last position
                // Output the pair (i, j)
                }
                else {
                  second_lcp_len = LCP (i_pos+lcp_len+1, j_pos+lcp_len+1);
                  if (lcp_len+second_lcp_len>=k-1) { // second lcp goes beyond
                    // Output the pair(i, j)
                  }
                }
            }
        }
    }
    

Sie können die SDSL-Bibliothek verwenden , um das Suffix-Array in komprimierter Form zu erstellen und die LCP-Abfragen zu beantworten.

Analyse: Der Aufbau des verbesserten Suffixarray ist linear in der Länge von dh O ( n k ) . Jede LCP-Abfrage benötigt eine konstante Zeit. Die Abfragezeit ist also O ( n 2 ) .XO(nk)O(n2)

O(nk+qn2)q

j<ij

Ritu Kundu
quelle
O(kn2)k
O(nk+n2)O(kn2)O(1)
Mein Punkt ist, dass k = 20..40 für den Frageautor und das Vergleichen solch kleiner Zeichenfolgen nur wenige CPU-Zyklen erfordern, sodass ein praktischer Unterschied zwischen Brute Force und Ihrem Ansatz wahrscheinlich nicht existiert.
Bulat
1

O(nk)**bcdea*cde

Sie können diesen Ansatz auch verwenden, um die Arbeit auf mehrere CPU- / GPU-Kerne aufzuteilen.

Bulat
quelle
n=100,000k40O(nk)
0

Dies ist eine Kurzversion der Antwort von @SimonPrins ohne Hashes.

Angenommen, keine Ihrer Zeichenfolgen enthält einen Stern:

  1. nkkO(nk2)
  2. O(nk2Lognk)
  3. O(nk2)

Eine alternative Lösung mit impliziter Verwendung von Hashes in Python (kann der Schönheit nicht widerstehen):

def has_almost_repeats(strings,k):
    variations = [s[:i-1]+'*'+s[i+1:] for s in strings for i in range(k)]
    return len(set(variations))==k*len(strings)
Bananach
quelle
kO(nk)
O(n2)
0

Hier ist meine Einstellung zum 2+ Mismatches Finder. Beachten Sie, dass ich in diesem Beitrag jede Zeichenfolge als kreisförmig betrachte, z. B. besteht die Teilzeichenfolge mit der Länge 2 am Index k-1aus dem Symbol str[k-1]gefolgt von str[0]. Und der Teilstring mit der Länge 2 am Index -1ist derselbe!

Mkmlen(k,M)=k/M-1Mk=20M=4abcd*efgh*ijkl*mnop*

Der Algorithmus zum Durchsuchen aller MSymbole stimmt jetzt nicht mit den Symbolfolgen küberein:

  • für jedes i von 0 bis k-1
    • Teilen Sie alle Zeichenfolgen in Gruppen auf str[i..i+L-1], nach denen L = mlen(k,M). Wenn L=4Sie beispielsweise ein Alphabet mit nur 4 Symbolen (aus DNA) haben, werden 256 Gruppen gebildet.
    • Gruppen, die kleiner als ~ 100 Zeichenfolgen sind, können mit dem Brute-Force-Algorithmus überprüft werden
    • Für größere Gruppen sollten wir eine Zweiteilung durchführen:
      • Entfernen Sie aus jeder Zeichenfolge in den Gruppensymbolen L, die wir bereits abgeglichen haben
      • für jedes j von i-L + 1 bis kL-1
        • Teilen Sie alle Zeichenfolgen in Gruppen auf str[i..i+L1-1], nach denen L1 = mlen(k-L,M). ZB wenn k=20, M=4, alphabet of 4 symbolsja L=4und L1=3das ergibt 64 Gruppen.
        • der Rest bleibt als Übung für den Leser: D

Warum fangen wir nicht jbei 0 an? Da wir diese Gruppen bereits mit demselben Wert von erstellt haben i, entspricht job with j<=i-Lgenau dem Job mit vertauschten i- und j-Werten.

Weitere Optimierungen:

  • Berücksichtigen Sie an jeder Stelle auch Zeichenketten str[i..i+L-2] & str[i+L]. Dies verdoppelt nur die Anzahl der geschaffenen Arbeitsplätze, ermöglicht aber eine Erhöhung Lum 1 (wenn meine Rechnung korrekt ist). Anstelle von 256 Gruppen werden Sie also Daten in 1024 Gruppen aufteilen.
  • L[ich]*0..k-1M-1k-1
Bulat
quelle
0

Ich arbeite jeden Tag daran, Algen zu erfinden und zu optimieren. Wenn Sie also ein bisschen Leistung benötigen, ist dies der Plan:

  • Überprüfen Sie mit *in jeder Position unabhängig, dh anstelle von einzelnen n*kJobverarbeitungszeichenfolgenvarianten - starten Sie kunabhängige Jobs, die jeweils nZeichenfolgen überprüfen . Sie können diese kJobs auf mehrere CPU- / GPU-Kerne verteilen . Dies ist besonders wichtig, wenn Sie Unterschiede zwischen 2 und mehr Zeichen überprüfen möchten. Eine geringere Auftragsgröße verbessert auch die Cache-Lokalität, wodurch das Programm 10x schneller wird.
  • Wenn Sie Hash-Tabellen verwenden möchten, verwenden Sie eine eigene Implementierung mit linearer Abtastung und einem Lastfaktor von ~ 50%. Es ist schnell und ziemlich einfach zu implementieren. Oder verwenden Sie eine vorhandene Implementierung mit offener Adressierung. STL-Hash-Tabellen sind aufgrund der Verwendung einer separaten Verkettung langsam.
  • Sie können versuchen, Daten mithilfe des 3-Status-Bloom-Filters (Unterscheidung von 0/1/1 + Vorkommen) vorzufiltern, wie von @AlexReynolds vorgeschlagen.
  • Führen Sie für jedes i von 0 bis k-1 den folgenden Job aus:
    • Generieren Sie 8-Byte-Strukturen, die 4-5-Byte-Hash jeder Zeichenfolge (mit *der i-ten Position) und des Zeichenfolgenindex enthalten, und sortieren Sie sie dann oder erstellen Sie eine Hash-Tabelle aus diesen Datensätzen.

Zum Sortieren können Sie die folgende Kombination ausprobieren:

  • Erster Durchgang ist die MSD-Radix-Sortierung auf 64-256 Arten unter Verwendung des TLB-Tricks
  • Der zweite Durchgang ist eine MSD-Radix-Sortierung auf 256 bis 1024 Arten ohne TLB-Trick (insgesamt 64.000 Arten ).
  • Der dritte Durchgang ist die Einfügesortierung, um verbleibende Inkonsistenzen zu beheben
Bulat
quelle