Algorithmus am nächsten Zeichenfolge mit gleichen Zeichen zu finden

StackOverflow https://stackoverflow.com/questions/859441

  •  21-08-2019
  •  | 
  •  

Frage

eine Liste L von n Zeichenkette gegeben, und eine Eingabezeichenkette S, was ist ein effizienter Weg, um die Zeichenfolge in L zu finden, die die meisten Zeichen enthält, die in S existieren? Wir wollen die Zeichenfolge in L finden, die sich am meisten eng der Buchstaben in S enthalten aus.

Die offensichtliche Antwort ist durch all n Strings Schleife und überprüfen, um zu sehen, wie viele Zeichen in der aktuellen Zeichenkette in S. existiert jedoch wird dieser Algorithmus häufig ausgeführt werden, und die Liste L n String wird in einer Datenbank gespeichert werden ... Loop manuell durch alle n strings wäre so etwas wie big-Oh von n * m ^ 2 erforderlich, wobei n die Anzahl der Saiten in L ist, und m die maximale Länge jeder Zeichenfolge in L sowie der max Länge von S ... in diesem Fall m ist eigentlich eine konstante von 150.

Gibt es einen besseren Weg, als nur eine einfache Schleife? Gibt es eine Datenstruktur kann ich die n-Strings in dem laden würde mir schnelle Suche Fähigkeit? Gibt es einen Algorithmus, der die vorausberechneten Meta-Daten zu jedem der n-Strings verwendet, die besser als eine Schleife durchführen würde?

Ich weiß, dass es eine Menge Freaks gibt, die in die Algorithmen sind. Also bitte helfen Sie!

Danke!

War es hilfreich?

Lösung

Wenn Sie nach dem Teil sind, ein Trie oder Patrica trie könnte ein guter Ausgangspunkt sein .

Wenn Sie über die Reihenfolge ist egal, nur um die Anzahl der jedes Symbol oder Buchstaben, ich würde das Histogramm aller Strings berechnen und vergleichen sie dann mit dem Histogramm des Eingangs. 

               ABCDEFGHIJKLMNOPQRSTUVWXYZ
Hello World => ...11..1...3..2..1....1...

Damit werden die Kosten senken, um O(26 * m + n) sowie die Vorverarbeitung einmal, wenn Sie Groß- und Kleinschreibung lateinische Buchstaben betrachten.

Wenn m konstant ist, können Sie das Histogramm als 26-dimensionalen Vektor auf eine 26 dimensionale Einheitskugel interpretieren, indem es zu normalisieren. Dann könnten Sie einfach berechnen die Skalarprodukt von zwei Vektoren, die die Kosinus des Winkels zwischen den beiden nachgebend Vektoren, und dieser Wert sollte auf die Ähnlichkeit der Zeichenketten proportional sein.

Unter der Annahme, m = 3, ein Alphabet A = { 'U', 'V', 'W' } die Größe nur drei, und die folgende Liste von Strings. 

L = { "UUU", "UVW", "WUU" }

Die Histogramme sind die folgenden. 

H = { (3, 0, 0), (1, 1, 1), (2, 0, 1) }

Ein Histogramm h = (x, y, z) normiert ist mit h' = (x/r, y/r, z/r) der euklidischen Norm des Histogramm r h -. Das ist r = sqrt(x² + y² + z²) 

H' = { (1.000, 0.000, 0.000), (0.577, 0.577, 0.577), (0.894, 0.000, 0.447) }

Der Eingang S = "VVW" hat das Histogramm hs = (0, 2, 1) und das normalisierte Histogramm hs' = (0.000, 0.894, 0.447).

Jetzt können wir die Ähnlichkeit von zwei Histogrammen h1 = (a, b, c) und h2 = (x, y, z) als euklidischen Abstand beider Histogramme berechnet werden. 

d(h1, h2) = sqrt((a - x)² + (b - y)² + (c - z)²)

Für das Beispiel, das wir erhalten. 

d((3, 0, 0), (0, 2, 1)) = 3.742
d((1, 1, 1), (0, 2, 1)) = 1.414
d((2, 0, 1), (0, 2, 1)) = 2.828

Daher "UVW" am nächsten ist "VVW" (kleinere Zahlen zeigen eine höhere Ähnlichkeit).

Mit der normierten Histogramme h1' = (a', b', c') und h2' = (x', y', z') wir den Abstand als Punktprodukt der beiden Histogramme berechnen kann. 

d'(h1', h2') = a'x' + b'y' + c'z'

Für das Beispiel, das wir erhalten. 

d'((1.000, 0.000, 0.000), (0.000, 0.894, 0.447)) = 0.000
d'((0.577, 0.577, 0.577), (0.000, 0.894, 0.447)) = 0.774
d'((0.894, 0.000, 0.447), (0.000, 0.894, 0.447)) = 0.200

Again "UVW" bestimmt werden soll, am nächsten "VVW" (größere Zahlen zeigen eine höhere Ähnlichkeit).

Beide Versionen Ausbeute unterschiedliche Zahlen, aber die Ergebnisse sind immer die gleichen. Man könnte auch andere Normen verwenden - Manhattan-Distanz (L1-Norm) zum Beispiel -. Aber dies wird nur die Zahlen ändern, weil Normen in endlich dimensionalen Vektorräumen sind alle gleichwertig

Andere Tipps

Klingt wie Sie eine trie . Tries werden verwendet, um Wörter zu suchen, ähnlich wie eine Rechtschreibprüfung funktioniert. Also, wenn der String S die Zeichen in der gleichen Reihenfolge wie die Strings in L hat dann kann dies für Sie arbeiten.

Wenn jedoch die Reihenfolge der Zeichen in S nicht relevant - wie eine Reihe von Scrabblefliesen und Sie wollen für das längste Wort suchen - dann ist dies nicht Ihre Lösung.

Was Sie wollen, ist ein BK- Baum . Es ist ein bisschen unintuitive, aber sehr cool -. Und es macht es möglich, Elemente innerhalb eines levenshtein (edit) Distanzschwelle in O (log n) Zeit zur Suche

Wenn Sie die Bestellung in Ihrem Eingabezeichenfolgen kümmern, verwenden Sie sie, wie ist. Wenn Sie dies nicht tun können Sie die einzelnen Zeichen sortieren, bevor sie in die BK-Baum (oder Abfrage mit ihnen) eingefügt wird.

Ich glaube, was Sie suchen finden Sie hier: Fuzzy Logic Based Search Technique

Es ist ziemlich schwer, aber so ist das, was Sie für Fragen. Er spricht über Wort Ähnlichkeiten und Charakter Abhandenkommen. 

i.e:

L I N E A R T R N A S F O R M
L I N A E R T R A N S F O R M
L E N E A R T R A N S F R M

es scheint mir, dass die Reihenfolge der Zeichen in Ihr Problem ist nicht wichtig, aber Sie suchen nach „in der Nähe von-Anagramme“ des Wortes S.

Wenn das so ist, dann sind Sie jedes Wort in dem Satz L als ein Array von 26 ganzen Zahlen darstellen können (vorausgesetzt, Ihr Alphabet hat 26 Buchstaben). Sie können S darstellen, ähnlich wie ein Array von 26 ganzen Zahlen; jetzt, um die beste Übereinstimmung zu finden Sie nur einmal durch die Menge L laufen und eine Abstandsmetrik zwischen dem S-Vektor und dem aktuellen L-Vektor, aber Sie wollen definieren die Abstandsmetrik (zB euklidische / Summe der Quadrate oder Manhattan berechnen / Summe der absoluten Differenzen). Dies ist O (n) -Algorithmus, weil die Vektoren konstante Längen haben.

Hier ist ein T-SQL-Funktion ist, die für mich ist große Arbeit, haben Sie die Edit-Distanz:

Beispiel: 

  SELECT TOP 1 [StringValue] , edit_distance([StringValue, 'Input Value')
    FROM [SomeTable]
ORDER BY edit_distance([StringValue, 'Input Value')

Die Funktion: 

CREATE FUNCTION edit_distance(@s1 nvarchar(3999), @s2 nvarchar(3999))
RETURNS int
AS
BEGIN
  DECLARE @s1_len int, @s2_len int, @i int, @j int, @s1_char nchar, @c int, @c_temp int,
    @cv0 varbinary(8000), @cv1 varbinary(8000)
  SELECT @s1_len = LEN(@s1), @s2_len = LEN(@s2), @cv1 = 0x0000, @j = 1, @i = 1, @c = 0
  WHILE @j <= @s2_len
    SELECT @cv1 = @cv1 + CAST(@j AS binary(2)), @j = @j + 1
  WHILE @i <= @s1_len
  BEGIN
    SELECT @s1_char = SUBSTRING(@s1, @i, 1), @c = @i, @cv0 = CAST(@i AS binary(2)), @j = 1
    WHILE @j <= @s2_len
    BEGIN
      SET @c = @c + 1
      SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j-1, 2) AS int) +
        CASE WHEN @s1_char = SUBSTRING(@s2, @j, 1) THEN 0 ELSE 1 END
      IF @c > @c_temp SET @c = @c_temp
      SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j+1, 2) AS int)+1
      IF @c > @c_temp SET @c = @c_temp
      SELECT @cv0 = @cv0 + CAST(@c AS binary(2)), @j = @j + 1
    END
    SELECT @cv1 = @cv0, @i = @i + 1
  END
  RETURN @c
END
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top