algoritmo para encontrar la cadena más cercana usando los mismos caracteres

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

  •  21-08-2019
  •  | 
  •  

Pregunta

Dada una lista L de n cadenas de caracteres y una cadena de caracteres de entrada S, ¿cuál es una forma eficiente de encontrar la cadena de caracteres en L que contiene la mayor cantidad de caracteres que existen en S?Queremos encontrar la cadena en L que esté compuesta más estrechamente por las letras contenidas en S.

La respuesta obvia es recorrer todas las n cadenas y verificar cuántos caracteres en la cadena actual existen en S.Sin embargo, este algoritmo se ejecutará con frecuencia y la lista L de n cadenas se almacenará en una base de datos...recorrer manualmente todas las n cadenas requeriría algo como big-Oh de n*m^2, donde n es el número de cadenas en L y m es la longitud máxima de cualquier cadena en L, así como la longitud máxima de S ...en este caso m es en realidad una constante de 150.

¿Existe una forma mejor que un simple bucle?¿Existe una estructura de datos en la que pueda cargar las n cadenas que me brinde una capacidad de búsqueda rápida?¿Existe algún algoritmo que utilice metadatos precalculados sobre cada una de las n cadenas que funcione mejor que un bucle?

Sé que hay muchos geeks a los que les gustan los algoritmos.¡Así que por favor ayuda!

¡Gracias!

¿Fue útil?

Solución

Si buscas subcadenas, una intentarlo o Patrica Trie podría ser un buen punto de partida.

Si no le importa el orden, solo el número de cada símbolo o letra, calcularía el histograma de todas las cadenas y luego los compararía con el histograma de la entrada.

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

Esto reducirá los costos de O(26 * m + n) más el preprocesamiento una vez si considera solo letras latinas que no distinguen entre mayúsculas y minúsculas.

Si m es constante, podría interpretar el histograma como un vector de 26 dimensiones en una esfera unitaria de 26 dimensiones normalizándolo.Entonces podrías simplemente calcular el Producto escalar de dos vectores que dan el coseno del ángulo entre los dos vectores, y este valor debe ser proporcional a la similitud de las cadenas.

Asumiendo m = 3, un alfabeto A = { 'U', 'V', 'W' } de tamaño tres solamente, y la siguiente lista de cadenas.

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

Los histogramas son los siguientes.

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

un histograma h = (x, y, z) está normalizado a h' = (x/r, y/r, z/r) con r la norma euclidiana del histograma h - eso es r = sqrt(x² + y² + z²).

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

la entrada S = "VVW" tiene el histograma hs = (0, 2, 1) y el histograma normalizado hs' = (0.000, 0.894, 0.447).

Ahora podemos calcular la similitud de dos histogramas. h1 = (a, b, c) y h2 = (x, y, z) como la distancia euclidiana de ambos histogramas.

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

Para el ejemplo que obtenemos.

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

Por lo tanto, "UVW" es el más cercano a "VVW" (los números más pequeños indican una mayor similitud).

Usando los histogramas normalizados h1' = (a', b', c') y h2' = (x', y', z') Podemos calcular la distancia como el producto escalar de ambos histogramas.

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

Para el ejemplo que obtenemos.

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

Nuevamente se determina que "UVW" es el más cercano a "VVW" (los números más grandes indican una mayor similitud).

Ambas versiones arrojan números diferentes, pero los resultados son siempre los mismos.También se podrían usar otras normas, como la distancia de Manhattan (norma L1), por ejemplo, pero esto solo cambiará los números porque las normas en espacios vectoriales de dimensión finita son todas equivalentes.

Otros consejos

Parece que usted necesita un trie . Intentos se utilizan para buscar palabras similares a la forma en que un corrector ortográfico funcionará. Así que si la cadena S tiene los caracteres en el mismo orden que las cadenas de L, entonces esto puede funcionar para usted.

Si sin embargo, el orden de los caracteres en S no es relevante - como un juego de fichas del scrabble y desea buscar la palabra más larga - a continuación, esto no es la solución.

Lo que queremos es un BK- árbol. Es un poco intuitivo, pero muy fresco -. Y hace que sea posible la búsqueda de elementos dentro de un levenshtein (editar) umbral de distancia en O (log n)

Si se preocupan acerca de la adquisición de sus cadenas de entrada, utilizarlos como es. Si no lo hace puede clasificar los caracteres individuales antes de insertarlos en el BK-árbol (o consultar con ellos).

Creo que lo que usted está buscando se puede encontrar aquí: lógica difusa Basado Buscar Técnica

Es bastante pesado, pero también lo es lo que estás pidiendo. Se habla de las similitudes de palabras, y la mala colocación de caracteres. 

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

Me parece que el orden de los caracteres no es importante en su problema, pero se encuentran enlaces para "casi" anagramas de la palabra S.

Si eso es así, entonces se puede representar cada palabra en el conjunto de L como un arreglo de 26 enteros (asumiendo que su alfabeto tiene 26 letras). Puede representar S de manera similar como una matriz de 26 números enteros; ahora para encontrar el mejor partido que acaba de ejecutar una vez a través del conjunto L y calcular una métrica de distancia entre la S-vector y el actual L-vector, sin embargo desea definir la distancia métrica (por ejemplo euclidiana / suma de cuadrados o Manhattan / suma de las diferencias absolutas). Esto es O algoritmo (n), ya que los vectores tienen longitudes constantes.

Aquí es una función de T-SQL que ha estado trabajando muy bien para mí, le da la distancia de edición:

Ejemplo: 

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

La Función: 

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
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top