Wie viele Zeichenfolgen befinden sich in der Nähe eines bestimmten Satzes von Zeichenfolgen?

Diese Frage wurde von Efficient Data Structures zum Erstellen einer schnellen Rechtschreibprüfung gestellt .

Bei zwei Strings sagen wir, dass sie nah sind, wenn ihr Damerau-Levenshtein-Abstand ¹ klein ist, dh für ein festes . Informell ist die Mindestanzahl von Lösch-, Einfüge-, Ersetzungs- und (Nachbar-) Auslagerungsoperationen, die erforderlich sind, um in umzuwandeln . Sie kann durch dynamische Programmierung in berechnet werden . Beachten Sie, dass eine Metrik ist , die insbesondere symmetrisch ist. $u,v$ $k$ $\operatorname{LD}(u,v) \geq k$ $k \in \mathbb{N}$ $\operatorname{LD}(u,v)$ $u$ $v$ $\Theta(|u|\cdot|v|)$ $\operatorname{LD}$

Die Frage des Interesses ist:

Was ist die Kardinalität von bei einer Menge $S$ von $n$ Strings über $\Sigma$ mit Längen von höchstens $m$ ?

$\qquad \displaystyle S_k := \{ w \in \Sigma^* \mid \exists v \in S.\ \operatorname{LD}(v,w) \leq k \}$ ?

Da sogar zwei Strings gleicher Länge unterschiedliche Anzahlen von $k$ Strings² haben², kann es schwierig (unmöglich?) Sein, eine allgemeine Formel / einen Ansatz zu finden. Daher müssen wir möglicherweise die Zahl für jedes gegebene explizit berechnen $S$ , was uns zu der Hauptfrage führt:

Was ist die (zeitliche) Komplexität des Findens der Kardinalität der Menge $\{w\}_k$ für (beliebiges) $w \in \Sigma^*$ ?

Beachten Sie, dass die gewünschte Menge in exponentiell ist Eine explizite Aufzählung ist daher nicht wünschenswert. Ein effizienter Algorithmus wäre großartig. $|w|$

Wenn es hilft, kann angenommen werden, dass wir tatsächlich eine (große) Menge von Zeichenfolgen haben, dh wir lösen die erste hervorgehobene Frage. $S$

Mögliche Varianten sind die Verwendung des Levenshtein-Abstands .
Betrachten Sie und . Die Sätze von geschlossenen Zeichenfolgen über sind (8 Wörter) und (10 Wörter). $aa$ $ab$ $1$ $\{a,b\}$ $\{ a, aa,ab,ba,aaa,baa,aba,aab \}$ $\{a,b,aa,bb,ab,ba,aab,bab,abb,aba\}$

algorithms time-complexity strings word-combinatorics string-metrics Raphael
quelle

Ist die hervorgehobene Frage nicht im Grunde eine Suche nach k-nächsten Nachbarn? Insbesondere denke ich über räumliche Indizes nach. Es gibt Datenstrukturen, die effiziente k-NN-Abfragen mit beliebiger Metrik (mit einigen Einschränkungen) unterstützen, wie z. B. M-Tree und seine Varianten. Vermisse ich etwas oder glaubst du, das würde funktionieren?

Juho

@mrm Sicher, das würde funktionieren - wenn ich alle exponentiell viele Wörter bis zu einer gewissen Länge aufschreiben würde (was ich nicht tun möchte), alle paarweisen Ausrichtungen berechnen (die ich umgehen möchte) und dann den Baum erstellen würde .

Raphael

@mrm: Jetzt, wo ich darüber nachdenke, löst das Finden der nächsten Nachbarn das Problem nicht. Wir wollen alle Nachbarn finden (bis zu einem festen Abstand).

k

$k$

Raphael

Richtig, dann ist es eine Bereichsabfragesuche . Ich denke, es gibt ziemlich viel Forschung zu diesem Thema, mit riesigen Datenmengen und großen Datenbanken. Aber egal, ich verstehe Ihren Standpunkt jetzt. Vielleicht gibt es einen klügeren Weg :)

Juho

Ein paar ziemlich einfache Beobachtungen: (1) Wenn nur Löschungen zulässig sind, ist das (zweite) Problem polynomisch; (2) Eine Grenze für die Zählung ist .

O ((| w | + k)^{k})

$O\bigl((|w|+k)^k\bigr)$

Rgrig

Antworten:

Siehe Levenshteins Artikel . Es enthält Grenzen für die Zahlenzeichenfolgen, die beim Einfügen und Löschen einer Zeichenfolge erhalten werden. Wenn die Länge der Zeichenfolge ist und die Zeichenfolge binär ist, beträgt die maximale Anzahl der nächsten Nachbarn in der Levenshtein-Entfernung . Es ist vergleichsweise schwieriger, etwas über nächste Nachbarn zu sagen , aber man kann Grenzen bekommen. Diese sollten Ihnen eine Schätzung der Komplexität geben. $n$ $\Theta(n^2)$ $k$

Ankur
quelle

Vielen Dank, aber dies ist weder die richtige Metrik, noch wird ein binäres Alphabet nicht ausreichen (obwohl die Alphabetgröße wahrscheinlich keine qualitativen Auswirkungen hat). Ich spreche kein Russisch und kann daher nicht überprüfen, wie einfach die Ergebnisse übertragen werden können.

Raphael

Grenzen scheinen leicht zu finden, aber die Frage fragt nach einer genauen Zählung. Bin ich falsch @Raphael?

Rgrig

Es gibt eine englische Version von Levenshteins Artikel, die Sie finden sollten; Es enthält auch Grenzen für das allgemeine Alphabet.

Ankur

@rgrig: Die Frage fragt nach der genauen Anzahl, aber (gute) Grenzen wären willkommen.

Raphael

Wenn Ihr festgelegt ist und Sie eine Vorverarbeitung durchführen dürfen, können Sie dies möglicherweise versuchen $k$

Konstruieren Sie einen Graphen so, dass die Knoten Wörter sind und eine Kante zwischen zwei Knoten besteht, wenn der Abstand zwischen diesen beiden Wörtern 1 beträgt.
Holen Sie sich die Adjazenzmatrix, die diesem Diagramm entspricht (sagen Sie ). $M$
Berechne $M^k$

Jetzt können Sie möglicherweise die endgültige Matrix verwenden, um alle Fragen zu beantworten. Wenn Sie usw. speichern können, können Sie möglicherweise für einen größeren Bereich von anstelle von festem antworten , natürlich zahlt man hier mit den Kosten der Matrixmultiplikation. $M, M^2, M^4, M^8 \ldots$ $k$ $k$

TenaliRaman
quelle

Dies ist eine ziemlich naive Prozedur, nicht wahr? Das Berechnen aller paarweisen Abstände und das Durchführen einer Breitensuche bis zur Tiefe ist bereits effizienter.

k

$k$

Raphael

Ich gehe davon aus, dass Sie in der oben erstellten Grafik die Breitensuche meinen. In diesem Fall führen Sie die Suche für jede von Ihnen durchgeführte Abfrage durch. Das wäre nicht besser als eine Aufzählung (die Sie in Ihrer Frage angegeben haben, die Sie nicht tun wollten). In meiner obigen Antwort berechne ich als Vorverarbeitungsschritt, der nur einmal ausgeführt werden muss. Danach muss man für jede Abfrage nur eine Zeile / Spalte dieser Matrix durchgehen, um eine schnellere Antwortzeit zu erzielen.

M^{k}

$M^k$

TenaliRaman

Nun, beide Wege können ihre "echte" Anstrengung als Vorverarbeitung verbergen. Beachten Sie, dass in der maximalen Länge exponentiell groß ist , so dass "nur durch eine Zeile / Spalte gehen" nicht effizient ist. Die Berechnung der Entfernungen selbst ist hier nicht der Engpass. (Sie würden übrigens benötigen .)

M

$M$

n

$n$

\sum_{i = 1}^{k} M^{i}

$\sum_{i=1}^k M^i$

Raphael

Eigentlich ist nur num_words x num_words. Außerdem ist es boolesch und möglicherweise sehr spärlich. Verstehst du warum?

M

$M$

TenaliRaman

Ja und nein. enthält alle engen Wörter, und es gibt exponentiell viele Wörter, dh . Ich habe die Frage bearbeitet, um sie zu klären.

S_{k}

$S_k$

num_words = 2^{m}

$\text{num_words } = 2^m$

Raphael