Indice inverso

[mij]

Estoy haciendo una aplicación en PHP/mysql para organizar y buscar textos. La parte de búsqueda la estoy implementando usando un indice inverso.
Pues bién, todos los -pocos- ejemplos que he encontrado en la red usan una tabla del estilo:

CREATE TABLE `indice` (
`id_indice` MEDIUMINT NOT NULL ,
`id_palabra` MEDIUMINT NOT NULL ,
`id_texto` MEDIUMINT NOT NULL ,
`posicion` SMALLINT NOT NULL
)

Cada palabra de cada texto ocupa entonces (3*mediumint + 1*smallint)=11bytes en el índice.
Ya que la longitud media de las palabras en español es de 4.96 letras, el texto plano requiere unos 5bytes por palabra. Por lo tanto, el índice inverso usaría más del doble de espacio en disco que el texto plano. ¿Es esto asi o optimiza MySql estos resultados (con listas enlazadas o similar)?

Y ya que estamos preguntando, me gustaría saber si alguno de vosotros conoce algun tutorial o sitio con abundante información sobre implementación de indices inversos, especialmente en php, ya que he encontrado relativamente poca información al respeto.

Muchas gracias!

[BrujoNic]

Hola, no conozco de índices inversos, pero si es programación en PHP lo que necesitas, mejor pregunta en esa sección. Si es completamente SQL, podes seguir en esta sección.

Función de la sección de Base de Datos

[mij]

Los índices inversos son una estructura de datos en las que aparecen como índices las palabras de un texto y como "contenido" una referencia a los textos donde aparece dicha palabra. Por regla general se almacenan en bases de datos. Mi pregunta se refiere precisamente al tamaño de almacenamiento de esas estructuras en bases de datos.
Es verdad que la post-data que escribi se sale un poco del tema, pero la pregunta no esta en si misma relacionada con programación, ni en php ni en otro lenguaje.

[seyko]

Ya que la longitud media de las palabras en español es de 4.96 letras, el texto plano requiere unos 5bytes por palabra. Por lo tanto, el índice inverso usaría más del doble de espacio en disco que el texto plano. ¿Es esto asi o optimiza MySql estos resultados (con listas enlazadas o similar)

Estas mezclando conceptos distintos.
1. Lógicamente, almacenar la información en una BD relacional utiliza más espacio que en texto plano!!
2. Lógicamente, las BDs optimizan los resultados!

Interesante el tema, es un proyecto personal o es laboral?
Lo que quieres "adaptar" es la forma de trabajar de un fichero inverso a una BD que gestione documentos?
Si es asi, busca información sobre implementación de gestores documentales,

Salu2

[mij]

Creo que no se me ha entendido bién.
Normalmente un índice ocupa un tamaño sustancialmente menor que el texto indexado (http://cat.inist.fr/?aModele=afficheN&cpsidt=15079715). No estoy comparando el tamaño de un texto en plano con el de un texto metido en una base de datos, sino el de un texto en plano con el de su índice (inverso, en este caso). Creo que ahi estaba la confusión.

Por ejemplo usando simplemente una estructura tipo tabla hash con listas enlazada, en la que a cada palabra le corresponda una lista enlazada con sus ocurrencias, ej:

La palabra 0 aparece en el texto 1 en la posición 2
0->{1->{2}}
La palabra 1 aparece en el texto 0 en las posiciones 3 y 4, y en el texto 5 en la posición 1
1->{0->{3,4} ; 5->{1}}

Aqui el primer numero de cada fila seria el hash de la palabra en cuestión. Asociada a ella hay una lista de "id" de cada documento donde aparece dicha palabra, y para cada id de documento una lista de posiciones en las que aparece la palabra en dicho documento.
Segun este esquema, insertar una palabra en el índice necesita, si usamos los tipos de dato del ejemplo anterior: 3 bytes para el "id" de la palabra, otros 3 para la id del documento y 2 para la posición de la palabra en el documento (total 8 bytes). Ahora bién, si esa misma palabra aparece en otro documento, solo necesitaría 5 bytes (igual que el texto plano), ya que no hay que repetir la informacion "id de la palabra". Análogamente, si una palabra se repite en un mismo documento, solo necesitamos 2 bytes adicionales para describirla (menos de la mitad del texto plano). Si añadimos una lista de stopwords, el resultado es que el índice asi construido ocupa bastante menos que el texto indexado.

Me preguntaba si MySQL hace esto mismo: obviar la información repetida para ahorrar espacio en disco.

El proyecto (gracias por interesarte!! ) era personal, hasta que recientemente una empresa me contrató para desarrollarlo (aunque sea por un sueldo de becario...) . Consiste en un buscador de textos científicos, aunque la parte interesante es que los cataloga automáticamente usando ontolgias.
En cuanto a lo del motor de búsqueda, no intento "adaptar" nada (o eso creo), usar indices inversos en bases de datos relacionados es una práctica standart, usado por todos los motores de busqueda que usan mysql que conozco (Sphider, nogoSearch, TSEP, PHPDig, iSearch y Sphinx)
Un saludo!

[seyko]

ok, no te habia entendido bien, pero sigo sin entenderte del todo

Me preguntaba si MySQL hace esto mismo: obviar la información repetida para ahorrar espacio en disco.

Si con repetida te refieres a id_palabra, logicamente si que la repite. La base de datos sigue tu diseño, si en tu diseño lo repites....

A ver si nos entendemos y si puedo te echo una mano.

Salu2