algoritmo per trovare più vicino stringa utilizzando stessi caratteri

Question

Dato un elenco di stringhe L n caratteri, e un carattere di input stringa S, quello che è un modo efficace per trovare la stringa di caratteri a L che contiene la maggior parte dei personaggi che esistono in S? Vogliamo trovare la stringa a L che è più strettamente-composto dalle lettere che compongono S.

La risposta ovvia è quella di un ciclo tra tutte le stringhe n e controllare per vedere quanti caratteri nella stringa corrente esiste in S. Tuttavia, questo algoritmo verrà eseguito di frequente, e la lista L di stringa n verrà memorizzata in un database ... ciclo manualmente tramite tutte le stringhe n richiederebbe qualcosa come big-Oh di n * m ^ 2, dove n è il numero di stringhe in L, ed m è la lunghezza massima di qualsiasi stringa a L, così come il max lunghezza di S ... in questo caso m è in realtà una costante di 150.

C'è un modo migliore di un semplice ciclo? C'è una struttura di dati posso caricare le stringhe n in che mi avrebbe dato la capacità di ricerca veloce? Esiste un algoritmo che utilizza il meta-dati di pre-calcolata su ciascuna delle stringhe n che eseguire meglio di un ciclo?

So che ci sono un sacco di geek là fuori che sono negli algoritmi. Quindi, per favore aiuto!

Grazie!

Answer 1

Se siete dopo sottostringhe, una Trie o Patrica trie potrebbe essere un buon punto di partenza .

Se non vi interessa circa l'ordine, solo il numero di ogni simbolo o una lettera, vorrei calcola l'istogramma di tutte le stringhe e poi confrontarli con l'istogramma dell'ingresso.

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

Questo abbasserà i costi per O(26 * m + n) più la pre-elaborazione una volta, se si considera solo lettere latine-case insensitive.

Se m è costante, si potrebbe interpretare l'istogramma come 26 vettore dimensionale su una sfera unitaria dimensionale 26 normalizzando esso. Poi si può solo calcolare la Dot Product di due vettori che producono il coseno dell'angolo tra i due vettori, e questo valore deve essere proporzionale alla somiglianza delle stringhe.

Supponendo m = 3, un alfabeto A = { 'U', 'V', 'W' } di dimensioni tre soltanto, e la seguente lista di stringhe.

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

Gli istogrammi sono i seguenti.

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

Un istogramma h = (x, y, z) è normalizzata a h' = (x/r, y/r, z/r) con r la norma euclidea dell'istogramma h -. Che è r = sqrt(x² + y² + z²)

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

L'ingresso S = "VVW" ha l'istogramma hs = (0, 2, 1) e l'istogramma normalizzato hs' = (0.000, 0.894, 0.447).

Ora possiamo calcolare la similarità dei due istogrammi h1 = (a, b, c) e h2 = (x, y, z) come la distanza euclidea dei due istogrammi.

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

Per l'esempio otteniamo.

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

Quindi "UVW" è più vicino a "VVW" (numeri più piccoli indicano maggiore similarità).

Utilizzando gli istogrammi normalizzati h1' = (a', b', c') e h2' = (x', y', z') possiamo calcolare la distanza come il prodotto scalare di due istogrammi.

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

Per l'esempio otteniamo.

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

Ancora "UVW" è determinato per essere vicini a "VVW" (numeri più grandi indicano maggiore similarità).

Sia la versione resa numeri diversi, ma i risultati sono sempre gli stessi. Si potrebbe anche usare altre norme - Manhattan distanza (L1 norma) per esempio -. Ma questo cambierà solo i numeri perché norme in spazi vettoriali finito dimensionali sono equivalenti

Answer 2

Suona come avete bisogno di un trie . Tentativi sono utilizzati per la ricerca di parole simili al modo in cui un correttore ortografico funzionerà. Quindi, se la stringa S ha i caratteri nello stesso ordine come le corde in L allora questo può funzionare per voi.

Se, tuttavia, l'ordine dei personaggi di S non è rilevante - come una serie di piastrelle di Scrabble e si desidera cercare la parola più lunga - allora questo non è la vostra soluzione.

Answer 3

Quello che vogliamo è un BK- tree. È un po 'poco intuitivo, ma molto cool -. E rende possibile la ricerca di elementi all'interno di una levenshtein (edit) soglia di distanza in O (log n)

Se vi preoccupate per ordinare nelle stringhe di input, li usano come è. Se non è possibile ordinare i singoli caratteri prima di inserirli nel BK-Tree (o l'esecuzione di query con loro).

Answer 4

Credo che quello che stai cercando può essere trovato qui: Fuzzy Logic In base tecnica di ricerca

E 'piuttosto pesante, ma lo è anche quello che stai chiedendo. Si parla di somiglianze di parola, e smarrimento carattere.

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

Answer 5

mi sembra che l'ordine dei personaggi non è importante per il vostro problema, ma sono alla ricerca di "near-anagrammi" della parola S.

Se è così, allora si può rappresentare ogni parola nel set L come un array di 26 interi (supponendo che l'alfabeto ha 26 lettere). È possibile rappresentare S allo stesso modo come un array di 26 interi; ora per trovare la migliore corrispondenza basta eseguire una volta attraverso il set di L e calcolare una distanza metrica tra la S-vettoriale e la corrente L-vettore, comunque lo si voglia definire la distanza metrica (ad es euclidea / somma dei quadrati o Manhattan / somma delle differenze assolute). Questo è O (n) algoritmo perché i vettori hanno lunghezze costanti.

Answer 6

Ecco una funzione T-SQL che ha lavorato molto per me, ti dà la distanza edit:

Esempio:

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

La funzione:

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