Ich habe eine große Menge an willkürlichen natürlichen Sprachzeichenfolgen. Für mein Werkzeug, um sie zu analysieren, muss ich jede Zeichenfolge in einen eindeutigen Farbwert (RGB oder andere) konvertieren. Ich brauche den Farbkontrast, um von der String-Ähnlichkeit abhängig zu sein (je mehr String sich von anderen unterscheidet, desto mehr sollten ihre jeweiligen Farben unterschiedlich sein). Wäre perfekt, wenn ich immer denselben Farbwert für die gleiche Saite bekommen würde.
Irgendwelche Ratschläge, wie Sie dieses Problem angehen können?
Ich brauche wahrscheinlich "Ähnlichkeit", definiert als Levenstein-ähnliche Distanz. Parsing in natürlicher Sprache ist nicht erforderlich.
Das ist:
%Vor%Ähnlich.
%Vor%Ähnlich (aber etwas weniger).
%Vor%Ziemlich nicht ähnlich.
(Danke, Welbog !)
Ich würde wahrscheinlich genau wissen, welche Entfernungsfunktion ich nur brauche, wenn ich die Programmausgabe sehen werde. Beginnen wir also mit einfacheren Dingen.
Ich habe meinen Vorschlag, die Aufgabe in zwei zu teilen, entfernt - absolute Abstandsberechnung und Farbverteilung. Dies würde nicht gut funktionieren, da wir zuerst dimensionale Informationen auf eine einzige Dimension reduzieren und dann versuchen, sie in drei Dimensionen zu synthetisieren.
Sie müssen näher erläutern, was Sie unter "ähnliche Strings" verstehen, um eine geeignete Konvertierungsfunktion zu erhalten. Sind die Zeichenfolgen
? %Vor%ähnlich betrachtet? Was ist mit den Strings
? %Vor%(alle Buchstaben im Original +1) oder
%Vor%? Je nachdem, was Sie mit "ähnlich" meinen, können Sie verschiedene Funktionen in Betracht ziehen.
Wenn der Unterschied allein auf den Werten der Zeichen basieren kann (in Unicode oder in welchem Raum auch immer), können Sie versuchen, die Werte zu summieren und das Ergebnis als Farbton für den HSV-Raum zu verwenden. Wenn eine längere Zeichenfolge die Farben unterschiedlicher gestalten sollte, können Sie die Zeichen anhand ihrer Position in der Zeichenfolge abwägen.
Wenn der Unterschied komplexer ist, etwa durch das Auftreten bestimmter Buchstaben oder Wörter, müssen Sie dies identifizieren. Vielleicht können Sie die Werte für Rot, Grün und Blau anhand der Anzahl von Es, Ss und Rs in einem String festlegen, wenn Ihre Domain viele davon enthält. Oder wählen Sie einen Farbton, der auf dem Verhältnis von Vokalen zu Konsonanten oder Wörtern zu Silben basiert.
Es gibt viele, viele verschiedene Möglichkeiten, das zu erreichen, aber das Beste hängt wirklich davon ab, was Sie mit "ähnlichen" Strings meinen.
Es klingt, als ob Sie einen Hash von irgendeiner Art wünschen. Es muss nicht sicher sein (also nichts so Kompliziertes wie MD5 oder SHA), sondern etwas in der Art von:
%Vor%würde als einfacher erster Schritt funktionieren. Du könntest auch schickere Dinge tun, wie jedes Zeichen als 'Amplitude' für R, G und B (e könnte + 1R, + 2G und -4B usw. sein) und addiere dann einfach alle Werte in eine Zeichenkette ... klammert sie am Ende und Sie haben eine Methode, Zeichenketten beliebiger Länge in Farbe als 'Farb-Hash'-Prozess umzuwandeln.
Zuerst müssen Sie einen Weg wählen, um die Stringähnlichkeit zu messen. Die minimale Bearbeitungsdistanz ist zwar traditionell, reicht aber nicht aus, um die Strings gut zu ordnen, was Sie benötigen, wenn Sie möchten um jedes Mal die gleichen Farben den gleichen Strings zuzuweisen - vielleicht könnten Sie die Bearbeitungskosten durch die alphabetische Entfernung gewichten. Auch die minimale Bearbeitungsentfernung an sich mag nicht sehr nützlich sein, wenn das, wonach Sie suchen, eine Ähnlichkeit in der Sprache und nicht in der geschriebenen Form ist (wenn ja, denken Sie zuerst an einen Stemming- / Soundex-Durchlauf) oder einen anderen Sinn für "Ähnlichkeit".
>Dann müssen Sie eine Möglichkeit wählen, den sichtbaren Farbraum basierend auf dieser Metrik zu durchlaufen. Es kann hilfreich sein, die HSL- oder HSV-Farbdarstellung in Erwägung zu ziehen - der Algorithmus könnte dann so einfach werden wie die Auswahl eines Starttons und Sie gehen den sortierten Korpus durch und weisen jeder Saite den aktuellen Farbton zu, bevor Sie ihn durch die Differenz der Saite von der vorherigen abgleichen.
Wie wichtig ist es, dass Sie niemals zwei ungleiche Saiten mit der gleichen Farbe haben?
Wenn es nicht so wichtig ist, könnte das vielleicht funktionieren?
Sie könnten einen 1-dimensionalen Farbraum wählen, der dem Kreis "homotop" ist: Angenommen, die Farbfunktion c(x)
ist für x
zwischen 0
und 1
definiert. Dann möchtest du c(0) == c(1)
.
Nun nimmst du die Summe aller Zeichenwerte modulo etwas Skalierungsfaktor und wickelst das zurück in den Farbraum:
c( (SumOfCharValues(word) modulo ScalingFactor) / ScalingFactor )
Dies funktioniert möglicherweise noch besser, wenn Sie einen "umhüllenden" Farbraum höherer Dimensionen definieren und für jede Dimension eine andere SumOfCharValues
-Funktion auswählen; jemand schlug vor, die Summe und die Länge zu wechseln.
Nur ein Gedanke ... HTH
Hier ist mein Vorschlag (ich denke, es gibt einen allgemeinen Namen für diesen Algorithmus, aber ich bin zu müde, um mich daran zu erinnern):
Sie möchten jede Zeichenfolge in einen 3D-Punktknoten (r, g, b) transformieren (Sie können die Werte so skalieren, dass sie in Ihren Bereich passen), sodass der folgende Fehler minimiert wird:
%Vor%Sie können dies tun:
Sie können etwas wie MinHash oder eine andere LSH-Methode und Ähnlichkeit als Schnittmenge zwischen Sets von Schindeln definieren von Jaccard-Koeffizienten . Es gibt eine gute Beschreibung in Mining of Massive Datensätze, Ch.3 von Rajaraman und Ullman.
Ich würde vielleicht ein Delta zwischen zwei Strings definieren. Ich weiß nicht, was Sie als die Differenz (oder "Ungleichheit") von zwei Strings definieren, aber die offensichtlichste Sache, an die ich denken könnte, wäre String-Länge und die Anzahl der Vorkommen bestimmter Buchstaben (und deren Index in der Zeichenfolge) . Es sollte nicht schwierig sein, es so zu implementieren, dass es den gleichen Farbcode in gleichen Strings zurückgibt (wenn Sie einen Gleichen zuerst machen und vor einem weiteren Vergleich zurückkehren).
Wenn es um den tatsächlichen RGB-Wert geht, würde ich versuchen, die String-Daten in 4 Bytes (RGBA) oder 3 Bytes zu konvertieren, wenn Sie nur RGB verwenden. Ich weiß nicht, ob jede Zeichenfolge in sie passen würde (wie kann das sprachspezifisch sein?).
Es tut uns leid, aber Sie können nicht tun, was Sie mit Levenshtein Abstand oder ähnlichem suchen. RGB und HSV sind dreidimensionale geometrische Räume, aber die Levenshtein-Distanz beschreibt einen metrischen Raum - eine viel lockere Menge von Constraints ohne feste Anzahl von Dimensionen. Es gibt keine Möglichkeit, einen metrischen Raum in eine feste Anzahl von Dimensionen zu mappen, wobei die Lokalität immer erhalten bleibt.
Soweit es Näherungen für einzelne Begriffe gibt, könnten Sie eine Modifikation eines Algorithmus wie Soundex oder Metaphon verwenden, um eine Farbe auszuwählen; Für mehrere Begriffe könnten Sie beispielsweise soundex oder metaphone auf jedes Wort einzeln anwenden und sie dann zusammenfassen (mit Überlauf).
Tags und Links algorithm colors string-metric