[pyar] [JUEGO] Búsqueda de strings

[Angel Java Lopez]

Bien ahi lo de la concatenacion!

Jejeje... si, en mi solucion se necesitan sillones ;-) pero era para
mostrar que hay un camino O(n)

Un camino intermedio a los sillones, es tener una sarta de bits por texto.
Una sola, digamos 32 bits o 64 bits, donde pongamos prendido un bit si una
secuencia (corta o letra) esta o no presente. Habria que asignar bits a
letras/digitos o secuencias cortas, de acuerdo a su frecuencia en el
lenguaje del texto. Esto para cada L[i]. Luego para cada S que queremos
buscar, calculamos esa misma palabra de bits, y solamente hacemos S in L[i]
para los P(S) and P(L[i]) == P(S) , donde P(x) da la palabra de bits
correspondiente al texto x, y and es un and binario.

En los ochenta, creo haber terminado usando esta variante de bits, en
alguna demo, para comparar con lo que estaba, que era una simple busqueda
(donde el in o cualquier variante, no tenia Boyer-Moore, debio ser en el
Basic que venia con el sistema operativo Pick)

Nos leemos!

Angel "Java" Lopez
@ajlopez


2014-05-03 23:30 GMT-03:00 Alejandro Santos <listas en alejolp.com>:

> 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
> _______________________________________________
> pyar mailing list pyar en python.org.ar
> http://listas.python.org.ar/listinfo/pyar
>
> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>
> La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre de
> Argentina - http://www.usla.org.ar
>
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.python.org.ar/pipermail/pyar/attachments/20140505/b44a5147/attachment.html>