¿Qué tan largas son tus cuerdas?
Si son relativamente breves (p. ej., palabras en inglés; avg_len=5) y tiene suficiente espacio de almacenamiento en la base de datos, pruebe este enfoque:
- Para cada palabra que desee almacenar en la tabla, tome todos los sufijos posibles de esa palabra. En otras palabras, sigues eliminando el primer carácter hasta que no quede nada. Por ejemplo, la palabra
valueda:valuevaluelueuee
- Almacenar cada uno de estos sufijos en la base de datos.
- Ahora puede buscar subcadenas usando
LIKE 'alu%'(que encontrará 'alu' como parte de 'valor').
Al almacenar todos los sufijos, ha eliminado la necesidad del comodín inicial (lo que permite usar un índice para una búsqueda rápida), a costa del espacio de almacenamiento.
Coste de almacenamiento
El número de caracteres necesarios para almacenar una palabra se convierte en word_len*word_len / 2 , es decir, cuadrático en la longitud de palabra, palabra por palabra. Este es el factor de aumento para varios tamaños de palabra:
- Palabra de 3 letras:
(3*3/2) / 3 = 1.5 - Palabra de 5 letras:
(5*5/2) / 5 = 2.5 - Palabra de 7 letras:
(7*7/2) / 7 = 3.5 - Palabra de 12 letras:
(12*12/2) / 12 = 6
El número de filas requeridas para almacenar una palabra aumenta de 1 a word_len . Tenga en cuenta esta sobrecarga. Las columnas adicionales deben mantenerse al mínimo para evitar almacenar grandes cantidades de datos redundantes. Por ejemplo, un número de página en el que se encontró originalmente la palabra debería estar bien (piense en una letra pequeña sin firmar), pero los metadatos extensos de la palabra deberían almacenarse en una tabla separada por palabra, en lugar de por cada sufijo.
Consideraciones
Hay una compensación en donde dividimos 'palabras' (o fragmentos). Como ejemplo del mundo real:¿qué hacemos con los guiones? ¿Almacenamos el adjetivo five-letter como una palabra o dos?
La compensación es la siguiente:
- Todo lo que está fragmentado no se puede encontrar como un solo elemento. Si almacenamos
fiveyletterpor separado, buscandofive-letterofive-letterfallará. - Cualquier cosa que no roto ocupará más espacio de almacenamiento. Recuerde, el requisito de almacenamiento aumenta cuadráticamente en la longitud de la palabra.
Para mayor comodidad, es posible que desee eliminar el guión y almacenar five-letter . La palabra ahora se puede encontrar buscando five , letter y five-letter . (Si también elimina los guiones de cualquier consulta de búsqueda, los usuarios aún pueden encontrar con éxito five-letter .)
Por último, hay formas de almacenar matrices de sufijos que no generan muchos gastos generales, pero aún no estoy seguro de que se traduzcan bien en las bases de datos.
