La pregunta es cómo se realiza la coincidencia de cadenas para encontrar las entradas que coinciden con el firefox 3 url bar. La coincidencia de subcadenas en cada entrada puede ser lenta. ¿Qué algoritmo se puede usar para unir en cualquier ubicación de una manera rápida?¿Cómo funciona la 'increíble' barra de fósforos de Firefox?
La manera normal de hacer una coincidencia de subcadenas rápida es crear una estructura de datos que contenga todos los sufijos de todas las cadenas que desee buscar. Según la organización, esto se puede llamar "árbol de sufijos" o "matriz de sufijos". Por ejemplo, si tiene 1000 cadenas y cada una tiene 50 caracteres de longitud, tiene 1.000 x 50 sufijos no triviales, es decir, su matriz de sufijos tendrá 50.000 entradas.
Luego, para hacer la coincidencia, realice una búsqueda binaria (si matriz) o árbol de búsqueda (si árbol) para buscar todos los sufijos en la estructura de datos cuyo comienza coincide con la cadena escrita en el cuadro de búsqueda. Debido a que es el comienzo del sufijo que está buscando, puede usar procedimientos de búsqueda estándar (búsqueda binaria, descenso de árbol) para obtener el resultado rápidamente. Cada sufijo está vinculado a las cadenas en las que aparece.
Ejemplo: tiene dos cadenas "CAT" y "DOT". Su arreglo de sufijos se parece a esto (nota lexiographic = ordenamiento alfabético):
#1 AT --> CAT
#2 CAT --> CAT
#3 DOT --> DOT
#4 OT --> DOT
#5 T --> DOT, CAT
Tenga en cuenta que hay seis sufijos pero dos de los son los mismos (el último "T" en "gato" y "DOT") y la ambos están representados por la misma entrada (# 5).
Ahora cuando el usuario escribe en la búsqueda, p. "OT" (que debe coincidir con "DOT"), puede hacer una búsqueda de ordenamiento lexiográfico simple en el tiempo de registro ya que ahora está buscando una coincidencia comenzando con en la matriz de sufijo.
Este es el principio básico de la búsqueda rápida de texto cuando el patrón de búsqueda no contiene comodines.
Creo que esto se deja en el almacenamiento subyacente: la base de datos SQLite donde Firefox almacena las páginas que visitas ofrece una función rápida para la comparación de subcadenas.
Creo que Firefox emite una consulta SQL a la base de datos. Esto es bastante rápido porque la base de datos está almacenada en la memoria caché.
Eso no está bien. De hecho, los datos se obtienen de SQLite, pero la coincidencia se realiza con un algoritmo completamente diferente. – sdwilsh
La barra de awesome sugiere URLS por un algoritmo llamado The Places frecency algorithm.
Según el sitio web para desarrolladores de Mozilla:
La palabra "frecency" en sí es una combinación de la "frecuencia" y las palabras "lo reciente."
Así es como se ordenan los datos y tiene muy poco que ver con los resultados que se muestran. – sdwilsh
Es cierto, pero la pregunta ha cambiado desde que se publicó originalmente. Entonces mi respuesta tenía que ver con la pregunta original y podría verse un poco fuera de contexto ... – RuudKok
El algoritmo de la barra de direcciones en Firefox 3.0 es un poco complicado. Se obtendrá los datos de dos (tres para Firefox 3.5 y posteriores) consultas diferentes:
Por primera consulta, se comprueba la tabla de moz_inputhistory para ver si la cadena de búsqueda actual se almacena en esa tabla. Estos resultados se ordenan por "rango", que es un número que determina qué tan recientemente se usa. Este número se degrada una vez al día. Esta búsqueda es lo que hace que la barra de ubicación sea adaptable a lo que seleccione a lo largo del tiempo (implementado en bug 95739).
En Firefox 3.5 y posterior, luego verifica la tabla moz_keyword de marcadores con una palabra clave que coincida exactamente con el texto de búsqueda.
La última consulta, revisa cada entrada en moz_places, que incluirá todas las visitas de historial y marcadores. Estos resultados están ordenados por frecency.
Para los tres de estos casos, el algoritmo siguiente se utiliza para hacer coincidir en contra de la etiquetas, el título y la URL (llamada "búsqueda de texto" a continuación). Esto es un poco difícil de explicar en palabras, por lo que podría ser más fácil look at the source code.
¡Espero que eso lo explique de una manera comprensible!
Explicación agradable +1 –
Esto solo es necesario si quiere encontrar coincidencias en medio de una palabra. Si está satisfecho con la coincidencia desde el comienzo de una palabra, basta con un índice invertido normal. –
Basado en mis propias pruebas, 'firefo' aparece un resultado muy rápido (y de forma incremental), mientras que 'irefo' tarda un tiempo. Supongo que usa un índice invertido inicialmente, y realiza un análisis de fuerza bruta del db completo si no se devuelve nada. –