[pyar] [JUEGO] Búsqueda de strings

[Angel Java Lopez]

Jajaja! Alguna vez tenia que aparece Boyer-Moore ;-)

#soytanviejo que vi nacer a ese algoritmo. Debio aparecer en mi radar en
alguna Scientific American de los ochenta. Eramos tan pobres. ... ;-)

No sabia que CPython se habia tomado la molestia de implementar todo eso,
buen dato!

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)

Luego, ante cada S que se presente, calcularia f(S) = n
Y me fijaria en cada L[i] si su sarta de bits tiene el n bit prendido

Me imagino que lo de arriba es O(n) (dependiente de la longitud L,
llamemosla n, como en los anteriores corroes, pero no dependiente de m, la
maxima longitud de los L[i])

Si no quiero llegar a esos extremos... .hmmm... recuerdo algo que
implemente a principio de los ochenta, antes de la guerra de las Malvinas,
aca en Argentina.

Varias variantes. Primero la sencilla. A cada letra del alfabeto que
estemos usando, le asignamos el numero n, distinto para cada letra que
consideramos distinta. Por cada L[i], mantengo una serie de bits. El bit n
esta prendido si la letra A correspondiente a n, esta en L[i] (uno a varias
veces). Luego, por cada S que se presente, calculo la sarta de bits que le
corresponde (que letras contiene). Hago AND logico de esa sarta de bits con
los de cada L[i]. Solo me mato haciendo el "in" en los L[i] que tengan
todos los bits de S

Segundo, en vez de bits por letra, tener un lugar que diga: la cantidad de
veces que esta esta letra en el texto T. Idem que antes

Tercera, la que implemente en los ochenta: tener bits de presencia de
letras por cada subsarta de L[i]. Digamos, tengo bits de presencia de
letras para los caracteres 0 a 15 de L[i], de 8 a 23, de 16 a 31, etc...
Por cada S que se presenta, calculo su presencia de letras. Si S tiene
longitud <= 16, solo busco en las subsartas de L[i] CONSECUTIVAS que entre
ambas tengan todas las letras de S, o en las subsartas de L[i] que tengan
todas las letras de S (algunos ajustes, pero es la idea). Si S tiene
longitud <= 32, se modifica un poco, y asi

Creo recordar que esta tercera variante es la que implemente para una
especie de full-text search de entrecasa de aquel entonces. El tener un bit
prendido o apagado en una sarta larguisima, debio ser sugerido por el
numero omega del bueno de Chaitin (al que finalmente conoci personalmente
en MathBA 2009)

Nos leemos!

Angel "Java" Lopez
@ajlopez



2014-05-02 17:18 GMT-03:00 Alejandro Santos <listas en alejolp.com>:

> 2014-05-02 20:59 GMT+02:00 Natalia Bidart <nataliabidart en gmail.com>:
> > 2014-05-02 15:16 GMT-03:00 fisa <fisadev en gmail.com>:
> >
> >> Buen punto, tomé el in como una operación más básica de lo que es.
> >>
> >> Sería un O(n . O-del-in), no?
> >
> > Esto está muy interesante, es exactamente la pregunta de la complejidad
> del
> > "in" para strings en Python:
> >
> >
> http://stackoverflow.com/questions/18139660/python-string-in-operator-implementation-algorithm-and-time-complexity
> >
>
> Ya casi lo bajaste a O(n) :)
>
>
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.python.org.ar/pipermail/pyar/attachments/20140503/ec3354ad/attachment.html>