¿Algoritmo más rápido para encontrar una cadena en una matriz de cadenas?

Esta pregunta es meramente sobre algoritmo. En pseudo código es así:¿Algoritmo más rápido para encontrar una cadena en una matriz de cadenas?

A = Array of strings; //let's say count(A) = N 
S = String to find; //let's say length(S) = M 

for (Index=0; Index<count(A); Index++) 
    if (A[Index]==S) { 
    print "First occurrence at index\x20"+Index; 
    break; 
    }

Este bucle for requiere la comparación de cadenas N veces (o los tiempos de comparación byte N * M, O (N * M)). Esto es malo cuando la matriz A tiene muchos elementos o cuando la cadena S es demasiado larga.

¿Algún método mejor para encontrar la primera vez? Algún algoritmo en O (K * logK) está bien, pero es preferible en O (K) o mejor en O (logK), donde K es N o M.

No me importa agregar algunas otras estructuras o haciendo algo de procesamiento de datos antes del ciclo de comparación.

Fuente

2012-04-28 jondinham

"Cuando la cadena S es demasiado larga" es irrelevante, a menos que haya muchas cadenas en 'A 'con la misma longitud y un prefijo largo idéntico. (Las comprobaciones de igualdad de cadenas pueden finalizar inmediatamente si las longitudes son diferentes, o tan pronto como se encuentre una falta de coincidencia al caminar sobre ellas). – Dougal

¿Por qué usa '\ x20' en lugar de un espacio? Tengo curiosidad :-) –

oh sí, el tiempo de comparación depende más de las longitudes de las cadenas en la matriz A – jondinham

Puede convertir todo el conjunto de cadenas a una máquina de estados finitos, donde las transiciones son los caracteres de las cadenas y colocar el índice más pequeño de las cadenas que producen un estado en el estado. Esto lleva mucho tiempo y puede considerarse indexación.

Fuente

2012-04-28 18:42:49 Reactormonk

Más comúnmente conocido como un [trie] (http://en.wikipedia.org/wiki/Trie). – Dougal

[f] lex puede ayudarlo a construir este DFA. – wildplasser

@ Dougal Gracias por el nombre, no lo sabía. – Reactormonk

Ponga las cuerdas en un conjunto basado en hash, y pruebe para ver si una cadena dada está contenida en el conjunto debería darle un rendimiento más o menos constante una vez que se haya construido el conjunto.

Fuente

2012-04-28 18:40:46 Bill

Si desea encontrar el índice, use un diccionario de cadenas basado en hash -> primera ocurrencia. – Dougal

pero tengo un poco de miedo de que algunos 2 elementos tengan el mismo valor hash – jondinham

Bueno, aún necesitas hacer la comparación final, dados los mismos valores hash. – wildplasser

Primero puede ordenar la matriz de cadenas, que tomará el tiempo O (m * nlogn). Y una vez que se ha ordenado A, puede realizar una búsqueda binaria en lugar de una búsqueda lineal, lo que podría reducir el tiempo total de ejecución a O (m * logn).

La ventaja de este método es que es bastante fácil de implementar. Por ejemplo, en Java que puede hacer esto con sólo 2 líneas de código:

Arrays.sort(A); 
int index = Arrays.binarySearch(A, "S");

Fuente

2012-04-28 18:57:44 Nova2358

el proceso de clasificación antes de la búsqueda binaria toma una gran parte del tiempo, ¿no es así? – jondinham

@PaulDinh Toma el tiempo O (M N log N). – Dougal

@PaulDinh Creo que en la práctica el tiempo está bien. La dosis toma el tiempo O (M N log N) en el peor de los casos. Pero cargar toda la cadena necesitará M * N hora, por lo que solo es log n veces más larga que IO. En la mayoría de los casos, log n es realmente pequeño, tal vez incluso más rápido que construir un trie o hashtable en la práctica. Si te preocupa la complejidad teórica del tiempo, entonces construir un trie o hashtable costará O (M * N) tiempo. – Nova2358

Se puede usar un Self-balancing binary search tree. La mayoría de las implementaciones tienen O (log (n)) para insertar, y O (log (n)) para buscar.

Si su conjunto no es muy grande, y tiene buenas funciones hash para sus valores, el conjunto basado en hash es una mejor solución, porque en ese caso tendrá O (1) para insertar y O (1) buscar. Pero si su función hash es mala o su conjunto es demasiado grande, será O (n) para insertar y O (n) para buscar.

Fuente

2012-04-28 19:02:57

La mejor manera de buscar lo más rápido posible, es tener la matriz ordenada como usted la describe, no parece haber ninguna información posible a priori, lo que permitiría algunas heurísticas o limitaciones en la búsqueda

Ordenar primero la matriz (Quicksort, por ejemplo, O (NlogN)), y hacer la búsqueda binaria siguiente O (registro (N))

Fuente

2012-04-28 19:06:13 jpmuc

¿Algoritmo más rápido para encontrar una cadena en una matriz de cadenas?

Respuesta

Cuestiones relacionadas