Zwischen- / Codierungsdarstellung für Levenshtein-Entfernung

8

Die Phrasen:

Der schnelle Braunfuchs springt über den faulen Hund [A]

und

Der schnelle braune Fuchs springt über den faulen Hund [B]

kann unter Verwendung des Levenshtein-Entfernungsalgorithmus verglichen werden, um die Ähnlichkeit zu bestimmen, indem die minimale Anzahl von Hinzufügungen, Löschungen oder Ersetzungen einzelner Zeichen berechnet wird, die erforderlich sind, um A in B umzuwandeln.

Ich bin interessiert zu wissen, ob es eine Zwischendarstellung oder möglicherweise ein Codierungsschema für die Levenshtein-Entfernung gibt. Nicht für die Verwendung zwischen zwei Phrasen, sondern nur für eine Codierung, die auf eine einzelne Phrase angewendet wird, sodass der Zeichenindex die Vergleiche nicht beeinflusst.

In B fehlt das 'q' im Vergleich zu A. Ein normaler Zeichenfolgenvergleich würde übereinstimmen 'The 'und dann 'uick brown fox...'nur aufgrund eines einzelnen Zeichenversatzes fehlschlagen . Die Levenshtein-Entfernung könnte verwendet werden, um sie mit der ursprünglichen Phrase A zu vergleichen, um einen verzeihenderen Vergleich zu ermöglichen, aber in meinem Fall habe ich nicht zwei Phrasen, nur eine.

Also, ich bin für irgendeine Art von eindeutig Codierung einen Satzes in der Suche Pakete von Informationen, wenig Atome der Wahrheit (ich denke , ein Paket pro Charakter?) , Die eine lokale Ordnung halten und so weiter, aber wenn einige der Pakete falsch sind, wirkt sich dies nicht auf spätere Zeichen aus.

Jede eindeutige Phrase sollte einer und nur einer eindeutigen Codierung / Zwischendarstellung zugeordnet werden, Sets A'und B'. Die Berechnung des Levenshtein-Abstands von A und B wäre dann dasselbe wie die Berechnung des Schnittpunkts von Mengen A' = B'.

Alternativ - wenn dieses Problem keine Lösung hat (und dies sicher einem ausgetretenen Forschungsbereich entspricht, wäre ich nicht überrascht), ein überzeugendes Argument / Beweis für seine Unlösbarkeit.

Jason Kleban
quelle
2
Vielleicht fehlt mir etwas, aber anscheinend möchten Sie einen Blockfehlerkorrekturcode. en.wikipedia.org/wiki/Block_code
S Huntsman
Sicherlich scheint das im Stadion zu sein, aber ich weiß nicht, wie ich das hier anwenden würde.
Jason Kleban
Für den Kontext möchte ich das Konzept eines Fuzzy-Tresors, das normalerweise auf biometrische Messungen angewendet wird, auf Passphrasen anwenden. Anstelle einer Reihe von Messungen wäre dies eine Reihe von atomaren Wahrheiten über eine Textfolge.
Jason Kleban
Mehr darüber nachdenken - Ich habe Probleme zu überlegen, wie ich die Prinzipien fehlerkorrigierender Codes anwenden kann, um dies zu lösen. Der Grund ist, dass die Passphrasen willkürlich sind und von einem Benutzer ausgewählt werden, nicht diktiert. Aber vielleicht ist es auf eine weniger offensichtliche Weise anwendbar?
Jason Kleban

Antworten:

14

In diesem Sinne gibt es in der Tat einige Untersuchungen zur Bearbeitungsentfernung mit einigen positiven und einigen negativen Ergebnissen. (Ich verstehe die Frage möglicherweise nicht genau, daher werde ich versuchen, Fragen zu beantworten, die ich beantworten kann.)

1

  • Ω(logn)n

  • 2O(lognloglogn)

n

Es gibt sicherlich mehr Literatur in diesem Sinne, aber lassen Sie mich zuerst wissen, ob dies irgendwo in der Nähe von dem ist, was Sie gemeint haben.

Alex Andoni
quelle
Vergessen zu erwähnen: Wenn Sie die Bearbeitungsentfernung für biometrische Informationen verwenden, sollten Sie sich <a href=" arxiv.org/abs/cs.CR/0602007"> dieses Papier von Dodis, Ostrovsky, Reyzin und Smith </a>.
Alex Andoni
Es ist eigentlich NICHT für biometrische Informationen. Ich finde es rätselhaft, dass Fuzzy Vaults für die Biometrie funktionieren könnten, aber nicht für etwas "Einfacheres" wie eine Textfolge verwendet werden könnten.
Jason Kleban
Ihre Antwort ist großartig, danke. Lassen Sie mich darüber nachdenken und recherchieren ...
Jason Kleban
Ja, Ihre Beschreibungen sind zutreffend - sie fühlen sich richtig an. +50! Ist meine beabsichtigte Anwendung aus Neugier durch die ursprüngliche Frage und unsere Kommentare klar?
Jason Kleban
Hallo Alex, ich denke die Seite hat einen Fehler. Ich habe Ihnen die vollen 50 Punkte verliehen, aber ich erhalte die Nachricht, dass die Antwort automatisch ausgewählt wurde - Sie erhalten nur 25 Punkte. Tut mir leid.
Jason Kleban
5

Wenn das einzige, was passieren kann, ist, dass Zeichen verschwinden, müssen Sie meines Erachtens nur das längste häufig auftretende Subsequenzproblem lösen . (Eine Teilsequenz ist eine Verallgemeinerung eines Teilstrings: Es kann mehrere Stellen in der Teilsequenz geben, an denen Material aus der größeren Sequenz entfernt wurde, nicht nur am Anfang und / oder Ende.)

Haben Sie darüber hinaus diese Liste von Metriken gesehen ?

Ich kann Ihre Problemstellung falsch verstehen, aber es scheint mir, dass es möglich sein sollte, nach dem Bezahlen einen ziemlich schnellen Algorithmus zu haben, wenn Sie genau definieren, wie Fehler auftreten können (Löschen, Umsetzen usw.) und dann einen Suffixbaum erstellen die Speicher- und Vorverarbeitungskosten für die Erstellung des Suffixbaums.

Aaron Sterling
quelle
Danke dafür! Sie haben mir einige neue Dinge gezeigt, die Sie berücksichtigen sollten.
Jason Kleban
Fehler können beim Einfügen und Löschen auftreten. Transpositionen und Swaps wären nett, sind aber Kompositionen der grundlegenden Einfügungen und Löschungen - falls dies die Befriedigung erleichtert.
Jason Kleban
1

Dies ist nur ein Gedanke, keine Lösung, aber zu lang für einen Kommentar.

Könnte Ihre Menge / Darstellung ein alphabetisches Gebäude der Zeichenfolge sein?
Beispiel (für A):


1. Start with the empty string (^$) 
2. Insert a between 1st ^ and 1st $ (now: ^a$)
3. Insert b between 1st ^ and 1st a (now: ^ba$) 
4. Insert c between 1st ^ and 1st b (now: ^cba$) 
5. Insert d between 1st b and 1st a (now: ^cbda$) 
6. Insert d between 1st a and 1st ^ (now: ^cbdad$) 

und so weiter...

Ihre Darstellung wären die Schritte, die Sie unternommen haben, um die Zeichenfolge zu erstellen (in alphabetischer Reihenfolge):

Das Element {a, {1, ^}, {1, $}} repräsentiert Schritt 2, während {d, {1, b}, {1, a}} den 5. Schritt repräsentiert.

Vorausgesetzt, Sie tun dies in jedem Fall alphabetisch, haben Sie möglicherweise etwas, das Sie verwenden können.

Ein ergänzender Gedanke: Beginnen Sie mit genügend Kopien jedes Buchstabens "abcdd" (für die ersten 4) und verfolgen Sie dann Ihre Transpositionen, um die Zeichenfolge zu erstellen. Wir bewegen uns jetzt vage in die Permutationstheorie.

[Übrigens, es ist "Sprünge", nicht "Sprünge", sonst gibt es keine "s" - ja, mir ist klar, dass du nie gesagt hast, dass es ein Pangram ist]

Barrycarter
quelle
Zunächst eine interessante Idee. ... und danke für die 'Jumps'-Korrektur - ich habe den Beitrag entsprechend geändert.
Jason Kleban
Ich denke, eine Lösung könnte keinen "5. Schritt" haben. Reihenfolge kann keine Rolle spielen - die Pakete können bei Bestellung oder Referenz nicht stark miteinander verknüpft werden - was ist, wenn ein Paket falsch ist / fehlt?
Jason Kleban
0

Es klingt für mich so, als ob Ihre einfache Sache funktionieren sollte. Jedes Paket enthält die Position und das Zeichen, z

The = <1, T>, <2, h>, <3, e>

Dann vergleichen Sie das erste Paar von A mit dem ersten Paar von B usw. Dies sollte Ihnen Levenshtein geben.

Xodarap
quelle
Aber was ist, wenn ein frühes Zeichen in der Zeichenfolge fehlt, dann würden alle späteren Paarungen um 1 abweichen, richtig? Wenn wir 'q' in [B] herausnehmen, dann ist [B] <u, 5>! = [A] <u, 6>, [B] <i, 6>! = [A. ] 's <i, 7>
Jason Kleban
Anders ausgedrückt, wenn ich Ihren Vorschlag richtig verstehe, entspricht er der Gleichheit von Zeichenfolge und Sequenz.
Jason Kleban
@ uosɐſ: Der Absender würde allerdings die richtige Reihenfolge kennen, oder? Sie würden <u, 6> senden; Der Empfänger erhält es möglicherweise als fünftes Paket, aber wenn er es überhaupt erhält, weiß er, dass es sich um den sechsten Buchstaben handelt.
Xodarap
1
Die Idee ist, dass Sie für jede Zeichenfolge s eine Menge T (s) erstellen und dann einfach T (s1) und T (s2) als Mengen vergleichen, um beispielsweise T (s1) -T (s2) und die zu finden Die Anzahl der Elemente in dieser Differenz ist der Abstand. Es gibt keinen "Absender" und "Empfänger"
Barrycarter