Koordinaten aus Abstandsfunktion

08/04/2013 - 10:48 von Hartmut Leister | Report spam
Liebe NG,

gibt es bereits Theorie, aus einer gegebenen Abstandsfunktion Koordinaten abzuleiten?

Konkretes Beispiel:
Ich möchte Zeichenketten beliebiger Lànge über einem festen Alphabet, in dem meine Abstandsfunktion die Levenshtein- oder Editierdistanz (siehe [1]) ist.
Ich möchte jede Zeichenkette in einen metrischen Raum fester Dimension "projizieren", sodass eine Separierung in dem Teilraum gegeben ist.
Weiterhin sollte auf dem Projektionsraum sich die Distanz (eine abgeleitete) sich nicht allzu sehr anders verhalten, als auf dem Ursprungsraum.

Also:
Alphabet A
Raum der Zeichenketten Z=A^\infty
Projektionsraum P
Levenshtein-Distanz D: Z x Z -> R+
Distanz im Projektionsraum d: P x P -> R+
Projektion p: Z -> P

für alle x,y \in Z: D(x,y) \approx d( p(x),p(y) )

Kennt jemand eine zugehörige Theorie?

Motivation:
Ich möchte eine Menge von Zeichenketten in einen möglichst minimal dimensionalen Raum projizieren, aber diese immer noch anhand einer einfachen Distanz unterscheiden können und schnell suchen.

Beste Grüße und vielen Dank für Ideen
Hartmut

[1] http://de.wikipedia.org/wiki/Levenshtein-Distanz
 

Lesen sie die antworten

#1 ram
08/04/2013 - 11:07 | Warnen spam
Hartmut Leister writes:
Ich möchte eine Menge von Zeichenketten in einen möglichst
minimal dimensionalen Raum projizieren



http://en.wikipedia.org/wiki/Dimens..._reduction

»In einen Raum möglichst niedriger Dimension«.

»Minimal« bezeichnet bereits die niedrigste Dimension
und kann nicht durch »möglichst« modifiziert werden.
(Wenn »möglichst« »möchte« modifizieren soll, dann
sollte es hinter »Zeichenketten« stehen.)

Ähnliche fragen