[pyar] [JUEGO] Búsqueda de strings

[Alejandro Santos]

2014-05-03 11:10 GMT+02:00 Angel Java Lopez <ajlopez2000 en gmail.com>:
> Ahora bien, sea S lo que  buscamos. Lo que yo haria es que a cada S
> distinta, le asignaria un numero natural distinto
>
> f(S) = n
>
> Para cada elemento de L, L[i], prepararia una sarta de bits. El bit n
> estaria prendido, si el S correspondiente a ese n (los S tales que f(S) = n)
> esta contenido en L[i]. (bien podriamos poner que  S = "com", S = "Com", S =
> "COM", ... todos den el mismo n)
>

Suena interesante! Aunque estoy un poco perdido. ¿Cuántos sillones* de
RAM necesitamos para esto? Porque cuando decís:

  f(S) = n

Me imagino algo así:

def f(S):
    return reduce(lambda x, y: ((x << 8) | y), map(ord, reversed(S)), 0)

que basicamente da vuelta el string y convierte el string en un long
de longitud arbitraria. Y para un string chiquito, "Onomatopeya",
tenemos 88 bits.

Hay una forma mucho más fácil de aprovechar el Boyer-Moore que ya
viene con Python. La idea es preprocesar L para que las búsquedas sean
más rápidas.

Hacemos un string W que sea la concatenación en orden de todos los
strings de L, usando un caracter especial como separador, ejemplo:

  L = ["Casa", "Perro", "Gato", ...]
  W = "Casa\nPerro\nGato\n..."

y hacemos una tabla T que nos diga cada elemento donde empieza en el string W:

  T = [0, 5, 11, 16, ... ]

Entonces:

- Averiguar si alguna de los strings de L tiene un substr S
determinado es simplemente: S in W.

- Averiguar cuales son los strings L que tienen un substr S determinado hay que:

1. buscar con W.find la posicion de S
2. hacer una busqueda binaria en T de la posicion
3. Repetir hasta que W.find == -1

En tiempo esto es O(n.m), con n=len(L) y m=promedio de longitud del
string, y gracias a Boyer-Moore el tiempo (casi) no depende de len(S).

En un gráfico hoy me dió esto:

  http://imgur.com/fdyOp2K

El eje horizontal es la longitud del S.

find1 es la version [x for x in L if S in x]

find2 es la versión de los párrafos anteriores.

Hay una tercer opción que es O(log n) con otra tabla adicional de
preprocesado, y él gráfico de tiempo da plano en cero, pero armar esta
tabla me esta tardando asquerosamente demasiado tiempo.

[*] sillones: zillions en argentino.


-- 
Alejandro Santos